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.

Aug 29, 2026

Nested Convex-Body Chasing for Online Optimization with Evolving Feasible Sets

We study online optimization with nested shrinking feasible regions in two settings: convex optimization with nested evolving feasible sets (CONES) and adversarial constrained online convex optimization (COCO). Our algorithms separate loss control from geometric movement: constrained minimizers and cumulative-loss tests preserve regret guarantees, while a deterministic resettable nested convex-body chaser limits movement. For CONES with a GG-Lipschitz, μμ-strongly convex objective on a diameter-DD domain, we chase intersections of the current feasible set with adaptive objective sublevel sets. Using the Euclidean chasing ratio O(dlog⁡(1+d))O(\sqrt{d\log(1+d)}), we obtain nonpositive regret at every prefix and movement O(dlog⁡(1+d) GDlog⁡(eT)/μ)O(\sqrt{d\log(1+d)\,GD\log(eT)/μ}). The bound adapts to the increase in the constrained optimum value. In dimension two, with all other parameters fixed, every randomized algorithm with terminal expected regret O(Tβ)O(T^β), β<1β<1, suffers Ω(log⁡T)Ω(\sqrt{\log T}) expected movement on some deterministic nested sequence, proving optimal horizon dependence. Under linear growth away from the constrained minimizer set, Steiner-point tracking yields movement independent of TT. For general convex COCO, one-step-delayed chasing with regularized-leader resets gives regret O(GfDdlog⁡(1+d)T)O(G_fD\sqrt{d\log(1+d)T}) and cumulative constraint violation O(GgDdlog⁡(1+d)T)O(G_gD\sqrt{d\log(1+d)T}). For strongly convex losses, both are O(dlog⁡(1+d)log⁡(eT))O(d\log(1+d)\log(eT)) when other parameters are fixed. These reductions replace the O(dd/2)O(d^{d/2}) projection-path factor in prior analyses by the polynomial dimension dependence of Euclidean nested convex-body chasing.
Aug 25, 2026

Minimax Alternating Regret for the Experts Problem and Online Convex Optimization

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(T)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 dd-expert problem, we show that the minimax alternating regret is Θ(log⁡d)Θ(\log d) by providing both a lower bound and an algorithm achieving a matching upper bound. This significantly improves upon the O(T1/3log⁡2/3d)O(T^{1/3}\log^{2/3} d) established by [HLLZ25]. We further extend our results to general OCO over a dd-dimensional compact convex set and prove that the worst-case minimax alternating regret is Θ(dlog⁡(1+Td))Θ\left(d\log \left(1+\frac{T}{d}\right)\right), also significantly improving upon the O((dlog⁡T)2/3T1/3)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(log⁡dT)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.
Aug 25, 2026

Optimal Alternating Regret for Online Learning and Games

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Δ_d, we give an algorithm with O(log⁡d)O(\log d) alternating regret that remains a constant for any time horizon TT, and a matching lower bound. Our constant regret bound significantly improves previous results with O(log⁡2/3d⋅T1/3)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)O(\log d /T) convergence to Nash equilibria in two-player zero-sum games and O(log⁡d/T)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)O(1/T) convergence to CCE in two-player general-sum games, while all prior works suffer additional log⁡T\log T factors. For general OCO over a dd-dimensional compact convex set, we give an algorithm with O(dlog⁡(1+T/d))O(d\log (1+T/d)) alternating regret, improving the previous best of O~(d2/3T1/3)\widetilde{O}(d^{2/3}T^{1/3}). We also prove a matching lower bound of Ω(dlog⁡(1+T/d))Ω(d\log (1+T/d)), showing that the Ω(log⁡T)Ω(\log T) factor is unavoidable.
Aug 15, 2026

Online Convex Optimization with Dueling Feedback

Noisy binary comparison between two candidates is a common interface between human and learning systems, especially in modern large language model (LLM) post-training alignment. We study online convex optimization with dueling (pairwise comparison) feedback, where the learner observes only a binary preference between two queried points. We consider adversarial sequences of convex losses and measure regret with the loss at both queried points, under a comparison link with a known nonzero slope at the origin. We propose a simple reduction that converts dueling feedback into approximate gradients, enabling the use of standard first-order methods. We show that regret guarantees transfer under this reduction, yielding O(T3/4)\mathcal O(T^{3/4}) static and adaptive regret, and O(T3/41+PT/D)\mathcal O(T^{3/4}\sqrt{1+P_T/D}) dynamic regret with unknown comparator path length PTP_T. For strongly convex losses, the static and adaptive bounds improve to O~(T2/3)\widetilde{\mathcal O}(T^{2/3}). For smooth losses, we presents unified dueling ellipsoidal FTRL, and proves O~(T2/3)\widetilde{\mathcal O}(T^{2/3}) static regret, which improves to O~(T)\widetilde{\mathcal O}(\sqrt T) under additional strong convexity.
Aug 10, 2026

Distributed Optimization with Streaming Data: A Temporal Weighting Perspective

Optimization theory is a widely used tool for intelligent decision-making. While classical optimization deals with fixed, time-invariant objective functions, many modern applications operate in dynamic environments where data arrive sequentially, and the learning objective evolves over time, often under decentralized data and communication constraints. Motivated by these trends, we study decentralized optimization from streaming data through a structured time-varying formulation in which the global objective is a temporally weighted average of losses observed across the network. We analyze multi-iteration decentralized first-order methods, including decentralized gradient descent. For strongly convex and smooth losses, we develop guarantees for the Euclidean-norm tracking error through a contraction-mapping viewpoint. The resulting bounds decompose the tracking error into a fixed-point tracking component and a bias term induced by decentralization and data heterogeneity. We specialize our analysis to uniform and exponentially discounted weights, as well as their finite-memory windowed counterparts. The bounds explicitly characterize the roles of the temporal weighting rule, per-step iteration budget, step size, and network connectivity. Uniform weighting yields a vanishing fixed-point tracking contribution of order O(1/t)\mathcal O(1/t), whereas discounted and windowed strategies generally induce non-vanishing tracking floors governed by the discount factor and effective memory, respectively. In all cases, decentralization induces an additional non-zero bias floor under a constant step size. Numerical experiments illustrate the predicted trends.
Aug 3, 2026

Sharp Root Anti-Concentration via Projective Incidence and Ordered Root Laws

This paper answers the one-dimensional local root anti-concentration questions posed by Balcan, Pegden, and Sharma in the context of online optimization of piecewise-Lipschitz functions. For a homogeneous feature curve and coefficients whose density relative to the uniform law on a symmetric convex body KK is bounded by AA, we show that the worst-case interval-hitting constant equals AA times a section-averaged projective incidence speed. For cube-supported coefficients, this speed is equivalent, up to universal constants, to the projective Lipschitz constant. This yields a sharp, dimension-free characterization and removes the previous N\sqrt N loss. For monic degree-dd polynomials under arbitrary coefficient laws, we prove that the interval-hitting constant is finite if and only if the ordered real-root laws have bounded densities, with a factor-dd comparison that is sharp. Conditional and joint coefficient-space area formulas, together with a two-chart certificate, make this criterion verifiable for dependent and singular coefficient laws. We also give two graph-learning applications that complete the transition-to-regret chain. A cost-sensitive Gaussian-RBF harmonic classifier uses the projective incidence theorem and achieves expected regret O~((An2DeBD/ℓ+1)T)\widetilde O((An^2D e^{BD}/\ell+1)\sqrt T). A common-offset polynomial-kernel model uses rigid translation of the ordered roots and achieves O~((qn2κ+1)T)\widetilde O((qn^2κ+1)\sqrt T) regret, even when the induced coefficient law is singular in the ambient coefficient space.
Jul 30, 2026

Real-Time Hard Peak Age-of-Information Safety with No-Regret Learning

Safety-critical IoT systems such as industrial closed-loop control, V2X coordination, and remote teleoperation require every sensor's peak Age of Information (peak AoI, also abbreviated PAoI) to stay below a hard per-slot deadline, not merely an average bound. Existing approaches meet this requirement only under restrictive assumptions: stochastic channels for Whittle-index AoI, simulator rollouts for deep reinforcement learning, or sublinear cumulative violation for long-term constrained online convex optimization. Under adversarial coefficients, OCO-PAoI-Hard guarantees zero per-slot violation of the modeled AoI state under one-step viability and O(sqrt(T)) regret against any static safe comparator; packet-level safety requires stronger service assumptions. Our key observation is that the fractional peak-AoI deadline collapses exactly to an affine half-space constraint on the resource-allocation vector, turning hard real-time scheduling into time-varying constrained online convex optimization over a polyhedral safe set. A strictly causal proposal-shield-update loop enforces feasibility through one Euclidean projection per slot, the gradient step preserves no-regret behavior, and the classical virtual queue is reduced to an a-posteriori certificate. We establish closed-form static and dynamic regret bounds, a matching Omega(sqrt(T)) minimax lower bound, a margin-safe variant against execution noise, and a deadline-induced competitive ratio. On a four-sensor adversarial fluid-model trap channel, OCO-PAoI-Hard attains zero modeled-state deadline violations across all ten seeds, while four representative baselines miss between 1.65 percent and 64.0 percent of slots, and the empirical normalized regret stays below the theoretical envelope across two orders of magnitude in T.
Jul 29, 2026

Parameter-Free Dynamic Regret under Heavy-Tailed Noise

We study online convex optimization with one unbiased stochastic subgradient per round and noise having a finite pp-th central moment, where p∈(1,2]p\in(1,2] is unknown. For a bounded convex domain of diameter DD, subgradients bounded by GG, noise scale σσ, and comparator path length PTP_T, let ΛT=1+PT/DΛ_T=1+P_T/D. A single algorithm, using none of G,σ,p,PTG,σ,p,P_T, attains expected dynamic regret Op(min⁡{GDTΛT+σDT1/pΛT(p−1)/p, GDT})O_p\left(\min\{GD\sqrt{TΛ_T}+σDT^{1/p}Λ_T^{(p-1)/p},\,GDT\}\right) against every fixed comparator sequence. Restarted AdaGrad experts produce the noise-path exponent (p−1)/p(p-1)/p, and a prior favoring longer restart intervals removes horizon-dependent logarithmic overhead. We give an explicit bound uniform in pp; its logarithm-free form has noise coefficient O(1+log⁡(p/(p−1)))O(1+\log(p/(p-1))), while the static-regret constant is universal. The analysis requires only marginal noise moments and permits dependent errors. Complete pathwise proofs retain both the expert-loss range and the gradient energies preceding comparator movement. Matching lower bounds hold on every bounded convex domain of positive diameter, under the same gradient-only information model. Together with a path-budget-tuned upper bound, they characterize the minimax rate with universal constants, including its linear-regret saturation.
Jul 28, 2026

Data-Dependent Regret and Polyak Corrections for Constrained Online Convex Optimization

Constrained online convex optimization requires minimizing regret against adversarial convex costs while satisfying a convex constraint at every round, as needed in safety-critical applications. A computationally efficient method combines online gradient descent with a Polyak feasibility step, using one constraint evaluation and one subgradient per round. Although this method achieves O(sqrt(T)) regret with per-round feasibility, we derive a tighter, data-dependent analysis by retaining two quantities omitted by the standard worst-case argument. First, we replace the gradient envelope G_f^2 T with the observed accumulation G_T = sum_t ||grad f_t(x_t)||^2. Second, we identify a nonnegative Polyak correction P_T that measures the cumulative squared displacement caused by feasibility projections and enters the regret bound with a negative sign. The resulting improvement, Delta_T = (eta/2)(G_f^2 T - G_T) + P_T/(2 eta), is always nonnegative. We further propose AdaOGD-PFS, an adaptive-step-size method that achieves O(sqrt(G_T)) regret while preserving per-round feasibility. Experiments on ball- and halfspace-constrained problems improve the regret bound by 38 to 43 percent, with both data-dependent gradients and Polyak corrections contributing substantially.
Jul 22, 2026

Decentralized Online Riemannian Optimization for Strongly Geodesically Convex Functions

We study decentralized online optimization for strongly geodesically convex (strongly g-convex) losses on Riemannian manifolds with bounded sectional curvature, including positively curved manifolds. In centralized Riemannian optimization, strong g-convexity tightens the optimal regret from O(T)O(\sqrt{T}) to O(log⁡T)O(\log T), where TT is the time horizon; in the decentralized Riemannian setting, however, existing methods address only g-convex losses, leaving the strongly g-convex regime unexplored. One challenge is that the required decaying step size in the centralized regime is incompatible with existing network-error analyses, which typically assume a fixed step size. First, we provide a general network-error analysis for time-varying schedules. Next, we build on this analysis to establish the first O(log⁡T)O(\log T) static regret bound for decentralized online Riemannian gradient descent, matching the minimax-optimal rate for strongly-convex Euclidean online optimization. Finally, we prove the same O(log⁡T)O(\log T) regret bound for the two-point bandit feedback setting using novel strong subconvexity arguments for the smoothed versions of the loss functions.
Jul 21, 2026

The Price of Hidden Curvature: An Ω~(d5/4T)\widetildeΩ (d^{5/4} \sqrt{T}) Lower Bound for Bandit Convex Optimization

We establish a Ω~(d5/4T)\widetildeΩ(d^{5/4}\sqrt T) lower bound on the minimax expected regret of stochastic bandit convex optimization of 11-Lipschitz functions on the Euclidean ball. This presents the first nontrivial regret lower bound that grows faster than dTd\sqrt{T} for this problem, establishing that stochastic bandit convex optimization is fundamentally harder than linear bandits. The hard class of convex functions we construct takes the following form in dimension 2d2d: for an action a=(a1,a2)∈B22da = (a^1,a^2) \in \mathbb{B}^{2d}_2, each function is the scaled soft maximum of a "tube", r−1∥W⋆a1−r8εa2∥2r^{-1} \| W^\star a^1 - \frac{r}{8\varepsilon} a^2 \|_2 (hyperparameterized by ε,r\varepsilon,r), and a squared distance function, 12∥a1−u⋆∥22−12∥u⋆∥22\frac12 \| a^1 - u^\star \|_2^2 - \frac12 \| u^\star \|_2^2. Here, W⋆∈Rd×dW^\star \in \mathbb{R}^{d \times d} is an unknown linear transformation, and u⋆∈Rdu^\star \in \mathbb{R}^{d} is an unknown vector which must be learned to minimize the function. Observations are informative about u⋆u^\star only when the learner's action lies near the tube determined by W⋆W^\star, satisfying a2≈8εrW⋆a1a^2 \approx \frac{8\varepsilon}{r} W^\star a^1: thus the learner must either find this tube without knowing W⋆W^\star, or spend observations learning useful directions of W⋆W^\star. Formally, our regret analysis exploits this tradeoff by bounding the posterior spread of Fisher information matrices obtained under an adaptive sequence of actions. Together, these ingredients give a sample complexity lower bound of Ω~(d5/2/ε2)\widetildeΩ(d^{5/2}/\varepsilon^2) to find an ε\varepsilon-optimal action, which translates to an Ω~(d5/4T)\widetildeΩ (d^{5/4} \sqrt{T}) regret lower bound. We also extend this lower bound to the unconstrained setting where the action space is Rd\mathbb{R}^d.
Jul 12, 2026

Lower Bound on the Cumulative Constrained Violation for the OGD+Projection algorithm for Constrained Online Convex Optimization (COCO)

The problem of constrained online convex optimization is considered, where at each round, once a learner commits to an action xt∈X⊂Rdx_t \in \mathcal{X} \subset \mathbb{R}^d, a convex loss function ftf_t and a convex constraint function gtg_t that drives the constraint gt(x)≤0g_t(x)\le 0 are revealed. The objective is to simultaneously minimize the static regret and cumulative constraint violation (CCV) compared to the benchmark that knows the loss functions and constraint functions ftf_t and gtg_t for all tt ahead of time, and chooses a static optimal action that is feasible with respect to all gt(x)≤0g_t(x)\le 0. Currently, the best known algorithm is OGD+Projection algorithm of [Vaze and Sinha, 2025] that has simultaneous regret of O(T)O(\sqrt{T}) and CCV of O(T1/3)O(T^{1/3}) for d=2d=2 [Balasundaram et al., 2026], and simultaneous regret of O(T)O(\sqrt{T}) and CCV of O(T)O(\sqrt{T}) for any dd [Sarkar and Sinha, 2026]. In this paper, we show that the CCV of the OGD+Projection algorithm is Ω(Td−12d)Ω(T^{\frac{d-1}{2d}}). This is the first such lower bound result.
Jul 3, 2026

On the Convergence of Adam, Revisited

We show that projected Adam for online optimization with arbitrary moment decay parameters β1,β2∈[0,1)β_1,β_2\in[0,1) can have average regret bounded away from zero. A similar result of Reddi-Kale-Kumar from 2018 required β1<β2β_1<\sqrt{β_2}. Similar to their result, we use a three-periodic sequence of linear functions on [−1,1][-1,1] with slopes c,−1,−1c,-1,-1, though we use cc slightly larger than 22. This nonzero average regret result extends to Adam variants such as AdamW, RMSProp, NAdam, Adan, AdaMax, Muon, and to an i.i.d. variant of the three-periodic sequence of slopes for Adam.
Jul 2, 2026

Revisiting Decentralized Online Convex Optimization with Compressed Communication

Decentralized online convex optimization (D-OCO) is a popular framework for distributed applications with streaming data. To tackle the communication bottleneck, previous studies have investigated D-OCO with compressed communication and proposed several algorithms that are variants of online gradient descent (OGD). However, for D-OCO with exact communication, the best existing algorithms are variants of follow-the-regularized-leader (FTRL). In this paper, for the first time, we propose two FTRL-type algorithms for D-OCO with compressed communication. Compared with OGD-type algorithms, our algorithms are more elegant in both algorithmic design and theoretical analysis. The key insight is that the dual update mechanism of FTRL allows us to make a simple application of the technique for average consensus with communication compression. More specifically, our first algorithm considers the full-information setting, and can match the existing regret bounds. Our second algorithm is designed for the bandit setting, and can significantly improve both the regret bounds and communication costs of existing algorithms.
Jun 30, 2026

Constrained Online Convex Optimization without Slater's Condition

We study constrained online convex optimization with adversarial losses and stochastic or adversarial constraints. For stochastic constraints, existing algorithms that achieve nearly optimal regret and constraint violation bounds typically rely on regularity assumptions such as Slater's condition, while adversarial-constraint algorithms avoid these assumptions by using a rather restrictive round-wise feasible comparator. We bridge this gap with an anytime primal-dual framework that incorporates an adaptive regularizer into the dual update. The regularizer stabilizes the dual process without relying on the negative drift induced by Slater's condition. For stochastic constraints and convex losses, our algorithm achieves O(T)O(\sqrt{T}) expected regret and O(Tlog⁡T)O(\sqrt{T}\log T) expected cumulative constraint violation. Furthermore, we show that our algorithm also admits high-probability bounds of the same order on regret and constraint violation. For strongly convex losses, the regret bound improves to O(log⁡T)O(\log T) with a violation bound of the same order. With a minor modification, the framework also applies to adversarial constraints and provides guarantees for hard constraint violation.
Jun 18, 2026

Adversarial Bandit Optimization with Globally Bounded Perturbations to Convex Losses

We study adversarial bandit optimization in which the loss functions may be non-convex and non-smooth. In each round, the learner selects an action and observes only the loss incurred at that action. The loss consists of an underlying convex and ββ-smooth component and an adversarial perturbation that may be chosen after observing the learner's action. The perturbations are subject to a global budget controlling their cumulative magnitude over time. This framework extends the globally budgeted, post-action perturbation model from underlying linear losses to general convex and ββ-smooth losses. For this broader class, we establish expected regret guarantees that explicitly characterize the effect of the perturbation budget. To establish these guarantees, we modify a standard bandit optimization algorithm and develop an analysis that controls the additional regret caused by the perturbations. In the absence of perturbations, our results reduce to regret guarantees for the standard bandit convex optimization setting with ββ-smooth losses.
Jun 12, 2026

Optimal Hidden-Target Learning for Online Inventory Optimization on General Convex Sets

Online inventory optimization (OIO) is online convex optimization with physical memory: inventory carryover makes the feasible action set depend on the past. A natural principle, used in stochastic inventory learning and recently in OIO under a single linear capacity constraint, is to maintain a hidden target chosen by an online learner and implement its projection onto the currently feasible order-up-to set. We prove that this simple principle is optimal for OIO on arbitrary bounded convex capacity sets. With online gradient descent as the base learner, the method improves the best known regret guarantee for OIO on general convex sets from inverse to inverse-square-root dependence on the common-demand probability, and we prove a matching lower bound. The same principle gives the first polylogarithmic regret guarantee for strongly convex losses and the first dynamic regret guarantee adapting to Euclidean path variation on general convex capacity sets. The analysis introduces a norm alignment principle: the right state variable is the distance from the hidden target to the feasible set, measured in the same norm as the projection. Under norm alignment, this distance evolves pathwise as a scalar queue, with target movement as arrival and common demand as service. This reduction to one-dimensional queue control resolves the state dependence and extends the guarantees to general convex capacity sets, beyond the reach of prior productwise approaches. Experiments on synthetic and real-world inventory data corroborate the theory.
Jun 12, 2026

Online Convex Optimization with Sublinear Noisy Probes

We study Online Convex Optimization (OCO) over a convex set K⊆RdK\subseteq \mathbb R^d, where in each round tt the learner selects xt∈Kx_t\in K and then observes a convex loss ft:K→[0,1]f_t:K\to[0,1], with the goal of minimizing regret to the best fixed decision in hindsight. We introduce a unified probing model that generalizes two recent lines of work: sublinear best-expert queries in the experts setting, and pairwise (comparison-based) feedback available every round in OCO. In our framework, the learner has a budget of k≤Tk\le T pairwise probes; on a probed round it may query two points and learn which one has smaller loss. Our main result shows that even a sublinear and noisy probe budget can provably improve worst-case regret in the full feedback OCO regime. With kk δδ-noisy pairwise probes, we obtain: RegT≤O(min⁡{dTln⁡T,  dTln⁡Tk∣1−2δ∣})\text{Reg}_T \le O\left(\min\left\{\sqrt{dT\ln T},\; \frac{dT\ln T}{k|1-2δ|}\right\}\right), which is tight (up to logarithmic factors in TT) across TT, kk and δδ. Specifically regarding the noise parameter δ∈[0,1]δ\in [0,1], the regret guarantee smoothly degrades as the oracle response approaches a coin flip, i.e., δδ is close to 12\frac{1}{2}. When applying the same techniques to a finite KK for the prediction with dd experts setting, the resulting rates are instead completely tight in all parameters, including dd. Our analysis gives a streamlined treatment of pairwise probing in OCO by quantifying the benefit of probing via a variance reduction effect, combined with a second-order (variance-based) analysis of Continuous Exponential Weights.
Jun 10, 2026

Capacity-Constrained Online Convex Optimization with Delayed Feedback

Online learning with delayed feedback typically assumes that the learner can track all pending rounds until their feedback arrives. In practice, tracking resources are finite, and feedback from rounds that cannot be tracked is permanently lost. In this paper, we study delayed online convex optimization (OCO) under a hard capacity constraint, where at most CC pending rounds can be tracked at any time. To model delay information, we introduce a semi-clairvoyant model that refines the clairvoyant assumption from prior work: rather than requiring delays to be known at prediction time, the learner observes delay expirations online, consistent with the classical unconstrained delayed setting. Our approach proceeds via a reduction to a novel ``delayed and weighted'' OCO problem, using a scheduler that randomizes which rounds are tracked and importance-weights the resulting observations. For the base problem, we propose and analyze Delayed-Weighted FTRL and its bandit analogue, obtaining regret bounds that characterize how weights interact with delayed feedback in both settings. Combining these bounds with our schedulers yields regret guarantees for capacity-constrained OCO under convex and strongly convex losses, for both first-order and bandit feedback. For first-order feedback, capacity C=Ω(log⁡T)C = Ω(\log T) suffices to recover the standard delayed OCO rates up to logarithmic factors. For bandit feedback, the standard delayed BCO rates are instead modulated by (1+σmax/C)(1 + σ_{\text{max}}/C) factors, where σmaxσ_{\text{max}} is the maximum number of outstanding observations. This allows the regret bound to degrade gracefully when C<σmaxC < σ_{\text{max}}. We complement our analysis with numerical experiments.
Jun 6, 2026

Noise-Adaptive High-Probability Regret Bounds for Online Convex Optimization

We study high-probability regret bounds for online convex optimization (OCO) with strongly convex losses and establish three results that resolve open questions at the intersection of noise adaptivity, feedback structure, and constraint satisfaction. For the full-information setting with sub-Gaussian stochastic gradients, we prove a noise-adaptive high-probability regret bound in which the martingale deviation term scales with the noise level σσ rather than the gradient bound GG, yielding a multiplicative improvement of G/σG/σ over the classical Azuma-Hoeffding baseline. Our analysis introduces an exponential supermartingale argument that bypasses the bounded-difference requirement of Freedman's inequality, enabling direct treatment of unbounded sub-Gaussian noise without truncation artifacts. For bandit feedback, we prove a minimax lower bound: the high-probability regret scales linearly in log⁡(1/δ)\log(1/δ), in contrast to the log⁡(1/δ)\sqrt{\log(1/δ)} confidence cost under full information. This constitutes a formal separation in the confidence cost of strongly convex OCO across feedback models. Regarding constrained OCO with stochastic constraints satisfying a Slater condition, we provide simultaneous high-probability guarantees for both cumulative regret and long-run constraint violation, achieving O(Tlog⁡(m/δ))\mathcal{O}(\sqrt{T\log(m/δ)}) regret and O(T/(ζδ)+mTlog⁡(m/δ))\mathcal{O}(\sqrt{T}/(ζδ) + m\sqrt{T\log(m/δ)}) violation. Synthetic experiments corroborate all theoretical predictions.
Jun 1, 2026

From Non-Convex to Strongly Convex: Curvature-Adaptive FTPL for Online Optimization

Curvature adaptivity is a classical theme in online optimization: for convex Lipschitz losses, adaptive methods interpolate between the optimal O(T)O(\sqrt{T}) regret for general convex losses and O(log⁡T)O(\log T) regret under strong convexity. Recent work has shown that Follow-the-Perturbed-Leader (FTPL) achieves optimal O(T)O(\sqrt{T}) regret even for online non-convex Lipschitz losses, assuming access to an approximate offline-optimization oracle, but these guarantees do not exploit curvature. We show that FTPL can be made curvature-adaptive in the non-convex setting, without knowing in advance how curvature will accumulate over time. Our algorithm replaces the fixed perturbation scale of standard FTPL with a time-varying scale chosen using only past information. We give a simple follow-the-leader tuning rule for this scale and show that it competes, up to constants, with the best choice in hindsight. The resulting method achieves O(T)O(\sqrt{T}) regret for arbitrary non-convex Lipschitz losses and improves as cumulative curvature grows; with sufficiently accurate oracle calls, it achieves O(log⁡T)O(\log T) regret when cumulative curvature grows linearly, which includes the classical strongly convex regime. We complement these upper bounds with matching lower bounds for prescribed cumulative-curvature sequences, already for one-dimensional convex losses, showing that the tradeoff between worst-case non-convex regret and curvature-driven fast rates is intrinsic.
May 27, 2026

Decentralized Parameter-Free Online Learning with Compressed Gossip

We study decentralized online convex optimization when agents communicate over a graph and messages may be compressed. Classical decentralized online methods typically require learning-rate choices that depend on the horizon, comparator scale, or other problem parameters, while compressed communication introduces additional disagreement that must be controlled. We propose DECO-EF (DEcentralized COin-betting with Error Feedback), a decentralized parameter-free online learning algorithm that combines coin-betting predictions with compressed difference-based gossip. Each agent maintains a clean accumulated state and a compressed tracker, and communicates only compressed state differences during gossip steps. The method is parameter-free in the online-learning sense: it does not tune to the horizon, the comparator norm, or the learning rate. We prove expected comparator-adaptive network-regret bounds for DECO-EF under compressed communication. To the best of our knowledge, this gives the first expected sublinear network-regret guarantees for parameter-free decentralized online learning under compressed communication.
May 25, 2026

Online Learning on Hidden-Convex Losses via Algorithmic Equivalence: Optimal Regret, Geometric Barrier, and Bandit Feedback

We study adversarial online learning with hidden-convex losses, i.e., nonconvex losses that become convex after a nonlinear reparameterization. Ghai, Lu and Hazan (2022) proved that, under geometric and smoothness assumptions, online gradient descent (OGD) on such nonconvex losses approximately simulates online mirror descent (OMD) on the underlying convex losses with a suitable regularizer, yielding O(T2/3)\mathcal{O}(T^{2/3}) regret. They left open whether the optimal Θ(T)Θ(\sqrt{T}) regret from online convex optimization can be recovered in this hidden-convex setting. We answer this question affirmatively. More specifically, via a sharper discrete-time algorithmic equivalence argument, we prove that OGD achieves O(T)\mathcal{O}(\sqrt{T}) regret under the same assumptions, matching the optimal worst-case rate for adversarial online convex optimization. We also address another open question of Ghai, Lu and Hazan (2022) by clarifying the geometry required for this algorithmic equivalence. We replace the diagonal-Jacobian sufficient condition with a necessary-and-sufficient Hessian compatibility condition, thereby expanding the class of admissible reparameterizations. We complement our tight regret bound with a lower bound showing that OGD suffers Ω(T)Ω(T) regret even with a stepsize of order 1/T1/\sqrt{T}, for a smooth Hessian incompatible reparameterization between convex domains and an adversarial sequence of hidden-convex losses. Finally, we extend our analysis to one-point bandit feedback and prove a O(T3/4)\mathcal{O}(T^{3/4}) expected regret bound for bandit OGD with spherical smoothing, matching its classical rate on convex losses.
May 21, 2026

Bandit Convex Optimization with Gradient Prediction Adaptivity

Bandit convex optimization (BCO) is a fundamental online learning framework with partial feedback, where the learner observes only the loss incurred at the chosen decision point in each round. In this work, we investigate whether optimistic gradient predictions can improve worst-case regret guarantees in a prediction-adaptive manner. Specifically, given gradient predictions mtm_t, we seek regret bounds that scale with the cumulative prediction error ST=∑t=1T∥∇ft(xt)−mt∥2.S_T=\sum_{t=1}^T \|\nabla f_t(x_t)-m_t\|^2. We first establish a negative result: under the single-point feedback protocol, an unavoidable Ω(T)Ω(\sqrt{T}) regret lower bound persists even when ST=o(T)S_T=o(T), showing that the variance of gradient estimation fundamentally obscures the benefit of accurate predictions. To overcome this barrier, we propose Two-Point Variance-Reduced Optimistic Gradient Descent (TP-VR-OPT) for the two-point feedback setting. The key idea is a novel variance-reduced gradient estimator whose variance scales with the prediction error rather than the gradient norm. This yields a regret bound of O(d E[ST]),O\big(\sqrt{d\,\mathbb{E}[S_T]}\big), where dd is the decision dimension. Complementing this result, we establish an information-theoretic lower bound that scales as Ω(E[ST])Ω(\sqrt{\mathbb{E}[S_T]}), providing a fundamental characterization of the best achievable prediction-adaptive regret and showing that TP-VR-OPT is optimal up to a factor of d\sqrt d. We further develop adaptive variants that eliminate the need for prior knowledge of E[ST]\mathbb{E}[S_T] or the horizon TT, and extend our framework to non-stationary environments, establishing dynamic regret guarantees that adapt simultaneously to the cumulative prediction error and the comparator path length.
May 20, 2026

A Geometric Approach to Constrained Online Learning

We study constrained online convex optimization with adversarial time-varying constraints. At each round the learner acts before observing the loss and constraint, and is compared with the best fixed action satisfying all constraints in hindsight. The goal is to obtain minimax-optimal regret while controlling cumulative constraint violation (CCV). Prior algorithms achieved O(log⁡T)O(\log T) regret with O(Tlog⁡T)O(\sqrt{T\log T}) CCV for strongly convex losses, and O(T)O(\sqrt{T}) regret with O(Tlog⁡T)O(\sqrt{T}\log T) CCV for convex losses. We propose NP-OGD, an iterated nested-projection algorithm. For strongly convex losses it achieves O(log⁡T)O(\log T) regret and O(log⁡T)O(\log T) CCV; for convex losses it achieves O(T)O(\sqrt{T}) regret and O(T)O(\sqrt{T}) CCV. The analysis relies on a geometric movement bound: after lifting the nested projected-gradient trajectory to one higher dimension, the lifted path is self-contracted under a nonstandard norm, so a finite-length theorem for self-contracted curves controls the total projection movement. We also prove complementary lower bounds using layered sphere packings. For strongly convex losses, any online algorithm with polynomially sublinear regret can incur CCV at least Ω((log⁡T)(d−1)/(d+1)/log⁡log⁡T)Ω((\log T)^{(d-1)/(d+1)}/\log\log T). For convex losses, we prove CCV lower bounds Ω(T(d−1)/(2(d+3)))Ω(T^{(d-1)/(2(d+3))}) for weakly adaptive algorithms and Ω(T(d−1)/(2d))Ω(T^{(d-1)/(2d)}) for NP-OGD. Finally, for the constrained experts special case over NN experts, an active Hedge algorithm attains O(Tlog⁡N)O(\sqrt{T\log N}) regret and O(N)O(N) CCV, with a matching minimax CCV lower bound for sufficiently large horizons.
May 13, 2026

Polyhedral Instability Governs Regret in Online Learning

Many online decision problems over combinatorial actions are addressed via convex relaxations, leading to online convex optimization with piecewise linear objectives and induced polyhedral structure. We show that regret in such problems is governed by polyhedral instability: the number of changes of the active region. Under full information feedback and fixed partition assumptions, if RST\mathrm{RS}_T denotes the number of region switches and Vmax⁡V_{\max} the maximum number of vertices per region, we prove \RegretT=Θ((1+RST) T log⁡Vmax⁡)\Regret_T= Θ(\sqrt{(1+\mathrm{RS}_T)\,T\,\log V_{\max}}) interpolating between experts-like and dimension-dependent OCO rates. For online submodular--concave games under Lovász convexification, this reduces to the permutation-switch count SCT\mathrm{SC}_T, yielding the matching rate \RegretT=Θ((1+SCT) T log⁡n)\Regret_T= Θ(\sqrt{(1+\mathrm{SC}_T)\,T\,\log n}). Experiments on synthetic and real combinatorial problems (shortest path, influence maximization) validate the predicted scaling and indicate that low-instability regimes can arise in practice without explicit enumeration of actions.
May 8, 2026

Convex Optimization with Nested Evolving Feasible Sets

Convex Optimization with Nested Evolving Feasible Sets (CONES)} is considered 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 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(T1−β),O(Tβ)O(T^{1-β}), O(T^β) simultaneous regret and movement cost for any β∈(0,1]β\in (0,1], over a time horizon of TT. 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)O(\log T). To complement this, we show that any online algorithm with o(T)o(T) regret has a movement cost of Ω(log⁡T)Ω(\log{T}) for both cases, proving optimality of Frugal.
Apr 21, 2026

FedSEA: Achieving Benefit of Parallelization in Federated Online Learning

Online federated learning (OFL) has emerged as a popular framework for decentralized decision-making over continuous data streams without compromising client privacy. However, the adversary model assumed in standard OFL typically precludes any potential benefits of parallelization. Further, it fails to adequately capture the different sources of statistical variation in OFL problems. In this paper, we extend the OFL paradigm by integrating a stochastically extended adversary (SEA). Under this framework, the loss function remains fixed across clients over time. However, the adversary dynamically and independently selects the data distribution for each client at each time. We propose the \algoOFL{} algorithm to solve this problem, which utilizes online stochastic gradient descent at the clients, along with periodic global aggregation via the server. We establish bounds on the global network regret over a time horizon TT for two classes of functions: (1) for smooth and convex losses, we prove an O(T)\mathcal{O}(\sqrt{T}) bound, and (2) for smooth and strongly convex losses, we prove an O(log⁡T)\mathcal{O}(\log T) bound. Through careful analysis, we quantify the individual impact of both spatial (across clients) and temporal (over time) data heterogeneity on the regret bounds. Consequently, we identify a regime of mild temporal variation (relative to stochastic gradient variance), where the network regret improves with parallelization. Hence, in the SEA setting, our results improve the existing pessimistic worst-case results in online federated learning.
Apr 13, 2026

Gradient-Variation Regret Bounds for Unconstrained Online Learning

We develop parameter-free algorithms for unconstrained online learning with regret guarantees that scale with the gradient variation VT(u)=∑t=2T∥∇ft(u)−∇ft−1(u)∥2V_T(u) = \sum_{t=2}^T \|\nabla f_t(u)-\nabla f_{t-1}(u)\|^2. For LL-smooth convex losses, we provide fully-adaptive algorithms achieving regret of O~(∥u∥VT(u)+L∥u∥2+G4)\widetilde{O}(\|u\|\sqrt{V_T(u)} + L\|u\|^2+G^4) without requiring prior knowledge of comparator norm ∥u∥\|u\|, Lipschitz constant GG, or smoothness LL. The update in each round can be computed efficiently via a closed-form expression. Our results extend to dynamic regret and find immediate implications for the stochastically-extended adversarial (SEA) model, which significantly improves upon the previous best-known result (Wang et al., 2025).
Apr 10, 2026

Distributed Online Convex Optimization with Compressed Communication: Optimal Regret and Applications

Distributed online convex optimization (D-OCO) is a powerful paradigm for modeling distributed scenarios with streaming data. However, the communication cost between local learners and the central server is substantial in large-scale applications. To alleviate this bottleneck, we initiate the study of D-OCO with compressed communication. Firstly, to quantify the compression impact, we establish the Ω(δ−1/2T)Ω(δ^{-1/2}\sqrt{T}) and Ω(δ−1log⁡T)Ω(δ^{-1}\log{T}) lower bounds for convex and strongly convex loss functions, respectively, where δ∈(0,1]δ\in (0,1] is the compression ratio. Secondly, we propose an optimal algorithm, which enjoys regret bounds of O(δ−1/2T)O(δ^{-1/2}\sqrt{T}) and O(δ−1log⁡T)O(δ^{-1} \log T) for convex and strongly convex loss functions, respectively. Our method incorporates the error feedback mechanism into the Follow-the-Regularized-Leader framework to address the coupling between the compression error and the projection error. Furthermore, we employ the online compression strategy to mitigate the accumulated error arising from the bidirectional compression. Our online method has great generality, and can be extended to the offline stochastic setting via online-to-batch conversion. We establish convergence rates of O(δ−1/2T−1/2)O(δ^{-1/2}T^{-1/2}) and O(δ−1T−1)O(δ^{-1} T^{-1}) for convex and strongly convex loss functions, respectively, providing the first guarantees for distributed non-smooth optimization with compressed communication and domain constraints.