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

arXiv: https://arxiv.org/abs/2111.06826 · HTML: https://mlsanity.com/paper/2111.06826/

## 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 (most cited first, 15 of 15)

- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [SGD: General Analysis and Improved Rates](https://mlsanity.com/paper/1901.09401/) (2019)
- [Better Theory for SGD in the Nonconvex World](https://mlsanity.com/paper/2002.03329/) (2020)
- [Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence](https://mlsanity.com/paper/2002.10542/) (2020)
- [Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)](https://mlsanity.com/paper/1306.2119/) (2013)
- [Relatively-Smooth Convex Optimization by First-Order Methods, and Applications](https://mlsanity.com/paper/1610.05708/) (2016)
- [Relative Loss Bounds for On-line Density Estimation with the Exponential Family of Distributions](https://mlsanity.com/paper/1301.6677/) (2013)
- [Generalized Self-Concordant Functions: A Recipe for Newton-Type Methods](https://mlsanity.com/paper/1703.04599/) (2017)
- [Finite-sample analysis of M-estimators using self-concordance](https://mlsanity.com/paper/1810.06838/) (2018)
- [Stochastic Mirror Descent: Convergence Analysis and Adaptive Variants via the Mirror Stochastic Polyak Stepsize](https://mlsanity.com/paper/2110.15412/) (2021)
- [Fast Stochastic Bregman Gradient Methods: Sharp Analysis and Variance Reduction](https://mlsanity.com/paper/2104.09813/) (2021)
- [Homeomorphic-Invariance of EM: Non-Asymptotic Convergence in KL Divergence for Exponential Families via Mirror Descent](https://mlsanity.com/paper/2011.01170/) (2020)
- [The entropic barrier: a simple and optimal universal self-concordant barrier](https://mlsanity.com/paper/1412.1587/) (2014)
- [Fastest Rates for Stochastic Mirror Descent Methods](https://mlsanity.com/paper/1803.07374/) (2018)
- [An Analysis of the Adaptation Speed of Causal Models](https://mlsanity.com/paper/2005.09136/) (2020)

## 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.