Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors

2015/12/08 by Samuel B. Hopkins, Hopkins, Samuel B., Tselil Schramm +5 · 5 citations
Computer Science · Mathematics · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #cs.CC #cs.DS #cs.LG #stat.ML

paper · pdf · doi:10.48550/arxiv.1512.02337

62 pages, title changed, to appear at STOC 2016

arxiv created 2016/02/03 · arxiv updated 2016/02/04

Abstract

We consider two problems that arise in machine learning applications: the problem of recovering a planted sparse vector in a random linear subspace and the problem of decomposing a random low-rank overcomplete 3-tensor. For both problems, the best known guarantees are based on the sum-of-squares method. We develop new algorithms inspired by analyses of the sum-of-squares method. Our algorithms achieve the same or similar guarantees as sum-of-squares for these problems but the running time is significantly faster. For the planted sparse vector problem, we give an algorithm with running time nearly linear in the input size that approximately recovers a planted sparse vector with up to constant relative sparsity in a random subspace of \mathbb Rⁿ of dimension up to Ω(√ n). These recovery guarantees match the best known ones of Barak, Kelner, and Steurer (STOC 2014) up to logarithmic factors. For tensor decomposition, we give an algorithm with running time close to linear in the input size (with exponent ≈ 1.086) that approximately recovers a component of a random 3-tensor over \mathbb Rⁿ of rank up to Ω(n^4/3). The best previous algorithm for this problem due to Ge and Ma (RANDOM 2015) works up to rank Ω(n^3/2) but requires quasipolynomial time.

Cited by

• Near-Optimal Tensor PCA via Normalized Stochastic Gradient Ascent with Overparameterization
• Rotated Mean-Field Variational Inference and Iterative Gaussianization
• A large deviation view of stationarized fully lifted blirp interpolation
• Statistical Limits for Finite-Rank Tensor Estimation
• Spectral clustering of network time series via the sample covariance matrix
• Survey on Algorithms for multi-index models

Related

• Dictionary Learning and Tensor Decomposition via the Sum-of-Squares\n Method
• Polynomial-time Tensor Decompositions with Sum-of-Squares
• Fast algorithm for overcomplete order-3 tensor decomposition
• Fast and robust tensor decomposition with applications to dictionary learning
• Tensor principal component analysis via sum-of-squares proofs