Recht-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 sampling -- does the latter have superior convergence rate compared to the former? A groundbreaking result of Recht and R\'e reduces the problem to a noncommutative analogue of the arithmetic-geometric mean inequality where $n$ positive numbers are replaced by $n$ positive definite matrices. If this inequality holds for all $n$, then without-replacement sampling indeed outperforms with-replacement sampling. The conjectured Recht-R\'e inequality has so far only been established for $n = 2$ and a special case of $n = 3$. We will show that the Recht-R\'e conjecture is false for general $n$. Our approach relies on the noncommutative Positivstellensatz, which allows us to reduce the conjectured inequality to a semidefinite program and the validity of the conjecture to certain bounds for the optimum values, which we show are false as soon as $n = 5$.
Code (0)
등록된 구현이 없습니다.
Tasks
Stochastic OptimizationSimilar Papers 제목 키워드 기반
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 OptimizationRandom 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…
Can Single-Shuffle SGD be Better than Reshuffling SGD and GD?
We propose matrix norm inequalities that extend the Recht-R\'e (2012) conjecture on a noncommutative AM-GM inequality by supplementing it with another inequality that accounts for single-shuffle, which is a widely used w…
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. Thi…