Linear Convergence of Black-Box Variational Inference: Should We Stick the Landing?

• URL: http://arxiv.org/abs/2307.14642v6
• Date: Tue, 18 Jun 2024 21:33:56 GMT
• Title: Linear Convergence of Black-Box Variational Inference: Should We Stick the Landing?
• Authors: Kyurae Kim, Yian Ma, Jacob R. Gardner,
• Abstract summary: Black-box variational inference converges at a geometric (traditionally called "linear") rate under perfect variational family specification. We also improve existing analysis on the regular closed-form entropy gradient estimators.
• Score: 14.2377621491791
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We prove that black-box variational inference (BBVI) with control variates, particularly the sticking-the-landing (STL) estimator, converges at a geometric (traditionally called "linear") rate under perfect variational family specification. In particular, we prove a quadratic bound on the gradient variance of the STL estimator, one which encompasses misspecified variational families. Combined with previous works on the quadratic variance condition, this directly implies convergence of BBVI with the use of projected stochastic gradient descent. For the projection operator, we consider a domain with triangular scale matrices, which the projection onto is computable in $\Theta(d)$ time, where $d$ is the dimensionality of the target posterior. We also improve existing analysis on the regular closed-form entropy gradient estimators, which enables comparison against the STL estimator, providing explicit non-asymptotic complexity guarantees for both.

Related papers

• Refined Risk Bounds for Unbounded Losses via Transductive Priors [58.967816314671296]
  We revisit the sequential variants of linear regression with the squared loss, classification problems with hinge loss, and logistic regression. Our key tools are based on the exponential weights algorithm with carefully chosen transductive priors.
  arXiv  Detail & Related papers  (2024-10-29T00:01:04Z)
• Multivariate root-n-consistent smoothing parameter free matching estimators and estimators of inverse density weighted expectations [51.000851088730684]
  We develop novel modifications of nearest-neighbor and matching estimators which converge at the parametric $sqrt n $-rate. We stress that our estimators do not involve nonparametric function estimators and in particular do not rely on sample-size dependent parameters smoothing.
  arXiv  Detail & Related papers  (2024-07-11T13:28:34Z)
• Transformers as Support Vector Machines [54.642793677472724]
  We establish a formal equivalence between the optimization geometry of self-attention and a hard-margin SVM problem. We characterize the implicit bias of 1-layer transformers optimized with gradient descent. We believe these findings inspire the interpretation of transformers as a hierarchy of SVMs that separates and selects optimal tokens.
  arXiv  Detail & Related papers  (2023-08-31T17:57:50Z)
• On the Convergence of Black-Box Variational Inference [16.895490556279647]
  We provide the first convergence guarantee for full black-box variational inference (BBVI) Our results hold for log-smooth posterior densities with and without strong log-concavity and the location-scale variational family.
  arXiv  Detail & Related papers  (2023-05-24T16:59:50Z)
• Convergence of Adam Under Relaxed Assumptions [72.24779199744954]
  We show that Adam converges to $epsilon$-stationary points with $O(epsilon-4)$ gradient complexity under far more realistic conditions. We also propose a variance-reduced version of Adam with an accelerated gradient complexity of $O(epsilon-3)$.
  arXiv  Detail & Related papers  (2023-04-27T06:27:37Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  This paper shows that graph spectral embedding using the random walk Laplacian produces vector representations which are completely corrected for node degree. In the special case of a degree-corrected block model, the embedding concentrates about K distinct points, representing communities.
  arXiv  Detail & Related papers  (2021-05-03T16:36:27Z)
• Last iterate convergence of SGD for Least-Squares in the Interpolation regime [19.05750582096579]
  We study the noiseless model in the fundamental least-squares setup. We assume that an optimum predictor fits perfectly inputs and outputs $langle theta_*, phi(X) rangle = Y$, where $phi(X)$ stands for a possibly infinite dimensional non-linear feature map.
  arXiv  Detail & Related papers  (2021-02-05T14:02:20Z)
• Inference on the change point in high dimensional time series models via plug in least squares [2.7718973516070684]
  We study a plug in least squares estimator for the change point parameter where change is in the mean of a high dimensional random vector. We obtain sufficient conditions under which this estimator possesses sufficient adaptivity against plug in estimates of mean parameters.
  arXiv  Detail & Related papers  (2020-07-03T18:08:12Z)
• Nearest Neighbour Based Estimates of Gradients: Sharp Nonasymptotic Bounds and Applications [0.6445605125467573]
  gradient estimation is of crucial importance in statistics and learning theory. We consider here the classic regression setup, where a real valued square integrable r.v. $Y$ is to be predicted. We prove nonasymptotic bounds improving upon those obtained for alternative estimation methods.
  arXiv  Detail & Related papers  (2020-06-26T15:19:43Z)
• Tight Nonparametric Convergence Rates for Stochastic Gradient Descent under the Noiseless Linear Model [0.0]
  We analyze the convergence of single-pass, fixed step-size gradient descent on the least-square risk under this model. As a special case, we analyze an online algorithm for estimating a real function on the unit interval from the noiseless observation of its value at randomly sampled points.
  arXiv  Detail & Related papers  (2020-06-15T08:25:50Z)
• A Random Matrix Analysis of Random Fourier Features: Beyond the Gaussian Kernel, a Precise Phase Transition, and the Corresponding Double Descent [85.77233010209368]
  This article characterizes the exacts of random Fourier feature (RFF) regression, in the realistic setting where the number of data samples $n$ is all large and comparable. This analysis also provides accurate estimates of training and test regression errors for large $n,p,N$.
  arXiv  Detail & Related papers  (2020-06-09T02:05:40Z)

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.