19 problems

Let $E$ be the objective function, let $\boldsymbol{s}^{(k)}$ be the iterate at iteration $k$, let $E^*$ denote the optimal objective value, and let…

The intermediate gradient method texttt{ISTM} is studied for minimizing a smooth convex function in the presence of relative noise, with convergence estimates given by Theorem. Opt…

The Shampoo method uses preconditioners whose eigenvalues increase monotonically. Shampoo plateau conjecture. Shampoo may not effectively improve the behaviour of first-order metho…

Tightest-bound conjecture. The following infinite-dimensional optimization problem may provide the tightest bound for the gradient method:

An optimization method evolves according to a dynamical system or algorithm for minimizing a function, and an adapted Tikhonov regularization term is a regularization term chosen i…

Equivalence conjecture. These two conditions also imply each other. The proximal Polyak–Łojasiewicz condition and gradient-mapping domination are related through an interlacing ine…

Let $f$ be an $L$-smooth function, let $f^\star$ be its minimum value, let $x^1$ be an initial point, and write $\Delta=f(x^1)-f^\star$. Consider gradient-method iterates $x^k$ wit…

Let $f:\mathbb{R}^d\to\mathbb{R}$ be an $L$-smooth function, let $f^\star$ be its minimum value, let $x^1$ be an initial point, and write $\Delta=f(x^1)-f^\star$. For gradient-meth…

Let $K>0$. Consider a method whose iterates have the form … where $\boldsymbol{x}_0\in\mathbb{R}^d$ is the initial point, $f$ is a convex function accessed through a gradient oracl…

Let $F$ be an $(L_0,L_1)$-smooth function whose stochastic gradient noises are … denote the initial optimality gap, $\varepsilon$ the desired stationarity accuracy, and $\Delta$ th…

Quadratic LPL exponent conjecture. The exponent $alpha$ equals either $2$ or $\frac{4}{3}$.

A second order differentiable function $f$ is $(L_0,L_1)$-smooth if … The authors propose this condition because empirical observations suggest a positive correlation between funct…

Let $D_x$, $D_H$, $obreaktextstyle n$, $obreaktextstylekappa$, and $obreaktextstylemu$ denote the problem-dependent quantities and condition parameter used in the complexity bou…

Let $H$ be the Hilbert space used by the gradient method, and let $T_{u_n}$ denote the subspace associated with the iterate $u_n$. Let $N$ be the dimension of the approximation spa…

Taylor et al.'s one-step gradient-decrease conjecture. The optimal step size in terms of gradient decrease is $h=\sqrt{2}$, with worst-case bound

Tight constant-step GM conjecture. At least one of the two functions specified in the paper is a worst-case function for GM with constant step size $0<h<2$. The bound is proved for…

Strongly convex gradient-norm conjecture. Every sequence of iterates generated in this way satisfies

Drori–Teboulle conjecture. Every sequence of iterates generated in this way satisfies

SAG step-size conjecture. When $\b5/L$ is small, choosing