Source-linked AI summary
On the non-ergodic convergence rate of an inexact augmented Lagrangian framework for composite convex programming
Ya-Feng Liu, Xin Liu, Shiqian Ma
TL;DR
The paper considers a linearly constrained composite convex optimization problem. The proposed IAL framework approximately solves each AL subproblem using a weaker, potentially easier-to-check stopping condition and updates the dual variable inexactly. The framework has global convergence when its nonnegative tolerance sequence is summable, and the paper establishes non-ergodic convergence rates under weaker conditions than those in.
Problem
The paper considers a linearly constrained composite convex optimization problem.
Source: §1 · p. 2Method
The proposed IAL framework approximately solves each AL subproblem using a weaker, potentially easier-to-check stopping condition and updates the dual variable inexactly.
Source: §1 · p. 4Results
The framework has global convergence when its nonnegative tolerance sequence is summable, and the paper establishes non-ergodic convergence rates under weaker conditions than those in.
Source: §1 · p. 4Takeaways & Limitations
In the reported basis-pursuit results, the non-ergodic solution is significantly sparser than the ergodic solution, and its sparsity pattern matches the true solution's.
Source: §6 · p. 22The analysis assumes strong duality and a bounded domain for g; boundedness is stated to be mainly for ease of presentation.
Source: §1 · p. 3
Abstract
from arXiv · showhide
In this paper, we consider the linearly constrained composite convex optimization problem, whose objective is a sum of a smooth function and a possibly nonsmooth function. We propose an inexact augmented Lagrangian (IAL) framework for solving the problem. The stopping criterion used in solving the augmented Lagrangian (AL) subproblem in the proposed IAL framework is weaker and potentially much easier to check than the one used in most of the existing IAL frameworks/methods. We analyze the global convergence and the non-ergodic convergence rate of the proposed IAL framework.
1 Introduction
The paper studies linearly constrained composite convex optimization with a smooth term and a possibly nonsmooth term. It proposes an inexact augmented Lagrangian framework with an easier-to-check subproblem stopping condition, and analyzes its global convergence and non-ergodic convergence rate.
1 Introduction
- The problem has a linear constraint, a convex smooth function f with Lipschitz-continuous gradient, and a closed convex function g that may be nonsmooth.An indicator function of a closed convex set is one example of g.Source: §1 · p. 2
- For large problems, exact AL-subproblem solutions can be expensive, leaving the exact dual gradient unavailable and motivating inexact methods.Prior IAL work had primarily analyzed ergodic rates; non-ergodic rate analysis had been missing for a long time.Source: §1 · p. 3
- The analysis assumes strong duality and a bounded domain for g; the paper says boundedness is mainly for ease of presentation.It notes that a bounded set containing a solution can be used to restrict g's domain in many applications.Source: §1 · pp. 3–4
- The proposed IAL framework uses a weaker, potentially easier-to-check AL-subproblem termination condition and establishes global convergence and non-ergodic convergence rates.The rate analysis shows how subproblem error affects convergence.Source: §1 · p. 4
- Non-ergodic analysis studies the algorithm's iterates rather than weighted averages; these iterates can retain solution structure such as sparsity.For basis pursuit, the paper reports that the last iterate is much sparser than the average of all iterates.Source: §1 · p. 4
2 The IAL framework
The IAL framework alternates an inexact AL-subproblem solve with an inexact dual gradient-ascent update. Its stopping rule is designed to be easier to check, while the choice of tolerance trades inner computational cost against gradient approximation error.
2 The IAL framework
- Each iteration approximately solves the AL subproblem until (1.11) holds, then updates the dual variable with an inexact gradient-ascent step.The framework specifies no single required inner solver.Source: §2 · p. 5
- Smaller ηk requires more computation to find an acceptable subproblem point, while larger ηk increases gradient approximation error and may slow convergence or cause divergence.The tolerance sequence balances inner-solve cost against convergence behavior.Source: §2 · p. 5
- Accelerated proximal-gradient and Frank-Wolfe methods can solve the AL subproblem inexactly; Frank-Wolfe generally takes more iterations but has cheaper iterations.The paper analyzes particular choices of both methods.Source: §2 · pp. 6, 10
- For the general composite-minimization case, the paper's result improves the referenced bound by a factor of two.The text identifies this as an improvement over the bound associated with Nesterov's result.Source: §2 · p. 10
3 Global convergence
The paper establishes global convergence for the proposed IAL framework under a summable tolerance sequence. Its analysis connects approximate and exact dual quantities, and the resulting conditions are weaker than classical conditions cited for the framework.
3 Global convergence
- The global-convergence result is independent of the method used to find each approximate AL-subproblem solution.The framework's stopping condition can be replaced by another condition if it implies the bounds used in the analysis.Source: §3 · p. 10
- The analysis extends lemmas previously proved for smooth objectives to composite nonsmooth objectives, bounding dual-function values and the error between exact and approximate dual gradients.The paper identifies these bounds as crucial to its global-convergence and non-ergodic-rate results.Source: §3 · p. 10
- Theorem 3.4 shows global convergence of Algorithm 1 under conditions (1.11) and (3.10), while the IAL framework assumes the nonnegative sequence {ηk} is summable.The paper describes these conditions as weaker than classical conditions (1.9) and (3.10) in, since (1.9) implies (1.11).Source: §3 · pp. 10, 14
4 Non-ergodic convergence rate
The section establishes non-ergodic convergence-rate results for the IAL framework. The rate of δk depends on the slower of two terms, τ1 and ηk.
4 Non-ergodic convergence rate
- The rate of δk is determined by the slower of the two terms τ1 and ηk.Source: §4 · p. 15
- When ηk = 0 for all k ≥ 1, Algorithm 1 reduces to exact dual gradient ascent and achieves an O(1/k) convergence rate.Source: §4 · p. 15
- For the positive tolerance sequence chosen as in (4.6), Theorem 4.3 provides a non-ergodic convergence-rate result for Algorithm 1.Source: §4 · pp. 14–16
- Theorem 4.6 gives an iteration-complexity bound for reaching an ε-optimal solution using Algorithm 2 or 3 to solve AL subproblems under (1.11).Source: §4 · p. 19
5 Comparisons with existing works [16, 23]
The paper contrasts its IAL framework with methods in and [23] in problem scope, subproblem stopping rules, convergence guarantees, and algorithm design. Its framework supports general composite objectives and non-ergodic convergence results while retaining a dual-variable convergence guarantee.
5 Comparisons with existing works [16, 23]
- Unlike, which is designed for g(x) = IndX(x), the IAL framework addresses problem (1.1) with a general composite g(x), approximately solving subproblem (2.1) until (1.11), easier to check than (1.9).Source: §5 · p. 20
- For exact solutions, requires solving every AL subproblem exactly, whereas this framework allows tolerances η_i of order O(1/i^2).Source: §5 · p. 20
- The method in [23] addresses a class of convex conic problems, while the paper presents its framework for linearly constrained composite convex programming.Source: §5 · p. 20
- With summable error tolerances, this IAL framework has global convergence, whereas the inexact gradient augmented Lagrangian method in [23] lacks that guarantee because it uses a positive accuracy constant δ.Source: §5 · p. 21
- The paper's rates for dual objective values, primal infeasibility, and primal objective values concern non-ergodic solutions, unlike the ergodic results in [23].Source: §5 · p. 21
- Unlike the penalty method underlying [23]'s complexity result, which does not update the dual variable, this IAL method updates it and guarantees its convergence.The paper also distinguishes the dual-variable update formulas used by the two methods.Source: §5 · p. 21
- The paper's ε-optimality definition is a perturbation of the KKT conditions that includes the dual variable, unlike the definition in [23].Source: §5 · p. 21
6 Numerical results
In basis-pursuit experiments, IAL was much faster than EAL while producing comparable solution quality, and its non-ergodic solutions were sparser than the ergodic ones. The authors report the same qualitative pattern on larger instances.
6 Numerical results
- The small-instance experiments used 10 random basis-pursuit instances with m = 60, n = 100, and sparsity s = 15.The methods ran for 200 dual iterations from zero initial primal and dual variables; proximal gradient solved the AL subproblems.Source: §6 · pp. 21–22
- The reported measures included runtime, relative solution error, constraint residual, objective-value error, and sparsity for non-ergodic and ergodic outputs.Source: §6 · p. 22
- For both IAL and EAL, non-ergodic solutions were significantly sparser than ergodic solutions, and their sparsity patterns matched the true solution.Source: §6 · p. 22
- On larger basis-pursuit instances, the authors report the same pattern: IAL was faster than EAL, and non-ergodic solutions were sparser than ergodic ones.Source: §6 · p. 22
- IAL was much faster than EAL, with comparable relerr, resi, and objerr and no evidence that either method had better solution quality.This comparison covers the Table 6.1 instances; even in the last 100 iterations, when IAL's subproblems were solved slightly more accurately than EAL's, it remained faster.Source: §6 · p. 22, Table 6.1 · p. 23