Fetching the paper…
Reading the bibliography…
We show that a simple randomized sketch of the matrix multiplicative weight (MMW) update enjoys (in expectation) the same regret bounds as MMW, up to a small constant factor.
An iteration method for the solution of the eigenvalue problem of linear differential and integral operators
Cornelius Lanczos · 1950
Earlier work this paper cites.
Probability inequalities for sums of bounded random variables
W. Hoeffding · 1963
Earlier work this paper cites.
Weighted sums of certain dependent random variables
K. Azuma · 1967
Earlier work this paper cites.
Error bounds in the simple Lanczos procedure for computing functions of symmetric matrices and eigenvalues
Vladimir Druskin and Leonid Knizhnerman · 1991
Earlier work this paper cites.
Analysis of some Krylov subspace approximations to the matrix exponential operator
Yousef Saad · 1992
Earlier work this paper cites.
Convex Analysis and Minimization Algorithms I & II
J. Hiriart-Urruty and C. Lemaréchal · 1993
Earlier work this paper cites.
Krylov subspace approximation of eigenpairs and matrix functions in exact and computer arithmetic
Vladimir Druskin and Leonid Knizhnerman · 1995
Earlier work this paper cites.
A divide-and-conquer algorithm for the symmetric tridiagonal eigenproblem
Ming Gu and Stanley C. Eisenstat · 1995
Earlier work this paper cites.
Convex analysis on the Hermitian matrices
Adrian Lewis · 1996
Earlier work this paper cites.
On some inequalities for the gamma and psi functions
Horst Alzer · 1997
Earlier work this paper cites.
The complexity of the matrix eigenproblem
Victor Y Pan and Zhao Q Chen · 1999
Earlier work this paper cites.
Twice differentiable spectral functions
Adrian S. Lewis and Hristo S. Sendov · 2001
Earlier work this paper cites.
Nineteen dubious ways to compute the exponential of a matrix, twenty-five years later
Cleve B. Moler and Charles Van Loan · 2003
Earlier work this paper cites.
On the generalization ability of on-line learning algorithms
N. Cesa-Bianchi, A. Conconi, and C. Gentile · 2004
Earlier work this paper cites.
Prox-method with rate of convergence O ( 1 / t ) O(1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems
Arkadi Nemirovski · 2004
Earlier work this paper cites.
Efficient algorithms for online decision problems
A. Kalai and S. Vempala · 2005
Cited alongside, same era.
Matrix exponentiated gradient updates for on-line learning and bregman projection
Koji Tsuda, Gunnar Rätsch, and Manfred K Warmuth · 2005
Cited alongside, same era.
The Lanczos and Conjugate Gradient Algorithms: From Theory to Finite Precision Computations
Gérard Meurant · 2006
Cited alongside, same era.
A combinatorial, primal-dual approach to semidefinite programs
Sanjeev Arora and Satyen Kale · 2007
Cited alongside, same era.
Smoothing technique and its applications in semidefinite optimization
Yurii Nesterov · 2007
Cited alongside, same era.
Randomized online PCA algorithms with regret bounds that are logarithmic in the dimension
Manfred K. Warmuth and Dima Kuzmin · 2008
A randomized mirror-prox method for solving structured large-scale matrix saddle-point problems
Michel Baes, Michael Bürgisser, and Arkadi Nemirovski · 2013
Later among the works it cites.
Online PCA with optimal regrets
Jiazhong Nie, Wojciech Kotłowski, and Manfred K Warmuth · 2013
Later among the works it cites.
Analyze Gauss: optimal bounds for privacy-preserving principal component analysis
Cynthia Dwork, Kunal Talwar, Abhradeep Thakurta, and Li Zhang · 2014
Later among the works it cites.
Faster algorithms via approximation theory
Sushant Sachdeva and Nisheeth K. Vishnoi · 2014
Later among the works it cites.
Online learning of eigenvectors
Dan Garber, Elad Hazan, and Tengyu Ma · 2015
Later among the works it cites.
Chordal graphs and semidefinite optimization
Lieven Vandenberghe, Martin S Andersen, et al · 2015
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Robust stochastic approximation approach to stochastic programming
A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro · 2009
Cited alongside, same era.
Primal-dual subgradient methods for convex problems
Y. Nesterov · 2009
Cited alongside, same era.
Exponential integrators
Marlis Hochbruck and Alexander Ostermann · 2010
Cited alongside, same era.
Subsampling algorithms for semidefinite programming
Alexandre d’Aspremont · 2011
Cited alongside, same era.
The multiplicative weights update method: a meta algorithm and applications
S. Arora, E. Hazan, and S. Kale · 2012
Cited alongside, same era.
Regret analysis of stochastic and nonstochastic multi-armed bandit problems
Sébastien Bubeck and Nicoló Cesa-Bianchi · 2012
Cited alongside, same era.
Using optimization to obtain a width-independent, parallel, simpler, and faster positive sdp solver
Zeyuan Allen-Zhu, Yin Tat Lee, and Lorenzo Orecchia · 2016
Later among the works it cites.
Geometric median in nearly linear time
Michael B. Cohen, Yin Tat Lee, Gary L. Miller, Jakub W. Pachocki, and Aaron Sidford · 2016
Later among the works it cites.
Sublinear time algorithms for approximate semidefinite programming
Dan Garber and Elad Hazan · 2016
Later among the works it cites.
Introduction to online convex optimization
Elad Hazan · 2016
Later among the works it cites.
Faster and simpler width-independent parallel algorithms for positive semidefinite programming
Richard Peng, Kanat Tangwongsan, and Peng Zhang · 2016
Later among the works it cites.
Follow the compressed leader: Faster online learning of eigenvectors and faster mmwu
Zeyuan Allen-Zhu and Yuanzhi Li · 2017
Later among the works it cites.
Arun Jambulapati, Kirankumar Shiragur, and Aaron Sidford · 2018
Later among the works it cites.
Stability of the Lanczos method for matrix function approximation
Cameron Musco, Christopher Musco, and Aaron Sidford · 2018
Later among the works it cites.