mlsanityData to 7 Oct 2026

Unconstrained Online Linear Learning in Hilbert Spaces: Minimax Algorithms and Normal Approximations

arXiv 1403.0628 ↗First posted 3 Mar 2014cs.LGcited by 46

Not on the map. Why?

Abstract (arXiv)

We study algorithms for online linear optimization in Hilbert spaces, focusing on the case where the player is unconstrained. We develop a novel characterization of a large class of minimax algorithms, recovering, and even improving, several previous results as immediate corollaries. Moreover, using our tools, we develop an algorithm that provides a regret bound of OBig(U √T log(U √T log2 T +1)Big), where U is the L2 norm of an arbitrary comparator and both T and U are unknown to the player. This bound is optimal up to √log log T terms. When T is known, we derive an algorithm with an optimal regret bound (up to constant factors). For both the known and unknown T case, a Normal approximation to the conditional value of the game proves to be the key analysis tool.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 6; 2022: 7; 2023: 9; 2024: 7; 2025: 9; 2026: 8.

46 papers.

Sort:

By area:

  1. 2023Prodigy: An Expeditiously Adaptive Parameter-Free Learnercited by 129
  2. 2023Learning-Rate-Free Learning by D-Adaptationcited by 113
  3. 2022Making SGD Parameter-Freecited by 50
  4. 2021Tight Concentrations and Confidence Sequences from the Regret of Universal Portfoliocited by 42
  5. 2023DoWG Unleashed: An Efficient Universal Parameter-Free Gradient Descent Methodcited by 35
  6. 2021Parameter-free Stochastic Optimization of Variationally Coherent Functionscited by 27
  7. 2022PDE-Based Optimal Strategy for Unconstrained Online Learningcited by 27
  8. 2022Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Banditscited by 22
  9. 2023Stochastic Nonsmooth Convex Optimization with Heavy-Tailed Noises: High-Probability Bound, In-Expectation Rate and Initial Distance Adaptationcited by 20
  10. 2023Normalized Gradients for Allcited by 18
  11. 2024Fast TRAC: A Parameter-Free Optimizer for Lifelong Reinforcement Learningcited by 16
  12. 2021Adversarial Tracking Control via Strongly Adaptive Online Learning with Memorycited by 14
34 more
  1. 2024Discounted Adaptive Online Learning: Towards Better Regularizationcited by 12
  2. 2024How Free is Parameter-Free Stochastic Optimization?cited by 12
  3. 2023Unconstrained Dynamic Regret via Sparse Codingcited by 11
  4. 2024The Price of Adaptivity in Stochastic Convex Optimizationcited by 11
  5. 2022Exploiting the Curvature of Feasible Sets for Faster Projection-Free Online Learningcited by 10
  6. 2022Optimal Comparator Adaptive Online Learning with Switching Costcited by 9
  7. 2024An Equivalence Between Static and Dynamic Regret Minimizationcited by 9
  8. 2022Implicit Parameter-free Online Learning with Truncated Linear Modelscited by 8
  9. 2023Improving Adaptive Online Learning Using Refined Discretizationcited by 8
  10. 2021Distributed Online Learning for Joint Regret with Communication Constraintscited by 5
  11. 2023SANIA: Polyak-type Optimization Framework Leads to Scale Invariant Stochastic Algorithmscited by 5
  12. 2021On the Initialization for Convex-Concave Min-max Problemscited by 4
  13. 2025Dynamic Regret Reduces to Kernelized Static Regretcited by 4
  14. 2025Sparsity-Based Interpolation of External, Internal and Swap Regretcited by 3
  15. 2023Parameter-free projected gradient descentcited by 2
  16. 2024Structured Prediction in Online Learningcited by 2
  17. 2025LightSAM: Parameter-Agnostic Sharpness-Aware Minimizationcited by 2
  18. 2025Infinite-Dimensional Operator/Block Kaczmarz Algorithms: Regret Bounds and λ-Effectivenesscited by 2
  19. 2026Parameter-free Dynamic Regret: Time-varying Movement Costs, Delayed Feedback, and Memorycited by 2
  20. 2026Parameter-Free Dynamic Regret for Unconstrained Linear Banditscited by 2
  21. 2021Parameter-free Gradient Temporal Difference Learningcited by 1
  22. 2024Learning-Rate-Free Stochastic Optimization over Riemannian Manifoldscited by 1
  23. 2025The Sample Complexity of Parameter-Free Stochastic Convex Optimizationcited by 1
  24. 2025Instance-Optimal Matrix Multiplicative Weight Update and Its Quantum Applicationscited by 1
  25. 2025Decentralized Parameter-Free Online Learningcited by 1
  26. 2026Distance-Aware Muon: Adaptive Step Scaling for Normalized Optimizationcited by 1
  27. 2026Policy Regret for Embedding Model Routing: Contextual Bandits with Low-Rank Expertscited by 1
  28. 2022Parameter-free Online Linear Optimization with Side Information via Universal Coin Bettingcited by 0
  29. 2025Reasoning without Regretcited by 0
  30. 2025A regret minimization approach to fixed-point iterationscited by 0
  31. 2026Operationalizing Stein's Method for Online Linear Optimization: CLT-Based Optimal Tradeoffscited by 0
  32. 2026A Perturbation Approach to Unconstrained Linear Banditscited by 0
  33. 2026Decentralized Parameter-Free Online Learning with Compressed Gossipcited by 0
  34. 2026Zero-order Parameter-free Optimization for LMO-based Methods: Novel Approach for Efficient Fine-tuningcited by 0