# How to iron out rough landscapes and get optimal performances: Averaged Gradient Descent and its application to tensor PCA

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 May 2019.

## Built on by (most cited first, 14 of 14)

- [Smoothing the Landscape Boosts the Signal for SGD: Optimal Sample Complexity for Learning Single Index Models](https://mlsanity.com/paper/2305.10633/) (2023)
- [The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics](https://mlsanity.com/paper/2205.09727/) (2022)
- [Survey on Algorithms for multi-index models](https://mlsanity.com/paper/2504.05426/) (2025)
- [Long Random Matrices and Tensor Unfolding](https://mlsanity.com/paper/2110.10210/) (2021)
- [When Random Tensors meet Random Matrices](https://mlsanity.com/paper/2112.12348/) (2021)
- [Tensor cumulants for statistical inference on invariant distributions](https://mlsanity.com/paper/2404.18735/) (2024)
- [On free energy barriers in Gaussian priors and failure of cold start MCMC for high-dimensional unimodal distributions](https://mlsanity.com/paper/2209.02001/) (2022)
- [Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials](https://mlsanity.com/paper/2211.05274/) (2022)
- [A theory of learning data statistics in diffusion models, from easy to hard](https://mlsanity.com/paper/2603.12901/) (2026)
- [Sharp Analysis of Power Iteration for Tensor PCA](https://mlsanity.com/paper/2401.01047/) (2024)
- [Overparametrization bends the landscape: BBP transitions at initialization in simple Neural Networks](https://mlsanity.com/paper/2510.18435/) (2025)
- [Improved high-dimensional estimation with Langevin dynamics and stochastic weight averaging](https://mlsanity.com/paper/2603.06028/) (2026)
- [On maximum-likelihood estimation in the all-or-nothing regime](https://mlsanity.com/paper/2101.09994/) (2021)
- [Selective Multiple Power Iteration: from Tensor PCA to gradient-based exploration of landscapes](https://mlsanity.com/paper/2112.12306/) (2021)

## Abstract (arXiv)

In many high-dimensional estimation problems the main task consists in minimizing a cost function, which is often strongly non-convex when scanned in the space of parameters to be estimated. A standard solution to flatten the corresponding rough landscape consists in summing the losses associated to different data points and obtain a smoother empirical risk. Here we propose a complementary method that works for a single data point. The main idea is that a large amount of the roughness is uncorrelated in different parts of the landscape. One can then substantially reduce the noise by evaluating an empirical average of the gradient obtained as a sum over many random independent positions in the space of parameters to be optimized. We present an algorithm, called Averaged Gradient Descent, based on this idea and we apply it to tensor PCA, which is a very hard estimation problem. We show that Averaged Gradient Descent over-performs physical algorithms such as gradient descent and approximate message passing and matches the best algorithmic thresholds known so far, obtained by tensor unfolding and methods based on sum-of-squares.