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

Abstract

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.

23 pages, 16 figures, including Supplementary Material

References in corpus (3)

• Phase transition in the detection of modules in sparse networks
• A statistical model for tensor PCA
• Algorithmic thresholds for tensor PCA

Cited by in corpus (11)

• Computational Barriers to Estimation from Low-Degree Polynomials
• Limits and performances of algorithms based on simulated annealing in solving sparse hard inference problems
• Online stochastic gradient descent on non-convex losses from high-dimensional inference
• Landscape Complexity for the Empirical Risk of Generalized Linear Models
• Estimating Rank-One Spikes from Heavy-Tailed Noise via Self-Avoiding Walks
• Statistical Query Lower Bounds for Tensor PCA
• Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials
• Some Remarks on Replicated Simulated Annealing
• Long Random Matrices and Tensor Unfolding
• Efficient approximation of branching random walk Gibbs measures
• Gradient descent dynamics and the jamming transition in infinite dimensions