Beneath the valley of the noncommutative arithmetic-geometric mean inequality: conjectures, case-studies, and consequences
arXiv:1202.4184
Abstract
Randomized algorithms that base iteration-level decisions on samples from some pool are ubiquitous in machine learning and optimization. Examples include stochastic gradient descent and randomized coordinate descent. This paper makes progress at theoretically evaluating the difference in performance between sampling with- and without-replacement in such algorithms. Focusing on least means squares optimization, we formulate a noncommutative arithmetic-geometric mean inequality that would prove that the expected convergence rate of without-replacement sampling is faster than that of with-replacement sampling. We demonstrate that this inequality holds for many classes of random matrices and for some pathological examples as well. We provide a deterministic worst-case bound on the gap between the discrepancy between the two sampling models, and explore some of the impediments to proving this inequality in full generality. We detail the consequences of this inequality for stochastic gradient descent and the randomized Kaczmarz algorithm for solving linear systems.
arXiv comment25 pages, 6 figures
Cited by in corpus (22)
- Paved with Good Intentions: Analysis of a Randomized Block Kaczmarz Method
- Finito: A Faster, Permutable Incremental Gradient Method for Big Data Problems
- Asynchronous stochastic convex optimization
- Generalized Row-Action Methods for Tomographic Imaging
- Without-Replacement Sampling for Stochastic Gradient Methods: Convergence Results and Application to Distributed Optimization
- On the Efficiency of Random Permutation for ADMM and Coordinate Descent
- SGD with shuffling: optimal rates without component convexity and large epoch requirements
- Scan Order in Gibbs Sampling: Models in Which it Matters and Bounds on How Much
- Random Shuffling Beats SGD after Finite Epochs
- How Good is SGD with Random Shuffling?
- A note on the non-commutative arithmetic-geometric mean inequality
- Dimension-Free Iteration Complexity of Finite Sum Optimization Problems
- Noncommutative versions of the arithmetic-geometric mean inequality
- Random Shuffling Beats SGD Only After Many Epochs on Ill-Conditioned Problems
- On the symmetrized arithmetic-geometric mean inequality for opertors
- Reducing Runtime by Recycling Samples
- Permutation-Based SGD: Is Random Optimal?
- Siamese Survival Analysis with Competing Risks
- Understanding Limitation of Two Symmetrized Orders by Worst-case Complexity
- Block Kaczmarz Method with Inequalities
- An arithmetic-geometric mean inequality for products of three matrices
- Two-subspace Projection Method for Coherent Overdetermined Systems (Technical Report)