acceptodds
Under review as a conference paper at ICLR 2027

Closed-Form Parameter Selection for ADMM and Over-Relaxed ADMM via Spectral Upper-Envelope Analysis

Abstract

The Alternating Direction Method of Multipliers (ADMM) and its over-relaxed variant (oADMM) are among the most effective optimization solvers in modern machine learning. However, their convergence performance depends critically on penalty and relaxation parameters that are challenging to tune properly. In practice, these parameters are typically selected through manual tuning, iterative procedures such as gradient-based search, or adaptive schemes such as residual balancing. Such approaches incur substantial computational overhead while offering limited theoretical guidance. To address this issue, we introduce a spectral upper-envelope framework, supported by strong theoretical guarantees, that provides analytical parameter-selection rules for ADMM and oADMM over a broad class of linear quadratic problems (LQPs). By formulating these algorithms as fixed-point iterations, we relate their convergence behavior to the spectral radius of the corresponding iteration matrix. This viewpoint leads to a tight and tractable upper bound, from which closed-form parameter choices can be derived, thereby eliminating the need for manual or iterative tuning. Extensive stochastic experiments show that the proposed parameters closely match optimal values obtained via gradient-descent search. In addition, experiments on two application domains, namely heterogeneous parabolic partial differential equations (PDEs) and diffeomorphic image registration, demonstrate that the proposed framework enables ADMM and oADMM to achieve faster convergence than state-of-the-art iterative solvers. Overall, our spectral upper-envelope framework provides a practical and theoretically grounded approach to parameter selection for ADMM and oADMM.

Primary area:
optimization
Keywords:
ADMM, over-relaxed ADMM, spectral analysis, parameter selection, convergence analysis, linear quadratic problems, partial differential equations, image registration

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_X4J4OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes an automated parameter-selection strategy for the ADMM algorithm applied to linear-quadratic problems, eliminating the need for exhaustive parameter searching and thereby enhancing computational efficiency. The authors introduce a theoretically grounded "upper-envelope" framework along with analytical parameter-selection rules, and demonstrate the effectiveness of the proposed approach through applications in PDEs and diffeomorphic image registration.

Critical strengths
  • Designing automated selection strategies for numerical algorithms that require hyperparameters is highly practical;
  • The paper presents plausible theorems and proofs, and demonstrates fast convergence in practical applications;
  • The paper has a relatively clear structure.
Critical weaknesses
  • ADMM is proposed to solve problems of the form minu,wf(u)+g(w)min_{u,w} f(u) + g(w), where f and g are not necessarily quadratic functions, and can even be non-differentiable functions, such as L1L_1. The paper solves a specific case where ff and gg are quadratic functions, which is a relatively simple problem that can be solved directly using least squares without ADMM. Is the proposed method applicable to general problems that require ADMM for solution?

  • According to Algorithm 1, the update of uk+1u^{k+1} depends on w and b. Is the iteration matrix in Eq. (2) correct? How can ww and bb be eliminated to obtain the form Q in Eq.(2)? It has not been derived in detail, and the formula seems to have some omissions.

  • Is the selection of ADMM parameters important? Are different parameters sensitive to the results? It is suggested to add a graph showing the decrease in the objective function value or ground-truth error of the ADMM algorithm with different parameters as the number of iterations decreases, such as in Figure 7, to more fully illustrate the importance of automated parameter selection.

Questions for authors
  • Discuss the applicability of the proposed method to more general problems solved by ADMM;

  • Supplement the sensitivity analysis of the ADMM algorithm to parameters;

  • Is Eq. (2) correct?

2 comments

We thank the reviewer for the constructive comments and positive assessment of our work. Below, we address the three critical weaknesses (CW1–CW3) and their corresponding questions (Q1–Q3).

Critical Weaknesses:

CW1 / Q1: Applicability to general ADMM problems and motivation for solving quadratic problems with ADMM.

As discussed in the Introduction, although the first-order optimality condition of Eq. (1) yields the normal equation

(μA⊤A+L⊤L)u=μA⊤f,(\mu A^\top A+L^\top L)u=\mu A^\top f,

directly solving this system can be computationally challenging. The system matrix may be singular, and even when it is positive definite, direct methods can be computationally expensive for large-scale problems.

The key advantage of ADMM in our setting is that it exploits the structure of the problem through operator splitting. Specifically, the resulting subproblems involve the shifted operators μA⊤A+θI\mu A^\top A+\theta I and L⊤L+θIL^\top L+\theta I, which are positive definite for θ>0\theta>0. More importantly, these subproblems often admit efficient specialized solvers, including FFT/DCT diagonalization, multigrid methods, and Sherman–Morrison–Woodbury identities, as explained in the Introduction and demonstrated in our PDE and image-registration applications.

We emphasize that our contribution is an analytical parameter-selection framework specifically designed for structured linear-quadratic problems. We do not claim that the proposed spectral upper-envelope analysis directly extends to general nonlinear or nonsmooth ADMM formulations. Such extensions are beyond the scope of the present work.

CW2 / Q3: Correctness and derivation of the iteration matrix in Eq. (2).

We appreciate the reviewer pointing out that the elimination of the auxiliary and dual variables was not explicitly derived. Below, we provide the derivation.

Let H=μA⊤AH=\mu A^\top A, G=L⊤LG=L^\top L, and d=μA⊤fd=\mu A^\top f. From Algorithm 1, the ADMM updates are

wk+1=θ(G+θI)−1(uk+bk),w^{k+1}=\theta(G+\theta I)^{-1}(u^k+b^k),

uk+1=(H+θI)−1(d+θwk+1−θbk),u^{k+1}=(H+\theta I)^{-1}(d+\theta w^{k+1}-\theta b^k),

bk+1=bk+uk+1−wk+1.b^{k+1}=b^k+u^{k+1}-w^{k+1}.

Combining the second and third equations gives

θbk+1=d−Huk+1.\theta b^{k+1}=d-Hu^{k+1}.

Therefore, for k≥1k\geq1, the dual variable can be eliminated as

bk=θ−1(d−Huk).b^k=\theta^{-1}(d-Hu^k).

Substituting this identity into the ww-update yields

wk+1=(G+θI)−1[(θI−H)uk+d].w^{k+1}=(G+\theta I)^{-1}[(\theta I-H)u^k+d].

Using the same identity in the uu-update, we obtain

uk+1=(H+θI)−1[Huk+θwk+1].u^{k+1}=(H+\theta I)^{-1}[Hu^k+\theta w^{k+1}].

Consequently, the iteration can be expressed as

uk+1=M1uk+c,u^{k+1}=M_1u^k+c,

where

M1=I+θ(H+θI)−1[(G+θI)−1(θI−H)−I],M_1=I+\theta(H+\theta I)^{-1}[(G+\theta I)^{-1}(\theta I-H)-I],

and

c=θ(H+θI)−1(G+θI)−1d.c=\theta(H+\theta I)^{-1}(G+\theta I)^{-1}d.

This recovers exactly the iteration matrix given in Eq. (2), thereby confirming its correctness. We will include the intermediate elimination steps in the revised manuscript to make the derivation more explicit.

CW3 / Q2: Sensitivity to penalty and relaxation parameters.

We conducted a fixed-parameter sensitivity study on a 128×128128\times128 image-registration quadratic subproblem. All runs use identical problem data and zero initialization. Convergence is measured by the relative normal-equation residual Rk=∥Hvk−b∥2/∥b∥2R_k=\|Hv^k-b\|_2/\|b\|_2, where Hv=bHv=b is the optimality condition of the quadratic problem. Each run terminates when Rk≤10−6R_k\leq10^{-6}.

The analytically selected penalties for ADMM and oADMM are both θ^≈0.0036384\hat\theta\approx0.0036384, with the selected oADMM relaxation β^≈1.752\hat\beta\approx1.752. For ADMM, we vary θ\theta over {0.1,0.5,1,2,10}θ^\{0.1,0.5,1,2,10\}\hat\theta with β=1\beta=1. For oADMM, we fix θ=θ^\theta=\hat\theta and vary β\beta.

The following table reports the number of iterations required to reach the common residual tolerance.

ADMM penaltyIterationsoADMM relaxationIterations
0.1θ^0.1\hat\theta894β=1.0\beta=1.0149
0.5θ^0.5\hat\theta189β=1.2\beta=1.2123
θ^\hat\theta (proposed)149β=1.5\beta=1.597
2θ^2\hat\theta274β=1.7\beta=1.785
10θ^10\hat\theta1110β^≈1.752\hat\beta\approx1.752 (proposed)82
——β=1.9\beta=1.9159

These results illustrate the sensitivity of ADMM and oADMM convergence to the penalty and relaxation parameters. The proposed ADMM penalty requires 149 iterations, compared with 189–1110 iterations for the tested alternatives. For oADMM, the proposed relaxation reduces the iteration count from 149 at β=1\beta=1 to 82, while a larger relaxation of β=1.9\beta=1.9 requires 159 iterations.

We will include the corresponding residual convergence curves in the revised Appendix.

Thank you for the detailed clarifications and additional experimental results. The authors have provided further explanations regarding the scope of the proposed method, supplemented the mathematical derivations, and conducted additional parameter sensitivity experiments, which have helped address several of my concerns.

Nevertheless, the applicability of the proposed method remains relatively limited, as it is specifically designed for structured linear-quadratic problems rather than general nonlinear or nonsmooth formulations. Additionally, I am unable to fully verify the correctness of all the mathematical derivations.

Reviewer_7umHOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper studies penalty and relaxation selection for ADMM applied to

min⁡u  μ2∥Au−f∥22+12∥Lu∥22.\min_u\;\frac{\mu}{2}\lVert Au-f\rVert_2^2+\frac12\lVert Lu\rVert_2^2.

Writing QA=μA⊤AQ_A=\mu A^\top A and QL=L⊤LQ_L=L^\top L, the analysis assumes that both matrices are positive definite and expresses the ADMM iteration spectrum through a product of symmetric Cayley transforms. The scalar function

=\frac{\alpha\ell+\theta^2}{(\alpha+\theta)(\ell+\theta)}$$ defines lower and upper envelopes over the four corners of the two spectral intervals. A disk containing the possibly complex iteration spectrum yields the ADMM bound $\rho(M_1)\leq S_{\max}$. An affine transformation gives an over-relaxed bound, whose minimizing relaxation at fixed $\theta$ is $$\widehat\beta(\theta)=\frac{2}{2-S_{\min}(\theta)-S_{\max}(\theta)}.$$ The paper derives a piecewise closed-form penalty for ADMM and a finite candidate set for jointly tuning over-relaxed ADMM. These optimize spectral upper bounds rather than necessarily the exact spectral radius. Experiments compare the rules with numerical spectral-radius search, adaptive ADMM variants, and iterative solvers on diffusion and image-registration problems; Appendix B includes parameter-selection and end-to-end timings. The central unresolved issue is whether the stated treatment of singular component Hessians justifies the theoretical interpretation of the application results.
Critical strengths
  1. A useful treatment of noncommuting quadratic operators. The disk argument in Lemma 2 and Theorem 9 is more informative than an analysis that assumes simultaneous diagonalization or a real iteration spectrum. The Cayley-product formulation, four-corner envelopes, and affine transformation for over-relaxation form a coherent route from spectral information to an inexpensive tuning rule (§3; Appendix A.2). I did not identify a counterexample to the stated positive-definite disk result. The subsequent distinction between minimizing the exact radius and minimizing its upper envelope is also important and generally made explicit.

  2. The practical evaluation includes meaningful setup and solver costs. The paper does more than compare iteration counts. Appendix B.1 reports the cost of obtaining parameters, B.2 compares residual balancing and adaptive spectral/relaxed variants, and B.3 includes startup cost and end-to-end timing. For example, Table 4 reports 4.27 seconds for over-relaxed ADMM versus 8.10 for ADMM and 50.30 for CG on the specified registration instance. These are useful results for a setting where shifted subproblems have specialized fast solvers. They support practical interest in avoiding repeated spectral-radius searches, even though they do not establish universal superiority over other linear-system solvers.

Critical weaknesses
  1. The proposed semidefinite extension can discard the dominant contracting mode. Footnote 1 on page 4 says that the same analysis can be applied by replacing the minimum eigenvalues with the smallest positive eigenvalues of QAQ_A and QLQ_L, excluding zero-eigenvalue modes. This does not in general provide a bound on the original iteration. A zero eigenvalue of one component Hessian is not necessarily a fixed-point direction, and the two positive spectral supports need not provide a common invariant subspace.

    A concrete counterexample is

    Q_L=\operatorname{diag}(1,4),\qquad \theta=20.$$ Here $Q_A+Q_L=\operatorname{diag}(1,104)\succ0$, so the optimization problem has a unique minimizer. Using only the positive eigenvalues gives $[\alpha_1,\alpha_n]=[100,100]$ and $[\ell_1,\ell_n]=[1,4]$. Theorem 4's disjoint-interval rule then selects $\theta=\sqrt{100\cdot4}=20$, and the resulting envelopes are $$S_{\min}=\frac{25}{126},\qquad S_{\max}=\frac5{18}.$$ Direct substitution into the paper's Eq. (2), however, gives $$M_1=\operatorname{diag}\!\left(\frac{20}{21},\frac5{18}\right), \qquad \rho(M_1)=\frac{20}{21}>S_{\max}.$$ The discarded direction is therefore precisely the slow contracting direction, not an irrelevant nonunique-solution mode. At the same $\theta$, Eq. (12) gives $\widehat\beta=21/16$ and the surrogate bound $J=5/96$, whereas $$M_2=\operatorname{diag}\!\left(\frac{15}{16},\frac5{96}\right), \qquad \rho(M_2)=\frac{15}{16}.$$ This does **not** refute the theorems under their stated positive-definite assumptions. It refutes the footnote's general prescription as a justification for the full semidefinite problem. The distinction matters because the diffusion dual contains $DD^\top$, and the registration construction also has singular component operators (§4). Appendix B.4's favorable rank-deficient experiments cannot supply the missing general argument. A repair requires a valid joint invariant-subspace restriction or an analysis retaining the relevant zero modes; simply dropping individual zero eigenvalues is insufficient. The application results should otherwise be explicitly presented as heuristic extensions. Because both motivating applications rely on this issue, it is consequential to the current recommendation rather than a cosmetic footnote correction.
  2. The generality and optimality positioning need a sharper comparison with existing bound-based tuning. Section 2 groups earlier spectral approaches as relying on numerical search or problem-specific design, but optimizing convergence-rate bounds analytically is already a substantial strand of the Douglas–Rachford/ADMM literature. In particular, the bibliography omits Pontus Giselsson and Stephen Boyd, Linear Convergence and Metric Selection for Douglas–Rachford Splitting and ADMM, IEEE Transactions on Automatic Control 62(2):532–544, 2017. That work gives tight bounds and parameter/metric selection under strong-convexity and smoothness assumptions. It does not automatically subsume this paper's two-operator disk envelope, but the new information supplied by both spectral intervals should be compared with it explicitly. Empirically, the numerical gradient-based search is also a comparator, not a certified global optimum. Parameter agreement on random matrices and the favorable Appendix B timings are useful, but do not quantify worst-case envelope looseness or its effect on convergence across controlled eigenvector orientations, conditioning, and nullspaces. The strongest claim supported at present is an efficient bound-optimized rule with promising results in the tested implementations, not broadly established near-optimality across the advertised class.

Questions for authors
  1. Validity on the actual application operators. How is Footnote 1 intended to handle the counterexample above? For the diffusion and registration experiments, what exact subspace and spectral endpoints were used? Please either prove that this subspace is invariant and contains all relevant error modes, provide a valid full-space bound, or separate the positive-definite guarantees from the heuristic application results. This is the main issue that could change my assessment.

  2. Tightness and robustness of the tuning rule. Can the authors compare the selected parameters using the resulting spectral radius and time to a common residual tolerance, rather than parameter agreement alone, on controlled families with fixed spectral endpoints but changing eigenvector alignment? Please also state the random-matrix sampling law, endpoint-estimation tolerances, and how numerical search failures/local minima are handled. Appendix B already contains valuable timing and adaptive-baseline results; the requested clarification concerns what they establish beyond those instances.

  3. Relationship to existing analytical tuning. Please discuss and cite the Giselsson–Boyd work above, and state precisely which bound or parameter regimes the proposed envelope improves. A comparison of analytical bounds on the same positive-definite instances would clarify the contribution without requiring a wholesale expansion of the application suite.

1 comment

I keep my original rating.

Reviewer_TvkaOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper proposes rules for selecting the penalty and relaxation parameters of ADMM and over-relaxed ADMM for regularized linear quadratic problems. The rules minimize a spectral-radius upper bound constructed from the extremal eigenvalues of the quadratic operators, avoiding repeated numerical optimization. The empirical evaluation includes random-matrix comparisons, tuning costs, and applications to heterogeneous diffusion PDEs and image registration.

Critical strengths
  1. A useful approach to parameter selection. The method gives a simple rule for choosing parameters once the largest and smallest eigenvalues are known. This avoids a costly numerical search and makes parameter tuning more convenient.

  2. Promising practical results. The paper reports substantial reductions in tuning time, small spectral-radius gaps on the tested instances, and competitive performance against adaptive methods and standard solvers. The PDE and image-registration examples demonstrate the potential usefulness of the approach.

Critical weaknesses
  1. The treatment of singular operators needs stronger justification. Footnote 1 on p. 4 proposes using the smallest positive eigenvalues, but this can leave out directions that affect convergence. Consider the simple example

    QA=diag⁡(0,4),QL=I2,θ=2.Q_A=\operatorname{diag}(0,4),\qquad Q_L=I_2,\qquad \theta=2.

    Ignoring the zero eigenvalue gives α1=αn=4\alpha_1=\alpha_n=4 and ℓ1=ℓn=1\ell_1=\ell_n=1, so the proposed bound is Smin⁡=Smax⁡=h4,1(2)=4/9S_{\min}=S_{\max}=h_{4,1}(2)=4/9. However, the actual ADMM iteration matrix is

    M1=diag⁡(2/3,4/9),ρ(M1)=2/3>4/9.M_1=\operatorname{diag}(2/3,4/9),\qquad \rho(M_1)=2/3>4/9.

    The omitted direction therefore contracts by 2/32/3 per iteration and is not covered by the claimed bound. For oADMM, the proposed relaxation rule gives β=9/5\beta=9/5 and a bound of zero, whereas M2=(1−β)I+βM1=diag⁡(2/5,0)M_2=(1-\beta)I+\beta M_1=\operatorname{diag}(2/5,0) has spectral radius 2/52/5.

    Here QA+QL=diag⁡(1,5)Q_A+Q_L=\operatorname{diag}(1,5) is positive definite, so the issue occurs even when the objective has a unique minimizer. This example shows that simply dropping zero eigenvalues does not give a valid bound for the full iteration matrix. If the analysis is intended to cover only a smaller subspace, the authors need to explain why the actual iterations stay in that subspace, particularly in the PDE and image-registration applications, where the operators are singular.

  2. The practical tradeoff between analytical and numerical tuning is not fully established. Figure 4 and Table 1 compare parameter values, while Tables 2 and 5 report tuning times and spectral-radius gaps. These comparisons are useful, but the random-matrix sampling and conditioning, as well as the numerical search's initialization, step-size policy, stopping criteria, and sensitivity to initialization, are insufficiently specified. This makes it difficult to assess how reliable and representative the numerical reference is.

    The appendix also includes runtime comparisons with adaptive methods and CG/PCG. However, a direct comparison between analytically tuned and search-tuned ADMM/oADMM on the same application instances is still missing. Reporting iteration counts and total runtime, including parameter selection, would show more clearly how the savings in tuning translate into overall solution time.

Questions for authors
  1. In the PDE, image-registration, and rank-deficient experiments, do the spectral endpoints include zero eigenvalues or use only the positive spectrum? How is this choice justified for the iterations actually used?

  2. How are the random matrices generated and scaled, and what initialization, step-size policy, and stopping criteria are used for numerical search? Have the resulting parameters been checked across multiple initializations?

  3. On the same PDE and image-registration instances, how do analytically tuned and search-tuned ADMM/oADMM compare in iteration count and total runtime, including tuning?

2 comments

We thank the reviewer for the careful assessment and constructive comments. We address the concerns below and clarify the scope of our theoretical guarantees and empirical findings.

Critical Weakness:

CW1 / Q1: Scope of the theoretical guarantees for singular operators.

We emphasize that our main theoretical results, including the spectral disk enclosure and analytical parameter-selection rules, are rigorously established for positive-definite operators. These results apply to general noncommuting operators and constitute a nontrivial theoretical contribution. The reviewer's counterexample does not affect their validity under the stated assumptions.

We acknowledge that simply discarding zero eigenvalues does not yield a valid bound in general. Extending the analysis to positive-semidefinite operators is substantially more challenging, since zero modes can affect convergence and the nullspaces of noncommuting operators need not form a common invariant subspace. We will therefore remove the unsupported extension in Footnote 1 while retaining the positive-definite theoretical results.

Although the PDE and image-registration applications involve singular operators, our numerical results demonstrate promising performance of the proposed parameter-selection rules in these settings. In these applications, we use the smallest positive eigenvalues as the lower spectral endpoints for parameter selection, without claiming that this provides a rigorous full-space spectral bound. This suggests potential applicability beyond the current theoretical guarantees, without claiming a general spectral upper bound for semidefinite problems. We will clarify this distinction in the revised manuscript.

CW2 / Q3: End-to-end comparison of analytical and numerical parameter selection.

We thank the reviewer for this valuable suggestion. We provide an end-to-end comparison of analytical parameter selection and the numerical search approach of Song et al. (2024) on the same 256×256256\times256 image-registration quadratic subproblem.

Both approaches use identical problem data, initialization, and solver implementation, with a common relative normal-equation residual tolerance of 10−610^{-6}. The total runtime includes both parameter-selection and solver costs.

MethodParameter selectionIterationsTuning (s)Solve (s)Total (s)
ADMMAnalytical (ours)2740.00070.7430.744
ADMMNumerical search (Song et al., 2024)2262.8620.6133.475
oADMMAnalytical (ours)1740.00070.4650.466
oADMMNumerical search (Song et al., 2024)1468.1010.3948.495

Numerical search achieves fewer iterations for both ADMM and oADMM. However, the additional parameter-selection cost outweighs the reduction in solver runtime. Consequently, analytical tuning achieves approximately 4.67×4.67\times and 18.2×18.2\times faster end-to-end computation for ADMM and oADMM, respectively, on this instance.

These results illustrate the practical benefit of inexpensive analytical parameter selection while retaining competitive convergence performance.

Thank you for the detailed response. It addresses some of my questions, though my main concern is still the treatment of zero eigenvalues. With that claim removed, I find the scope of the theoretical guarantees too narrow, so I will keep my original score.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.