CS Paper Radar

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

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

cs.LG math.OC ·submitted 2026-09-17 17:02 UTC · v2

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, attaining the lower bounds in a COLT 2015 open problem (Guz15b) with efficient algorithms. In particular, the rate is $\widetilde{O}(GR/T)$ for Euclidean Lipschitzness with an $\ell_1$-ball domain of radius $R$ ($p=1,q=2$). Our solution consists of reducing convex Lipschitz optimization to the chasing nested convex sets problem (BBE+20) in sublevel sets of an evolving maximum of affine lower bounds, that is, the bundle (LNN95): 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 nearly optimally. For nested convex subsets of the $\ell_p$ ball $R B_p^d$, we introduce novel stable selectors whose movement 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 for our optimization algorithm in polynomial time in the real-arithmetic model.

Comment
polished writing, added a few more general results (such as a better lower bound, and a more general potential-energy center)

Closest papers

Nearest neighbours by meaning across the whole index.

Near-Optimal Acceleration for Smooth $\ell_p$ / $\ell_q$ Nondual Convex First-Order Oracle Optimization

cs.LG math.OC ·2026-09-18 ·David Martínez-Rubio, Brian Bullins, Cristóbal Guzmán, Mathieu Molina
similarity 0.77
Abstract

We study the optimization of convex objectives with $(L,κ-1)$-Hölder-continuous gradients in $\ell_q$ over $R B_p^d$, $1<κ\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 to bounds on the movement of selectors. We couple that movement with Hölder descent yielding a polynomial-runtime first-order method whose feasible output, in the high-dimensional regime $T\le d$ and for $p<\min\{q,2\}$, has error $$ \widetilde O_{κ,p,q}\!\left( \frac{LR^κ}{T^{κ(1+1/p-(1/q-1/2)_+)-1}} \right), $$ after $T$ queries to a first-order oracle, solving the COLT 2015 open problem of (Guz15), up to logarithmic factors. At $(p,q)=(1,2)$, the rate is $\widetilde{O}(LR^κ/T^{2κ-1})$, including $\widetilde{O}(LR^2/T^{3})$ cubic decay in the smooth case.

0.41

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

cs.LG math.OC ·2026-09-17 ·Brian Bullins, Cristóbal Guzmán, David Martínez-Rubio, Mathieu Molina
theory similarity 0.74
Abstract · Polished writing. Small additions (quasar-convex optimization, clarification regarding optimizing in a subset...)

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 $\mathcal{X}$ and the set of possible subgradients $\mathcal{H}$ admit a type of minimax 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.

0.43

Sharp Oracle-Regret Tradeoffs for Projection-Free Online Convex Optimization

cs.LG ·2026-09-23 ·Vaneet Aggarwal
theory similarity 0.68
Abstract

We characterize the regret attainable in online convex optimization when access to the feasible set is limited to an exact linear optimization oracle. The learner is given an inscribed ball and a diameter bound and must remain feasible on every consistent instance. For convex $G$-Lipschitz losses, diameter at most $D$, a total allowance of $Q$ oracle calls, and a strict limit of $B$ calls per round, the dimension-free minimax expected regret is $Θ(GD\max\{\sqrt T,T/(1+\min\{Q,BT\})^{1/4}\})$. The lower bound applies to arbitrary randomized learners. Universal feasibility first forces each action into the hull of the supplied ball and the preceding oracle replies. A fixed-body construction then couples fresh phase directions to a shared simplex, making useful replies costly repeatedly even though all losses have a common minimizer. A counted approximate-gradient method with interleaved blocks attains the matching rate. Total-budget and strict per-round guarantees follow as special cases, including the $T^{3/4}$ rate with one call per round and the quadratic total budget needed for $\sqrt T$ regret. For prescribed smoothness $β$, an analytic construction yields a curvature-dependent lower bound and identifies the threshold above which the general characterization remains sharp.

0.16

Lower Bounds for Randomized Linear-Oracle Optimization over Strongly Convex Sets

cs.LG math.OC ·2026-10-09 ·Sebastian Pokutta
theory similarity 0.67
Abstract

Recent results [arXiv:2602.04378, arXiv:2602.22608] have established worst-case objective-error lower bounds of order $1/T^2$ after $T$ linear minimization oracle (LMO) calls, matching the upper bound [arXiv:1406.1305] in its dependence on $T$ and thereby resolving a long-standing open question. Upon close inspection, however, both lower bounds are somewhat brittle. The first [arXiv:2602.04378] applies only to the standard Frank--Wolfe algorithm, and, as we show, its prescribed slow exact-line-search trajectories can amplify sufficiently small initialization errors exponentially, corresponding to roughly one additional bit of initialization accuracy per iteration. The second [arXiv:2602.22608] obtains lower bounds for any deterministic LMO-based first-order method via a resisting oracle that adversarially adapts to the queries of the algorithm. In both cases it is conceivable that randomization may circumvent these lower bounds; in particular, neither establishes a lower bound for unrestricted randomized first-order LMO methods. We close this gap by proving an $Ω(L\operatorname{diam}(S)^2/T^2)$ distributional lower bound for randomized first-order linear minimization oracle methods over strongly convex sets. While our construction reuses the family of [arXiv:2602.22608], our proof characterizes the conditional distribution of the hidden permutation after adaptive queries and bounds the expected decrease of a combinatorial statistic controlling optimizer variance. We further show that the same error threshold holds with probability at least $3/4$ and yields a stopping-time tail bound.

0.17

Minimax-Optimal Small-Loss Bounds for Online Linear Optimisation on $\ell_p$ Balls

cs.LG math.OCstat.ML ·2026-10-26 ·Jack J. Mayo
similarity 0.65
Abstract · 49 pages

We study full-information online linear optimisation on the unit $\ell_p$ ball in $\mathbb{R}^d$, for fixed $2\le p<\infty$ and losses of dual norm at most one. Let $Δ_T$ denote the cumulative loss of the best fixed action above each round's minimum. A follow-the-regularised-leader (FTRL) algorithm attains, on every loss sequence and without knowing $T$ or $Δ_T$, regret $O_p(1+\min\{Δ_T^{1-1/p},\, d^{1/2-1/p}\sqrt{Δ_T}\})$. Matching lower bounds show that this rate is minimax for each fixed $p$, and its constant $(2+o(1))p/\log p$ is optimal as $p\to\infty$ among guarantees uniform in $d$ and $T$. The algorithm uses a bounded radial regulariser and switches at most once to its quadratic augmentation. On some paths where follow-the-leader (FTL) has regret one, its regret grows with $T$. A switching extension keeps the sharp constant and also guarantees $\mathrm{Reg}_T\le 2\,\mathrm{Reg}_T^{\mathrm{FTL}}$. For i.i.d. losses whose mean has no zero coordinates, we compute the exact $\log T$ coefficient of the expected regret, which separates FTL's variance term from the bias of the regulariser.

0.24

The Exponential Price of Determinism in Nonsmooth Nonconvex Optimization

cs.LG math.OC ·2026-09-20 ·Guy Kornowski
theoryhighly cited similarity 0.64
Abstract · 13 pages

We study the complexity of finding $(δ,ε)$-Goldstein stationary points of nonsmooth nonconvex Lipschitz functions. By now, it is known that randomized first-order algorithms can solve this task with a dimension-free oracle complexity [Zhang et al., 2020], whereas deterministic algorithms cannot, as their complexity must scale at least linearly with the dimension $d$ [Jordan et al., 2023, Tian and So, 2024]. This leaves open whether deterministic algorithms can nevertheless solve the problem with oracle complexity polynomial in $d$. We answer this question negatively by proving a lower bound of order $(1/ε)^{Ω(d)}$ for deterministic algorithm, closing the exponential gap between the previously known lower and upper bounds and resolving an open problem posed by Jordan et al. [2023]. We further discuss several extensions and implications of this result to weaker stationarity notions, finding a descent direction and deterministic smoothing. Overall, our results establish an exponential computational advantage in nonsmooth nonconvex optimization offered by randomization.

0.54

Geometry-Dependent Online and Offline Approximation for Non-Monotone DR-Submodular Maximization

cs.LG ·2026-09-30 ·Vaneet Aggarwal, Yiyang Lu
theory similarity 0.62
Abstract

We study online and offline maximization of nonnegative, non-monotone DR-submodular functions over compact convex down-closed sets $K\subseteq[0,1]^d$ that contain a supplied diagonal point $ζ\mathbf{1}$. Our online algorithm earns at least $\underlineα(ζ)=\frac{1}{2}-\frac{(1-2ζ)_+^2}{2(3-2ζ)^2}$ times the reward of the best fixed feasible point, minus $O(\sqrt{T})$, using one possibly stochastic gradient query and one projection per round; $\underlineα(0)=4/9$. One post-decision noisy value query per round gives $O(T^{3/4})$ regret, and two exact value queries give $O(\sqrt{T})$. Conversely, no offline algorithm with polynomially many exact value-and-gradient queries attains a coefficient above an explicit $β_*\approx 0.4704$ at $ζ=0$, improving the bound $2(e^{-1/2}-e^{-1})\approx 0.478$ of Oveis Gharan and Vondrák (2011); for $ζ>0$, two families of hard instances give an upper bound that we reduce exactly to finitely many convex problems below $ζ=1/8$ and give in closed form above it. The bound $β_*$ also holds for nonnegative submodular set functions under a cardinality constraint, improving the previous $0.478$. Online-to-offline conversion gives $\underlineα(ζ)-\varepsilon$ offline, and the upper bound also limits online learners with polynomial query budgets and uniform $O(T^κ)$ regret, $κ<1$. Both coefficients equal $1/2$ for $ζ\ge 1/2$ and fall short of $1/2$ by order $(1/2-ζ)^2$ below. For quadratic objectives we attain $1/2$, and for cubic objectives $\max\{8/17,\,2\sqrt{3-4r}/(1+\sqrt{3-4r})^2\}$ with $r=\min\{ζ,1/2\}$. For submodular set functions, rounding the multilinear extension gives $\underlineα(ζ)-\varepsilon$ under a matroid whose polytope contains $ζ\mathbf{1}$ and $4/9-\varepsilon$ under a fixed number of knapsack constraints.

0.26

Lower Bounds for Linear-Oracle Online Learning

cs.LG stat.MLmath.OC ·2026-09-29 ·Mohit Sinha
theory similarity 0.62
Abstract

Can a constant number of linear minimizations per round improve on the $T^{3/4}$ regret rate of online Frank-Wolfe on general convex sets? Weibel et al. conjectured that fixed-coefficient methods cannot. We prove their conjecture and extend the lower bound to every deterministic learner in an oracle-only model. The learner receives an initial feasible point and a diameter bound, and must remain feasible on every domain consistent with its oracle replies. For $T$ rounds, at most $b$ calls between decisions, diameter bound $D$, and gradient norm bound $L$, we construct an instance in dimension $d=2b(T-1)+1$ with regret at least $2^{-1/4}LDb^{-1/4}T^{3/4}$. The adversary fixes the domain, initial point, deterministic tie rule and linear losses before play. The vertices form a path on which every point available before a decision has zero current loss, while the final vertex has negative loss on every round. For constant $b$, the result matches the known upper rate for dimension-independent guarantees. For one-call fixed schedules with a nonzero coefficient on the newest gradient, a second construction gives regret at least $3LDT^{3/4}/4$ with unique minimizers at every issued query. Exact-arithmetic certificates for the tuned schedule of Weibel et al. closely match their finite-horizon numerical worst cases, with unique oracle replies.

0.08