Learning Polynomials of Few Relevant Dimensions

Abstract

Polynomial regression is a basic primitive in learning and statistics. In its most basic form the goal is to fit a degree $d$ polynomial to a response variable $y$ in terms of an $n$-dimensional input vector $x$. This is extremely well-studied with many applications and has sample and runtime complexity $\Theta (n^d)$. Can one achieve better runtime if the intrinsic dimension of the data is much smaller than the ambient dimension $n$? Concretely, we are given samples $(x,y)$ where $y$ is a degree at most $d$ polynomial in an unknown $r$-dimensional projection (the relevant dimensions) of $x$. This can be seen both as a generalization of phase retrieval and as a special case of learning multi-index models where the link function is an unknown low-degree polynomial. Note that without distributional assumptions, this is at least as hard as junta learning. In this work we consider the important case where the covariates are Gaussian. We give an algorithm that learns the polynomial within accuracy $\epsilon$ with sample complexity that is roughly $N=O_{r,d}(n{\log }^2(1/\epsilon )(\log n{)}^d)$ and runtime $O_{r,d}(N{n}^2)$. Prior to our work, no such results were known even for the case of $r=1$. We introduce a new filtered PCA approach to get a warm start for the true subspace and use geodesic SGD to boost to arbitrary accuracy; our techniques may be of independent interest, especially for problems dealing with subspace recovery or analyzing SGD on manifolds.

64 pages

References in corpus (14)

• An algebraic characterization of injectivity in phase retrieval
• Sever: A Robust Meta-Algorithm for Stochastic Optimization
• Beating the Perils of Non-Convexity: Guaranteed Training of Neural Networks using Tensor Methods
• Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method
• Learning One-hidden-layer Neural Networks with Landscape Design
• Riemannian SVRG: Fast Stochastic Optimization on Riemannian Manifolds
• Tensor principal component analysis via sum-of-squares proofs
• A new algorithm for estimating the effective dimension-reduction subspace
• Learning Neural Networks with Two Nonlinear Layers in Polynomial Time
• Structure from Local Optima: Learning Subspace Juntas via Higher Order PCA
• Learning Two Layer Rectified Neural Networks in Polynomial Time
• On Stein's Identity and Near-Optimal Estimation in High-dimensional Index Models
• A note on concentration inequality for vector-valued martingales with weak exponential-type tails
• One-bit compressed sensing with non-Gaussian measurements

Cited by in corpus (3)

• Towards Understanding Hierarchical Learning: Benefits of Neural Representations
• Learning Deep ReLU Networks Is Fixed-Parameter Tractable
• Reconstruction Algorithms for Low-Rank Tensors and Depth-3 Multilinear Circuits