mlsanityData to 7 Oct 2026

Relative Loss Bounds for On-line Density Estimation with the Exponential Family of Distributions

arXiv 1301.6677 ↗First posted 23 Jan 2013cs.LG stat.MLcited by 59

Not on the map. Why?

Abstract (arXiv)

We consider on-line density estimation with a parameterized density from the exponential family. The on-line algorithm receives one example at a time and maintains a parameter that is essentially an average of the past examples. After receiving an example the algorithm incurs a loss which is the negative log-likelihood of the example w.r.t. the past parameter of the algorithm. An off-line algorithm can choose the best parameter based on all the examples. We prove bounds on the additional total loss of the on-line algorithm over the total loss of the off-line algorithm. These relative loss bounds hold for an arbitrary sequence of examples. The goal is to design algorithms with the best possible relative loss bounds. We use a certain divergence to derive and analyze the algorithms. This divergence is a relative entropy between two exponential distributions.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 13; 2022: 10; 2023: 9; 2024: 9; 2025: 8; 2026: 10.

59 papers.

Sort:

  1. 2021The Bayesian Learning Rulecited by 95
  2. 2021Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizabilitycited by 44
  3. 2021Optimal Dynamic Regret in Exp-Concave Online Learningcited by 39
  4. 2023Oracle Efficient Online Multicalibration and Omnipredictioncited by 36
  5. 2021Online Learning with Optimism and Delaycited by 33
  6. 2022Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regressioncited by 30
  7. 2022Smooth Calibration, Leaky Forecasts, Finite Recall, and Nash Dynamicscited by 22
  8. 2024ConjNorm: Tractable Density Estimation for Out-of-Distribution Detectioncited by 22
  9. 2021Distribution-Free Robust Linear Regressioncited by 19
  10. 2022Fast Rates in Pool-Based Batch Active Learningcited by 15
  11. 2022"Calibeating": Beating Forecasters at Their Own Gamecited by 14
  12. 2022Scale-free Unconstrained Online Learning for Curved Lossescited by 13
38 more
  1. 2021Mixability made efficient: Fast online multiclass logistic regressioncited by 12
  2. 2022Bilinear Exponential Family of MDPs: Frequentist Regret Bound with Tractable Exploration and Planningcited by 12
  3. 2023Unconstrained Dynamic Regret via Sparse Codingcited by 11
  4. 2021Stochastic Online Linear Regression: the Forward Algorithm to Replace Ridgecited by 10
  5. 2023Likelihood Ratio Confidence Sets for Sequential Decision Makingcited by 10
  6. 2024Online Linear Regression in Dynamic Environments via Discountingcited by 10
  7. 2022Quasi-Newton Steps for Efficient Online Exp-Concave Optimizationcited by 9
  8. 2023High-Probability Risk Bounds via Sequential Predictorscited by 9
  9. 2025Confidence Sequences for Generalized Linear Models via Regret Analysiscited by 9
  10. 2022A Regret-Variance Trade-Off in Online Learningcited by 7
  11. 2021Statistically Near-Optimal Hypothesis Selectioncited by 6
  12. 2023Oracle Efficient Algorithms for Groupwise Regretcited by 6
  13. 2024No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimizationcited by 6
  14. 2025Exploiting Curvature in Online Convex Optimization with Delayed Feedbackcited by 6
  15. 2021Online nonparametric regression with Sobolev kernelscited by 5
  16. 2022Optimal Online Generalized Linear Regression with Stochastic Noise and Its Application to Heteroscedastic Banditscited by 5
  17. 2024Predictive Linear Online Tracking for Unknown Targetscited by 5
  18. 2025Universal Learning of Nonlinear Dynamicscited by 5
  19. 2025Dynamic Regret Reduces to Kernelized Static Regretcited by 4
  20. 2021Fast approximations of the Jeffreys divergence between univariate Gaussian mixture models via exponential polynomial densitiescited by 3
  21. 2021Expert Aggregation for Financial Forecastingcited by 3
  22. 2023Local Risk Bounds for Statistical Aggregationcited by 3
  23. 2023Online Infinite-Dimensional Regression: Learning Linear Operatorscited by 3
  24. 2024A Rate-Distortion View of Uncertainty Quantificationcited by 3
  25. 2023Divergences induced by dual subtractive and divisive normalizations of exponential families and their convex deformationscited by 2
  26. 2024Online Learning with Unknown Constraintscited by 2
  27. 2026Spectral Filtering for Complex Linear Dynamical Systemscited by 2
  28. 2026Dynamic Regret via Discounted-to-Dynamic Reduction with Applications to Curved Losses and Adam Optimizercited by 2
  29. 2022Spatially Adaptive Online Prediction of Piecewise Regular Functionscited by 1
  30. 2023Online Learning for Equilibrium Pricing in Markets under Incomplete Informationcited by 1
  31. 2024sc-OTGM: Single-Cell Perturbation Modeling by Solving Optimal Mass Transport on the Manifold of Gaussian Mixturescited by 1
  32. 2025Random feature-based double Vovk-Azoury-Warmuth algorithm for online multi-kernel learningcited by 1
  33. 2025A hierarchical Vovk-Azoury-Warmuth forecaster with discounting for online regression in RKHScited by 1
  34. 2026Self-Normalized Martingales and Uniform Regret Bounds for Linear Regressioncited by 1
  35. 2026The Power of Second Order Methods for Sequence Preconditioningcited by 1
  36. 2021On Learning to Rank Long Sequences with Contextual Banditscited by 0
  37. 2021Convergence Rates for the MAP of an Exponential Family and Stochastic Mirror Descent -- an Open Problemcited by 0
  38. 2024Multivariate Online Linear Regression for Hierarchical Forecastingcited by 0

50 most cited of 59 All 59 (JSON)