Efficiency of Coordinate Descent Methods for Structured Nonconvex Optimization

Qi Deng, Chenghao Lan

TL;DR

This paper introduces a suite of novel coordinate descent (CD) algorithms designed to tackle a challenging class of nonconvex optimization problems common in machine learning. These methods offer improved efficiency and convergence guarantees compared to existing approaches, particularly for problems with complex structures like sparsity-inducing penalties.

What Problem Does This Paper Address?

Many modern machine learning tasks, such as sparse regression and low-rank optimization, can be formulated as minimizing functions with a specific structure: a continuously differentiable term, a simple convex term, and a concave term. This combination leads to nonconvex optimization problems, which are notoriously difficult to solve. Traditional optimization methods often struggle with these problems due to their nonsmoothness, non-convexity, and the sheer scale of data. Existing coordinate descent methods, while scalable, often lack theoretical guarantees for these complex scenarios. This paper aims to bridge this gap by developing efficient and theoretically sound CD algorithms for this challenging problem class.

Methods

The authors propose four main algorithmic contributions:

  1. Randomized Coordinate Subgradient Descent (RCSD): This method extends randomized CD to handle nonsmooth and nonconvex settings. It uses a block composite subgradient mapping to randomly update variables, offering asymptotic convergence to critical points with a sublinear convergence rate.
  2. Randomly Permuted Coordinate Descent (RPCD): This algorithm alternates between linearizing the concave part of the objective and cycling through variables. It guarantees asymptotic convergence to critical points and provides a sublinear complexity rate.
  3. Randomized Proximal Difference-of-Convex (DC) Algorithm (ACPDC): This approach tackles DC problems by using Accelerated Coordinate Descent (ACD) to inexactly solve subproblems. This strategy significantly speeds up convergence, requiring only a few ACD iterations per DC subproblem.
  4. ACD-based Proximal Point Method (ACPP): This method is tailored for weakly convex functions, particularly those with a high Lipschitz constant to negative curvature ratio (ill-conditioned problems). It demonstrates superior complexity compared to conventional gradient methods.

Datasets

The paper evaluates its proposed methods on both synthetic and real-world datasets.

  • Synthetic Data: Generated from a d-dimensional Gaussian distribution with a specific covariance structure.
  • Real-world Datasets:
    • Regression: E2006-tfidf, E2006-log1p, resl-sim, news20.binary, UJIndoorLoc, dexter, mnist.
  • Classification: The paper mentions classification problems but focuses experiments on regression and classification tasks using the mentioned datasets.

The paper also discusses the use of smoothed $l_1$ loss with SCAD penalty, which involves approximating the $l_1$ loss with a Huber loss function.

Key Insights and Ideas

  • Bridging the Gap for Nonsmooth Nonconvexity: The paper successfully extends the power of coordinate descent to a broader class of nonsmooth and nonconvex problems, which are prevalent in machine learning.
  • Leveraging ACD for Efficiency: By using Accelerated Coordinate Descent (ACD) to solve subproblems within DC and proximal point algorithms, the authors achieve significant speedups, reducing the need for exact solutions.
  • Handling Ill-Conditioned Problems: The development of ACPP specifically addresses weakly convex functions that are "ill-conditioned," a scenario where standard methods often falter.
  • Unified Framework: The proposed algorithms offer a unified approach to tackle various structured nonconvex problems, from sparsity-inducing penalties to weakly convex objectives.

Key Results

  • Theoretical Guarantees: All proposed algorithms (RCSD, RPCD, ACPDC, ACPP) come with theoretical guarantees for asymptotic convergence to critical points.
  • Complexity Bounds: Sublinear convergence rates are established for optimality measures, and improved complexity bounds are shown for ill-conditioned problems.
  • Empirical Superiority: Experiments demonstrate that the proposed CD methods (especially ACPDC and ACPP) outperform gradient-based methods like PDCA and pDCA on various large-scale sparsity-inducing learning problems. Notably, ACPDC achieved the best performance among all tested algorithms in logistic loss classification with largest-k norm penalty.

Limitations and Future Work

  • Ill-Conditioned Problems: While ACPP shows promise for ill-conditioned problems, the paper notes that convergence can slow down when the smoothing parameter $\delta$ decreases.
  • Parameter Tuning: The performance of the algorithms can be sensitive to parameter choices, and the paper mentions tuning parameters like $t$ and $\mu$ as hyperparameters.
  • Future Directions: The paper's conclusion highlights the success of CD methods over gradient-based approaches and suggests that further research into CD for structured nonconvex optimization is warranted. The authors' work lays a strong foundation for future advancements in this area.

Summary updated

Abstract

We propose novel coordinate descent (CD) methods for minimizing nonconvex functions comprising three terms: (i) a continuously differentiable term, (ii) a simple convex term, and (iii) a concave and continuous term. First, by extending randomized CD to nonsmooth nonconvex settings, we develop a coordinate subgradient method that randomly updates block-coordinate variables by using block composite subgradient mapping. This method converges asymptotically to critical points with proven sublinear convergence rate for certain optimality measure. Second, we develop a randomly permuted CD method with two alternating steps: linearizing the concave part and cycling through variables. We prove asymptotic convergence to critical points and establish sublinear complexity rate for objectives with both smooth and concave components. Third, we develop a randomized proximal difference-of-convex (DC) algorithm whereby we solve the subproblem inexactly by accelerated coordinate descent (ACD). Convergence is guaranteed with at most a few number of ACD iterations for each DC subproblem, and convergence complexity is established for identifying certain approximate critical points. Fourth, we further develop the third method to minimize smooth and composite weakly convex functions, and show advantages of the proposed method over gradient methods for ill-conditioned nonconvex functions, namely the weakly convex functions with high Lipschitz constant to negative curvature ratios. Finally, an empirical study on sparsity-inducing learning models demonstrates that CD methods are superior to gradient-based methods for certain large-scale problems.
BibTeX
@inproceedings{deng2020efficiency,
  author = {Qi Deng and Chenghao Lan},
  title = {{Efficiency of Coordinate Descent Methods for Structured Nonconvex Optimization}},
  booktitle = {ECML/PKDD},
  year = {2020},
  url = {https://openreview.net/forum?id=raSw_eF7Df0},
}
Figure