mlsanityData to 7 Oct 2026

Online Linear Optimization via Smoothing

arXiv 1405.6076 ↗First posted 23 May 2014cs.LGcited by 23

Not on the map. Why?

Abstract (arXiv)

We present a new optimization-theoretic approach to analyzing Follow-the-Leader style algorithms, particularly in the setting where perturbations are used as a tool for regularization. We show that adding a strongly convex penalty function to the decision rule and adding stochastic perturbations to data correspond to deterministic and stochastic smoothing operations, respectively. We establish an equivalence between "Follow the Regularized Leader" and "Follow the Perturbed Leader" up to the smoothness properties. This intuition leads to a new generic analysis framework that recovers and improves the previous known regret bounds of the class of algorithms commonly known as Follow the Perturbed Leader.

Key facts. Cited by 23 papers in the map (data through 7 Oct 2026). First posted on arXiv 23 May 2014.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 1; 2022: 5; 2023: 4; 2024: 3; 2025: 8; 2026: 2.

23 papers.

Sort:

By area:

  1. 2022Smoothed Online Learning is as Easy as Statistical Learningcited by 50
  2. 2023Optimal Algorithms for Online Convex Optimization with Adversarial Constraintscited by 33
  3. 2022Optimistic No-regret Algorithms for Discrete Cachingcited by 10
  4. 2025Differentiable Generalized Sliced Wasserstein Planscited by 7
  5. 2022On Efficient Online Imitation Learning via Classificationcited by 5
  6. 2023Oracle-Efficient Smoothed Online Learning for Piecewise Continuous Decision Makingcited by 5
  7. 2022Fast Stochastic Composite Minimization and an Accelerated Frank-Wolfe Algorithm under Parallelizationcited by 4
  8. 2025Online Decision-Focused Learningcited by 4
  9. 2026Muon with Finite Newton-Schulz: The Smoothing Benefit in Nonsmooth Nonconvex Optimizationcited by 4
  10. 2024Optimism in the Face of Ambiguity Principle for Multi-Armed Banditscited by 3
  11. 2025Revisiting Follow-the-Perturbed-Leader with Unbounded Perturbations in Bandit Problemscited by 3
  12. 2022Some performance considerations when using multi-armed bandit algorithms in the presence of missing datacited by 1
11 more
  1. 2023On the Regret of Online Edge Service Hostingcited by 1
  2. 2025Efficient and Optimal No-Regret Caching under Partial Observationcited by 1
  3. 2021Structural Causal Models Reveal Confounder Bias in Linear Program Modellingcited by 0
  4. 2023Agnostic Interactive Imitation Learning: New Theory and Practical Algorithmscited by 0
  5. 2024On The Statistical Representation Properties Of The Perturb-Softmax And The Perturb-Argmax Probability Distributionscited by 0
  6. 2024On the Regret of Coded Caching with Adversarial Requestscited by 0
  7. 2025Bayesian Algorithms for Adversarial Online Learning: from Finite to Infinite Action Spacescited by 0
  8. 2025Optimistic Learning for Communication Networkscited by 0
  9. 2025Self-Concordant Perturbations for Linear Banditscited by 0
  10. 2025Prediction with Expert Advice under Local Differential Privacycited by 0
  11. 2026Smooth Learning with Hard Constraints via Legendre-Regularized Policiescited by 0