Skip to content
Preprint

The Complexity of Convex Optimization with Mismatched Geometry

Sep 2026 · 0 citations
Mathematics

TL;DR

It is shown that for this mismatched problem the minimax value of the gap is of order $LR^2/N^3$ up to logarithmic factors, for deterministic and for randomized methods alike, and already in dimension proportional to the number of queries.

Abstract

Optimal first-order methods on non-Euclidean domains such as the $\ell_1$ ball $B_1^n(R)=\{x\in\mathbb R^n:\|x\|_1\le R\}$ pair the prox-function with the norm in which smoothness is measured. When the gradient is $L$-Lipschitz in the Euclidean norm only, the accelerated method with a Euclidean prox-setup reduces the functional gap $f(x_N)-\min_{B_1^n(R)}f$ to $O(LR^2/N^2)$ after $N$ first-order queries (an entropic $\ell_1$ prox-setup replaces $L$ by the $\ell_1\to\ell_\infty$ constant $L_1\le L$, at the cost of a factor $\log n$ and with the same exponent). The lower bound of Guzm\'an and Nemirovski is of order $LR^2/N^3$, and whether the upper bound can be brought down to that order is a question of A. S. Nemirovski. We show that for this mismatched problem the minimax value of the gap is of order $LR^2/N^3$ up to logarithmic factors, for deterministic and for randomized methods alike, and already in dimension proportional to the number of queries. The upper bound is attained by a Steiner-point level method: every supporting hyperplane seen so far is kept as a level cut, and the next query is made near the Steiner point of the resulting localization polytope. The analysis rests on a single geometric fact: along nested subsets of the ball the Steiner points travel a distance that is polylogarithmic in the dimension, in contrast to $\sqrt n$ for the Euclidean ball. All queries stay feasible, and a randomized selector keeps the internal work polynomial. The same geometry yields optimal rates for nonsmooth objectives, H\"older gradients, higher-order oracles and Lipschitz monotone operators, the last with a matching deterministic lower bound. For convex quadratics, a curvature-learning method attains the optimal rate on every $\ell_p$ ball with $1\le p<2$ and without logarithmic loss. Experiments confirm the predicted $N^{-3}$ behaviour on objectives that are hard for Euclidean methods.

View source

Similar papers

Near-Optimal Acceleration for Smooth ℓp / ℓq Nondual Convex First-Order Oracle Optimization

We study the optimization of convex objectives with $(L,\kappa-1)$-H\"older-continuous gradients in $\ell_q$ over $R B_p^d$, $1<\kappa\le 2$. (MG26) provides selectors with a movement bound for the problem of chasing high-dimensional convex nested sets for every $p<q$ and generally reduces Lipschitz convex optimization...

David Martínez-Rubio, Brian Bullins, Cristóbal Guzmán et al. · 1 citation
Preprint Sep 2026

Matching Lower Bounds for Randomized First-Order Methods in Hessian-Lipschitz Nonconvex Optimization

We establish a randomized first-order lower bound for finding an $\epsilon$-stationary point, $\|\nabla f(x)\|\le \epsilon$, of a nonconvex function with initial gap at most $\Delta$, $L_1$-Lipschitz gradient, and $L_2$-Lipschitz Hessian. Each oracle call returns the exact function value and gradient. Let $Q_{\mathrm{r...

Hai-Han Zhang, Wen-Dao Wu, Chen-Heng Zhang et al. · 2 citations · ⚡1
Preprint Sep 2026

Convex-Hull Instability of the $\gamma_2$-Functional in $L^p$

For every $2<p<\infty$ and every integer $r\ge2$, we construct a finite set $T\subseteq S_{L^p[0,1]}$ such that $|T|\le2^{Cr^2}$, $\gamma_2(T)\le Cr$, and $\gamma_2(\conv T)\ge c r^{3/2-1/p}$. Consequently, for every fixed $p>2$, both estimates in Talagrand's Research Problem~2.11.3 fail in each of the spaces $L^p[0,1]...

Helen W. J. Zhang, Cheng-Dong Zhao · 0 citations
Preprint Aug 2026

Square Functions and Rectifiability under Monotone Transformations of the Density

Let $\mu$ be an $n$-AD-regular measure in $\mathbb{R}^d$. Chousionis, Garnett, Le and Tolsa [CGLT] proved that $\mu$ is uniformly $n$-rectifiable if and only if the square function built from the density differences $\Delta_\mu(x,r)=\mu(B(x,r))/r^n-\mu(B(x,2r))/(2r)^n$ satisfies a Carleson condition. In this paper we s...

T. Le · 0 citations
Preprint Sep 2026

Lower Bounds for Nonconvex-Concave Minimax Optimization

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-ga...

Qi-Long Wu, Zhi-Hao Gu, Jun-Chi Yang · 7 citations
Preprint Aug 2026

Lower Bounds for Nonconvex-P{\L} Minimax Optimization

It is proved that every deterministic first-order method requires $\Omega(\ell\Delta\kappa/\epsilon^2)$ oracle queries in the worst case to find $x$ satisfying $\Phi(0)-\inf_x\Phi(x)$ and that the linear dependence on $\kappa$ is unavoidable for deterministic first-order methods.

Si-Yu Pan, Jia-Jin Li · 5 citations · ⚡1

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.