Analysing heavy-tail properties of Stochastic Gradient Descent by means of Stochastic Recurrence Equations

• URL: http://arxiv.org/abs/2403.13868v1
• Date: Wed, 20 Mar 2024 13:39:19 GMT
• Title: Analysing heavy-tail properties of Stochastic Gradient Descent by means of Stochastic Recurrence Equations
• Authors: Ewa Damek, Sebastian Mentemeier,
• Abstract summary: In recent works, it has been observed that heavy tail properties of Gradient Descent (SGD) can be studied in the probabilistic framework of recursions. We will answer several open questions of the quoted paper and extend their results by applying the theory of irreducibleproximal (i-p) matrices.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In recent works on the theory of machine learning, it has been observed that heavy tail properties of Stochastic Gradient Descent (SGD) can be studied in the probabilistic framework of stochastic recursions. In particular, G\"{u}rb\"{u}zbalaban et al. (arXiv:2006.04740) considered a setup corresponding to linear regression for which iterations of SGD can be modelled by a multivariate affine stochastic recursion $X_k=A_k X_{k-1}+B_k$, for independent and identically distributed pairs $(A_k, B_k)$, where $A_k$ is a random symmetric matrix and $B_k$ is a random vector. In this work, we will answer several open questions of the quoted paper and extend their results by applying the theory of irreducible-proximal (i-p) matrices.

Related papers

• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  Single-Index Models are high-dimensional regression problems with planted structure. We show that computationally efficient algorithms, both within the Statistical Query (SQ) and the Low-Degree Polynomial (LDP) framework, necessarily require $Omega(dkstar/2)$ samples.
  arXiv  Detail & Related papers  (2024-03-08T18:50:19Z)
• Probabilistic Unrolling: Scalable, Inverse-Free Maximum Likelihood Estimation for Latent Gaussian Models [69.22568644711113]
  We introduce probabilistic unrolling, a method that combines Monte Carlo sampling with iterative linear solvers to circumvent matrix inversions. Our theoretical analyses reveal that unrolling and backpropagation through the iterations of the solver can accelerate gradient estimation for maximum likelihood estimation. In experiments on simulated and real data, we demonstrate that probabilistic unrolling learns latent Gaussian models up to an order of magnitude faster than gradient EM, with minimal losses in model performance.
  arXiv  Detail & Related papers  (2023-06-05T21:08:34Z)
• Robust Regularized Low-Rank Matrix Models for Regression and Classification [14.698622796774634]
  We propose a framework for matrix variate regression models based on a rank constraint, vector regularization (e.g., sparsity), and a general loss function. We show that the algorithm is guaranteed to converge, all accumulation points of the algorithm have estimation errors in the order of $O(sqrtn)$ally and substantially attaining the minimax rate.
  arXiv  Detail & Related papers  (2022-05-14T18:03:48Z)
• Optimal Online Generalized Linear Regression with Stochastic Noise and Its Application to Heteroscedastic Bandits [88.6139446295537]
  We study the problem of online generalized linear regression in the setting of a generalized linear model with possibly unbounded additive noise. We provide a sharp analysis of the classical follow-the-regularized-leader (FTRL) algorithm to cope with the label noise. We propose an algorithm based on FTRL to achieve the first variance-aware regret bound.
  arXiv  Detail & Related papers  (2022-02-28T08:25:26Z)
• When Random Tensors meet Random Matrices [50.568841545067144]
  This paper studies asymmetric order-$d$ spiked tensor models with Gaussian noise. We show that the analysis of the considered model boils down to the analysis of an equivalent spiked symmetric textitblock-wise random matrix.
  arXiv  Detail & Related papers  (2021-12-23T04:05:01Z)
• A Precise Performance Analysis of Support Vector Regression [105.94855998235232]
  We study the hard and soft support vector regression techniques applied to a set of $n$ linear measurements. Our results are then used to optimally tune the parameters intervening in the design of hard and soft support vector regression algorithms.
  arXiv  Detail & Related papers  (2021-05-21T14:26:28Z)
• Linear-Sample Learning of Low-Rank Distributions [56.59844655107251]
  We show that learning $ktimes k$, rank-$r$, matrices to normalized $L_1$ distance requires $Omega(frackrepsilon2)$ samples. We propose an algorithm that uses $cal O(frackrepsilon2log2fracepsilon)$ samples, a number linear in the high dimension, and nearly linear in the matrices, typically low, rank proofs.
  arXiv  Detail & Related papers  (2020-09-30T19:10:32Z)
• 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)
• Quadruply Stochastic Gaussian Processes [10.152838128195466]
  We introduce a variational inference procedure for training scalable Gaussian process (GP) models whose per-iteration complexity is independent of both the number of training points, $n$, and the number basis functions used in the kernel approximation, $m$. We demonstrate accurate inference on large classification and regression datasets using GPs and relevance vector machines with up to $m = 107$ basis functions.
  arXiv  Detail & Related papers  (2020-06-04T17:06:25Z)
• Asymptotic errors for convex penalized linear regression beyond Gaussian matrices [23.15629681360836]
  We consider the problem of learning a coefficient vector $x_0$ in $RN$ from noisy linear observations. We provide a rigorous derivation of an explicit formula for the mean squared error. We show that our predictions agree remarkably well with numerics even for very moderate sizes.
  arXiv  Detail & Related papers  (2020-02-11T13:43:32Z)

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.