An accelerated stochastic ADMM for nonconvex and nonsmooth finite-sum optimization

Yuxuan Zeng, Zhiguo Wang, Jianchao Bai, Xiaojing ShenAutomatica 2024 · DOI

TL;DR

This paper introduces ASVRG-ADMM, a novel algorithm for solving complex optimization problems common in machine learning that are both "nonconvex" (meaning they have many local minima) and "nonsmooth" (meaning they have sharp corners or kinks). The authors demonstrate that their method achieves faster convergence than existing approaches, both theoretically and empirically, and can even achieve linear convergence rates under certain conditions.

What Problem Does This Paper Address?

Many real-world machine learning problems, such as those in image processing, computer vision, and system identification, can be formulated as optimization problems. A common challenge is that these problems often involve a sum of many individual functions (finite-sum optimization) and can be "nonconvex" and "nonsmooth." Traditional optimization methods struggle with these characteristics, especially when dealing with massive datasets. While stochastic methods like ADMM (Alternating Direction Method of Multipliers) have been adapted for these problems, most existing work focuses on convex settings. There's a significant gap in understanding how to efficiently and reliably solve these nonconvex, nonsmooth problems, particularly when incorporating acceleration techniques that have proven effective in other areas. This paper aims to bridge this gap by developing and analyzing an accelerated stochastic ADMM for these challenging optimization landscapes.

Methods

The core contribution is the development of ASVRG-ADMM (Accelerated Stochastic Variance Reduced Gradient ADMM). This algorithm combines several key ideas:

  • Stochastic Variance Reduction (SVRG): This technique reduces the noise inherent in using only a subset of data for gradient calculations, leading to more stable and faster convergence compared to basic stochastic methods.
  • ADMM: This is a powerful framework for solving optimization problems with constraints by breaking them down into smaller, more manageable subproblems.
  • Momentum (Katyusha-type): Inspired by Nesterov's acceleration techniques, this adds a "momentum" term to the updates. This helps the algorithm "overshoot" local minima and accelerate convergence, especially in the later stages of optimization.
  • Potential Energy Function: The authors introduce a novel potential energy function to analyze the algorithm's convergence. This function is designed to decrease monotonically, providing a theoretical basis for convergence.
  • Kurdyka-Lojasiewicz (KL) Property: To establish linear convergence rates (a much faster convergence than sublinear), the authors leverage the KL property, which is a weaker condition than strong convexity and is applicable to a broader class of nonsmooth and nonconvex functions.

Datasets

The paper evaluates ASVRG-ADMM on several standard datasets:

  • Synthetic data: Used for a nonconvex quadratic problem and for comparing different momentum parameters.
  • Real datasets:
    • ijcnn1
    • a9a
    • w8a These datasets are commonly used for evaluating classification algorithms and are employed here for the graph-guided fused Lasso and regularized logistic regression problems.

Key Insights and Ideas

  • Bridging the Gap for Nonconvexity: The paper successfully extends the benefits of accelerated stochastic ADMM to the challenging realm of nonconvex and nonsmooth optimization, a significant step beyond prior work that largely focused on convex settings.
  • Momentum's Role in Nonconvexity: The authors demonstrate that momentum techniques, while sometimes problematic in nonconvex settings due to potential gradient inaccuracies, can be effectively integrated with variance reduction to achieve faster convergence without sacrificing stability.
  • KL Property for Linear Convergence: The use of the KL property is crucial for proving linear convergence rates. This is a key theoretical contribution, as it allows for faster convergence guarantees on a wider range of problems than methods relying solely on strong convexity.
  • Empirical Validation: The numerical experiments consistently show ASVRG-ADMM outperforming state-of-the-art methods, validating the theoretical findings and highlighting the practical benefits of the proposed approach.

Key Results

  • Sublinear Convergence: The proposed ASVRG-ADMM algorithm is theoretically proven to achieve a sublinear convergence rate of $O(1/T)$ for general nonconvex nonsmooth finite-sum optimization problems.
  • Linear Convergence (Almost Sure): Under the additional Kurdyka-Lojasiewicz (KL) property, ASVRG-ADMM is shown to converge almost surely to a stationary solution with a linear convergence rate. This is a significant theoretical achievement for accelerated stochastic ADMM methods.
  • Empirical Performance: Numerical experiments on synthetic and real-world datasets (graph-guided fused Lasso, regularized logistic regression) demonstrate that ASVRG-ADMM consistently outperforms SADMM, SVRG-ADMM, and SAG-ADMM in terms of convergence speed and variance reduction. The paper shows that smaller momentum parameters often lead to better empirical performance.

Limitations and Future Work

  • KL Property Assumption: The theoretical guarantee of linear convergence relies on the Kurdyka-Lojasiewicz (KL) property, which, while applicable to many functions, is not universally satisfied.
  • Parameter Tuning: While the paper explores different momentum parameters, optimal parameter selection can still be a challenge in practice.
  • Future Work: The authors suggest several promising directions:
  • Applying momentum acceleration to other algorithms like SAG-ADMM and SAGA-ADMM.
  • Further theoretical improvements to the convergence rate.
  • Extending ASVRG-ADMM and its theoretical results to distributed optimization settings.
  • Investigating its application to other nonsmooth and nonconvex optimization problems.

Summary updated

BibTeX
@article{zeng2024accelerated,
  author = {Yuxuan Zeng and Zhiguo Wang and Jianchao Bai and Xiaojing Shen},
  title = {{An accelerated stochastic ADMM for nonconvex and nonsmooth finite-sum optimization}},
  journal = {Automatica},
  year = {2024},
  doi = {10.1016/j.automatica.2024.111554},
}
Figure