Stable Movement for Nondual Lipschitz Convex Optimization: Efficiency and Nearly Optimal Oracle Rates

David Martínez-Rubio; Cristóbal Guzmán

math.OCSep 17, 2026

Stable Movement for Nondual Lipschitz Convex Optimization: Efficiency and Nearly Optimal Oracle Rates

Authors: David Martínez-Rubio, Cristóbal Guzmán

Abstract

We study efficient algorithms for realizing the first-order oracle complexity of optimization of $G$ -Lipschitz convex functions with respect to the $\ell_{q}$ -norm over an $\ell_{p}$ -ball of radius $R$ , where $1\leq p,q\leq \infty$ . For $p<q$ , we obtain error $\widetilde{O}_{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 $\widetilde{O}(GR/T)$ for Euclidean Lipschitzness over an $\ell_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 $\widetilde{O}_{p,q}(RT^{1-1/p+(1/q-1/2)_{+}})$ in the $\ell_{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.

Explore similar work

Sep 17, 2026math.OC

The First-Order Oracle Complexity of Lipschitz Convex Optimization in Nondual Settings

We study first-order black-box convex optimization over an

\ell_p

-ball for objectives Lipschitz in the

\ell_q

-norm, solving in the affirmative the nonsmooth version of the COLT open question (Guz15b) on whether the geometry of a smaller feasible set (

p < q

) can improve convergence rates in convex optimization, and matching prior lower bounds up to logarithmic factors. Our rates include

\widetilde O(1/T)

for convex Euclidean-Lipschitz optimization over the

\ell_1

-ball, improving on the

O(1/\sqrt{T})

classical rate under general assumptions. The key technical device is a new online learning game, where the comparator is evaluated using the maximum of affine losses observed so far. We bound the value of this game above and below in terms of a combinatorial online learning quantity: the sequential fat-shattering dimension, which we characterize for the

\ell_p / \ell_q

case. Our results generally apply when the feasible set

X

and the set of possible subgradients

H

are convex, centrally symmetric, and admit a type of minmax theorem, advancing on a fundamental question by Sridharan [Sri12, Section 10.1.2, Q3]. As a geometric consequence of our analysis, of independent interest, we obtain estimates for the expected distance of a convex hull of samples to their mean in several Banach geometries, a version of the celebrated Wendel's theorem (Wen62), but quantitative and for bounded general distributions as opposed to centrally symmetric ones.

David Martínez-Rubio, Brian Bullins, Cristóbal Guzmán +1

Convex Optimization Optimal Sample Complexity

Ask PDF

Jul 21, 2026cs.DS

Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memory

We prove two lower bounds for the first order oracle complexity of minimizing a

d

-dimensional

1

-Lipschitz convex function over the unit ball with

m

bits of memory. We first show that any such (possibly randomized) algorithm must make

\tildeΩ(\frac{d^2}{\sqrt{m}})

oracle queries. For deterministic optimization algorithms, we show that

\tildeΩ(\min\{d^{1.6},\frac{d^{8/3}}{m^{2/3}}\})

queries are required. For all memory regimes of interest, these improves upon the previous best known lower bounds of

\tildeΩ(\max\{\frac{d^{8/3}}{m^{4/3}},\frac{d^{4/3}}{m^{1/6}}\})

and

\tildeΩ(\frac{d^{5/3}}{m^{1/3}})

for randomized and deterministic algorithms respectively. Notably, due to existing upper bounds, our lower bound for deterministic algorithms is the first to show a sharp oracle complexity phase transition around

m\approx d^2

, where a polylogarithmic change in memory leads to a

\mathsf{poly}(d)

change in the number of required oracle calls. Further, when the suboptimality is polynomially small in

d

, our lower bound randomized algorithms is the first to show that

\tildeΩ(d^2)

memory is necessary to nearly match the optimal query complexity among algorithms without memory constraints. Previously, such a result was only known for the regime where the suboptimality is quasipolynomially small in

d

Michael Menart, Aleksandar Nikolov, Ohad Shamir

Lower Bounds Convex Optimization

Ask PDF

May 8, 2026cs.LG

Convex Optimization with Nested Evolving Feasible Sets

Convex Optimization with Nested Evolving Feasible Sets (CONES)} is considered where the objective function

f

remains fixed but the feasible region evolves over time as a nested sequence

S_1 \supseteq S_2 \supseteq \cdots \supseteq S_T

. The goal of an online algorithm is to simultaneously minimize the regret with respect to hindsight static optimal benchmark and the total movement cost while ensuring feasibility at all times. CONES is an optimization-oriented generalization of the well-known nested convex body chasing problem. When the loss function is convex, we propose a lazy-algorithm and show that it achieves

O(T^{1-β}), O(T^β)

simultaneous regret and movement cost for any

β\in (0,1]

, over a time horizon of

T

. When the loss function is strongly convex or

α

-sharp, we propose an algorithm Frugal that simultaneously achieves zero regret and a movement cost of

O(\log T)

. To complement this, we show that any online algorithm with

o(T)

regret has a movement cost of

Ω(\log{T})

for both cases, proving optimality of Frugal.

Karthick Krishna M., Haricharan Balasundaram, Rahul Vaze

Convex Optimization O(T^Β)$ Simultaneous Regret Convex Sets Feasibility

Ask PDF