CS Paper Radar

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

Jack J. Mayo

cs.LG math.OCstat.ML ·submitted 2026-10-26 18:15 UTC · v1

Abstract

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.

Comment
49 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Minimax Alternating Regret for the Experts Problem and Online Convex Optimization

cs.LG stat.ML ·2026-08-25 ·Mengxiao Zhang
theory similarity 0.70
Abstract

In this paper, we study alternating regret in online convex optimization (OCO), motivated by the success of alternating learning dynamics in two-player games. Although previous works have shown that $o(\sqrt{T})$ alternating regret is achievable under various assumptions on the loss functions and feasible domains, the minimax regret rate has remained open even for the expert problem. In this paper, we resolve this question by showing matching lower and upper bounds for both the expert problem and general OCO. Somewhat surprisingly, for the $d$-expert problem, we show that the minimax alternating regret is $Θ(\log d)$ by providing both a lower bound and an algorithm achieving a matching upper bound. This significantly improves upon the $O(T^{1/3}\log^{2/3} d)$ established by [HLLZ25]. We further extend our results to general OCO over a $d$-dimensional compact convex set and prove that the worst-case minimax alternating regret is $Θ\left(d\log \left(1+\frac{T}{d}\right)\right)$, also significantly improving upon the $O((d\log T)^{2/3}T^{1/3})$ upper bound and resolving the open problem posed by [CCK+23,HLLZ25]. As a direct implication, our alternating dynamics achieve $O(\frac{\log d}{T})$ convergence to Nash equilibrium in two-player zero-sum games, matching the state of the art, and give the first such convergence rate to coarse correlated equilibrium in two-player general-sum games. Technically, our upper bound for the expert problem is achieved by a corrected variant of Hedge. We extend the same corrected-potential argument to continuous action sets to obtain the optimal alternating-regret rate for OCO. For the lower bounds, the construction for the expert problem repeatedly eliminates half of the candidate experts, while the OCO lower bound instance construction replaces this discrete elimination by a more involved multiscale construction on the unit disk.

0.26

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

cs.LG ·2026-09-23 ·Vaneet Aggarwal
theory similarity 0.69
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

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

A Linear Lower Bound for Convex Body Chasing in Every Norm

cs.DS cs.CGmath.MG ·2026-10-23 ·Nicolas Christianson
theory similarity 0.67
Abstract · Updates the previous version to extend the lower bound to all norms

We establish an $Ω(d)$ lower bound on the competitive ratio of convex body chasing in $\mathbb{R}^d$ with movement costs measured in any norm. Previously, the best known lower bound valid across all norms was $Ω(d^{1/6})$, established by Papazov (2023); stronger lower bounds were known for $\ell_p$ norms, where Bubeck, Klartag, Lee, Li, and Sellke (2019) had established a lower bound of $Ω(\max\{\sqrt{d}, d^{1-1/p}\})$. In particular, a linear lower bound was known only for the $\ell_\infty$ norm, realized by the standard construction of chasing faces of a hypercube. Our lower bound strictly improves on the prior universal and $\ell_p$ lower bounds for $p < \infty$ and shows that the functional Steiner point algorithm of Sellke (2023) - which has competitive ratio $O(d)$ - is asymptotically optimal for every norm. Our approach is based on the recursive construction of Bubeck, Coester, and Rabani (2023) for metrical service systems, which gives a lower bound of $Ω(r^2)$ for requests of size $O(r)$. We show that requests in their construction, each comprising a set of discrete points in a graph metric, can be mapped to the vertices of convex requests in a $(2r+1)$-dimensional $\ell_p$ vector space while approximately preserving movement costs up to a factor of $O(r)$; the general result then follows via Milman's (1985) quotient-of-a-subspace theorem.

0.29

Dimension-Optimal Dynamic Regret in Exp-Concave Online Learning

cs.LG math.OC ·2026-10-14 ·Yanyi Li, Wendao Wu, Haihan Zhang, Qinshi Wang, Chenheng Zhang +4 more
theory similarity 0.67
Abstract

Tracking changing comparators is a central problem in online learning. For exp-concave losses, previous work established the $T^{1/3}P_T^{2/3}$ dependence on the horizon $T$ and Euclidean path length $P_T$ for fixed dimension, while the optimal cost of dimension remained unresolved. We resolve this question by establishing a sharp $d^{1/3}$ curved dimension factor, improving the $d^{2/3}$ factor of recent switching and interval reductions [1, 2]. To achieve this improvement, we develop a proper, full-information learner on compact convex subsets of $\mathbb{R}^d$ that adapts to the unknown path length and, under fixed dimension-independent diameter, gradient, and curvature parameters, guarantees $$\operatorname{Reg}_T(u_{1:T}) \le \widetilde{O}\left(d+\min\left\{d^{1/3}T^{1/3}P_T^{2/3},\sqrt{TP_T},T\right\}\right).$$ A matching lower bound on a diameter-one Euclidean ball establishes the minimax frontier up to logarithmic factors when $T\gtrsim d^2$, including the transition from the curved rate to larger path budgets. The lower bound already holds for losses that depend on only one coordinate per round, isolating an unavoidable cost of learning across directions. Our upper bound follows from square-root Gaussian KL control of comparator movement and a cancellation argument that pays for history restarts. The curved learner maintains $O(\log^2 T)$ Gaussian states, uses one gradient per round, and runs in time near-linear in $T$ under a Mahalanobis-projection oracle.

0.14

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

cs.LG ·2026-09-30 ·Vaneet Aggarwal, Yiyang Lu
theory similarity 0.67
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

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

Optimal Alternating Regret for Online Learning and Games

cs.LG cs.GTstat.ML ·2026-08-25 ·Yixin Tao, Weiqiang Zheng
theoryhighly cited similarity 0.66
Abstract · 21 pages

We settle the minimax-optimal alternating regret, a regret notion motivated by alternating learning dynamics in games, for both online linear optimization (OLO) and online convex optimization (OCO). For OLO over the probability simplex $Δ_d$, we give an algorithm with $O(\log d)$ alternating regret that remains a constant for any time horizon $T$, and a matching lower bound. Our constant regret bound significantly improves previous results with $O(\log ^{2/3}d \cdot T^{1/3})$ regret [Cevher, Cutkosky, Kavis, Piliouras, Skoulakis, Viano, NeurIPS 2023, Hait, Li, Luo, Zhang, COLT 2025]. As a result, we obtain alternating learning dynamics with $O(\log d /T)$ convergence to Nash equilibria in two-player zero-sum games and $O(\log d /T)$ convergence to coarse correlated equilibria in two-player general-sum games. This is the first uncoupled learning dynamics with $O(1/T)$ convergence to CCE in two-player general-sum games, while all prior works suffer additional $\log T$ factors. For general OCO over a $d$-dimensional compact convex set, we give an algorithm with $O(d\log (1+T/d))$ alternating regret, improving the previous best of $\widetilde{O}(d^{2/3}T^{1/3})$. We also prove a matching lower bound of $Ω(d\log (1+T/d))$, showing that the $Ω(\log T)$ factor is unavoidable.

0.32