79 problems

Let $f$ be an $L$-smooth function. A Goldstein approximate second-order stationary point (SOSP) is an approximate second-order stationary point in the Goldstein sense, as defined i…

The consensus model assumes a separable objective of the form $\sum_j f_j(\mathbf{x}_j,\mathbf{y}_j)$, with each term depending only on agent $j$'s own variables. In the non-separa…

Rate-optimality conjecture. The $\alpha$-dependent price in the convergence rate, namely $\mathcal{O}(\varepsilon^{-(4+\alpha)})$ for $\alpha\in(0,1)$ and…

The nonsmooth stochastic minimax setting considered here has objective complexity ${\mathcal{O}}(\varepsilon^{-7})$ in the extreme case $\theta=1$, under a restricted concavity con…

Let $\boldsymbol{\theta}^\ast$ be the planted parameter, let $\mathcal{L}_n$ be the loss associated with the Wirtinger-flow objective … and consider the proportional regime $n=Cd$.…

Let $\mathcal{L}_n(\boldsymbol{\theta})$ be the loss function for the single-index model, let $\delta$ denote the aspect ratio, and let $\mathcal{T}_s(\cdot)$ be the preprocessing…

In stochastic minimax optimization, let $F(x,\xi)=\max_{y\in\mathcal{Y}(x,\xi)}\hat{F}(x,y,\xi)$, where $\mathcal{Y}(x,\xi)\subset\mathbb{R}^m$ is the feasible set of the adversari…

Consider a control component with activity sets … where … and suppose that the cost function is strongly convex on each restriction $g_i|_{[a_i^k,b_i^k]}$. Tangent-compatibility co…

Conjectured exact finite-iteration behavior. If $\mu_2<0<\mu_1<L_2$, so that $F$ is nonconvex-nonconcave, then

The high-order proximal-point method uses a regularization parameter $p$, and the critical points of the objective may lie in either a “steep valley” or a “wide valley.” Valley-geo…

Consider Problem Class 2 and Algorithm Class 1, with the lower complexity bound established in Theorem … is also nearly tight under these additional conditions. The conjecture is m…

The framework uses exponentially increasing weights, corresponding to a constant $c_t=\gamma$, and these weights achieve optimal worst-case convergence guarantees. Instance-depende…

Convex-set extension conjecture. Theorem continuous strongly convex remains valid under this replacement.

The preceding discussion concerns the case in which the concave term $h$ is removed from the definition of $f$. Extension conjecture. Similar statements should be provable with $h$…

Xia's conjecture. Under these two assumptions, $(GTR)$ has at most two local-nonglobal minimizers.

Let $\mu\in(-\infty,0)$ and consider $N$ iterations of gradient descent with constant stepsize $\gamma L\in[\gbari[\bar{N}-1],\gbari[\bar{N}])\subseteq[\gbari[1],\gbari[N-1])$, sta…

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…

Let $f$ belong to the function class considered in the paper, let $abla f(xi)$ denote the gradient along the gradient-descent iterates, and let the stepsizes $gammai$ be chosen as…

Let $U_r\in\mathbb{R}^{d\times r}$ be an orthonormal matrix, and let $\mathrm{Gr}(d,r)$ denote the Grassmann manifold of $r$-dimensional subspaces of $\mathbb{R}^d$. Define … as in…

Consider constrained, $L$-smooth min-max problems that may be stochastic and nonconvex-nonconcave, satisfying $\rho$-cohypomonotonicity or admitting a solution to the $\rho$-weakly…

The setting concerns stochastic gradient descent (SGD) without replacement, in which the data batches used at successive steps are dependent because they are disjoint, and saddle e…

Let $\mathcal{C}_n$ be the space of full-order dynamic policies for $\mathcal{H}_\infty$ control. A policy $\mathsf{K}\in\mathcal{C}_n$ is Clarke stationary when…

Let $\mathcal{C}_n$ be the space of full-order dynamic policies, and let $\mathcal{C}_{\mathrm{nd}}$ be the subset of non-degenerate policies, namely those admitting a certificate…

Let $p$ denote the factorization rank in the Burer–Monteiro factorization … is benign with high probability in each of the following settings: the high-dimensional Kuramoto model,…

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