The Complexity of Convex Optimization with Mismatched Geometry
Abstract
Optimal first-order methods on non-Euclidean domains such as the ℓ1 ball B1n(R)={x∈ℝn:|x|1≤ 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(xN)−minB1n(R)f to O(LR2/N2) after N first-order queries (an entropic ℓ1 prox-setup replaces L by the ℓ1→ℓ∞ constant L1≤ L, at the cost of a factor log n and with the same exponent). The lower bound of Guzmán and Nemirovski is of order LR2/N3, 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 LR2/N3 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 √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ölder 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 ℓp ball with 1≤ p<2 and without logarithmic loss. Experiments confirm the predicted N−3 behaviour on objectives that are hard for Euclidean methods.
Related
- Randomized Parallel Complexity of Weakly Convex Optimization
- On tractability, complexity, and mixed-integer convex programming representability of distributionally favorable optimization
- Near-Optimal Exact-Value Zeroth-Order Complexity for Smooth Strongly Convex Optimization
- Descending Everest with First-Order Oracles: Oracle Complexity of Convex Optimization under (L0,L1)-Smoothness
- Near-Optimal Deterministic Exact-Value Complexity for Smooth Convex Optimization
BibTeX
@misc{loginov2026complexity,
title = {{The Complexity of Convex Optimization with Mismatched Geometry}},
author = {Timofei Loginov and Alexander Gasnikov and Yuriy Dorn and Aleksandr Shestakov and Nazarii Tupitsa and Osman Osmanov and Darina Dvinskikh},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.32910},
eprint = {2609.32910},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.32910},
}
RIS
TY - UNPB
TI - The Complexity of Convex Optimization with Mismatched Geometry
AU - Timofei Loginov
AU - Alexander Gasnikov
AU - Yuriy Dorn
AU - Aleksandr Shestakov
AU - Nazarii Tupitsa
AU - Osman Osmanov
AU - Darina Dvinskikh
PY - 2026
DA - 2026/09/26
PB - arXiv
DO - 10.48550/arxiv.2609.32910
UR - https://arxiv.org/abs/2609.32910
AB - Optimal first-order methods on non-Euclidean domains such as the ℓ_1 ball B_1^n(R)={x∈ℝ^n:|x|_1≤ 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 ℓ_1 prox-setup replaces L by the ℓ_1→ℓ_∞ constant L_1≤ L, at the cost of a factor log n and with the same exponent). The lower bound of Guzmán 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 √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ölder 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 ℓ_p ball with 1≤ p<2 and without logarithmic loss. Experiments confirm the predicted N^−3 behaviour on objectives that are hard for Euclidean methods.
ER -