Spectral sparsification and regret minimization beyond matrix multiplicative updates
From MaRDI portal
Abstract: In this paper, we provide a novel construction of the linear-sized spectral sparsifiers of Batson, Spielman and Srivastava [BSS14]. While previous constructions required running time [BSS14, Zou12], our sparsification routine can be implemented in almost-quadratic running time . The fundamental conceptual novelty of our work is the leveraging of a strong connection between sparsification and a regret minimization problem over density matrices. This connection was known to provide an interpretation of the randomized sparsifiers of Spielman and Srivastava [SS11] via the application of matrix multiplicative weight updates (MWU) [CHS11, Vis14]. In this paper, we explain how matrix MWU naturally arises as an instance of the Follow-the-Regularized-Leader framework and generalize this approach to yield a larger class of updates. This new class allows us to accelerate the construction of linear-sized spectral sparsifiers, and give novel insights on the motivation behind Batson, Spielman and Srivastava [BSS14].
Recommendations
Cites work
- Approximate distance oracles
- Approximate distance oracles with constant query time
- Automata, Languages and Programming
- Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
- Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
- Fast C-K-R partitions of sparse graphs
- Near-Linear Time Construction of Sparse Neighborhood Covers
- On approximate distance labels and routing schemes with affine stretch
- On sparse spanners of weighted graphs
- Ramsey partitions and proximity data structures
- Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
- Shortest-path queries in static networks
Cited in
(20)- Near-optimal discrete optimization for experimental design: a regret minimization approach
- Nearly linear-time packing and covering LP solvers. Nearly linear-time packing and covering LP solvers, achieving width-independence and =(1/)-convergence
- Approximation algorithms for \(D\)-optimal design
- Constructing linear-sized spectral sparsification in almost-linear time
- Finding Sparse Solutions for Packing and Covering Semidefinite Programs
- Oracle-Based Primal-Dual Algorithms for Packing and Covering Semidefinite Programs
- A Local Search Framework for Experimental Design
- A Spectral Approach to Network Design
- A general framework for graph sparsification
- scientific article; zbMATH DE number 7651209 (Why is no real title available?)
- Graph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle Decompositions
- Optimal experimental design: formulations and computations
- Spectral sparsification via bounded-independence sampling
- Better sparsifiers for directed Eulerian graphs
- Sparsification of the regularized magnetic Laplacian with multi-type spanning forests
- Eldan's stochastic localization and the KLS conjecture: isoperimetry, concentration and mixing
- Small-space spectral sparsification via bounded-independence sampling
- Graph matching via convex relaxation to the simplex
- Smoothed analysis with adaptive adversaries
- Sparsification of directed graphs via cut balance
This page was built for publication: Spectral sparsification and regret minimization beyond matrix multiplicative updates
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2941512)
