Stable Movement for Nondual Lipschitz Convex Optimization: Efficient First-Order Algorithms over ℓp-Balls

Forum topic · 小凯 · 2026-09-20

Summary

This arXiv paper (2609.20701) by David Martínez-Rubio and Cristóbal Guzmán presents efficient first-order algorithms for optimizing convex functions that are G-Lipschitz with respect to the ℓq-norm over an ℓp-ball of radius R, for all 1≤p,q≤∞. For p<q, the algorithms achieve error Õ_{p,q}(GR/T^{1/p-(1/q-1/2)+}) after T oracle queries, efficiently matching the nearly optimal rates of (MBG+26) and resolving the nonsmooth end of the COLT 2015 open problem (Guz15b). Notably, the rate is Õ(GR/T) for Euclidean Lipschitz functions over an ℓ1-ball (p=1, q=2). The approach reduces convex Lipschitz optimization to chasing nested convex sets in sublevel sets of an evolving bundle: each query either finds a low-value point or produces a deep cut on the current sublevel set. The paper introduces the novel concept of a stable centroid, whose ℓq-norm movement after T steps is bounded by Õ_{p,q}(RT^{1-1/p+(1/q-1/2)+}), shown to be nearly optimal in high dimensions, with Monte Carlo averaging achieving near-optimal rates in polynomial time.

Overview

Field: Machine Learning / Optimization
Authors: David Martínez-Rubio, Cristóbal Guzmán
Posted: 2026-09-17
arXiv: 2609.20701

Problem

The paper studies efficient algorithms realizing the first-order oracle complexity of optimizing convex functions that are G-Lipschitz with respect to the ℓq-norm over an ℓp-ball of radius R, where 1 ≤ p, q ≤ ∞.

Main Results

For p < q, the algorithms 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).

This resolves the nonsmooth end of the COLT 2015 open problem (Guz15b).
In particular, the rate is Õ(GR/T) for Euclidean Lipschitz functions over an ℓ1-ball of radius R (p = 1, q = 2).

Technique

The solution reduces convex Lipschitz optimization to the chasing nested convex sets problem in sublevel sets of an evolving bundle (LNN95; BBE+20): at each oracle query, the algorithm either finds a point with low function value or produces a deep cut on the current sublevel set and chases it. A dichotomy between selector stability and deep-cut-enforced movement nearly optimally bounds the number of iterations.

For nested subsets of an ℓp-ball, the authors introduce the new concept of a stable centroid: after T steps, its ℓq-norm movement is at most Õ_{p,q}(RT^{1-1/p+(1/q-1/2)_{+}}), which they prove is nearly optimal in high dimensions. Monte Carlo averaging of the proposed selector attains near-optimal rates with high probability, and the scheme is implementable in polynomial time in the real arithmetic model.

Original Abstract (English)

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

Read the full paper: https://arxiv.org/abs/2609.20701