mlsanityData to 14 Oct 2026

Convergence Rates for the MAP of an Exponential Family and Stochastic Mirror Descent -- an Open Problem

arXiv 2111.06826 ↗First posted 12 Nov 2021stat.ML cs.LG math.STcited by 0

Not on the map. Why?

Abstract (arXiv)

We consider the problem of upper bounding the expected log-likelihood sub-optimality of the maximum likelihood estimate (MLE), or a conjugate maximum a posteriori (MAP) for an exponential family, in a non-asymptotic way. Surprisingly, we found no general solution to this problem in the literature. In particular, current theories do not hold for a Gaussian or in the interesting few samples regime. After exhibiting various facets of the problem, we show we can interpret the MAP as running stochastic mirror descent (SMD) on the log-likelihood. However, modern convergence results do not apply for standard examples of the exponential family, highlighting holes in the convergence literature. We believe solving this very fundamental problem may bring progress to both the statistics and optimization communities.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 15 of its 42 references that are in the map. First posted on arXiv 12 Nov 2021.

Builds on

15 of 42 references.

References · 15

  1. 2014Convex Optimization: Algorithms and Complexitycited by 575
  2. 2019SGD: General Analysis and Improved Ratescited by 207
  3. 2020Better Theory for SGD in the Nonconvex Worldcited by 158
  4. 2020Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergencecited by 137
  5. 2013Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)cited by 111
  6. 2016Relatively-Smooth Convex Optimization by First-Order Methods, and Applicationscited by 108
  7. 2013Relative Loss Bounds for On-line Density Estimation with the Exponential Family of Distributionscited by 60
  8. 2017Generalized Self-Concordant Functions: A Recipe for Newton-Type Methodscited by 33
  9. 2018Finite-sample analysis of M-estimators using self-concordancecited by 30
  10. 2021Stochastic Mirror Descent: Convergence Analysis and Adaptive Variants via the Mirror Stochastic Polyak Stepsizecited by 22
  11. 2021Fast Stochastic Bregman Gradient Methods: Sharp Analysis and Variance Reductioncited by 19
  12. 2020Homeomorphic-Invariance of EM: Non-Asymptotic Convergence in KL Divergence for Exponential Families via Mirror Descentcited by 18
3 more
  1. 2014The entropic barrier: a simple and optimal universal self-concordant barriercited by 15
  2. 2018Fastest Rates for Stochastic Mirror Descent Methodscited by 14
  3. 2020An Analysis of the Adaptation Speed of Causal Modelscited by 9

Built on by

Not cited yet.