Source-linked AI summary
Accelerated first-order primal-dual proximal methods for linearly constrained composite convex programming
Yangyang Xu
TL;DR
Structured linearly constrained convex problems motivate accelerated first-order methods because standard first-order methods can converge slowly and their subproblems may be difficult. The paper proposes accelerated linearized ALM and ADMM methods, establishing O(1/t^2) convergence under stated convexity assumptions. Numerical experiments demonstrate acceleration and higher efficiency over existing accelerated methods.
Problem
First-order methods can converge slowly, and subproblems for linearly constrained convex problems may be difficult to solve.
Source: §1 · p. 2Method
The paper proposes accelerated linearized ALM for linearly constrained composite convex problems and accelerated linearized ADMM for two-block structured problems.
Source: §1.4 · pp. 6–7Results
Adaptive-parameter ALM achieves O(1/t^2) under weak convexity, while ADMM achieves O(1/t^2) with strong convexity on one block; experiments report higher efficiency over existing accelerated methods.
Source: §2 · p. 7, §4 · p. 26Takeaways & Limitations
The methods combine acceleration with linearization, enabling easier subproblems while retaining the stated convergence guarantees under their respective assumptions.
Source: §1.4 · p. 7, §2 · p. 7The O(1/t^2) ALM analysis does not permit linearizing the augmented term, which may leave difficult subproblems when the nonsmooth term is complicated.
Source: §4 · p. 26
Abstract
from arXiv · showhide
Motivated by big data applications, first-order methods have been extremely popular in recent years. However, naive gradient methods generally converge slowly. Hence, much efforts have been made to accelerate various first-order methods. This paper proposes two accelerated methods towards solving structured linearly constrained convex programming, for which we assume composite convex objective. The first method is the accelerated linearized augmented Lagrangian method (LALM). At each update to the primal variable, it allows linearization to the differentiable function and also the augmented term, and thus it enables easy subproblems. Assuming merely weak convexity, we show that LALM owns $O(1/t)$ convergence if parameters are kept fixed during all the iterations and can be accelerated to $O(1/t^2)$ if the parameters are adapted, where $t$ is the number of total iterations. The second method is the accelerated linearized alternating direction method of multipliers (LADMM). In addition to the composite convexity, it further assumes two-block structure on the objective. Different from classic ADMM, our method allows linearization to the objective and also augmented term to make the update simple. Assuming strong convexity on one block variable, we show that LADMM also enjoys $O(1/t^2)$ convergence with adaptive parameters. This result is a significant improvement over that in [Goldstein et. al, SIIMS'14], which requires strong convexity on both block variables and no linearization to the objective or augmented term. Numerical experiments are performed on quadratic programming, image denoising, and support vector machine. The proposed accelerated methods are compared to nonaccelerated ones and also existing accelerated methods. The results demonstrate the validness of acceleration and superior performance of the proposed methods over existing ones.
1 Introduction
The introduction motivates easier, faster first-order methods for structured linearly constrained convex problems, then presents accelerated linearized ALM and ADMM approaches. Their assumptions and acceleration strategy distinguish them from prior methods.
1.1 Linearized ALM for linearly constrained composite convex problems
- Linearized ALM approximates the smooth objective term to simplify subproblems, then uses adaptive parameters and a shifted linearization point for acceleration.The paper also allows linearizing the augmented term with a suitable weight matrix.Source: §1.1 · p. 3
1.2 Linearized ADMM for two-block structured problems
- For two-block problems, linearized ADMM adapts parameters and linearizes the smooth objective term and augmented terms to simplify updates.With simple block terms and suitable matrices, both subproblems can have closed-form solutions.Source: §1.2 · p. 4
1.3 Related works
- Prior accelerated ALM methods generally omit objective or augmented-term linearization, while requires strong convexity of both blocks and [26] gives only partial acceleration.The paper relates its approach to, a primal-dual method that is a special case of linearized ADMM on the dual problem.Source: §1.3 · pp. 5–6
1.4 Contributions
- The contributions are full O(1/t^2) acceleration for linearized ALM under weak convexity and for linearized ADMM with strong convexity on one block; experiments report superiority over other accelerated methods.The experiments cover quadratic programming, total variation image denoising, and elastic-net support vector machines.Source: §1.4 · p. 7
2 Convergence analysis
The section analyzes convergence of the accelerated linearized methods, including convergence rates for adaptive and fixed-parameter LALM and LADMM and boundedness and convergence inequalities for accelerated linearized ADMM.
2.2.1 Constant parameters
- With fixed parameters, Algorithm 1 converges to a KKT point at O(1/t); its analysis allows γ∈(0, 2β), rather than requiring β=γ.The theorem uses αk=1 and P≻LfI.Source: §2.2.1 · p. 11
2.2.2 Adaptive parameters
- Adaptive LALM improves its O(1/t) rate to O(1/t²), optimal even without a linear constraint, under weak convexity.This parameter setting does not permit linearizing the augmented term; retaining O(1/t²) convergence while linearizing it requires strong convexity of the objective.Source: §2 · p. 7, §2.2.2 · pp. 12–13
2.3 Analysis of the accelerated linearized ADMM
- With constant parameters, Algorithm 2 has O(1/t) convergence without requiring strong convexity of the objective.This result is stated for βk=γk and fixed proximal matrices.Source: §2.3 · p. 15
- Adaptive LADMM achieves O(1/t²) convergence under strong convexity of the z-part, while allowing linearization of the augmented term.The assumptions require Lipschitz continuity of ∇h and strong convexity of g and h with moduli whose sum is positive.Source: §2 · p. 7, §2.3 · pp. 14, 16
- If P ≻ 0, the proof establishes boundedness of the iterate sequence {(xk, yk, λk)}.This boundedness is used in the subsequent convergence argument.Source: §2.3 · p. 19
- When η > 1, successive multiplier differences vanish, and the update rule yields the associated convergence condition.The proof also derives an objective-gap bound, but the supplied passage truncates its rate.Source: §2.3 · p. 19
- For any multiplier λ, the averaged iterates satisfy an objective-plus-constraint inequality bounded above by φ1/Pt.The proof invokes convexity of F to obtain this inequality.Source: §2.3 · p. 19
3 Numerical results
The experiments compare the proposed methods with fixed-parameter and existing accelerated methods across quadratic programming, image denoising, and elastic-net support vector machines. Adaptive variants outperform fixed-parameter counterparts in the reported comparisons, while results against other methods vary by task.
3.1 Quadratic programming
- Adaptive-parameter ALM performs significantly better than fixed-parameter ALM on both objective distance and feasibility violation.Source: §3.1 · p. 20, Figure 1 · p. 20
- At 10^-6 subproblem tolerance, restarted ALALM reaches almost machine accuracy; FISTA [1] reaches an accurate solution only at 10^-10 with Gaussian B.The comparisons include Gaussian- and uniform-distribution B; ALALM is reported as more stable than FISTA across tolerances.Source: §3.1 · p. 21, Figure 2 · p. 21, Figure 3 · p. 22
3.2 Image denoising
- Adaptive-parameter ADMM outperforms its fixed-parameter counterpart; Chambolle–Pock leads initially, but accelerated ADMM later catches up and surpasses it.On the Cameraman image, the denoised result after 200 iterations has PSNR 33.29, versus 25.62 for the noisy image.Source: §3.2 · p. 23, Figure 5 · p. 24, Figure 4 · p. 24
3.3 Elastic net regularized support vector machine
- Accelerated linearized ADMM performs significantly better than its nonaccelerated counterpart, while nonaccelerated linearized ADMM is comparable to classic nonlinearized ADMM.Source: §3.3 · p. 26, Figure 6 · p. 26
4 Conclusions
The paper proposes two accelerated methods for structured linearly constrained convex programming and establishes O(1/t2) convergence under their respective convexity assumptions. Its ALALM analysis leaves open whether the augmented term can be linearized while retaining that rate under the same assumptions.
4 Conclusions
- O(1/t2) convergence is established for ALALM under weak convexity and for ALADMM under strong convexity of one block variable.Numerical experiments demonstrate acceleration and higher efficiency over existing accelerated methods.Source: §4 · p. 26
- Numerical experiments demonstrate the validity of acceleration and higher efficiency over existing accelerated methods.Source: §4 · p. 26
- ALALM's O(1/t2) analysis does not permit linearizing the augmented term, which may complicate subproblems when the nonsmooth term is complicated.Whether that term can be linearized under the same assumptions while retaining O(1/t2) remains open.Source: §4 · p. 26