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

• URL: http://arxiv.org/abs/2111.06826v1
• Date: Fri, 12 Nov 2021 17:18:06 GMT
• Title: Convergence Rates for the MAP of an Exponential Family and Stochastic Mirror Descent -- an Open Problem
• Authors: R\'emi Le Priol, Frederik Kunstner, Damien Scieur, Simon Lacoste-Julien
• Abstract summary: We consider the problem of upper bounding the expected log-likelihood sub-optimality of the maximum likelihood estimate. Surprisingly, we found no general solution to this problem in the literature.
• Score: 33.74484936098467
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Taming Nonconvex Stochastic Mirror Descent with General Bregman Divergence [25.717501580080846]
  This paper revisits the convergence of gradient Forward Mirror (SMD) in the contemporary non optimization setting. For the training, we develop provably convergent algorithms for the problem of linear networks.
  arXiv  Detail & Related papers  (2024-02-27T17:56:49Z)
• Curvature-Independent Last-Iterate Convergence for Games on Riemannian Manifolds [77.4346324549323]
  We show that a step size agnostic to the curvature of the manifold achieves a curvature-independent and linear last-iterate convergence rate. To the best of our knowledge, the possibility of curvature-independent rates and/or last-iterate convergence has not been considered before.
  arXiv  Detail & Related papers  (2023-06-29T01:20:44Z)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  We propose algorithms with high-probability convergence results under less restrictive assumptions. These results justify the usage of the considered methods for solving problems that do not fit standard functional classes in optimization.
  arXiv  Detail & Related papers  (2023-02-02T10:37:23Z)
• The One-Inclusion Graph Algorithm is not Always Optimal [11.125968799758436]
  We provide an in-expectation optimal one-inclusion graph algorithm for Vapnik-Chervonenkis class. We show that the same poor high-probability performance is inherited by several recent prediction strategies.
  arXiv  Detail & Related papers  (2022-12-19T06:49:39Z)
• Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noise [64.85879194013407]
  We prove the first high-probability results with logarithmic dependence on the confidence level for methods for solving monotone and structured non-monotone VIPs. Our results match the best-known ones in the light-tails case and are novel for structured non-monotone problems. In addition, we numerically validate that the gradient noise of many practical formulations is heavy-tailed and show that clipping improves the performance of SEG/SGDA.
  arXiv  Detail & Related papers  (2022-06-02T15:21:55Z)
• Benign Underfitting of Stochastic Gradient Descent [72.38051710389732]
  We study to what extent may gradient descent (SGD) be understood as a "conventional" learning rule that achieves generalization performance by obtaining a good fit training data. We analyze the closely related with-replacement SGD, for which an analogous phenomenon does not occur and prove that its population risk does in fact converge at the optimal rate.
  arXiv  Detail & Related papers  (2022-02-27T13:25:01Z)
• Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems [98.34292831923335]
  Motivated by the problem of online correlation analysis, we propose the emphStochastic Scaled-Gradient Descent (SSD) algorithm. We bring these ideas together in an application to online correlation analysis, deriving for the first time an optimal one-time-scale algorithm with an explicit rate of local convergence to normality.
  arXiv  Detail & Related papers  (2021-12-29T18:46:52Z)
• Fast approximations of the Jeffreys divergence between univariate Gaussian mixture models via exponential polynomial densities [16.069404547401373]
  The Jeffreys divergence is a renown symmetrization of the statistical Kullback-Leibler which is often used in machine learning, signal processing, and information sciences. We propose a simple yet fastarine to approximate the Jeffreys divergence between two GMMs of arbitrary number of components.
  arXiv  Detail & Related papers  (2021-07-13T07:58:01Z)
• Homeomorphic-Invariance of EM: Non-Asymptotic Convergence in KL Divergence for Exponential Families via Mirror Descent [18.045545816267385]
  We show that for common setting of exponential family distributions, viewing EM as a mirror descent algorithm leads to convergence rates in Kullback-Leibler divergence. In contrast to previous works, the analysis is in to the choice of parametrization and holds with minimal assumptions.
  arXiv  Detail & Related papers  (2020-11-02T18:09:05Z)
• Generalized Sliced Distances for Probability Distributions [47.543990188697734]
  We introduce a broad family of probability metrics, coined as Generalized Sliced Probability Metrics (GSPMs) GSPMs are rooted in the generalized Radon transform and come with a unique geometric interpretation. We consider GSPM-based gradient flows for generative modeling applications and show that under mild assumptions, the gradient flow converges to the global optimum.
  arXiv  Detail & Related papers  (2020-02-28T04:18:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.