Online Convex Optimization

Overview

Online convex optimization studies how to choose actions sequentially as convex losses arrive, measuring performance against the best fixed or changing comparator in hindsight. Common methods include Online Mirror Descent, projected gradient descent, Follow-the-Regularized-Leader, and adaptive or optimistic variants; feedback may be full-information, bandit, delayed, or distributed. Constraints and changing feasible sets add costs such as cumulative violation, movement, communication, and computation, so algorithms often balance these against regret. Current work sharpens guarantees for dynamic comparators and problem-dependent conditions, while a central challenge is achieving optimal regret and feasibility with partial feedback and limited resources.

Latest papers

73 papers16 papers in the last four weeks, up 78% on the four weeks before. 0.1% of all new papers.

Nov 12, 2026

Adversarially Batched Online Learning

We introduce adversarially batched online learning, where the learner may update its decision rule only at a restricted set of time steps. Equivalently, the time horizon is partitioned into batches, within which the learner must use a fixed policy. We study this model for four canonical problems: stochastic bandits, online convex optimization, prediction with expert advice, and adversarial bandits. For stochastic bandits, we identify a universal complexity measure based on relative batch growth and establish both gap-dependent and gap-independent regret bounds. We show that the multiplicative penalty relative to the standard gap-dependent complexity can grow superlinearly in batch hardness. For the remaining three, we show that the optimal regret is tightly characterized by the 2-norm of the batch-length sequence. The upper bound is achieved by a batch-oblivious learner who does not know the batch structure, via a generic adaptive doubling trick tailored to this complexity measure. In contrast, the lower bound holds even for batch-aware learners.
Nov 9, 2026

KKT-Perturbation-Aware Communication for Fully Distributed Online Convex Optimization with Nonseparable Coupling

Nonseparable costs and coupled constraints in distributed online convex optimization often arise when system performance and operational constraints depend on the joint configuration of all agents and cannot be decomposed into individual contributions. Such nonseparability leads to fully distributed decision-making with challenging partial local information, where each agent evaluates its local primal-dual update using estimated global information via a local belief of the joint action and the shared Lagrange multiplier to be exchanged with neighbors. While the belief consensus established by prior works ensures no-regret learning, exchanging beliefs comprising full-dimensional primal and dual states at every round imposes a communication overhead that scales with both the joint decision dimension and the network size. Existing event-triggered schemes typically activate communication according to state variation or consensus error. Under nonseparable coupling, however, errors of equal magnitude can produce markedly different perturbations after passing through the KKT operator. We therefore propose a randomized KKT-perturbation-aware communication mechanism, where the triggering of each agent's primal and dual communication channels depends on their impact on the KKT operator. The proposed mechanism transfers the adaptive-sampling principle of coordinate descent from allocating computation across decision blocks to allocating communication across information channels: channels with larger estimated perturbations receive greater priority for refresh. Under standard regularity assumptions, the resulting algorithm achieves O(T2/3)O({T}^{2/3}) expected static regret and O(T2/3)O({T}^{2/3}) expected cumulative constraint violation. Numerical experiments demonstrate improved learning and constraint-enforcement performance per transmitted bit over belief consensus baselines.
Nov 5, 2026

Dynamic Optimistic Constrained OCO with Memory via Delay Equivalence

Online Convex Optimization with memory and time-varying constraints (COCO-M) is a recently-introduced framework that captures the dynamics of stateful online learning and non-stochastic control with budget constraints. Despite its expressive power, COCO-M remains largely understudied. In this work, we tackle this problem in its full scale, providing an optimistic algorithm that incorporates untrusted predictions to tame universal dynamic regret and cumulative constraint violation. Our analysis leverages a potent reduction from memory to delay and treats state-dependent gradients as delayed feedback. We establish the first bounds that adapt to both environment non-stationarity (path length PTP_T) and prediction accuracy, while lifting previous restrictive assumptions such as functional separability. En route to these results, we derive findings of independent interest for the memory-to-delay reduction, and for delayed OCO with time-varying constraints. The proposed framework ensures sublinear worst-case guarantees that improve with prediction accuracy, reaching O(1)\mathcal O(1) regret under perfect predictions, with cumulative constraint violation (CCV) O(T)\mathcal O(\sqrt{T}) for unknown PTP_T and O(log⁡T)\mathcal O(\log T) for known or online observable PTP_T , while recovering the optimal COCO rates when memory disappears.
Nov 5, 2026

Optimal Competitive Ratios for Chasing Convex Functions with Quadratic Growth

Chasing convex function has attracted much attention in recent years, which can be formulated as a game between a learner and an adversary. In each round, the adversary reveals a convex function, and the learner selects a decision and incurs a hitting cost and a movement cost for changing its decision. The performance of the learner is measured by the competitive ratio, which compares its cumulative cost with that of an optimal offline decision sequence. For Euclidean movement, existing upper and lower bounds for κκ-well-conditioned functions exhibit a polynomial gap. For squared Euclidean movement, dimension-free competitive guarantees have been established under quadratic growth, but the optimal competitive ratio remains unclear. In this paper, we establish optimal dimension-free competitive ratios for convex function chasing under two types of movement costs. For Euclidean movement, we propose Clipped Proximal Descent (CPD), which combines a balanced proximal step with a clipped correction toward the current minimizer. CPD achieves an O(κ1/3)O(κ^{1/3}) competitive ratio for smooth convex functions satisfying quadratic growth, improving the previous O(κ)O(\sqrtκ) upper bound and matching the existing Ω(κ1/3)Ω(κ^{1/3}) lower bound. For squared Euclidean movement, we establish the exact optimal dimension-free competitive ratio for convex functions satisfying quadratic growth. Our result is based on a new tight competitive analysis of Regularized Online Balanced Descent (R-OBD) and a matching lower bound against randomized algorithms.
Nov 2, 2026

Tilted Convexity and an Exact Offline-Online Separation

Convexity has three equivalent descriptions: support by affine functions, monotonicity of the subdifferential, and increasing secant slopes. We weaken all three by one distortion with parameter γ∈(0,1]γ\in(0,1], which multiplies positive changes by γγ and divides negative ones by γγ. The resulting classes are the convex functions at γ=1γ=1 and, for γ<1γ<1, are distinct and nested, with the parameter dropping by at most a square along the chain. For proper lower semicontinuous functions in these classes, the effective domain is convex, local minimizers are global, and the function is locally Lipschitz on the relative interior of its domain. The classes separate offline from online optimization over compact convex sets with efficient projection, with access to function values and bounded support vectors. A smooth member of any class can be minimized to additive accuracy ε\varepsilon with poly(1/ε)\mathrm{poly}(1/\varepsilon) first-order queries and projections. Online, with nonpositive losses and αα-regret measured against αα times the best fixed point, a polynomial-time algorithm achieves γγ-regret O(T)O(\sqrt T) on the largest class. For every fixed, effectively specified γ∈(0,1)γ\in(0,1) and every α∈(γ,1]α\in(γ,1], no randomized polynomial-time algorithm has sublinear expected αα-regret unless NP=RP\mathbf{NP}=\mathbf{RP}, already for smooth concave polynomial losses in the smallest class, each minimized by one linear optimization. Thus, unless NP=RP\mathbf{NP}=\mathbf{RP}, γγ is the exact online coefficient of each class, while the offline coefficient is one.
Nov 2, 2026

When Is Tracking Affordable? A Movement-Budget Feasibility Threshold for Dynamic Regret

Dynamic regret measures an online learner against a moving comparator, and standard analyses assume the learner may move freely at every round. We study what happens when it may not: the learner is given a hard budget SS on its total movement ∑t∥xt−xt−1∥\sum_t \|x_t - x_{t-1}\|. Our main result is that a movement budget creates a feasibility barrier. On a domain of diameter DD with GG-Lipschitz convex losses, for every comparator path length PT∈[D,DT]P_T \in [D, DT] we exhibit a deterministic adversary that forces Rd=Ω(GDT)R_d = Ω(GDT) on every budget-feasible algorithm whenever S≤cPTS \le c P_T for a universal constant c>0c>0. This barrier is caused by the budget rather than by a volatile environment: for fixed DD, it applies when PT=o(T)P_T = o(T), where the unconstrained minimax rate Θ(GD(D+PT)T)Θ(G\sqrt{D(D+P_T)T}) is sublinear, so the same instances are learnable with an unbounded budget and unlearnable without one. Conversely, projected online gradient descent with a budget-aware step size is budget-feasible and attains o(GDT)o(GDT) once S=ω(D+PT)S = ω(D + P_T). Thus the critical movement scale is D+PTD+P_T: linear regret is unavoidable below a sufficiently small constant multiple of PTP_T, while sublinear regret is achievable when S/(D+PT)→∞S/(D+P_T)\to\infty in the learnable regime. The construction rests on a distinction we make explicit: what makes a comparator expensive to track under a movement budget is the distance it forces the learner to travel, not its path length. Above the threshold we give a budget-dependent upper bound and identify the tight minimax rate in this region as an open problem rather than claiming a product law. Experiments support the predicted transition location and the 1/S1/S decay.
Oct 29, 2026

Conic-Lifting for Learning-rate-free Convex Optimization

A central topic in online and stochastic optimization is to design algorithms that do not require tuning of hyperparameters. Successful strategies in online learning include AdaGrad-style learning rates, Conic Blackwell algorithms, and parameter-free algorithms. However, these classes require different, often difficult, analyses. We develop a unifying family of Online Convex Optimization (OCO) algorithms that require no user-tuned learning rate on convex domains that may be unbounded. The construction lifts the domain to a cone by adding one scalar coordinate, an idea going back to Blackwell (1954). The lifted subgradients are orthogonal to the corresponding lifted decisions, leaving the comparator scale free to optimize in the regret analysis. Applying Follow-the-Regularized-Leader (FTRL) and Online Mirror Descent (OMD) on the cone recovers Conic Blackwell Algorithm (CBA) and Conic Blackwell Algorithm Plus (CBA+^+) on bounded domains in Hilbert spaces and extends them to finite-dimensional normed spaces with a strongly convex squared norm. For arbitrary nonempty closed convex domains in these spaces, a known gradient bound yields parameter-free regret guarantees. Surprisingly, on an unconstrained Hilbert space, the construction recovers the Krichevsky--Trofimov (KT) coin-betting algorithm exactly. We also give a parameter-free algorithm for unconstrained domains that requires no gradient bound.
Oct 29, 2026

Strongly Adaptive Online Learning Achieves Uniform Discounted Regret

Discounted regret measures the performance of an online learner by assigning exponentially decaying weights to past losses, reflecting the greater importance of recent losses in non-stationary online learning. While previous work obtains uniform discounted regret bounds over a continuous range of discount factors using a specialized meta-algorithm, its results are limited to convex functions. In this paper, we demonstrate that strongly adaptive regret bounds can directly imply uniform discounted regret guarantees for convex, strongly convex, and exp-concave loss functions. Our key observation is that discounted regret against a fixed comparator admits an exact decomposition into a convex combination of interval regrets. For convex functions, this reduction yields an O(log⁡T/(1−λ))O(\sqrt{\log T/(1-λ)}) discounted regret bound for all discount factors λ∈(0,1)λ\in(0,1), matching the previous rate over a broader range of discount factors. For strongly convex and exp-concave functions, we provide regret bounds of O(log⁡T(1+log⁡11−λ))O\left(\log T\left(1+\log\frac{1}{1-λ}\right)\right).
Oct 28, 2026

Optimal Regret for Communication-Efficient Decentralized Online Learning

In this paper, we investigate decentralized online convex optimization with compressed communication, where nn learners over a network jointly minimize a sequence of global loss functions based only on their local losses and compressed messages from their neighbors. The best known regret bounds for this problem are O(ω−1/2nρ−1Tln⁡n)O(ω^{-1/2}nρ^{-1}\sqrt{T\ln n}) and O(ω−1nρ−2ln⁡nln⁡T)O(ω^{-1}nρ^{-2}\ln n\ln T) for convex and strongly convex loss functions, respectively, where ρ∈(0,1)ρ\in(0,1) is the spectral gap of the communication matrix and ω∈(0,1]ω\in(0,1] is the compression quality factor. Compared with the corresponding lower bounds of Ω(ω−1/2nρ−1/4T)Ω(ω^{-1/2}nρ^{-1/4}\sqrt{T}) and Ω(ω−1nρ−1/2ln⁡T)Ω(ω^{-1}nρ^{-1/2}\ln T), these upper bounds exhibit polynomial gaps in their dependence on ρ−1ρ^{-1}. To close these gaps, we first develop Ascent-gossip, which combines an online compression strategy with a Chebyshev recursion and attains a faster consensus rate than existing compressed gossip methods. Furthermore, by adopting Ascent-gossip, we propose an online algorithm that achieves optimal regret bounds of O~(ω−1/2nρ−1/4T)\widetilde O(ω^{-1/2}nρ^{-1/4}\sqrt{T}) and O~(ω−1nρ−1/2ln⁡T)\widetilde O(ω^{-1}nρ^{-1/2}\ln T) for convex and strongly convex loss functions, respectively. Up to logarithmic factors in nn and ρ−1ρ^{-1}, these results match the lower bounds in terms of TT, nn, ρρ, and ωω.
Oct 27, 2026

An Ω(T3/4)Ω(T^{3/4}) lower bound for projection-free online learning with linear minimization oracles

This work considers projection-free online learning algorithms with linear minimization oracles for handling the decision set. For Online Frank--Wolfe (OFW), regret upper bounds were already known for specific OFW tunings [Hazan and Kale, 2012, Hazan, 2016] which scaled as T3/4T^{3/4} (where TT is the horizon length). However, it remained an open question whether the regret of all OFW tunings scaled as T3/4T^{3/4}. We answer that question, proving a universal worst-case regret lower bound Ω(T3/4m−1/4)Ω(T^{3/4} m^{-1/4}) for any projection-free algorithm that makes at most mm linear minimization oracle calls per round. The analysis suggests an extended OFW to resort to multiple linear optimizations per round, for which we prove a regret upper bound O(max⁡{T3/4m−1/4,T})O(\max \{ T^{3/4} m^{-1/4}, \sqrt{T} \}).
Oct 26, 2026

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

We study full-information online linear optimisation on the unit ℓp\ell_p ball in Rd\mathbb{R}^d, for fixed 2≤p<∞2\le p<\infty and losses of dual norm at most one. Let ΔTΔ_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 TT or ΔTΔ_T, regret Op(1+min⁡{ΔT1−1/p, d1/2−1/pΔT})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 pp, and its constant (2+o(1))p/log⁡p(2+o(1))p/\log p is optimal as p→∞p\to\infty among guarantees uniform in dd and TT. 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 TT. A switching extension keeps the sharp constant and also guarantees RegT≤2 RegTFTL\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\log T coefficient of the expected regret, which separates FTL's variance term from the bias of the regulariser.
Oct 23, 2026

Strongly Adaptive Online Learning with Time-Varying Movement Costs

We study online convex optimization (OCO) with time-varying movement costs, where the learner incurs both a loss and a time-dependent penalty for changing its decisions. While previous work has established dynamic regret guarantees for this setting, obtaining strongly adaptive guarantees that hold simultaneously over arbitrary intervals remains an open challenge. We address this by developing a new algorithm which, for every interval [a,b]⊆[T][a,b]\subseteq[T] and arbitrary comparator sequence, achieves a data-dependent regret bound of O~((D2+DP[a,b])∑t∈[a,b](∥gt∥2+λt∥gt∥))\widetilde{\mathcal{O}}\left( \sqrt{(D^2+DP_{[a,b]})\sum_{t \in [a,b]}(\|g_t\|^2+λ_t\|g_t\|)} \right), where DD is the diameter of the decision domain, P[a,b]P_{[a,b]} is the path length of the comparator sequence over [a,b][a,b], gtg_t is the gradient of the loss, and λtλ_t is the movement-cost coefficient at round~tt. Key to our approach is a novel reduction to sleeping experts with movement costs, a previously unexplored variant that is of independent interest. As a result of our development, we further obtain strongly-adaptive dynamic regret guarantees under arbitrary delayed feedback with a refined dependence on interval-restricted cumulative delays. Our approach also naturally extends to OCO with time-varying memory, where we obtain strongly-adaptive guarantees which improve the best-known bounds.
Oct 20, 2026

Universal Online Convex Optimization With Delayed Feedback

We study universal online convex optimization with delayed feedback. We develop a single algorithm that simultaneously adapts to general convex, strongly convex, and exp-concave losses without prior knowledge of the curvature class or parameters. Our regret bounds match the best known dependence on the time horizon TT and delays up to doubly logarithmic factors: roughly T+dtot\sqrt{T + d_{\mathrm{tot}}} for convex losses and σmax⁡log⁡Tσ_{\max}\log T rates with curved losses, where dtotd_{\mathrm{tot}} is the total cumulative delay and σmax⁡σ_{\max} is the maximum number of simultaneously missing observations. Our main technical contribution is a delayed meta-learner with a second-order excess-loss guarantee, which enables curvature-adaptive aggregation of delayed base learners. In addition, our new exp-concave base learner yields a sharper regret bound which improves the state-of-the-art delay dependence by replacing the maximum delay with the potentially much smaller σmax⁡σ_{\max}, while retaining the complementary dtot\sqrt{d_{\mathrm{tot}}} dependence.
Oct 18, 2026

Decentralized Online Exp-Concave Optimization

Decentralized Online Convex Optimization (D-OCO) is a fundamental framework in which a set of local agents aims to minimize a sequence of global loss functions using only local computations and communications. While recent work has established near-optimal regret guarantees for convex and strongly convex losses, the case of exp-concave losses remains an open challenge: specifically, whether logarithmic regret is achievable. In this paper, we answer this question affirmatively by proposing Decentralized Online Newton Step (D-ONS), which adapts the idea of blocking and accelerated gossip to the Online Newton Step algorithm in a non-trivial manner. Concretely, our algorithm achieves a regret bound of O(Nd(1−σ2)−1/2 log⁡2(T))O\left(Nd(1-σ_2)^{-1/2}\,\log^2(T) \right) where NN is the number of agents, dd is the dimension, TT is the horizon, and 1−σ21-σ_2 represents the spectral gap of the network. To our knowledge, this is the first logarithmic regret bound for decentralized online exp-concave optimization. We further establish a nearly matching lower bound of Ω(Nd(1−σ2)−1/2 log⁡(T/N))Ω\left(Nd (1-σ_2)^{-1/2}\,\log(T/N) \right) showing the near optimality of our upper bound. Finally, we extend our algorithm to decentralized online linear regression in which the feasible domain is unbounded and features and labels are locally observed. By gossiping covariance and label-feature statistics, we also achieve logarithmic regret.
Oct 17, 2026

Revisiting Smoothed Online Learning: Competitive Ratio, Dynamic Regret with Switching Cost, and Best of Both Worlds

We revisit smoothed online learning and develop algorithms with improved competitive ratios, optimal dynamic regret with switching cost, and best-of-both-worlds guarantees. Surprisingly, minimizing the hitting cost alone is max⁡(1,2α)\max(1,\frac{2}α)-competitive for αα-polyhedral functions under the ℓ2\ell_2-norm switching cost and 1+4λ1+\frac{4}λ-competitive for λλ-quadratic growth functions under the squared ℓ2\ell_2-norm switching cost, significantly improving existing guarantees. The polyhedral bound is tight for this naive algorithm, and we establish a matching lower bound for α≥1α\geq1. For convex λλ-quadratic growth hitting costs, minimizing a suitably weighted sum of hitting and squared ℓ2\ell_2-norm switching costs yields a competitive ratio of 1+2λ1+\frac{2}{\sqrtλ}. For dynamic regret with the ℓ2\ell_2-norm switching cost, we develop Smoothed Ader (SAder), which achieves the optimal O(T(1+PT))O(\sqrt{T(1+P_T)}) rate in the standard online convex optimization setting, where PTP_T is the comparator's path-length. Its lookahead version removes the bounded-gradient assumption, and a matching lower bound establishes optimality in this setting. Finally, for convex hitting costs on a bounded convex domain, we develop UDNP to aggregate any two experts in the lookahead setting under both switching costs. Its additional cumulative cost is at most O(1)O(1) relative to the first expert and O(Tlog⁡T)O(\sqrt{T\log T}) relative to the second, yielding best-of-both-worlds guarantees without bounded gradients.
Oct 14, 2026

Tracking a Small Set of Experts in Online Convex Optimization

For the fundamental problem of prediction from expert advice, Freund asked whether one could compete with a comparator that switches kk times among only mm experts. For a discrete set of experts, this problem was resolved by Bousquet and Warmuth (2020), who gave an efficient algorithm with optimal regret matching the information-theoretic limit. We study the analogous problem in online convex optimization, where the action space is continuous. An inefficient algorithm can be derived by discretizing the action space and applying the Bousquet--Warmuth algorithm, giving regret of O~(md+k)\widetilde{O}(md+k), while the best known efficient algorithm for this problem has regret O~(dk)\widetilde{O}(dk). We show that this computational inefficiency is inherent, establishing a separation between the information-theoretic and polynomial-time regret achievable for this problem. Specifically, under the hypergraphic planted-clique conjecture, we show that for every polynomial-time algorithm there exist instances for which it incurs at least (kd)1−o(1)(k\sqrt d)^{1-o(1)} regret.
Oct 14, 2026

Dimension-Optimal Dynamic Regret in Exp-Concave Online Learning

Tracking changing comparators is a central problem in online learning. For exp-concave losses, previous work established the T1/3PT2/3T^{1/3}P_T^{2/3} dependence on the horizon TT and Euclidean path length PTP_T for fixed dimension, while the optimal cost of dimension remained unresolved. We resolve this question by establishing a sharp d1/3d^{1/3} curved dimension factor, improving the d2/3d^{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 Rd\mathbb{R}^d that adapts to the unknown path length and, under fixed dimension-independent diameter, gradient, and curvature parameters, guarantees Reg⁡T(u1:T)≤O~(d+min⁡{d1/3T1/3PT2/3,TPT,T}).\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≳d2T\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⁡2T)O(\log^2 T) Gaussian states, uses one gradient per round, and runs in time near-linear in TT under a Mahalanobis-projection oracle.
Oct 12, 2026

Efficient Preconditioned Optimization Methods with Frequent Directions

Adaptive optimization methods have received considerable attention in recent years due to their strong empirical performance. However, they generally require maintaining a preconditioning matrix, which incurs prohibitive computational overhead in large-scale applications. To address these limitations, we investigate the acceleration of preconditioned optimization methods through frequent directions (FD), a widely used matrix sketching technique. We first propose FTSL by integrating FD with adaptive subgradient methods under the primal-dual framework and adding back the cumulative information discarded by FD. FTSL obtains a tighter regret bound than existing state-of-the-art results. We then apply a doubling trick that further reduces the time complexity of FTSL, while maintaining the same regret guarantee. We also consider optimization over matrix-valued decision variables and exploit their structural properties to construct sketched preconditioners. We develop FTSL-Shampoo by adapting FD to Shampoo and give a novel analysis under the primal-dual framework. To further mitigate its computational complexity, we design one-sided variants of FTSL-Shampoo under both mirror descent and primal-dual frameworks. Our algorithms not only reduce the computational cost of FTSL-Shampoo, but also achieve tighter regret bounds. We extend our methods to offline stochastic convex optimization and exploit smoothness to achieve faster convergence rates. Finally, we introduce practical variants of our algorithms and empirically demonstrate their efficiency and effectiveness across a broad range of tasks.
Oct 2, 2026

O~(T)\tilde{O}(\sqrt{T}) Regret and Polylogarithmic Constraint Violation for COCO

We study constrained online convex optimization with adversarial convex costs and constraints (COCO\mathsf{COCO}). At each round t∈[T]t\in[T], a learner selects xtx_t from a dd-dimensional convex decision set XX, after which an adaptive adversary reveals a convex cost function ftf_t and constraint function gtg_t. Consequently, the learner incurs a cost of ft(xt)f_t(x_t) and a constraint violation of max⁡{0,gt(xt)}\max\{0,g_t(x_t)\}, and aims to simultaneously minimize regret and cumulative constraint violation (CCV\mathsf{CCV}) over the entire horizon. Existing algorithms achieve O(T)O(\sqrt{T}) regret and O~(T)\widetilde O(\sqrt{T}) CCV\mathsf{CCV}. We show that an online policy can achieve O(Tlog⁡T)O(\sqrt{T\log T}) regret and O(log⁡2T)O(\log^2 T) CCV\mathsf{CCV}, reducing the CCV\mathsf{CCV} from polynomial to polylogarithmic while retaining near-optimal regret. When all cost functions are either αα-exp-concave or ββ-strongly convex, the algorithm achieves O(log⁡T)O(\log T) regret with the same CCV\mathsf{CCV} bound as above. Our approach combines continuous Hedge with elimination on shrinking feasible sets. The key observation is that whenever the mean of the Hedge distribution violates a constraint, Grünbaum's inequality guarantees that a constant fraction of the Hedge probability mass is eliminated. We use an adaptive learning-rate schedule and a potential function coupling the surviving volume with the learning rate to convert this probability-mass reduction into a bound of O(log⁡2T)O(\log^2 T) on the CCV\mathsf{CCV}.
Sep 30, 2026

Parameter-Free Interval-Dynamic Regret under Heavy-Tailed Noise

We study online convex optimization with one unbiased stochastic subgradient per round and an unknown finite conditional ppth noise moment, 1<p≤21<p\le2. For every fixed interval II of length nn and comparator path with ΛI=1+PI/DΛ_I=1+P_I/D, one learner achieves E[RegretI(u)]≤min⁡(GDn,C[GDn(ΛI+log⁡2(2T))+σDn1/p(ΛI+log⁡2(2T))(p−1)/p]).E[Regret_I(u)]\le\min(GDn, C[GD\sqrt{n(Λ_I+\log^2(2T))} +σDn^{1/p}(Λ_I+\log^2(2T))^{(p-1)/p}]). The learner uses none of G,σ,p,I,PIG,σ,p,I,P_I, and the constant is universal. Interval adaptation adds to comparator complexity, preserving the distinct mean-gradient and noise exponents. The analysis controls calibration in expectation and limits the cost of observation-scale changes. Its general theorem compares to distributions over predictably available experts with relative-entropy dependence on a nonuniform prior. A common prior favors long windows and long restart lengths. With the statistics supplied, the interval cost becomes 1+log⁡(T/n)1+\log(T/n), including the optimal full-horizon static rate. A change-of-measure lower bound identifies the noise power of this logarithm for learners retaining a full-horizon optimal guarantee, under explicit conditions. Static comparisons and deterministic partitions follow from the same decisions.
Sep 29, 2026

Lower Bounds for Linear-Oracle Online Learning

Can a constant number of linear minimizations per round improve on the T3/4T^{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 TT rounds, at most bb calls between decisions, diameter bound DD, and gradient norm bound LL, we construct an instance in dimension d=2b(T−1)+1d=2b(T-1)+1 with regret at least 2−1/4LDb−1/4T3/42^{-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 bb, 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 3LDT3/4/43LDT^{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.
Sep 28, 2026

Universal Dynamic Portfolios

Cover's Universal Portfolio (Cover, 1991) matches the performance of the best constant rebalanced portfolio in hindsight. We generalize this framework to compete with an arbitrary comparator sequence u1,…,uT\mathbf{u}_1,\ldots,\mathbf{u}_T, leading to a dynamic regret minimization problem for the log loss where existing methods break down due to potentially unbounded gradients. The log loss is exp-concave, a curvature property that classically yields fast rates for static regret, yet we show that this advantage generally disappears in the dynamic setting. In particular, a linear-loss-type TPT\sqrt{TP_T} dependence is unavoidable, where PT=∑t=2T∥ut−ut−1∥1P_T=\sum_{t=2}^T\lVert\mathbf{u}_t-\mathbf{u}_{t-1}\rVert_1 is the standard path length. This limitation stems from the coarse nature of PTP_T, which obscures finer spatial and temporal structure of the comparator sequence. We therefore introduce two structure-aware measures---the Jensen-Shannon distance for spatial structure and the JSq^q-path length for temporal structure---under which faster rates are attainable when the comparator sequence has favorable structure. To achieve sharp bounds for both measures simultaneously, we develop Universal Dynamic Portfolio, a parameter-free method that combines a new Dirichlet Hedge algorithm with a fixed-share update, while retaining a near-optimal PTP_T guarantee in the worst case. Finally, under an additional bounded-gradient assumption, we show that OPS admits the faster T1/3PT2/3T^{1/3}P_T^{2/3} dynamic regret rate over all comparator sequences. We attain this rate with a tractable proper algorithm that applies more broadly to general online exp-concave optimization over arbitrary compact convex domains.
Sep 28, 2026

On the Relation Between Interval Regret and Dynamic Regret

Non-stationary online learning has attracted much attention in recent years, as static regret is insufficient to guide algorithm design in changing environments. To address this limitation, interval regret and dynamic regret have been introduced as two representative performance metrics that strengthen static regret in complementary directions. Interval regret requires an online algorithm to achieve competitive static regret over every local time interval, whereas dynamic regret evaluates performance against an arbitrary sequence of time-varying comparators. Despite their importance, the relation between these metrics has long remained unclear. Prior work has often regarded interval regret as the stronger notion, based on the intuition that local guarantees should naturally induce global guarantees. Consequently, it is widely conjectured that an algorithm with optimal interval regret should automatically attain optimal dynamic regret. In this paper, we first establish a negative result that refutes this intuition of a metric-level implication. Specifically, for both convex and curved functions (including exp-concave and strongly convex functions), we show that there exist instances in which an algorithm with optimal interval regret nevertheless fails to achieve optimal dynamic regret. We then show how to leverage local adaptivity to obtain optimal dynamic regret. In particular, optimal dynamic regret can be attained by invoking an interval regret minimization process over an enlarged Euclidean ball containing the original convex feasible domain and using a suitable domain-converted surrogate loss. This reduction applies to both convex and curved functions. As a byproduct, we obtain the first proper and efficient algorithm with optimal dynamic regret for exp-concave functions, improving prior results while significantly simplifying the analysis.
Sep 24, 2026

Dynamic Regret in Online Convex Optimization with Indicator Switching Costs

We study dynamic regret in online convex optimization with an indicator switching cost: a fixed penalty incurred whenever two consecutive decisions differ. This captures startup overheads such as server activation, model deployment, and cache updates, and on a bounded domain it recovers norm-based movement costs as a special case. Existing guarantees for indicator costs handle only static comparators. We show that a direct extension of these techniques to dynamic regret provably fails, motivating a different approach. We propose a meta-learning framework: a set of randomized lazy FTRL base learners restarted at dyadic time scales, aggregated by a movement-aware master that mixes their proposal densities and samples actions via maximal coupling of consecutive mixtures. The resulting algorithm satisfies, in expectation, RT1≤O~(min⁡{T(ST+1),T2/3(PT+1)1/3})\mathcal{R}^{\mathbf{1}}_T \le \tilde{\mathcal{O}}(\min\{\sqrt{T(S_T{+}1)},T^{2/3}(P_T+1)^{1/3}\}), where RT1\mathcal{R}^{\mathbf{1}}_T is the dynamic regret plus the cumulative indicator switching cost, STS_T counts comparator switches, and PTP_T is the comparator path length. The bound holds simultaneously for all sequences and requires no prior knowledge of STS_T or PTP_T: it is minimax-optimal (up to logarithmic factors) for tracking piecewise-constant comparators, and also captures frequently moving comparators with small total path length.
Sep 23, 2026

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

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 GG-Lipschitz losses, diameter at most DD, a total allowance of QQ oracle calls, and a strict limit of BB calls per round, the dimension-free minimax expected regret is Θ(GDmax⁡{T,T/(1+min⁡{Q,BT})1/4})Θ(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 T3/4T^{3/4} rate with one call per round and the quadratic total budget needed for T\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.
Sep 23, 2026

Resource-Adaptive Stochastic Gradient Descent for Online Linear Programming without Re-solving

The growth of large language model (LLM) inference and search services increases the scale of online linear programming problems, motivating computationally efficient algorithms. We develop resource-adaptive stochastic gradient descent (RASGD) for stochastic online linear programming. The algorithm uses one request and current inventory to update resource prices, requiring O(m) operations for m resources and memory per arrival and no LP or sample-average optimization. The central idea is to express the current-resource pricing logic of re-solving through a first-order SGD update: each arrival refreshes the remaining-inventory allowance in the dual objective, while the stepsize decreases for early learning and increases later to match the speed of inventory adjustment. Under standard non-degeneracy conditions, our algorithm is feasible on every sample path and achieves O(\log T) expected regret against the realized fractional hindsight optimum, which matches the lower bound, even for policies that know the distribution and have unrestricted computation. The analysis converts curvature around the fixed reference price into inventory stability without tracking optimal prices at changing resource levels. Numerical experiments show that RASGD achieves regret competitive with per-arrival LP re-solving and improves upon the tested first-order baselines, while retaining the computational efficiency of first-order methods. These results establish RASGD as a computationally efficient approach to achieving high allocation quality in large-scale OLP.
Sep 17, 2026

From Switching to Dynamic Regret: A Simple Reduction via Unbiased Random Sequences

In non-stationary online learning, dynamic regret has attracted increasing attention as a measure of how well an online learner performs against a time-varying comparator sequence. Despite considerable advances, attaining optimal bounds for strongly convex and exp-concave losses often involves intricate analysis. In this paper, we present a simple framework that reduces dynamic regret minimization to switching regret minimization. As a result, we can derive dynamic regret bounds by using off-the-shelf algorithms with switching regret guarantees. The key idea of our reduction is to construct, for any comparator sequence, an auxiliary random sequence that is unbiased at each round, with the controlled variance and a manageable number of switches. Combining this construction with suitable surrogate losses, we can decompose dynamic regret into the expected switching regret against the random sequence and its controlled variance. Theoretically, for strongly convex and exp-concave losses, we establish the O~(T1/3PT2/3)\widetilde{O}(T^{1/3}P_T^{2/3}) dynamic regret bounds, where TT denotes the time horizon and PTP_T denotes the path-length of the comparator sequence. Moreover, for general convex losses, the same reduction also recovers the O(T(1+PT))O(\sqrt{T(1+P_T)}) dynamic regret bound. Notably, all our findings match the minimax optimal results for these three types of losses, highlighting the versatility of our proposed framework.
Sep 12, 2026

Curvature-Independent Regret Bounds for Distributed Online Optimization on Hadamard Manifolds

This work addresses decentralized online Riemannian optimization on Hadamard manifolds. Prior work under geodesic convexity (g-convexity) may require curvature information in the optimization analysis, typically through a finite lower bound on the sectional curvature. Curvature may also enter the step size or contraction factor of tangent-space Riemannian consensus schemes. In this work, we relax the curvature dependence for a narrower class of horospherical convex (h-convex) functions. We study Distributed Riemannian Online Gradient Descent (D-ROGD), which combines local Riemannian h-subgradient updates with an implicit Fréchet-mean consensus. For h-convex and strongly h-convex local objectives, we establish O(T)O(\sqrt{T}) and O(log⁡T)O(\log T) static regret, respectively, matching the corresponding Euclidean rates with respect to TT, with network dependence governed solely by the spectral gap. To our knowledge, these are the first curvature-independent regret guarantees for decentralized online optimization on Hadamard manifolds. Experiments on hyperbolic embeddings corroborate the predicted rates, with no observable degradation due to curvature.
Sep 10, 2026

Convex Optimization with Nested Evolving Feasible Sets (CONES) under Time-Varying Loss Functions

Convex Optimization with Nested Evolving Feasible Sets (CONES)} was introduced in \cite{CONESVaze} where the objective function ff remains fixed but the feasible region evolves over time as a nested sequence S1⊇S2⊇⋯⊇STS_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 M\cA(T)M_\cA(T) while ensuring feasibility at all times. CONES is an optimization-oriented generalization of the well-known nested convex body chasing (NCBC). In this paper, we extend CONES to allow for loss functions ft′f_t's to also change over time. When all loss functions are convex, we show that the projected proximal algorithm achieves O(T1−β),O(Tβ)O(T^{1-β}), O(T^β) simultaneous regret and movement cost, respectively, for any β∈[0,1)β\in [0,1), over a time horizon of TT. We also show that any {\it weakly adaptive} online algorithm with O(Tβ)O(T^β) regret has a movement cost of Ω(T1−β2)Ω\left(T^{\frac{1-β}{2}}\right) for any β∈[0,1)β\in [0,1). When all loss functions are strongly convex, we show that the projected proximal algorithm simultaneously achieves O(1)O(1) regret and a movement cost of O(log⁡T)O(\log T). To complement this, we show that any online algorithm with sublinear {\it anytime} regret has a movement cost of Ω(log⁡T)Ω\left(\log T\right).
Sep 7, 2026

Constrained Online Learning with Noisy Constraint Values

We study constrained online convex optimization with adversarial constraints and conditionally unbiased, finite-variance observations of constraint values and gradients. Under common feasibility, our \LEDGER\ algorithm attains O(T)O(\sqrt T) expected regret and O(Tlog⁡(eT))O(\sqrt{T\log(eT)}) expected budget violation, the largest cumulative overspend over any window. It uses a reflected exponential potential, clipped signed observations, and predictable adaptive regularization, with one feedback triple and one projection per round. Neither a Slater condition, independence between feedback channels, nor an absolute constraint-value bound is needed. A Gaussian testing lower bound proves that the budget rate has optimal horizon dependence under square-root regret at fixed positive noise, including the logarithm. The same obstruction holds for terminal violation, so the logarithm is not a cost of maximizing over windows; an O(T)O(\sqrt T) budget bound instead forces linear regret. In contrast, fixed positive Gaussian value noise yields a joint regret--hard-violation lower bound of Ω(min⁡{σ,1}T/log⁡2T)Ω(\min\{σ,1\}T/\log^2 T), even with exact gradients in one dimension. The hard-violation construction matches arbitrarily many moments while preserving a feasible-endpoint gap and constant endpoint probabilities. Together, the bounds separate uncertainty about hard feasibility from learnable signed budgets. Deterministic restarts remove the horizon input without changing either upper rate.