30 problems

Roots-of-unity cycle conjecture. For any stationary first-order method, if there exists a cyclic trajectory, then there exists a roots-of-unity two-dimensional cycle on the functio…

Quadratic worst-case conjecture. The function $f_2({\bm{x}})$ is a worst-case function for the secondary sequence of OGM1$'$ and OGM2$'$, so the displayed lower bound is the tight…

Let $0<\mu<L$, let $p\in\mathbb{N}$, and let $\mathcal{A}$ be a consistent $p$-SCLI optimization algorithm with diagonal inversion matrix and linear coefficient matrices. Let…

Let $N$ denote the iteration count, let $L$ be the smoothness constant, and consider inexact gradient descent for minimizing $f(x_N)-f(x_*)$ under $\|x_0-x_*\|\leq R$. Let…

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…

Let $N$ denote the iteration count, and consider full fixed-step cyclic coordinate descent on a problem partitioned into $2$ blocks, allowing the update to use all past gradient in…

Let ITEM denote a known minimax-optimal first-order method for smooth strongly convex optimization, and let OGM-G denote a known minimax-optimal first-order method for minimizing t…

Convergence bounds conjecture. The convergence bounds for both generalized families should satisfy

The bilevel setting involves a hyperobjective $F$ and an inexact gradient oracle, while the current construction requires access to the exact dual multiplier. Primal-only gradient…

The PDQP solver applies adaptive restart to a first-order method for convex quadratic programming. Unlike diagonal preconditioning, adaptive restart does not readily preserve the m…

Kwon et al.'s conjecture. A fundamental gap may exist between gradient-based methods and HVP-based methods for bilevel optimization.

Let $\mathcal{J}$ be a finite index set, and for each $j\in\mathcal{J}$ let $f_j$ be a convex $(M_j,v_j)$-Hölder smooth function. Let $x_0$ be the initial point, $x^*$ an optimizer…

Consider the Acc-DNGD algorithm with diminishing step-size … and let $f(\bar{x}^K)-f(x^*)$ denote its average functional error, where $f(x)=\frac{1}{N}\sum_{i=1}^N f_i(x)$ and…

The Acc-DNGD algorithm uses a diminishing step-size … where $\eta$ and $k_0$ are parameters, and its average functional error is measured by $f(\bar{x}^k)-f(x^*)$, with…

Let $f$ be an objective function in dimension $d$, and let a first-order algorithm produce iterates $(x_i)_i$ by using past iterates, function values, and gradients. Write $n$ for…

OBL-G$_\flat$'s $\mathcal{A}^\star$-optimality conjecture. OBL-G$_\flat$ is $\mathcal{A}^\star$-optimal in the sense that

Let $f$ be a smooth convex function, let $f_\star$ denote its minimum value, and let $x_0$ be the initial point. An algorithm is anytime if it does not need to know the total itera…

Consider optimistic gradient (OG) applied to the setting discussed in the paper, with step size $\eta$ and a vector field satisfying the relevant smoothness and strong monotonicity…

Let a first-order algorithm have $T$ steps of memory. For each integer $n\geq 1$, an off-by-$n$ pointwise IQC is the quadratic constraint associated with a pair of iterates…

Let $(f,h)$ belong to the class $\mathcal{B}_L(C)$ of pairs satisfying the general $h$-smoothness assumptions, and consider IGA with a step size in $(0,1/L]$. IGA nonconvergence co…

OGM-G lower-bound conjecture. The lower bound above for OGM-G under the distance initialization condition is exact. This is posed as an open problem and is supported by numerical e…

Let OGM-G be the first-order method discussed in the source, with worst-case gradient bound given by equation. OGM-G optimality conjecture. The exact worst-case bound of OGM-G may…

Composite-gradient FPGM conjecture. The solution $\hat{{\bm{h}}}_{\mathrm{D'}}$ corresponds to the coefficients defined by the FPGM construction in with the above choice of $t_i$.

FISTA global-minimizer conjecture. The feasible point with $t_i^2=T_i$ that corresponds to FPGM (FISTA) is a global minimizer of the relaxed problem defining…

Consider optimal fixed-step first-order methods and their worst-case functions for the performance criterion under study. In the OGM discussion, the two observed types are a piecew…