Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updates
Open Access
- 14 June 2015
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 237-245
Abstract
In this paper, we provide a novel construction of the linear-sized spectral sparsifiers of Batson, Spielman and Srivastava [11]. While previous constructions required Ω(n4) running time [11, 45], our sparsification routine can be implemented in almost-quadratic running time O(n2+ε). 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 [39] via the application of matrix multiplicative weight updates (MWU) [17, 43]. 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 [11].Keywords
All Related Versions
Funding Information
- Simons Foundation (Graduate Student Award under grant no. 284059)
- National Science Foundation (CCF-1319460)
This publication has 32 references indexed in Scilit:
- An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations2013
- Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit ProblemsFoundations and Trends in Machine Learning, 2012
- Online Learning and Online Convex OptimizationFoundations and Trends in Machine Learning, 2012
- QIP = PSPACEJournal of the ACM, 2011
- Spectral Sparsification of GraphsSIAM Journal on Computing, 2011
- Graph Sparsification by Effective ResistancesSIAM Journal on Computing, 2011
- Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing ProblemsSIAM Journal on Computing, 2007
- A desicion-theoretic generalization of on-line learning and an application to boosting1995
- Extensions of Lipschitz mappings into a Hilbert space1984
- Convex trace functions and the Wigner-Yanase-Dyson conjectureAdvances in Mathematics, 1973