The paper establishes the first finite-time convergence rate of 1/T^{2/13} for classical Adam (with bias correction, no extra steps) in nonsmooth nonconvex optimization under heavy-tailed noise with β1=β2.
hub Mixed citations
A Modern Introduction to Online Learning
Mixed citation behavior. Most common role is background (60%).
49
Pith papers citing it
Background
60% of classified citations
abstract
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.
hub tools
citation-role summary
background 4
method 1
citation-polarity summary
representative citing papers
NEOL decouples neuroevolution into outer architecture search and inner online weight adaptation, proving sublinear regret under mild conditions and showing empirical gains over pure NEAT on control benchmarks.
A robust variant of binary search achieves regret O(C + log T) for dynamic pricing with known corruption C and O(C + log² T) when unknown.
A primal-dual framework with adaptive dual regularizer achieves O(√T) regret and O(√T log T) constraint violation for constrained OCO without Slater's condition under stochastic constraints, with extensions to adversarial constraints and strongly convex losses.
Under a model-loss decomposition, clipping model outputs in tail events yields adaptive SCO bounds matching known-parameter optima up to logarithmic factors in uncertainty.
OMWU has last-iterate asymptotic convergence to a saddle point for smooth convex-concave saddle-point problems with small constant step size, via a new boundary argument on cluster points.
Provides the first regret guarantees for capacity-constrained delayed OCO under convex and strongly convex losses via randomized schedulers and Delayed-Weighted FTRL, recovering standard rates for C = Omega(log T) in the full-information case.
POGO uses multi-portfolio wealth maximization to produce a single sequence of radii that achieve the strongest known finite-time group-conditional coverage without any learning-rate hyperparameter.
DECO-EF achieves the first expected comparator-adaptive sublinear network-regret bounds for parameter-free decentralized online learning under compressed communication.
A unified primal-dual framework derives four accelerated three-operator splitting algorithms (ACV-I, ACV-II, APDTR-I, APDTR-II) with Lyapunov analysis establishing iteration complexities for smooth and nonsmooth cases.
OGD achieves O(sqrt(T)) regret on hidden-convex losses via sharper algorithmic equivalence under Hessian compatibility, with a matching lower bound and O(T^{3/4}) bandit extension.
Prudent-Banker achieves pseudo-regret Õ(√T + √D) and Õ(1) regret vs. safe comparator in adversarial bandits both with and without delays, matching new lower bounds up to logs.
TP-VR-OPT achieves O(√(d E[S_T])) prediction-adaptive regret in two-point bandit convex optimization, with a matching Ω(√E[S_T]) lower bound up to √d, while single-point feedback cannot benefit from predictions.
A nested-projection gradient algorithm attains O(log T) regret with O(log T) cumulative constraint violation for strongly convex losses, and O(√T) for both with convex losses; the body's proof is coherent, though the abstract claims lower-bound results the body never contains.
Develops robust online conformal prediction schemes that provide explicit miscoverage guarantees under feedback modeled as arbitrary binary flips or bounded-memory errors.
A Bregman divergence approach yields a general calibeating framework that achieves U-calibration with logarithmic regret for Tsallis losses and a new regret equality for Be The Regularized Leader.
Presents first online L2D algorithm for multiclass classification with bandit feedback and varying experts, achieving O((n+n_e)T^{2/3}) regret generally and O((n+n_e)√T) under low noise.
An algorithm for online resource allocation with budget and general constraints achieves O(sqrt(T)) regret in stochastic and alpha-regret in adversarial regimes with bounded constraint violations.
A modular reduction from budget-constrained contextual bandits with adversarial contexts to unconstrained bandits via surrogate rewards, yielding improved guarantees and an efficient algorithm based on SquareCB.
Predictive hints from any stabilizing Luenberger observer make hint residuals uniformly bounded in online least squares, yielding logarithmic regret for nonstochastic prediction despite unbounded trajectories in marginally stable systems.
CRRA portfolio selection equals Rényi information projection with the Rényi order matching the relative risk aversion coefficient, yielding a Blahut-Arimoto-style alternating optimizer that needs fewer iterations at low risk aversion.
A framework for concave distributional utility maximization in stochastic bandits via influence-function stochastic gradients and entropic mirror ascent on the simplex, with regret bounds.
FedSEA achieves O(sqrt(T)) regret for smooth convex losses and O(log T) for smooth strongly convex losses in federated online learning under stochastic adversary, with parallelization benefits when temporal heterogeneity is mild relative to gradient noise.
Fully parameter-free online-learning algorithms achieve regret Õ(||u||√V_T(u) + L||u||² + G⁴) adapting to gradient variation with closed-form O(d) updates, extending to dynamic regret and the stochastically-extended adversarial model.
citing papers explorer
-
Adam Converges in Nonsmooth Nonconvex Optimization
The paper establishes the first finite-time convergence rate of 1/T^{2/13} for classical Adam (with bias correction, no extra steps) in nonsmooth nonconvex optimization under heavy-tailed noise with β1=β2.
-
Provably Sub-Linear Two-Timescale NeuroEvolution with Online Plasticity
NEOL decouples neuroevolution into outer architecture search and inner online weight adaptation, proving sublinear regret under mild conditions and showing empirical gains over pure NEAT on control benchmarks.
-
Toward Optimal Regret in Robust Pricing: Decoupling Corruption and Time
A robust variant of binary search achieves regret O(C + log T) for dynamic pricing with known corruption C and O(C + log² T) when unknown.
-
Constrained Online Convex Optimization without Slater's Condition
A primal-dual framework with adaptive dual regularizer achieves O(√T) regret and O(√T log T) constraint violation for constrained OCO without Slater's condition under stochastic constraints, with extensions to adversarial constraints and strongly convex losses.
-
Clipping the Price of Adaptivity at the Tail
Under a model-loss decomposition, clipping model outputs in tail events yields adaptive SCO bounds matching known-parameter optima up to logarithmic factors in uncertainty.
-
Last-Iterate Convergence of Optimistic Multiplicative Weight Update
OMWU has last-iterate asymptotic convergence to a saddle point for smooth convex-concave saddle-point problems with small constant step size, via a new boundary argument on cluster points.
-
Capacity-Constrained Online Convex Optimization with Delayed Feedback
Provides the first regret guarantees for capacity-constrained delayed OCO under convex and strongly convex losses via randomized schedulers and Delayed-Weighted FTRL, recovering standard rates for C = Omega(log T) in the full-information case.
-
Parameter-Free and Group Conditional Online Conformal Prediction
POGO uses multi-portfolio wealth maximization to produce a single sequence of radii that achieve the strongest known finite-time group-conditional coverage without any learning-rate hyperparameter.
-
Decentralized Parameter-Free Online Learning with Compressed Gossip
DECO-EF achieves the first expected comparator-adaptive sublinear network-regret bounds for parameter-free decentralized online learning under compressed communication.
-
A Unified Primal-Dual Recipe for Accelerating Three-Operator Splitting Methods
A unified primal-dual framework derives four accelerated three-operator splitting algorithms (ACV-I, ACV-II, APDTR-I, APDTR-II) with Lyapunov analysis establishing iteration complexities for smooth and nonsmooth cases.
-
Online Learning on Hidden-Convex Losses via Algorithmic Equivalence: Optimal Regret, Geometric Barrier, and Bandit Feedback
OGD achieves O(sqrt(T)) regret on hidden-convex losses via sharper algorithmic equivalence under Hessian compatibility, with a matching lower bound and O(T^{3/4}) bandit extension.
-
Prudent-Banker: No Extra Fees for Baseline Safety in Adversarial Bandits With and Without Delays
Prudent-Banker achieves pseudo-regret Õ(√T + √D) and Õ(1) regret vs. safe comparator in adversarial bandits both with and without delays, matching new lower bounds up to logs.
-
Bandit Convex Optimization with Gradient Prediction Adaptivity
TP-VR-OPT achieves O(√(d E[S_T])) prediction-adaptive regret in two-point bandit convex optimization, with a matching Ω(√E[S_T]) lower bound up to √d, while single-point feedback cannot benefit from predictions.
-
A Geometric Approach to Constrained Online Learning
A nested-projection gradient algorithm attains O(log T) regret with O(log T) cumulative constraint violation for strongly convex losses, and O(√T) for both with convex losses; the body's proof is coherent, though the abstract claims lower-bound results the body never contains.
-
Online Conformal Prediction with Corrupted Feedback
Develops robust online conformal prediction schemes that provide explicit miscoverage guarantees under feedback modeled as arbitrary binary flips or bounded-memory errors.
-
Calibeating for general proper losses: A Bregman divergence approach
A Bregman divergence approach yields a general calibeating framework that achieves U-calibration with logarithmic regret for Tsallis losses and a new regret equality for Be The Regularized Leader.
-
Online Learning-to-Defer with Varying Experts
Presents first online L2D algorithm for multiclass classification with bandit feedback and varying experts, achieving O((n+n_e)T^{2/3}) regret generally and O((n+n_e)√T) under low noise.
-
Online Resource Allocation With General Constraints
An algorithm for online resource allocation with budget and general constraints achieves O(sqrt(T)) regret in stochastic and alpha-regret in adversarial regimes with bounded constraint violations.
-
Constrained Contextual Bandits with Adversarial Contexts
A modular reduction from budget-constrained contextual bandits with adversarial contexts to unconstrained bandits via surrogate rewards, yielding improved guarantees and an efficient algorithm based on SquareCB.
-
Online Nonstochastic Prediction: Logarithmic Regret via Predictive Online Least Squares
Predictive hints from any stabilizing Luenberger observer make hint residuals uniformly bounded in online least squares, yielding logarithmic regret for nonstochastic prediction despite unbounded trajectories in marginally stable systems.
-
Single-Period Portfolio Selection via Information Projection
CRRA portfolio selection equals Rényi information projection with the Rényi order matching the relative risk aversion coefficient, yielding a Blahut-Arimoto-style alternating optimizer that needs fewer iterations at low risk aversion.
-
Concave Statistical Utility Maximization Bandits via Influence-Function Gradients
A framework for concave distributional utility maximization in stochastic bandits via influence-function stochastic gradients and entropic mirror ascent on the simplex, with regret bounds.
-
FedSEA: Achieving Benefit of Parallelization in Federated Online Learning
FedSEA achieves O(sqrt(T)) regret for smooth convex losses and O(log T) for smooth strongly convex losses in federated online learning under stochastic adversary, with parallelization benefits when temporal heterogeneity is mild relative to gradient noise.
-
Gradient-Variation Regret Bounds for Unconstrained Online Learning
Fully parameter-free online-learning algorithms achieve regret Õ(||u||√V_T(u) + L||u||² + G⁴) adapting to gradient variation with closed-form O(d) updates, extending to dynamic regret and the stochastically-extended adversarial model.
-
Distributed Online Convex Optimization with Compressed Communication: Optimal Regret and Applications
Optimal regret bounds O(δ^{-1/2}√T) for convex and O(δ^{-1} log T) for strongly convex losses are achieved in distributed online convex optimization under compressed communication.
-
Learning Safely Without Knowing the World:COMPASS-Hedge
COMPASS-Hedge is claimed to be the first parameter-free full-information anytime algorithm with simultaneous minimax adversarial, gap-dependent stochastic, and near-constant baseline-relative regret.
-
Non-Stationary Online Structured Prediction with Surrogate Losses
In non-stationary online structured prediction, cumulative target loss is bounded by F_T + O(1 + P_T) using dynamic regret of OGD combined with surrogate-gap exploitation.
-
Leveraging Similarities in Multi-Armed Bandits
Impossibility result for one-point feedback in tree-structured bandits plus algorithms for multi-point feedback achieving best-of-both-worlds regret with effective action count K_eff, including √T regret for d≤2 Lipschitz bandits under two-point feedback.
-
QueryMarket: Cost-Aware Online Active Learning in Data Markets
QueryMarket introduces OVBAL, an online active learning rule that selects samples using D-optimality with exponential forgetting and executes purchases under rolling budget constraints for nonstationary streams.
-
Theoretical Foundations of Continual Learning via Drift-Plus-Penalty
Introduces COLD, a DPP-based continual learning framework with stability and convergence guarantees that outperforms prior methods on benchmarks via tunable stability-plasticity control.
-
Regularized Offline Policy Optimization with Posterior Hybrid Bayesian Belief
PhyB averages over the k worst dynamics models with entropy-weighted coefficients and uses Bregman-regularized policy iteration; it claims bounded pessimism, monotonic improvement, and top D4RL scores.
-
In-Expectation Convergence of Stochastic Gradient Methods under Heavy-Tailed Noise
New in-expectation convergence guarantees for SMD, ASMD (convex) and SGD, SGDM (nonconvex) under heavy-tailed noise without bounded-domain restrictions or algorithmic modifications.
-
Optimistic Dual Averaging Unifies Modern Optimizers
SODA unifies several modern optimizers under optimistic dual averaging and supplies a 1/k decay wrapper that improves performance without weight decay tuning.
-
Online Sharp-Calibrated Bayesian Optimization
OSCBO adaptively balances Gaussian process sharpness and calibration in Bayesian optimization by casting hyperparameter selection as constrained online learning, while preserving sublinear regret bounds.
-
Online Localized Conformal Prediction
OLCP and OLCP-Hedge achieve long-run valid coverage in non-exchangeable online settings with narrower prediction sets by localizing conformal prediction to covariates and selecting bandwidth via online convex optimization.
-
StoSignSGD: Unbiased Structural Stochasticity Fixes SignSGD for Training Large Language Models
StoSignSGD resolves SignSGD divergence on non-smooth objectives via structural stochasticity, matching optimal convex rates and improving non-convex bounds while delivering 1.44-2.14x speedups in FP8 LLM pretraining.
-
Partially Lazy Gradient Descent for Smoothed Online Learning
k-lazyGD achieves optimal dynamic regret O(sqrt((P_T+1)T)) in SOCO for laziness k up to Theta(sqrt(T/P_T)).
-
Eventually LIL Regret: Almost Sure $\ln\ln T$ Regret for a sub-Gaussian Mixture on Unbounded Data
A sub-Gaussian mixture achieves almost sure ln ln V_T regret on unbounded data via a pathwise bound that holds on the probability-one Ville event.
-
Implicit score-driven filters for time-varying parameter models
Implicit score-driven updates preserve the full observation density to deliver global stability and mean-squared-error contraction toward the pseudo-true parameter for log-concave densities in time-varying parameter models.
-
Dissecting Discrete Soft Actor-Critic: Limitations and Principled Alternatives
Shows entropy coupling limits DSAC on discrete tasks and introduces a generalized actor-critic framework with m-step critics and novel entropy-regularized objectives that perform robustly on Atari.
-
Zero-order Parameter-free Optimization for LMO-based Methods: Novel Approach for Efficient Fine-tuning
AdaNAGED combines zeroth-order gradient-free training, automatic parameter adaptation, and LMO-based non-Euclidean geometry with claimed convergence guarantees, demonstrated on OPT-1.3B fine-tuning.
-
Zeroth-Order Nonconvex Nonsmooth Optimization with Heavy-Tailed Noise
Proposes a clipped two-point zeroth-order algorithm achieving O(d^{p/2(p-1)} δ^{-1} ε^{-(2p-1)/p-1}) complexity for (δ, ε)-Goldstein stationary points in nonconvex nonsmooth problems with heavy-tailed noise.
-
When Determinants Are Not Enough: Private Rare Switching
Replaces determinant growth with generalized Rayleigh quotient for rare switching in private linear bandits to control worst-direction volume despite non-monotonic design matrices from noise.
-
A Note on How to Remove the $\ln\ln T$ Term from the Squint Bound
Shifted KT potentials equal a prior change in KT, and this removes the ln ln T factor from Squint's data-independent bound.
-
Revisiting Active Sequential Prediction-Powered Mean Estimation
Non-asymptotic analysis of prediction-powered mean estimation shows that no-regret learning for query probabilities converges to the maximum allowed constant value, independent of covariates.
-
Distributed Associative Memory via Online Convex Optimization
A distributed online convex optimization protocol for associative memory achieves sublinear regret guarantees and outperforms baselines in experiments.
-
FOAM: Frequency and Operator Error-Based Adaptive Damping Method for Reducing Staleness-Oriented Error for Shampoo
FOAM adaptively controls damping and update frequency in Shampoo based on staleness-oriented error approximation to cut wall-clock time while preserving convergence.
-
The Bayesian Reflex: Online Learning as the Autonomic Nervous System of Modern and Future AI
The Bayesian reflex unifies online Bayesian learning through belief maintenance, Bayes' theorem updates, and exploration-exploitation balancing, with extensions to climate modeling, time series, prime number discovery, and deep architectures.
-
Stochastic Optimization and Data Science
A survey equating offline Monte-Carlo/SAA and online stochastic-approximation sample complexities for convex stochastic optimization arising in statistics and ML.