11 problems

Let $N$ denote the iteration count and let the performance criterion be the minimum squared gradient norm, $\min_{k\in\{1,\ldots,N\}}\|\nabla f(x_k)\|^2$, for minimizing a smooth c…

Intermediate-regime tightness conjecture. The intermediate regime in Theorem 1 is tight. Furthermore, the corresponding worst-case function is bivariate.

Basic g-composable schedule conjecture. For each $n$, every minimax-optimal stepsize schedule solving

Let $h_{\circ}^{(n)}$ denote the primitive stepsize schedule generated by Definition, let $\Call{ConPP}$ denote the concatenation operation, and let $\mathbf 1$ be the all-ones vec…

Fix $N$, a $1$-smooth convex function $f$, an initial point $x_0$, a minimizer $x_\star$, and gradient-descent iterates $x_0,\ldots,x_N$ with constant stepsize $\alpha$. Write…

Let $\mathcal{F}_{L,D}$ be the class of pairs $(f,x_0)$ where $f$ is $L$-smooth and convex, has a minimizer $x_\star$ with $\|x_0-x_\star\|\leq D$, and $x_N$ is obtained by $N$ ste…

Let $f\in\mathcal{F}_{\mu,L}$ with $\mu\in(-\infty,0)$, and consider $N$ gradient-descent iterations from $x_0$ with stepsizes satisfying $\gamma_iL\in[1,\gbari[1]]$ for…

Consider gradient descent run for a fixed number $N$ of steps with constant stepsize $h\in(0,1]$, starting from $x_0$ with $\lVert x_0-x_\star\rVert=D$. For simple extrapolation by…

Gradient-descent performance conjecture. For a proper constant $\eta$, and for a random initial point drawn from a certain distribution, such as Xavier initialization,

Let $f:\mathbb{R}^m\rightarrow\mathbb{R}$ be a $C^1$ function that is $C^2$ near its critical points, and let $\{z_n\}$ be the sequence generated by the Backtracking GD method from…

Let $M$ be a Riemannian manifold, let $\rho\leq r_{\operatorname{cx}}$, and let $\{x_i\}_{i=1}^N\subset B(o,\rho)\subset M$. Set $\bar{x}_2$ to be their $L^2$ center of mass, and d…