Beneath the valley of the noncommutative arithmetic-geometric mean inequality: conjectures, case-studies, and consequences
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.
Code (3)
Similar Papers 제목 키워드 기반
Random Reshuffling is Not Always Better
Many learning algorithms, such as stochastic gradient descent, are affected by the order in which training examples are used. It is often observed that sampling the training examples without-replacement, also known as ra…
Recht-Re Noncommutative Arithmetic-Geometric Mean Conjecture is False
Stochastic optimization algorithms have become indispensable in machine learning. An unresolved foundational question in this area is the difference between with-replacement sampling and without-replacement sampling --- …
Stochastic OptimizationRecht-Re Noncommutative Arithmetic-Geometric Mean Conjecture is False
Stochastic optimization algorithms have become indispensable in machine learning. An unresolved foundational question in this area is the difference between with-replacement sampling and without-replacement sampling --- …
Stochastic OptimizationRecht-Ré Noncommutative Arithmetic-Geometric Mean Conjecture is False
Stochastic optimization algorithms have become indispensable in modern machine learning. An unresolved foundational question in this area is the difference between with-replacement sampling and without-replacement sampli…
Stochastic OptimizationOn Noncommutative Quantum Mechanics and the Black-Scholes Model
Two novel and direct quantum mechanical representations of the Black-Scholes model are constructed based on the (Wick-rotated) quantization of two specific mechanical systems. The quantum setup is achieved by means of th…
Quantization