Adaptive ADMM with Spectral Penalty Parameter Selection

1 Introduction

• ADMM decomposes complex optimization problems into simpler subproblems, often solvable in closed form.The passage describes its simplicity, flexibility, and broad applicability.Source: §1 · p. 1
• ADMM efficiency hinges on careful manual selection of a penalty parameter for each problem instance.Adaptive stepsize rules for gradient and proximal-gradient methods can dispense with user oversight and boost performance.Source: §1 · p. 1
• The proposed method adapts Barzilai-Borwein spectral stepsize rules to ADMM and safeguards choices with a curvature-reliability criterion.It analyzes the dual problem, and the resulting algorithm is described as fully automated and fairly insensitive to initial stepsize.Source: §1 · p. 1

2.1 ADMM

• ADMM alternates subproblems for closed, proper, convex objectives under linear constraints, and its penalty sequence is the only free choice with high impact on speed.Source: §2.1 · pp. 1–2

2.2 Parameter tuning and adaptation

• Residual balancing tunes the penalty to keep primal and dual residuals similar, but adaptive-penalty ADMM is not guaranteed to converge unless the penalty is fixed after finitely many iterations.Source: §2.2 · p. 2
• Residual-balancing criteria can be arbitrary under problem rescaling, vary in performance across scalings, and adapt slowly when the initial penalty is far from optimal.Source: §2.2 · p. 2

2.3 Dual interpretation of ADMM

• ADMM for problem (1) is equivalent to Douglas-Rachford splitting for its dual, providing the dual interpretation used by the proposed approach.Source: §2.3 · pp. 2–3

2.4 Spectral stepsize selection

• Barzilai-Borwein spectral selection sets the stepsize as the inverse of a scalar curvature approximation estimated across the previous step.Source: §2.4 · p. 3

3.1 Spectral stepsize for DRS

• The geometric mean of the optimal gradient-descent stepsizes for the two dual functions gives the optimal DRS stepsize and, by equivalence, the ADMM penalty parameter.The derivation models the dual subgradients linearly using local curvature estimates.Source: §3.1 · pp. 3–4

3.2 Spectral stepsize estimation

• Curvature parameters are estimated from current and older iterates using BB-style least-squares rules, and the resulting stepsizes use ADMM iterates without requiring the user to supply the dual problem.The authors propose a hybrid stepsize rule rather than choosing between the steepest-descent and minimum-gradient alternatives.Source: §3.2 · p. 4

3.3 Safeguarding

• A correlation test checks whether changes in dual variables and subgradients support the linear model, and spectral stepsizes update only when the estimates are credible.If both curvature estimates are judged inaccurate, the rule falls back to constant τk.Source: §3.3 · p. 4

3.4 Adaptive ADMM

• AADMM updates the stepsize every Tf iterations; the authors report that ϵcor = 0.2 and Tf = 2 generally perform well, with modest overhead.The added work is a few inner products and storage for one previous iterate.Source: §3.4 · p. 4

3.5 Convergence

• Convergence is guaranteed under either bounded-increasing or bounded-decreasing adaptive-penalty conditions; turning off adaptivity after finitely many steps can satisfy them, though the authors found this unnecessary in their experiments.The conditions bound increases or decreases of the adaptive penalty.Source: §3.5 · pp. 4–5

4.2 Applications

• The test suite spans elastic-net regression, low-rank least squares, quadratic programming, basis pursuit, consensus logistic regression, and semidefinite programming, using synthetic and benchmark data.The benchmarks include UCI and LIBSVM datasets.Source: §4.1 · p. 5

4.1 Experimental setting

• Comparisons included fixed-step, restarted, residual-balancing ADMM, and AADMM, using shared random starts and stopping tolerances scaled by problem size.AADMM used ϵcor = 0.2 and Tf = 2 in the experiments.Source: §4.1 · p. 5

4.3 Convergence results

• AADMM outperformed other variants in all reported test cases except residual balancing on Rcv1 consensus logistic regression; fixed-step ADMM failed to converge within its iteration cap on 13 of 23 realistic datasets.Table 1 reports iterations and runtime for the algorithms and applications.Source: Table 1 · p. 6, §4.3 · p. 7
• On synthetic basis pursuit, AADMM quickly adapts the penalty and converges fastest, while residual balancing's penalty oscillates and fast ADMM often restarts.Source: Figure 1 · p. 7, §4.3 · p. 7

4.4 Sensitivity

• Iteration counts were examined across initial penalty values and problem scales for elastic-net regression, quadratic programming, and low-rank least squares.Source: §4.4 · p. 7, Figure 2 · p. 8

• AADMM uses a spectral stepsize rule for dual Douglas–Rachford splitting, translated into an ADMM penalty-selection criterion and safeguarded against unreliable choices.Source: §5 · p. 8
• Experiments across a comprehensive range of problems and datasets report that AADMM outperforms other ADMM variants.Source: §5 · p. 8
• AADMM is reported to be robust to initial parameter choice and problem scaling.Source: §5 · p. 9