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

By Alekh Agarwal, Sahand N. Negahban, Martin J. Wainwright. 2011

257 citations recorded by the source corpus.

Many statistical $M$-estimators are based on convex optimization problems formed by the combination of a data-dependent loss function with a norm-based regularizer. We analyze the convergence rates of projected gradient and composite gradient methods for solving such problems, working within a high-dimensional framework that allows the data dimension $\pdim$ to grow with (and possibly exceed) the sample size $\numobs$. This high-dimensional structure precludes the usual global assumptions---namely, strong convexity and smoothness conditions---that underlie much of classical optimization analysis. We define appropriately restricted versions of these conditions, and show that they are satisfied with high probability for various statistical models. Under these conditions, our theory guarantees that projected gradient descent has a globally geometric rate of convergence up to the \emph{statistical precision} of the model, meaning the typical distance between the true unknown parameter $\theta^*$ and an optimal solution $\hat{\theta}$. This result is substantially sharper than previous convergence results, which yielded sublinear convergence, or linear convergence only up to the noise level. Our analysis applies to a wide range of $M$-estimators and statistical models, including sparse linear regression using Lasso ($\ell_1$-regularized regression); group Lasso for block sparsity; log-linear models with regularization; low-rank matrix recovery using nuclear norm regularization; and matrix decomposition. Overall, our analysis reveals interesting connections between statistical precision and computational efficiency in high-dimensional estimation.

Subfields: Computational Mechanics, Computer Vision and Pattern Recognition

How researchers see this paper

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

In Computational Mechanics

In Computer Vision and Pattern Recognition

Citations in the corpus

Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition (2016, background): “etry property (RIP) and the solution is suﬃciently sparse. Xiao and Zhang (2013) also assume the RIP property and show linear convergence using a homotopy method that slowly decreases the value of λ. Agarwal et al. (2012) give a linear convergence rate under a modiﬁed restricted strong convexity and”
Guaranteed Matrix Completion via Non-Convex Factorization (2014, background): “Index Terms —Matrix completion, matrix factorization, nonconvex optimization, alternating minimization, SGD, perturbation analysis.”
Distributed Stochastic Variance Reduced Gradient Methods (2015, methodology): “We generate Ai as rows of a N × d random matrix A following the experimental setup in [19, 20].”
A Proximal-Gradient Homotopy Method for the Sparse Least-Squares Problem (2012, methodology): “mine eﬃciently in practice even for the simple noise-free case of basis pursuit. The proof techniques are also diﬀerent, and the analysis of geometric convergence for PGH is more diﬃcult than that of [ANW11], because we have to demonstrate sparsity of all the intermediate solutions in the proximal g”
Phase Retrieval via Wirtinger Flow: Theory and Algorithms (2014, methodology): “Moving away from the phase retrieval problem, we would like to mention some very interesting work on the matrix completion problem using non-convex schemes by Montanari and coauthors [38]–[40], see also [2], [6], [32], [37], [41], [51], [52].”
On the Convergence of a Family of Robust Losses for Stochastic Gradient Descent (2016, unknown): “(Augmented Restricted Smoothness (ARSM)) If there exists a constant β > 0 such that for any i ∈ {1, · · · , n} and w, w̃ ∈ Bd(w ∗, γ), we have gi(w)− gi(w̃)− 〈∇gi(w̃),w − w̃〉 ≤ β 2 ‖w− w̃‖2 (3) then gi satisfies Augmented Restricted Smoothness.”
On the Linear Convergence of the Approximate Proximal Splitting Method for Non-smooth Convex Optimization (2014, background): “That said, by utilizing the so called restricted strong convexity and restricted smoothness (see [1]) instead of an error bound, the authors have established the linear convergence of the proximal splitting algorithm for a broad range optimization problems with non-smooth regularizers such as L 1…”
Challenges of Big Data Analysis (2013, unknown): “We also refer to [101] and [102] for research studies in this direction.”
Regularized M-estimators with nonconvexity: statistical and algorithmic theory for local optima (2013, background): “Such conditions have been discussed in previous literature [9, 1], and involve a lower bound on the remainder in the first-order Taylor expansion of Ln.”
Stochastic Variance Reduced Gradient Methods by Sampling Extra Data with Replacement (2017, methodology): “We generate (ai, bi) following the experimental setup in Agarwal et al. (2012) by choosing a correlation parameter ω ∈ [0, 1].”
Gradient methods for convex minimization: better rates under weaker conditions (2013, unknown): “We believe this has the definition of restricted strong convexity in [1], which extends the ordinary definition by including the relaxation term involving r(x).”
Communication-efficient Sparse Regression (2017, methodology): “To our knowledge, lowest known communication complexity for solving the lasso is at least mpσmax(Σ)σmin(Σ) log 1 , for any desired accuracy & √ s log p n (Agarwal et al., 2012).”
Provable Continual Learning via Sketched Jacobian Approximations (2021, background): “There is a large body of literature which ensures that the solution of a randomly sketched least-squares problem behaves similarly to the solution obtained for the un-perturbed problem (Sarlos, 2006; Agarwal et al., 2012; Pilanci and Wainwright, 2015).”