We study convex-concave minimax optimization problems with bilinear coupling of the form $\min_{x\in \mathcal X}\max_{y\in \mathcal Y} \; f(x)+\langle y,\mathbf{B}x\rangle-g(y),$ where the functions $f$ and $g$ have H\"older continuous (sub)gradients. This setting covers a broad range of regimes, from nonsmooth problems with bounded subgradient variation to smooth problems with Lipschitz continuous gradients; for a smooth component used in the coupling-induced regularizer, its Lipschitz-gradient constant is assumed to hold in the ambient space. We propose a sliding method that exploits the composite structure of the problem by querying the oracles associated with $f$, $g$, and the bilinear coupling operator at prescribed frequencies determined by their individual properties. The method is based on a recursive sliding scheme for monotone variational inequalities. We establish convergence guarantees under H\"older continuity and show how the resulting complexity bounds depend explicitly on the H\"older exponents, H\"older constants, strong convexity parameters, and spectral properties of the coupling matrix. Our analysis covers nonstrongly convex and partially strongly convex regimes. For stochastic problems, we prove a uniform expected-gap bound in the degenerate regime and, under ambient smoothness and positive effective curvature, convergence up to an explicit noise floor. Numerical experiments reproduce the predicted H\"older exponents and confirm that the number of gradient evaluations required for each function separates according to its own smoothness level rather than the worse of the two. A tomographic benchmark shows runtime gains when gradient evaluations are more expensive than the additional matrix-vector products.
We study lower bounds on the first-order oracle complexity of smooth nonconvex-concave minimax optimization. We consider objectives $f$ that are jointly $L$-smooth in the primal and dual variables $(x,y)$, concave in $y$, and whose primal value function $\Phi(x) := \max_{y\in\mathcal Y} f(x,y)$ satisfies the initial-gap condition $\Phi(0)-\inf_{x\in\mathcal X}\Phi(x)\le \Delta_\Phi$, with a bounded dual domain satisfying $\operatorname{diam}(\mathcal Y)\le D_{\mathcal Y}$. We measure stationarity by the norm of the gradient of the Moreau envelope of $\Phi+\iota_{\mathcal X}$ with parameter $1/(2L)$. We prove that any deterministic zero-respecting first-order algorithm requires $\Omega\left(L^2D_{\mathcal Y}\Delta_\Phi\epsilon^{-3}\right)$ oracle evaluations to find an $\epsilon$-stationary point. Under an unbiased stochastic first-order oracle with bounded variance, any stochastic zero-respecting algorithm requires $\Omega\left(L^3D_{\mathcal Y}^2\Delta_\Phi\epsilon^{-6}\right)$ oracle evaluations. The same lower bounds hold when $\Delta_\Phi$ is replaced by the initial primal-dual gap $\mathcal G_0$. These deterministic and stochastic lower bounds match the corresponding upper bounds of [14] and [29], respectively, up to a logarithmic factor in the deterministic setting.
We consider the problem of noisy gradient-free minimization of the k-th order partial derivative of a $\beta$-H{\"o}lder function supported on a d-dimensional cube. We show that T ^{($\beta$+d+k)/(2$\beta$+d)} log(T )^{(\beta-k)/(2\beta+d)} is a non-asymptotic minimax rate of the T step cumulative regret for all $\beta$ \ge 0. In the special case k = 0, our results cover the problem of noisy gradient-free minimization of $\beta$-H{\"o}lder functions, closing the existing gap between the known upper and lower bounds. We show that a minimizer of a suitably chosen local polynomial estimator is rate-optimal. The minimax optimal upper bound is achieved under the passive design, that is, when the query points are i.i.d. Thus, there is no advantage in considering sequential designs when it is only known that f is a $\beta$-H{\"o}lder function with no additional property. We propose an algorithm feasible in polynomial time that constructs a proxy of the minimizer of the local polynomial estimator. The procedure requires computing the estimator on auxiliary random points. The resulting polynomial time algorithm matches the lower bound.
Théo Paquier, A. Tsybakov, F. Portier et al.· 0 citations
Minimizing gradients of a convex function is an important problem across optimization and learning tasks. The gradient provides a directly computable certificate of approximate stationarity, and its minimization usually implies stronger results than those for minimization of function values. In this work, we study gradient-norm minimization for convex functions that are $(L,\kappa)$-H\"older smooth with respect to the $\ell_p$-norms, $p \geq 1$. We develop algorithms that achieve near-optimal gradient-oracle complexity for this problem. In the smooth case, our results resolve the previously open setting $p>2$. For H\"older-smooth objectives, we close the complexity gap throughout the full $p$-range, including to the best of our knowledge, a gap in the Euclidean case. We provide two families of algorithms: the first one comes with a simple iteration and generalizes a phenomenon known as mirror duality, exploiting dual behaviours of algorithms with errors and inexact computations. The second makes use of accumulating regularizers centered at different approximate solutions, which we sequentially minimize in order to provide our near-optimal rates.
Nico Pelleriti, Maryam Shiran, David Martínez-Rubio et al.· 0 citations
Can the classical Heavy-Ball method, with arbitrary horizon-dependent parameters chosen in advance, achieve Nesterov's $O(T^{-2})$ last-iterate rate on every smooth convex objective? We provide a negative answer. For every horizon $T\ge2$ and every predetermined schedule with nonnegative step sizes and momenta in $[0,1)$, there exists a convex $1$-smooth objective, with initialization distance at most one and zero initial velocity, for which the last iterate of the Heavy-Ball method satisfies \[ f(x_T)-f^\star=\Omega\!\left(\frac{1}{T^\alpha\log T}\right), \qquad \alpha=\frac{1+\sqrt5}{2}. \] Thus even fully nonstationary, horizon-dependent tuning cannot give the classical Heavy-Ball method a Nesterov-rate guarantee on the smooth convex class.
In this paper, let $u\in C^4(B_{10})$ with $D^2u\geq -KI$ define a $2$-admissible graph $M=\{(x,u(x)):x\in B_{10}\}\subset\R^{n+1}$ satisfying \[ \sigma_2(\kappa[u])=f(x). \] We prove an interior curvature estimate depending on the Lipschitz norm of the right-hand sides. The proof combines a shifted Jacobi inequality for \(b=\log(H+J_0)\), a parallel hypersurface transformation that makes the Newton tensor uniformly elliptic and local boundedness estimate then reduces the pointwise bound to a weighted $L^1$ estimate, which is completed using the Jacobi energy inequality and integration by parts.
Let $n\ge2$ and let $u$ be a smooth 2-convex and semi-convex solution of \[ \frac{\sigma _2(D^2u)}{\sigma _1(D^2u)}=f(x). \] We prove an interior Hessian estimate depending on the Lipschitz norm of $f$. The proof combines the integral approach of Chen--Jian--Zhou with the algebraic reduction of the quotient equation to a $\sigma _2$ structure. The main new point is a shifted algebraic inequality that yields a shifted trace Jacobi inequality in divergence form for $\log(\Delta u+a)$. We work with the linearized operator $G=(\Delta u-f)I-D^2u$ of the equivalent equation $\sigma_2(D^2u)=f \Delta u$. The almost divergence-free identity \(\partial_iG_{ij}=-f_j\) enables us to control the \(\Delta f\) term by integration by parts solely in terms of the Lipschitz norm of \(f\). A Legendre--Lewy transformation converts the resulting degenerate divergence-form equation into a uniformly elliptic one. The estimate then follows from a mean-value inequality together with a weighted energy argument. As an application, in dimension two we obtain interior $C^2$ regularity for convex viscosity solutions with positive Lipschitz right-hand side. Moreover, our counterexamples show that the Lipschitz regularity required of the right-hand side is optimal.
Ke Ji, Li-Chun Liang· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
