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.

Mar 26, 2026

Logarithmic High-Probability Regret for Online Convex Optimization with Two-Point Bandit Feedback

We study online convex optimization (OCO) with two-point bandit feedback against a non-anticipating adaptive adversary. In this setting, a learner competes with an adversarial sequence of convex losses while observing each loss only through two function evaluations. For strongly convex losses, Agarwal, Dekel, and Xiao~\citeyearpar{agarwal2010optimal} proved a comparator-wise logarithmic regret bound in expectation. Consequently, by minimizing outside the probability space, their result yields a pseudo-regret guarantee of the form \EBAT−min⁡x∈K\EBLT(x)\EB A_T-\min_{x\in\mathcal K}\EB L_T(x), where ATA_T is the algorithm's two-query cumulative loss and LT(x)L_T(x) is the comparator's cumulative loss. They asked whether a logarithmic high-probability guarantee is achievable in the same two-point strongly convex setting. Our main theorem provides the corresponding fixed-comparator high-probability statement: for any comparator x∈Kx\in\mathcal K fixed independently of the algorithmic random directions, the standard two-point projected gradient method guarantees, with probability at least 1−δ1-δ, a two-query regret bound of order O(dG2μ(log⁡T+log⁡(1/δ))+dGDlog⁡(1/δ)+Glog⁡T(1+Dr)).O\left(\frac{dG^2}μ\left(\log T+\log(1/δ)\right)+dGD\log(1/δ)+G\log T\left(1+\frac{D}{r}\right)\right). At the comparator-wise level, our leading horizon-dependent term is linear in dd, compared with the d2d^2-type term in the original analysis of Agarwal, Dekel, and Xiao. The key ingredient is a high-confidence analysis that simultaneously absorbs the martingale error into strong convexity and preserves the linear-in-dimension estimator control of the two-point method. A deterministic covering argument then yields a realized full-comparator guarantee against min⁡x∈KLT(x)\min_{x\in\mathcal K}L_T(x), preserving logarithmic dependence on TT at the cost of the standard covering-number factor.
Mar 22, 2026

Constrained Online Convex Optimization with Memory and Predictions

We study Constrained Online Convex Optimization with Memory (COCO-M), where both the loss and the constraints depend on a finite window of past decisions made by the learner. This setting extends the previously studied unconstrained online optimization with memory framework and captures practical problems such as the control of constrained dynamical systems and scheduling with reconfiguration budgets. For this problem, we propose the first algorithms that achieve sublinear regret and sublinear cumulative constraint violation under time-varying constraints, both with and without predictions of future loss and constraint functions. Without predictions, we introduce an adaptive penalty approach that guarantees sublinear regret and constraint violation. When short-horizon and potentially unreliable predictions are available, we reinterpret the problem as online learning with delayed feedback and design an optimistic algorithm whose performance improves as prediction accuracy improves, while remaining robust when predictions are inaccurate. Our results bridge the gap between classical constrained online convex optimization and memory-dependent settings, and provide a versatile learning toolbox with diverse applications.
Mar 21, 2026

Breaking the O(T)O(\sqrt{T}) Cumulative Constraint Violation Barrier while Achieving O(T)O(\sqrt{T}) Static Regret in Constrained Online Convex Optimization

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. In recent prior work Sinha and Vaze [2024], algorithms with simultaneous regret of O(T)O(\sqrt{T}) and CCV of O(T)O(\sqrt{T}) or (CCV of O(1)O(1) in specific cases Vaze and Sinha [2025], e.g. when d=1d=1) have been proposed. It is widely believed that CCV is Ω(T)Ω(\sqrt{T}) for all algorithms that ensure that regret is O(T)O(\sqrt{T}) with the worst case input for any d≥2d\ge 2. In this paper, we refute this and show that the algorithm of Vaze and Sinha [2025] simultaneously achieves regret of O(T)O(\sqrt{T}) regret and CCV of O(T1/3)O(T^{1/3}) when d=2d=2.
Mar 15, 2026

Structure-Dependent Regret and Constraint Violation Bounds for Online Convex Optimization with Time-Varying Constraints

Online convex optimization (OCO) with time-varying constraints is a critical framework for sequential decision-making in dynamic networked systems, where learners must minimize cumulative loss while satisfying regions of feasibility that shift across rounds. Existing theoretical analyses typically treat constraint variation as a monolithic adversarial process, resulting in joint regret and violation bounds that are overly conservative for real-world network dynamics. In this paper, we introduce a structured characterization of constraint variation - smooth drift, periodic cycles, and sparse switching - mapping these classes to common network phenomena such as slow channel fading, diurnal traffic patterns, and discrete maintenance windows. We derive structure-dependent joint bounds that strictly improve upon adversarial rates when the constraint process exhibits regularity. To realize these gains, we propose the Structure-Adaptive Primal-Dual (SA-PD) algorithm, which utilizes observable constraint signals to detect environmental structure online and adapt dual update strategies accordingly. Extensive experiments on synthetic benchmarks and real-world datasets - including online electricity scheduling and transformer load management - demonstrate that SA-PD reduces cumulative constraint violation by up to 53% relative to structure-agnostic baselines while maintaining competitive utility. This work serves as a comprehensive guide for exploiting temporal regularity in constrained online learning for robust network engineering.
Feb 13, 2026

Block-Norm Geometries for Online Mirror Descent with Sparse Losses

The performance of online mirror descent depends critically on the geometry induced by its mirror map, yet standard algorithms largely rely on two canonical choices: Euclidean and entropic geometry. We show that these two geometries can both be substantially suboptimal when loss gradients are sparse. We introduce a family of randomized block-norm mirror maps that interpolates between Euclidean and entropic geometries and adapts to intermediate sparsity structure. For several standard convex sets, including ℓp\ell_p balls, ellipsoids, boxes, and Minkowski sums of norm balls, we prove polynomial-in-dimension improvements in regret bounds over the better of online projected gradient descent and exponentiated gradient. We further construct explicit online convex optimization instances for which these improvements are realized: on a simple polytope, an intermediate block geometry achieves a poly(d)\text{poly}(d) separation in regret from both Euclidean and entropic geometries in dimension dd, while on the probability simplex we obtain a separation of order Ω(log⁡d/log⁡log⁡d)\Omega(\sqrt{\log d}/\log\log d). Finally, we study geometry selection when sparsity is unknown. We show that naively alternating between mirror maps can incur linear regret, even though either mirror map alone has sublinear regret, and give a Hedge meta-algorithm that competes with the best mirror map in a finite portfolio. For random block geometries, this yields regret within an O(log⁡log⁡d)O(\sqrt{\log\log d}) factor of the best random uniform block norm chosen in hindsight.
Feb 4, 2026

Improved Dimension Dependence for Bandit Convex Optimization with Gradient Variations

Gradient-variation online learning has drawn increasing attention due to its deep connections to game theory and optimization. It has been studied extensively in the full-information setting, but is underexplored with bandit feedback. In this work, we focus on gradient variation in Bandit Convex Optimization (BCO) with two-point feedback. By proposing a refined analysis of the non-consecutive gradient variation, a fundamental quantity in gradient variation with bandit feedback, we improve the dimension dependence for both convex and strongly convex functions compared with the best known results (Chiang et al., 2013). Our improved analysis of the non-consecutive gradient variation also implies other favorable problem-dependent guarantees, such as gradient-variance and small-loss regret bounds. Beyond the two-point setup, we demonstrate the versatility of our technique by achieving the first gradient-variation bound for one-point bandit linear optimization over hyper-rectangular domains. Finally, we validate the effectiveness of our results in more challenging tasks such as dynamic and universal regret minimization, establishing the first gradient-variation dynamic and universal regret bounds for two-point BCO.
Feb 2, 2026

A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees

This paper develops a reduction-based framework for online learning with delayed feedback that recovers and improves upon existing results for first-order and bandit convex optimization. We introduce a continuous-time model that enables an observation-centric rather than prediction-centric analysis. Under this model, regret decomposes into a delay-independent learning term and a delay-induced drift term, yielding a delay-adaptive reduction that converts any online linear optimization algorithm into one that handles round-dependent delays. For bandit convex optimization, we significantly improve existing regret bounds, with delay-dependent terms matching optimal first-order rates. For first-order feedback, we recover optimal regret bounds via a simpler, unified analysis. Quantitatively, for bandit convex optimization we obtain O(dtot+T34k)O(\sqrt{d_{\text{tot}}} + T^{\frac{3}{4}}\sqrt{k}) regret, improving the delay-dependent term from O(min⁡{Tdmax,(Tdtot)13})O(\min\{\sqrt{T d_{\text{max}}},(Td_{\text{tot}})^{\frac{1}{3}}\}) in prior work to O(dtot)O(\sqrt{d_{\text{tot}}}). Here, kk, TT, dmaxd_{\text{max}}, and dtotd_{\text{tot}} denote the dimension, time horizon, maximum and total delay, respectively. Under strong convexity, we achieve O(min⁡{σmaxln⁡T,dtot}+(T2ln⁡T)13k23)O(\min\{σ_{\text{max}} \ln T, \sqrt{d_{\text{tot}}}\} + (T^2\ln T)^{\frac{1}{3}} {k}^{\frac{2}{3}}), improving the delay-dependent term from O(dmaxln⁡T)O(d_{\text{max}} \ln T) to O(min⁡{σmaxln⁡T,dtot})O(\min\{σ_{\text{max}} \ln T, \sqrt{d_{\text{tot}}}\}), where σmaxσ_{\text{max}} denotes the maximum number of outstanding observations and may be considerably smaller than dmaxd_{\text{max}}.
Jan 20, 2026

Small Gradient Norm Regret for Online Convex Optimization

This paper introduces a new problem-dependent regret measure for online convex optimization with smooth losses. The notion, which we call the G⋆G^\star regret, depends on the cumulative squared gradient norm evaluated at the decision in hindsight. We show that the G⋆G^\star regret strictly refines the existing L⋆L^\star (small loss) regret, and that it can be arbitrarily sharper when the losses have vanishing curvature around the hindsight decision. We establish upper and lower bounds on the G⋆G^\star regret and extend our results to dynamic regret and bandit settings. As a byproduct, we refine the existing convergence analysis of stochastic optimization algorithms in the interpolation regime. Some experiments validate our theoretical findings.
Nov 28, 2025

Distributed Dynamic Associative Memory via Online Convex Optimization

An associative memory (AM) enables cue-response recall, and it has recently been recognized as a key mechanism underlying modern neural architectures such as Transformers. In this work, we introduce the concept of distributed dynamic associative memory (DDAM), which extends classical AM to settings with multiple agents and time-varying data streams. In DDAM, each agent maintains a local AM that must not only store its own associations but also selectively memorize information from other agents based on a specified interest matrix. To address this problem, we propose a novel tree-based distributed online gradient descent algorithm, termed DDAM-TOGD, which enables each agent to update its memory on the fly via inter-agent communication over designated routing trees. We derive rigorous performance guarantees for DDAM-TOGD, proving sublinear static regret in stationary environments and a path-length dependent dynamic regret bound in non-stationary environments. These theoretical results provide insights into how communication delays and network structure impact performance. Building on the regret analysis, we further introduce a combinatorial tree design strategy that optimizes the routing trees to minimize communication delays, thereby improving regret bounds. Numerical experiments demonstrate that the proposed DDAM-TOGD framework achieves superior accuracy and robustness compared to representative online learning baselines such as consensus-based distributed optimization, confirming the benefits of the proposed approach in dynamic, distributed environments.
Jul 13, 2025

Efficiency, Feasibility, and Incentive-Awareness in Constrained Online Resource Allocation

We study the dynamic allocation of indivisible resources to strategic agents under long-term constraints, where the planner aims to maximize social welfare, satisfy multiple constraints, and elicit near-truthful reports. We find standard primal-dual methods fragile in this setting: agents easily manipulate their reports to distort dual variables, sacrificing social efficiency for individual utility. To address this, we propose the Incentive-Aware Primal-Dual (IAPD) framework. On the primal side, we integrate three components to suppress manipulation: a VCG-based payment neutralizes immediate misreporting benefits, while epoch-based lazy updates and random exploration together ensure potential future gains are outweighed by immediate penalties. On the dual side, to overcome a learning barrier due to lazy updates -- which we call the "price of incentives" -- we design a novel optimistic online learning algorithm, O-FTRL-FP. It utilizes a fixed-point oracle to resolve the circular dependency between optimistic dual variables and the resulting allocations. Ultimately, our mechanism attains O~(T)\tilde{\mathcal O}(\sqrt T) social welfare regret, satisfies all long-term constraints, and induces a near-truthful equilibrium. It also smoothly generalizes to multi-unit multi-demand allocation problems. Notably, this O~(T)\tilde{\mathcal O}(\sqrt T) regret near-matches the non-strategic Ω(T)Ω(\sqrt T) lower bound, demonstrating that incentive-awareness can be accommodated at nearly no cost.
May 30, 2025

TIP-Search: Time-Predictable Inference Scheduling for Market Prediction under Uncertain Load

Real-time market prediction services need correct predictions before a decision deadline; a correct prediction delivered late is not usable. TIP-Search studies time-predictable inference scheduling over fixed market predictors under uncertain load. It filters conformal latency-quantile feasible models, dispatches over finite workers, and uses shielded constrained online experts to trade accuracy, queue pressure, and deadline risk. On the optimized deployable pool, TIP-Search reaches 0.994 raw accuracy and 0.991 timely accuracy. On official TLOB FI-2010 h=10, TIP-Search++ raises timely accuracy from 0.156 to 0.239 and deadline satisfaction from 0.391 to 0.962. In matched h10 profiled systems replay, OCO-ACPO reaches 0.303 timely accuracy and 0.951 deadline satisfaction, with paired gains over RAMSIS/SneakPeek/utility-style comparators of +0.00285+0.00285 timely accuracy (p=0.0118p=0.0118) and +0.0146+0.0146 deadline satisfaction (p=1.5×10−5p=1.5{\times}10^{-5}). SA-OCO-ACPO improves timely/deadline service by 0.188--0.417 over CPO under nonstationary stress. The claim is a systems scheduling result, not a broad LOB classifier leaderboard.
Jan 30, 2025

Decentralized Projection-free Online Upper-Linearizable Optimization with Applications to DR-Submodular Optimization

We introduce a novel framework for decentralized projection-free optimization, extending projection-free methods to a broader class of upper-linearizable functions. Our approach leverages decentralized optimization techniques with the flexibility of upper-linearizable function frameworks, effectively generalizing traditional DR-submodular function optimization. We obtain the regret of O(T1−θ/2)O(T^{1-θ/2}) with communication complexity of O(Tθ)O(T^θ) and number of linear optimization oracle calls of O(T2θ)O(T^{2θ}) for decentralized upper-linearizable function optimization, for any 0≤θ≤10\le θ\le 1. This approach allows for the first results for monotone up-concave optimization with general convex constraints and non-monotone up-concave optimization with general convex constraints. Further, the above results for first order feedback are extended to zeroth order, semi-bandit, and bandit feedback.
Dec 31, 2019

Online Learning: A Modern Introduction Using Convex Optimization

In this book, I introduce the concepts of online learning through a modern view based on convex optimization. Here, online learning refers to the framework of regret minimization under worst-case assumptions. I attempted to unify all the literature as instantiations of Online Mirror Descent and Follow-the-Regularized-Leader (and their variants). I paid particular attention to the issue of tuning the parameters of the algorithms, through adaptive and parameter-free online learning algorithms. The bandit setting is also briefly discussed, touching on the problem of adversarial and stochastic multi-armed bandits. Building on fundamental algorithms and concepts, I also cover advanced topics, including black-box reductions, saddle-point optimization, sequential investment, and non-stationary forms of regret analysis. Finally, I conclude with a selection of applications of online learning to domains far from it, such as generalization theory and concentration inequalities. I attempted to maintain an informal, yet mathematically rigorous, tone throughout the book. Moreover, all the included proofs have been carefully chosen to be as simple and as short as possible. This also means that sometimes I have added one or two additional assumptions, just to simplify the proofs.