Fast alternating linearization methods for minimizing the sum of two convex functions

Donald Goldfarb, Shiqian Ma, Katya ScheinbergMath. Program 2013 · OpenReview

TL;DR

This paper introduces new, faster algorithms for a common type of optimization problem: minimizing the sum of two convex functions. These "fast alternating linearization methods" achieve optimal iteration complexity, meaning they find accurate solutions with the fewest possible steps, making them highly efficient for large-scale problems in areas like signal processing and machine learning.

What Problem Does This Paper Address?

Many real-world problems in fields like machine learning, signal processing, and image analysis can be framed as minimizing a function that's the sum of two convex functions, $f(x) + g(x)$. A key challenge arises when $f(x)$ and $g(x)$ are "difficult" to minimize directly, but simpler "proximal" versions of each function (e.g., minimizing $f(x) + \frac{1}{2\mu}\|x-z\|^2$) are easy to solve. Traditional methods like ISTA and FISTA handle cases where one function is smooth and the other is not, but they can be slow. This paper aims to develop more efficient algorithms, particularly for problems where both functions might be smooth or where specific structures allow for faster convergence. They focus on improving the iteration complexity, which is the number of steps needed to reach a solution within a certain accuracy.

Methods

The authors propose "fast alternating linearization methods" (FALM) based on an "alternating direction augmented Lagrangian" (ADAL) framework. This approach tackles the problem by:

  • Variable Splitting: Rewriting the objective $f(x) + g(x)$ as $f(x) + g(y)$ subject to $x=y$.
  • Augmented Lagrangian: Introducing a penalty term to handle the equality constraint.
  • Alternating Minimization: Instead of minimizing the augmented Lagrangian with respect to $x$ and $y$ jointly (which is hard), they alternate between minimizing with respect to $x$ and then $y$.
  • Linearization: Crucially, at each step, one of the functions is approximated by its linear approximation plus a proximal term, while the other function is minimized exactly. This is where the "alternating linearization" comes in.
  • Gauss-Seidel vs. Jacobi: The proposed methods are "Gauss-Seidel type," meaning information from the current iteration is used immediately in subsequent steps within the same iteration. This contrasts with "Jacobi type" methods that use information only from the previous iteration.
  • Acceleration: The "fast" versions incorporate Nesterov's acceleration technique, which uses momentum-like steps to speed up convergence, achieving an optimal $O(1/\sqrt{\epsilon})$ iteration complexity.
  • Handling Nonsmoothness: They also present variants that can handle cases where one of the functions is not differentiable (nonsmooth), using "skipping steps" to maintain efficiency.

Datasets

The paper uses several standard benchmark problems for evaluation:

  • Image Deblurring: A problem from [17] involving a corrupted Cameraman image.
  • Robust Principal Component Analysis (RPCA): Applied to background extraction from surveillance videos (using datasets from [30]) and matrix completion problems with noisy data.
  • Sparse Inverse Covariance Selection (SICS): A problem from [43].

No new datasets were introduced.

Key Insights and Ideas

  • Optimal Iteration Complexity: The core contribution is achieving $O(1/\sqrt{\epsilon})$ iteration complexity for minimizing the sum of two convex functions, which is theoretically optimal for first-order methods. This means their "fast" algorithms are as efficient as possible in terms of the number of steps.
  • Gauss-Seidel Advantage: The Gauss-Seidel nature of their alternating linearization methods, compared to Jacobi-style methods, allows for better utilization of information within an iteration, leading to faster convergence in practice.
  • Unified Framework: The ADAL framework provides a flexible way to develop both basic ($O(1/\epsilon)$) and accelerated ($O(1/\sqrt{\epsilon})$) algorithms, and to handle variations like smooth vs. nonsmooth functions.
  • Practical Efficiency: Despite theoretical advancements, the algorithms are designed to have minimal computational overhead per iteration, making them practical for large-scale problems.
  • Nesterov Smoothing for Nonsmoothness: For problems where functions are inherently nonsmooth (like $l_1$ norm), they demonstrate how Nesterov's smoothing technique can be combined with their methods to achieve good performance.

Key Results

  • Theoretical Guarantees: The paper provides rigorous proofs for the iteration complexity bounds: $O(1/\epsilon)$ for basic methods and $O(1/\sqrt{\epsilon})$ for accelerated methods.
  • Numerical Performance: Experiments on image deblurring, RPCA, and SICS problems show that their proposed algorithms (especially the fast versions like FALM-S) often outperform or are competitive with existing state-of-the-art methods like ISTA, FISTA, SALSA, and EADM, particularly in terms of achieving better objective function values with fewer iterations or less CPU time.
  • Comparison to ISTA/FISTA: The authors highlight that their methods are more effective than ISTA/FISTA for problems like RPCA where both functions are complex, and that their accelerated versions offer a significant speedup.
  • Handling Missing Data: They successfully apply their methods to RPCA with missing data, demonstrating robustness.

Limitations and Future Work

  • Lipschitz Constants: Some algorithms require knowledge of Lipschitz constants for gradients, which might not always be readily available. However, the authors mention that backtracking techniques can be used to estimate these parameters.
  • Computational Cost per Iteration: While the iteration complexity is optimal, the computational cost per iteration can still be significant for very large problems, especially if SVDs are involved (as in RPCA).
  • Further Applications: The paper suggests that their methods are applicable to a broader range of problems that can be formulated as minimizing the sum of two convex functions, including those with linear constraints.
  • Comparison with Other ADMs: While they compare to some ADMs, further comparisons with other advanced ADM variants could be beneficial.
  • Nonsmooth Case Complexity: While they present algorithms for nonsmooth cases, the theoretical complexity bounds for these variants are not as strong as for the smooth cases.

Summary updated

Abstract

We present in this paper alternating linearization algorithms based on an alternating direction augmented Lagrangian approach for minimizing the sum of two convex functions. Our basic methods require at most $${O(1/\epsilon)}$$ iterations to obtain an $${\epsilon}$$ -optimal solution, while our accelerated (i.e., fast) versions of them require at most $${O(1/\sqrt{\epsilon})}$$ iterations, with little change in the computational effort required at each iteration. For both types of methods, we present one algorithm that requires both functions to be smooth with Lipschitz continuous gradients and one algorithm that needs only one of the functions to be so. Algorithms in this paper are Gauss-Seidel type methods, in contrast to the ones proposed by Goldfarb and Ma in (Fast multiple splitting algorithms for convex optimization, Columbia University, 2009) where the algorithms are Jacobi type methods. Numerical results are reported to support our theoretical conclusions and demonstrate the practical potential of our algorithms.
BibTeX
@inproceedings{goldfarb2013fast,
  author = {Donald Goldfarb and Shiqian Ma and Katya Scheinberg},
  title = {{Fast alternating linearization methods for minimizing the sum of two convex functions}},
  booktitle = {Math. Program},
  year = {2013},
  url = {https://openreview.net/forum?id=nTo57G1mqbf},
}
Figure