Source-linked AI summary
Fast Alternating Linearization Methods for Minimizing the Sum of Two Convex Functions
Donald Goldfarb, Shiqian Ma, Katya Scheinberg
TL;DR
The paper studies iteration complexity for convex optimization using alternating-direction methods. It proposes alternating linearization algorithms and reports basic and accelerated iteration bounds, while noting a positive-definiteness constraint in the SICS application.
Problem
The paper focuses on iteration complexity bounds for splitting and alternating-direction algorithms applied to a convex optimization problem.
Method
The algorithms alternately minimize approximations formed by keeping one function unchanged and linearizing the other within an augmented Lagrangian framework.
Results
Basic methods require at most O(1/ε) iterations, while accelerated methods require at most O(1/√ε) iterations to obtain an ε-optimal solution.
Takeaways & Limitations
The proposed methods provide iteration-complexity bounds for alternating-direction optimization and are reported as effective for RPCA problems.
Takeaways & Limitations
In the SICS problem, one objective term is defined only for positive definite matrices, and intermediate iterates may not be positive definite.
Abstract
from arXiv · showhide
We present in this paper first-order 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/ε)$ iterations to obtain an $ε$-optimal solution, while our accelerated (i.e., fast) versions of them require at most $O(1/\sqrtε)$ 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 [21] where the algorithms are Jacobi type methods. Numerical results are reported to support our theoretical conclusions and demonstrate the practical potential of our algorithms.
1. Introduction.
The paper develops alternating linearization methods for minimizing sums of two convex functions, using alternating direction augmented Lagrangian updates when the resulting subproblems are easier to solve. It provides basic and accelerated complexity guarantees, including variants for smooth and partially nonsmooth functions.
- Applications and implementation: The framework applies to examples including compressed sensing, nuclear norm minimization, robust principal component analysis, and sparse inverse covariance selection.These applications use structures such as shrinkage operations, spectral decomposition, or sparse regularization.
- Applications and implementation: The resulting subproblems can be inexpensive: one may reduce to a linear system, while another uses vector or matrix shrinkage.For RPCA, the corresponding subproblems have closed-form matrix- and vector-shrinkage solutions.
- Method: Variable splitting rewrites the problem using x − y = 0, enabling alternating minimization of the augmented Lagrangian.Joint minimization can be difficult, whereas alternating updates lead to subproblems that are often easier to solve.
- Motivation: ISTA and FISTA do not work well for RPCA with two complicated functions, while intermediate SICS iterates may make the gradient undefined and prevent their use.The paper reports that its ADM approach is effective for RPCA and that SICS problems can be efficiently solved by this approach.
- Contributions: For smooth problems, the methods achieve optimal first-order iteration complexity, with bounds similar to and sometimes up to a factor of two better than those in.The paper also presents an algorithm requiring only one function to be smooth.
2. Alternating Linearization Methods.
The paper develops alternating linearization methods from an alternating-direction augmented-Lagrangian framework, including variants for smooth and partially nonsmooth function pairs. These Gauss-Seidel methods have provable convergence and O(1/ε) iteration bounds under Lipschitz-gradient conditions.
- Smoothness requirements: Algorithm 3 requires both f and g to be continuously differentiable, whereas Algorithm 5 handles a nonsmooth g when f is differentiable.The skipping-step variant avoids requiring smoothness of both functions.
- Equivalence results: Algorithms 2, 3, 4, and 5 are equivalent under stated differentiability and step-size conditions.In particular, Algorithms 2 and 3 coincide when both functions are differentiable, Algorithms 3 and 4 when g is Lipschitz smooth with μ ≤ 1/L(g), and Algorithms 4 and 5 when f is differentiable.
- Complexity: O(1/ε) iterations suffice for Algorithm 4 to obtain an ε-optimal solution when ∇f is Lipschitz continuous and the step size satisfies the stated bounds.The bound is at most ⌈C/ε⌉, with C = βL(f)∥x0 − x∗∥2/2 under 1/(βL(f)) ≤ μ ≤ 1/L(f).
- Complexity: O(1/ε) iterations suffice for Algorithm 3 when both gradients are Lipschitz continuous, with a bound smaller than the analogous ISTA bound by a factor of two.The step size must satisfy μ ≤ min{1/L(f), 1/L(g)}; the stated complexity constant is β max{L(f),L(g)}∥x0 − x∗∥2/4.
- Computational cost: The per-iteration costs of Algorithms 3 and 4 are comparable to ISTA when minimizing the augmented-Lagrangian subproblem costs about as much as computing ∇f.The relevant subproblem often involves the same computations as the gradient evaluation.
3. Fast Alternating Linearization Methods.
The paper introduces fast alternating linearization methods that accelerate ALM through Nesterov-like over-relaxation while retaining nearly the same per-iteration work. A skipping-step variant extends the approach to cases where one function is nonsmooth.
- Complexity: O(1/√ε) iterations are required by the fast methods to obtain an ε-optimal solution, while keeping work per iteration almost the same as ALM.The supplied passages state the accelerated complexity and near-preservation of per-iteration work.
- Fast method: FALM is an accelerated version of ALM for minimizing the sum of two convex functions when both functions are differentiable.It is implemented as a Gauss-Seidel method.
- Nonsmooth extension: FALM-S uses skipping steps to handle problems where g is nondifferentiable and is presented as Algorithm 7.The method retains the smoothness requirement on f while avoiding the need for g to be smooth.
- Equivalence: Algorithms 6 and 7 are equivalent when both functions are differentiable, ∇g is Lipschitz continuous, and μ ≤ 1/L(g).Under this condition, no skipping steps occur because F(x_k) ≤ L_μ(x_k,z_k;λ_k) always holds.
- Analysis: The fast method’s analysis accounts for both regular and skipping iterations through sequence bounds involving t_k and the counts of each step type.The proof treats four possible transitions between regular and skipping steps.
4. Comparison of ALM, FALM, ISTA, FISTA, SADAL and SALSA.
The experiments compare basic and accelerated alternating linearization methods with ISTA, FISTA, SADAL, and SALSA on sparse wavelet-based image deblurring problems. Accelerated methods generally achieve better objective values and substantially reduce iterations, while FISTA can remain competitive in CPU time because its iterations are cheaper.
- Experimental setup: The experiments evaluate ALM, FALM, ALM-S, FALM-S, ISTA, FISTA, SADAL, and SALSA on wavelet-based image deblurring problems.The benchmark uses the 256 × 256 Cameraman image with uniform 9 × 9 blur and Gaussian noise; the tested regularizer is g(x) := ρ∥x∥1.
- Experimental setup: Smoothing the ℓ1 term gives gσ a Lipschitz-continuous gradient, enabling ALM and FALM to be applied to the smoothed problem.The smoothed approximation uses parameter σ > 0, with L(gσ) = 1/σ; an ε/2-optimal solution of the smoothed problem is ε-optimal for the original problem under the stated choice of σ.
- Objective values: FALM-S and FALM consistently achieve slightly better objective values than FISTA and much better values than the other tested algorithms after a fixed iteration count.The comparison uses objective values at iterations 10, 50, 100, 200, 500, 800, and 1000 for ρ = 0.01 and ρ = 0.1.
- Objective values: Nesterov-type acceleration substantially speeds up the basic algorithms: FALM-S and FALM outperform ALM-S and ALM, while FISTA outperforms ISTA.Although FISTA or ISTA can be better during early iterations, FALM-S and FALM are better at large iteration counts in the reported tests.
- Runtime and iterations: FISTA takes 35% and 4% more iterations than FALM-S in the last columns of Tables 4.1 and 4.2, but takes 7% more time and 20% less time, respectively.The difference reflects the lower cost per iteration of FISTA relative to FALM-S and FALM.
- Runtime and iterations: FALM-S performs many skipping steps, with 891 and 981 of the first 1000 iterations skipping steps for ρ = 0.01 and ρ = 0.1, respectively.ALM-S performed no skipping steps on either problem; the paper relates FALM-S skipping to its extrapolative Nesterov-like acceleration.
5. Applications.
The paper applies ALM and FALM to RPCA-related problems, using smoothing when required assumptions fail, and reports results on large-scale matrix, video, and covariance applications. These experiments show practical recovery and computational performance, while also noting sensitivity to problem-specific smoothness and parameter conditions.
- RPCA applications: ALM and FALM are applied to RPCA problems using Nesterov-type smoothing when the original functions lack the required smoothness conditions.The smoothed formulations inherit iteration-complexity results because their gradients are Lipschitz continuous.
- Numerical applications: The methods solve large practical problems, including one with roughly 40 million variables and 20 million linear constraints in about three-quarters of an hour.
- RPCA applications: Smoothing both nuclear and ℓ1 norms changes the ε-optimal iteration bounds to O(1/ε^2) for ALM and O(1/ε) for FALM.The degradation follows from the smoothed gradient Lipschitz constant L(fσ) = 1/σ.
- Numerical implementation: In numerical experiments, a continuation update for μ can violate the theoretical step-size requirement, yet ALM and FALM still work well and perform similarly.
- Background extraction: For surveillance video, ALM effectively separates nearly still backgrounds from moving foregrounds, with results summarized against EADM in Table 5.1.ALM is slightly worse than IADM but much faster than EADM in both SVD count and CPU time.
- Matrix completion: For noisy matrix completion, ALM recovers test matrices from limited observations, but small relative errors require many samples because of noise.The iteration count remains nearly constant at around 36 across problem sizes.
6. Conclusion.
The accelerated methods achieve an O(1/√ε) iteration bound with little additional computational effort per iteration, and numerical results demonstrate practical efficiency.
- O(1/√ε) iterations are sufficient for the accelerated methods to obtain an ε-optimal solution.
- The accelerated methods require only a small additional amount of computational effort at each iteration.
- Numerical results on image deblurring, surveillance-video background extraction, and matrix completion with grossly corrupted data demonstrate algorithmic efficiency and practical potential.