##### Department of Mathematics,

University of California San Diego

****************************

### Math 278C - Optimization and Data Science Seminar

## Zehua Lai

#### University of Chicago

## Recht-Re Noncommutative Arithmetic-Geometric Mean Conjecture is False

##### Abstract:

Stochastic optimization algorithms have become indispensable in modern machine learning. An important 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 paper of Recht and Re 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 (also known as random reshuffling) indeed outperforms with-replacement sampling in some important optimization problems. In this talk, We will explain basic ideas and techniques in polynomial optimization and the theory of 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. Finally, we show that Recht--Re conjecture is false as soon as $n = 5$. \\ \\ This is a joint work with Lek-Heng Lim.

Host: Jiawang Nie

### April 7, 2021

### 3:00 PM

### Meeting ID: 982 9781 6626 Password: 278CSP21

****************************