17 problems

Let $p\geq 2$, and consider the class of $p$th-order algorithms for convex-concave minimax optimization defined in the paper. For the constructed hard instance, the paper proves an…

Consider high-order extragradient methods for convex-concave minimax optimization, with complexity measured by the number of high-order oracle calls needed to find an $\epsilon$-so…

Let $f({\bm{x}},{\bm{y}})$ be a convex-concave function with $L_p$-Lipschitz continuous $p$th-order derivatives, and let $\epsilon>0$ be the target accuracy. The authors' upper bou…

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…

Consider a minimax quadratic optimization problem with outer variable $x\in\mathbb{R}^{n_x}$, inner variable $y\in\mathbb{R}^{n_y}$, objective … subject to coupled constraints…

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 convex-concave minimax problems measured by an accuracy parameter $\epsilon$, with convergence rate expressed in oracle complexity up to polylogarithmic factors. Optimal-r…

Let $f$ be a convex-concave objective function with $(L_x,L_y,L_{xy})$-Lipschitz gradients, and let Alex-GDA denote the extrapolated alternating gradient descent-ascent method. Ale…

Let ${\mathcal F}(\mu_x,\mu_y,L_x,L_y,L_{xy})$ denote the function class considered for the alternating gradient descent-ascent method, and let $\kappa_x$, $\kappa_y$, and…

Non-tight-analysis conjecture. The worse result is caused by the possibly non-tight analysis.

Let $n$ be the sample size and let $\epsilon>0$ be the target accuracy. Consider the gradient complexity of the stochastic nonconvex–strongly-concave (NC-SC) finite-sum minimax alg…

Let $\kappa$ denote the condition number and let $\epsilon>0$ be the target accuracy. An NC-SC stochastic minimax problem is a stochastic minimax optimization problem that is nonco…

Let $\delta$ be the sampling ratio, let $\varepsilon\geq 0$, and let $(\ell_q,\varepsilon)$-separability mean that there exists $\bm{\theta}\in\mathbb{R}^n$ satisfying … Consider t…

Strip minimaxmax optimum conjecture. The optimum of the minimaxmax problem is the couple $(\overline e_1,\operatorname{Strips})$.

Minimaxmax optimum conjecture. The optimum of the minimaxmax problem is the couple $(f^1,D^0)$.

Time-dependent initialization conjecture. In the general case, an optimal procedure is based on a deterministic time-dependent initialization $\{r_n\}_{n\geq1}$, with a threshold…

SR-$r$ equalizer conjecture. An optimal SR-$r$ procedure should be an equalizer at the beginning and at sufficiently large values of $\nu$, so the initialization $r_A$ should be se…