Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updates

DOI10.1145/2746539.2746610zbMath1321.68294arXiv1506.04838OpenAlexW2963841171MaRDI QIDQ2941512

Zhenyu Liao, Zeyuan Allen Zhu, Lorenzo Orecchia

Publication date: 21 August 2015

Published in: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1506.04838

zbMATH Keywords

regularizationregret minimizationspectral sparsificationmultiplicative weight updates

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Analysis of algorithms and problem complexity (68Q25) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Randomized algorithms (68W20)

Related Items (11)

Finding Sparse Solutions for Packing and Covering Semidefinite Programs ⋮ Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time ⋮ A Local Search Framework for Experimental Design ⋮ A Spectral Approach to Network Design ⋮ Nearly linear-time packing and covering LP solvers. Nearly linear-time packing and covering LP solvers, achieving width-independence and \(=(1/\varepsilon)\)-convergence ⋮ Graph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle Decompositions ⋮ Unnamed Item ⋮ Near-optimal discrete optimization for experimental design: a regret minimization approach ⋮ Oracle-Based Primal-Dual Algorithms for Packing and Covering Semidefinite Programs ⋮ Approximation Algorithms for D-optimal Design ⋮ A General Framework for Graph Sparsification

Uses Software

• Graphs

Cites Work

• Unnamed Item
• Ramsey partitions and proximity data structures
• On sparse spanners of weighted graphs
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• On Approximate Distance Labels and Routing Schemes with Affine Stretch
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Approximate distance oracles
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Near-Linear Time Construction of Sparse Neighborhood Covers
• Shortest-path queries in static networks
• Approximate distance oracles with constant query time
• Automata, Languages and Programming

This page was built for publication: Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updates