Decomposable norm minimization with proximal-gradient homotopy algorithm

Reza Eghbali, Maryam FazelComp. Opt. and Appl 2017 · OpenReview

Abstract

We study the convergence rate of the proximal-gradient homotopy algorithm applied to norm-regularized linear least squares problems for a general class of decomposable norms. While high-dimensional objective functions often lack global strong convexity, we demonstrate that the homotopy algorithm—which reduces the regularization parameter $\lambda$ in successive steps—achieves a global linear convergence rate. This is achieved by ensuring iterates remain within a "low-complexity" region where the objective behaves as if it were strongly convex. Our results generalize previous findings for $\ell_1$-regularization to a broader class of structured recovery problems, supported by numerical experiments in low-rank matrix recovery and group sparsity.

Introduction

In modern signal processing and statistical learning, the goal is often to recover a structured signal $x$ from a limited set of noisy linear observations $b = Ax + e$. This is typically framed as a regularized least-squares problem: $$\min_{x} \frac{1}{2}\|Ax - b\|_2^2 + \lambda\|x\|$$ where $\|x\|$ is a structure-inducing norm, such as the $\ell_1$ norm for sparsity or the nuclear norm for low-rank matrices.

A significant hurdle in high-dimensional settings—where the number of variables exceeds the number of samples—is that the measurement matrix $A$ possesses a non-trivial null space. Consequently, the objective function is not globally strongly convex. Standard first-order methods, like the proximal-gradient (PG) algorithm, typically exhibit slow sublinear convergence in these scenarios. While homotopy methods—which solve a sequence of problems with decreasing $\lambda$—have shown empirical success, a rigorous theoretical understanding of their convergence for general norms has been limited.

The Proximal-Gradient Homotopy Algorithm

The homotopy approach avoids solving the difficult target problem directly. Instead, it starts with a large regularization parameter $\lambda_0$ such that the solution is trivial (often $x=0$). It then iteratively reduces $\lambda$ according to a geometric schedule ($\lambda_{k+1} = \eta \lambda_k$ for $\eta \in (0, 1)$). At each stage, a proximal-gradient method is used to solve the sub-problem, using the solution from the previous stage as a warm start.

This strategy is motivated by the observation that for large $\lambda$, the solution is highly structured (e.g., very sparse). By gradually decreasing $\lambda$, the algorithm "tracks" the solution path through a sequence of low-complexity iterates, preventing the optimization from wandering into high-complexity regions where the landscape is less favorable.

Theoretical Foundations: Decomposable Norms and Complexity

To generalize the analysis beyond simple sparsity, the authors utilize two key concepts:

  1. Decomposable Norms: This class of norms includes the $\ell_1$ norm, the group Lasso ($\ell_{1,2}$) norm, and the nuclear norm. A norm is decomposable if it can be separated into components acting on a subspace and its orthogonal complement, allowing for a precise characterization of the "structure" it promotes.
  2. Generalized Cardinality ($K(x)$): The authors introduce $K(x)$ as a measure of complexity. For a vector, $K(x)$ might represent the number of non-zero entries; for a matrix, it represents the rank. A critical theoretical contribution is the proof that $K(x)$ is sublinear ($K(x+y) \leq K(x) + K(y)$), which ensures that the complexity of the iterates does not grow uncontrollably during the optimization process.

Linear Convergence via Restricted Strong Convexity

The core insight of the paper is the interaction between the homotopy path and Restricted Strong Convexity (RSC). While the objective function is not strongly convex everywhere, it often satisfies RSC—meaning it behaves like a strongly convex function when restricted to the set of low-complexity vectors.

The authors prove that if the measurement matrix $A$ satisfies a version of the Restricted Isometry Property (RIP), the homotopy algorithm ensures that all iterates $x^{(t)}$ remain within a low-complexity regime. Because the algorithm stays within this "well-behaved" region, it inherits the fast, linear convergence rate ($O(\kappa^t)$ with $\kappa < 1$) typically reserved for strongly convex problems. This effectively "tricks" the non-convex-like landscape into behaving efficiently.

Numerical Experiments

The theoretical findings were validated using synthetic high-dimensional recovery tasks:

  • Low-Rank Matrix Recovery: Recovering a $300 \times 300$ matrix (rank 10) from 20,000 samples using the nuclear norm.
  • Group Sparsity: Recovering a $50 \times 1000$ matrix with 50 non-zero columns from 18,000 samples using the $\ell_{1,2}$ norm.

In both cases, the proximal-gradient homotopy method reached high-precision solutions (e.g., an objective gap of $10^{-10}$) significantly faster than standard PG or accelerated proximal gradient (APG) methods. The experiments confirmed that the homotopy method maintains much lower iterate complexity (rank or sparsity) during the early stages of optimization, providing the empirical basis for the observed speedup.

Conclusion and Limitations

This work provides a unified theoretical framework for understanding why homotopy methods are so effective for structured recovery. By generalizing the analysis to decomposable norms, the authors show that the "low-complexity path" is a robust phenomenon that enables linear convergence even in the absence of global strong convexity.

However, some limitations remain. The proof relies on RIP constants, which are difficult to verify for deterministic real-world matrices. Additionally, the algorithm's performance is sensitive to the reduction factor $\eta$ and the internal stopping criteria. Future work may involve extending this analysis to non-quadratic loss functions and exploring more automated parameter tuning.

Summary updated

Abstract

We study the convergence rate of the proximal-gradient homotopy algorithm applied to norm-regularized linear least squares problems, for a general class of norms. The homotopy algorithm reduces the regularization parameter in a series of steps, and uses a proximal-gradient algorithm to solve the problem at each step. Proximal-gradient algorithm has a linear rate of convergence given that the objective function is strongly convex, and the gradient of the smooth component of the objective function is Lipschitz continuous. In many applications, the objective function in this type of problem is not strongly convex, especially when the problem is high-dimensional and regularizers are chosen that induce sparsity or low-dimensionality. We show that if the linear sampling matrix satisfies certain assumptions and the regularizing norm is decomposable, proximal-gradient homotopy algorithm converges with a linear rate even though the objective function is not strongly convex. Our result generalizes results on the linear convergence of homotopy algorithm for $$\ell _1$$ ℓ 1 -regularized least squares problems. Numerical experiments are presented that support the theoretical convergence rate analysis.
BibTeX
@inproceedings{eghbali2017decomposable,
  author = {Reza Eghbali and Maryam Fazel},
  title = {{Decomposable norm minimization with proximal-gradient homotopy algorithm}},
  booktitle = {Comp. Opt. and Appl},
  year = {2017},
  url = {https://openreview.net/forum?id=l_oU6mPcyb},
}
Figure