Fast global convergence rates of gradient methods for high-dimensional statistical recovery

156 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Escaping From Saddle Points - Online Stochastic Gradient for Tensor Decomposition (2015, background): “For a functionf : Rd → R,∇f and∇2f denote its gradient vector and Hessian matrix.”
Dropping Convexity for Faster Semi-definite Optimization (2015, background): “Finally, in high dimensional settings, often loss function f does not satisfy strong convexity globally, but only on a restricted set of directions; see [59, 2] and Section F for a more detailed discussion.”
Greedy Algorithms for Structurally Constrained High Dimensional Problems (2011, background): “Speciﬁcally, given a set A of very “simple” objects, called atoms, we can say that a vector x is simple (with some low-dimensional structure) if it can be written as a linear combination of few atoms: x = =1 c i a i , where k is small relative to the ambient dimensionality.”
On Solutions of Sparsity Constrained Optimization (2015, methodology): “[3] modified RSC and introduced the notions of restricted strong smoothness (RSS) that suffice to establish global linear convergence of a first-order method for the above problem.”
Compressed Sensing using Generative Models (2017, background): “The problem is also called high-dimensional sparse linear regression and there is vast literature on establishing conditions for different recovery algorithms, different assumptions on the design of A and generalizations of RIP and REC for other structures, see e.g. [6, 33, 1, 30, 3].”