Stable Movement for Nondual Lipschitz Convex Optimization: Efficiency and Nearly Optimal Oracle Rates
Abstract
We study efficient algorithms for realizing the first-order oracle complexity of optimization of G-Lipschitz convex functions with respect to the ℓq-norm over an ℓp-ball of radius R, where 1≤ p,q≤ ∞. For p<q, we obtain error Õp,q(GR/T1/p−(1/q−1/2)+) after T oracle queries, efficiently realizing the nearly optimal rates of (MBG+26), thereby resolving the nonsmooth end of the COLT 2015 open problem (Guz15b). In particular, the rate is Õ(GR/T) for Euclidean Lipschitzness over an ℓ1-ball of radius R (p=1,q=2). Our solution consists of reducing convex Lipschitz optimization to the chasing nested convex sets problem in sublevel sets of an evolving bundle (LNN95; BBE+20): at each query we either find a point with low function value or we produce a deep cut in the current sublevel of the bundle, that we chase. The dichotomy between stability of selectors and forced movement by deep cuts bounds the number of iterations of the algorithm near optimally. For nested subsets of R Bpd, we introduce a novel notion of stable center whose movement is bounded by Õp,q(RT1−1/p+(1/q−1/2)+) in the ℓq-norm after T steps, which we show is nearly optimal in high dimensions. A Monte Carlo average of the proposed selector achieves near-optimal rates with high probability and can be implemented in polynomial time for our optimization algorithm in the real-arithmetic model.
Related
- The First-Order Oracle Complexity of Lipschitz Convex Optimization in Nondual Settings
- Near-Optimal Acceleration for Smooth ℓp / ℓq Nondual Convex First-Order Oracle Optimization
- Financial Tail Risk Beyond Lipschitz Continuity via Semi-Discrete Optimal Transport
- Optimal Global Sobolev Estimates for Fractional Dirichlet Problems in Bounded Lipschitz Domains
- A Composite Representation Theorem for Solution Mappings in Regularized Composite Optimization with Applications to Hausdorff Lipschitz Stability
BibTeX
@misc{martinezrubio2026stable,
title = {{Stable Movement for Nondual Lipschitz Convex Optimization: Efficiency and Nearly Optimal Oracle Rates}},
author = {David Martínez-Rubio and Cristóbal Guzmán},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.20701},
eprint = {2609.20701},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.20701},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Stable Movement for Nondual Lipschitz Convex Optimization: Efficiency and Nearly Optimal Oracle Rates
AU - David Martínez-Rubio
AU - Cristóbal Guzmán
PY - 2026
DA - 2026/09/17
PB - arXiv
DO - 10.48550/arxiv.2609.20701
UR - https://arxiv.org/abs/2609.20701
AB - We study efficient algorithms for realizing the first-order oracle complexity of optimization of G-Lipschitz convex functions with respect to the ℓ_q-norm over an ℓ_p-ball of radius R, where 1≤ p,q≤ ∞. For p<q, we obtain error Õ_p,q(GR/T^1/p−(1/q−1/2)_+) after T oracle queries, efficiently realizing the nearly optimal rates of (MBG+26), thereby resolving the nonsmooth end of the COLT 2015 open problem (Guz15b). In particular, the rate is Õ(GR/T) for Euclidean Lipschitzness over an ℓ_1-ball of radius R (p=1,q=2). Our solution consists of reducing convex Lipschitz optimization to the chasing nested convex sets problem in sublevel sets of an evolving bundle (LNN95; BBE+20): at each query we either find a point with low function value or we produce a deep cut in the current sublevel of the bundle, that we chase. The dichotomy between stability of selectors and forced movement by deep cuts bounds the number of iterations of the algorithm near optimally. For nested subsets of R B_p^d, we introduce a novel notion of stable center whose movement is bounded by Õ_p,q(RT^1−1/p+(1/q−1/2)_+) in the ℓ_q-norm after T steps, which we show is nearly optimal in high dimensions. A Monte Carlo average of the proposed selector achieves near-optimal rates with high probability and can be implemented in polynomial time for our optimization algorithm in the real-arithmetic model.
ER -