On the (linear) convergence of Generalized Newton Inexact ADMM
Authors: Zachary Frangella
Theo Diamandis
Bartolomeo Stellato
Madeleine Udell
Venue: Accepted by TMLR ()

Abstract: This paper presents GeNI-ADMM, a framework for large-scale composite convex optimization that facilitates theoretical analysis of both existing and new approximate ADMM schemes. GeNI-ADMM encompasses any ADMM algorithm that solves a first- or second-order approximation to the ADMM subproblem inexactly. GeNI-ADMM exhibits the usual O(1/t)-convergence rate under standard hypotheses and converges linearly under additional hypotheses such as strong convexity. Further, the GeNI-ADMM framework provides explicit convergence rates for ADMM variants accelerated with randomized linear algebra, such as NysADMM and sketch-and-solve ADMM, resolving an important open question on the convergence of these methods. This analysis quantifies the benefit of improved approximations and can aid in the design of new ADMM variants with faster convergence.

Published in Transactions on Machine Learning Research (01/2026)
On the (linear) convergence of Generalized Newton Inexact ADMM
Zachary Frangella
xfrangella wwwwmmii.saaaaaaaaaaaaa edu
Deportment of Management Science and Engineering Stanford University
Theo Diamandis
tdkamanndmii. edu
Department of Electrical Engineering and Computer Science Massachusetts Instätute of Technology
Bartolomeo Stellato
bstellato@princeetoncco
Department of Operations Research and Financial Engineering Princeton University
Madeleine Udell
udellästanford.co edu
Department of Management Science and Engineering Stanford University
Reviewed on OpenReview: https: // openreview. net/ forum? id= GT3naIIBaK
Abstract
This paper presents GeNI-ADMM, framework for large-scale composite convex optimiza- tion that facilitates thcoretical analysis of both existing and new approximate ADMM schemes. GeNI-ADMM encompasses any ADMM algorithm that solves a first- second- order approximation to the ADMM subproblem inexactly. GeNI-ADMM exhibits the usual ((L/t)-convergenee rate under standard hypotheses and converges linearly under additional hypotheses such as strong convexity. Further, the GeNI-DDMM framework provides explicit convergence rales for ADMM variants accelerated with randomized linear algebra, such as NysADMM and skotch-and-solve ADMM, resolving an important open question on the con- vergence of these methods. This analysis quantifies the benefit of improved approximations and can aid in the design of new ADMM variants with faster convergence.
1 Introduction
The Alternating Direction Method of Multipliers (ADMM) is one of the most popular methods for solving composite optimization problems, as it provides a general template for a wide swath of problems and con- verges to an acceptable solution within a moderate number iterations (Boyd et al.) 2011). Indeed, Boyd et al. (201)) implicitly promulgates the vision that ADMM provides a unified solver for various convex ma- chine learning problems. Unfortunately, for the large-scale problem instances routinely encountered in the era of Big Data, ADMM scales poorly and cannot provide unified machine learning solver for problems of all scales. The scaling issue arises ADMM requires solving two subproblems at each iteration, whose cost can increase superlincarly with the problem size. As a concrete example, in the case of fi-logistic regression with an n x d data matrix, ADMM requires solving an Ez-regularized logistic regression problem at each iteration (Boyd et al. 2011). With a fast-gradient method, the total complexity of solving the subproblem is ((nd/R) (Bubock] 2015), where the condition number of the problem. When n and d are the tens of thousands or larger moderate problem size by contemporary machine learning standards and is large, such high per-iteration cost becomes unacceptable. Worse, ill-conditioning is ubiquitous in machine

---

Published in Transactions on Machine Learning Research (01/2026)
learning problems; often Q(n), in which case the cost of the subproblem solve becomes superlinear in the problem size.
Randomized numerical linear algebra (RandNLA) offers promising tools to scale ADMM to larger problem sizes. Recently Zhao et al. (2022) proposed the algorithm NysADMM, which uses a randomized fast linear system solver to scale ADMM up to problems with tens of thousands of samples and hundreds of thousands of features. The results in Zhao et al. (2022) show that ADMM combined with the RandNLA primitive runs 3 to 15x faster than state-of-the-art solvers machine learning problems from LASSO to SVM to logistic regression. Unfortumately, the convergence of randomized approximate ADMM solvers like NysADMM is not well understood. NysADMM approximates the z-subproblem using a lincarization based on a second-order Taylor expansion, which transforms the z-subproblem into a Newton-step, i.e., a linear system solve. then solves this system approximately (and quickly) using a randomized linear system solver. The convergence of this scheme, which combines lincarization and incxactness, not covered by prior theory for approximate ADMM; prior thcory covers either lincarization (Ouyang et al. 2015) or inexact solves (Eckstein & Bertsekas 1992 but not both.
In this work, we bridge the gap between theory and practice to explain the excellent performance of large class of approximate lincarized ADMM schemes, including NysADMM (Zhao et al. 2022] and many methods not previously proposed. We introduce a framework called Generalized Newton Inexact. ADMM, which we refer to as GeNI-ADMM (pronounced vemie-ADMMI GeNI-ADMM includes NysADMM and many other approximate ADMM schemes as special cases. The name is inspired by viewing the linearized z-subproblem in GeNI-ADMM as generalized Newton-step. GeNI-ADMM allows for inexactness in both the J-subproblem and the z-subproblem. We show GeNT-ADMM exhibits the usual ((1//))convergence rate under standard assumptions, with linear convergence under additional assumptions. Our analysis also clarifies the value of using curvature in the generalized Newton step: approximate ADMM schemes that take advantage of curvature converge faster than those that do not at a rate that depends on the conditioning of the subproblems. As the GeNI-ADMM framework covers any approximate ADMM scheme that replaces the z-subproblem by a linear system solve, our convergence theory covers any ADMM scheme that uses fast linear system solvers. Given the recent flurry of activity on fast linear system solvers within the (randomized) numerical lincar algebra community (Lacotte & Pilanci 2020: Meier & Nakatsukasa 2022 Frangella et al. 2023 our results will help realize these benefits for optimization problems power of the GeNI-ADMM framework, we establish convergence of NysADMM and another RandNT.- inspired scheme, sketch-and-solve ADMM, whose convergence was left as an open problem in Bulue et al.
well. To demonstrate the
2022h.
1.1
Contributions
Our contributions may be summarized concisely as follows:
1. We provide general ADMM framework GeNI-ADMM, that encompasses prior approximate ADMM schemes as well as new ones. It can take advantage of second-order information and allows for inexact subproblem solves.
2. Our analysis shows the benefits of schemes that employ preconditioning and variable metrics over methods that do not.
3. We show that despite all the approximations it makes, GeNI-ADMM converges ergodically at the usual ergodic O(1/t) rate.
We apply our framework to show some RandNLA- Las-baed approximate ADMM schemes converge at the same rate as vanilla ADMM, answering some open qucstions regarding their convergence (Buluc ct al.) 2022 Zhao et al. 2022). In the case of sketch-and-solve ADMM, we show modifications the naive scheme required to ensure convergence.
2

---

Published in Transactions on Machine Learning Research (01/2026)
1.2 Roadmap
In Section 2 we formally state the optimization problem that we focus on in this paper and briefly introduce ADMM. In Section we introduce the Generalized Newton Inexact ADMM framework and review ADMM and its variants. Section gives various technical backgrounds and assumptions needed for our analysis. Section 5 establishes that GeNI-ADMM converges at an ((1/t) rate in the convex setting. In Section apply our theory to establish convergence rates for two methods that naturally fit into our framework, and we illustrate these results numerically in Section S
1.3 Notation and preliminaries
We call a matrix psd if is positive semidefinite. We denote the convex cone of n x n real symmetric psd matrices by s Similarly we use S to denote the convex of symmetrie postive definite matrices. We denole the Loewner ordering St and S by I, that A < B if and only if B A is psd. Given a matrix H, denote its spectral norm by || If f is a smooth function denote its smoothness constant by Ly. We say positive sequence hx21 is summable if -k=1 e* <0.
2 Problem statement and ADMM
Let X, 2, H. be fiite-dimennional inner-product spaces with inner-product (5.)) and norm || ||. I. We wish to solve the convex constrained optimization problem
minimize subject to
[xx g(z) Mx Nu =
(1)
x E X, 2 2 Z,
with variables and 2, where C X and Z Z are closed convex sets, is a smooth convex function, g is a convex proper sereconeiiotss (Isc) function, and M + H and N operators.
are bounded linear
Remark 1. Often, the constraint is presented Mx + No for some non-zero vector however, by increasing the dimension of 2 by and replacing N by IN c), we can make = 0. Thus, our setfing of 0 is without loss of generality.
We can write problem 1 as the saddle point problem
minimize maximize f(x) g(() + (y, Mx N2), =EX,2e2 BEY
where Y S H a closed convex set. The saddle-point formulation will play an important role our analysis.
Perform the change of variables v/p and define the Lagrangian
2p( = f(x) + g(2) - (pn, Mx + N2).
Then 2 may be written concisely as
minimize maximize L, (2,,,,1)) =ex.ze2 wEU
(3)
The ADMM algorithm (Algorithm 1 popular method for solving Our presentation uses the scaled form of ADMM (Boyd et al., 2011 Ryu Yin 2022), which uses the change of variables = v/p, this simplifies the algorithms and analysis, so maintain this convention throughout the paper.
3

---

Published in Transactions on Machine Learning Research (01/2026)
Algorithm ADMM
input:
convex proper Isc functions f and 9: constraint matrix M, stepsize p
repeat
x++1 argmin (f(x) M + N * + 1
zEX
k+1 argmin(g(=)) + M + No + 133
=EZ
++ u² + Mæ*+1 N2
until convergence
output: solution 2x*, of problem
3 Generalized Newton Inexact ADMM
As shown in Algorithm 1 at each iteration of ADMM, two subproblems are solved sequentially to update variables v and z. ADMM is often the method of choice when the z-subproblem has a closed-form solution. For example, if g(z) = ||z]|], the z-subproblem is soft thresholding, and g(x) = 1s(x) is the indicator function of a convex set S, the z-subproblem projection onto S (Parikh & Boyd 2014 $6). However, compute even with closed-form solution. For example, when g(z) ss(x) and
it may be expensive S the psd cone, the z-subproblem requires eigendlecomposition to compute the projection, which is prohibitively expensive for large problems (Rontsis et al. 2022).
Let us consider the z-subproblem
2
argmin (f(z) GIMM + N + +
(4)
=EX
In contrast to the z-subproblem, there usually no closed-form solution for the z-subproblem. Instead, an iterative scheme is often used to solve inaccurately, especially for large-scale applications. This solve can be very expensive when the problem is large. To reduce computational effort, many authors have suggested replacing this problem with simplified subproblem that is easier to solve. We highlight several strategies to do so below.
Augmented Lagrangian linearization. One strategy is to linearize the augmented Lagrangian term in the ADMM subproblem and replace it by the quadratic penalty = [| for some
M + +N* 1 (carefully chosen) positive definite matrix More formally, the strategy adds quadratic term to form a new subproblem
1 1| x² 101 N + 1²122 + 2
k+1 = argmin x
f(x) + +IM N
zeX
which is substantially easier to solve for an appropriate choice of P. One canonical choice = nI-ppMM² M, where > is a constant. For this choice, the quadratic terms involving M cancel, and we may omit constants
with respect to v, resulting the subproblem
k+1 = argmin (f(x) + p(Mx, Ma - x* + uu ) " || =d|1²]_ 2
#eX
Here, an isotropic quadratic penalty replaces the augmented Lagrangian term in 4 This strategy allows the subproblem solve to be replaced by proximal operator with a (possibly) closed-form solution. This strategy has been variously called preconditioned ADMM, proximal ADMM, and (confusingly) lincarized
ADMM (Deng & Yin 2016 He Yuan 2012 Ouyang el al. 2015).
Function approximation. The second strategy to simplify the z-subproblem, is to approximate the function by first- or second-order approximation (Ouyang et al. 2015 Ryu & Yin 2022 Zhao et al. 2022), forming the new subproblem
x k+1 = argmin
f(x*) + (Vf(**), ) - 2²) + || x01 +
- P |M + N + s
(5)
2
zEX
4

---

Published in Transactions on Machine Learning Research (01/2026)
where H is the Hessian of f at x². The resulting subproblem is quadratic and may be solved by solving linear system or (for M = 1) performing linear update, as detailed below in Section 3. 3.1.1
Inexact subproblem solve. The third strategy is to solve the ADMM subproblems inexactly to achieve some larget accuracy, either absolute error or relative error. An absolute-error criterion chooses the sub- problem error a priori (Eckstein & Bertsekas 1992,, while relative error criterion requires the subproblem error to decrease as the algorithm nears convergence, for example, by sctting the error target cach iteration proportional to | n p(z >* Eckstein & Yao 2018
The GeNI-ADMM framework allows for any combination of the three strategies: augmented Lagrangian linearization, function approximation, and inexact subproblem solve. Consider the generalized second-order approximation to f
Approximations used by GeNI-ADMM.
1 2²) -- 11
f(x) ~ fi(x) + f2(#*) + (V x
(6)
where fi + f2 - f and {0* Fa21 is a sequence of psd matrices that approximate the Hessian of fz. GeNI- ADMM uses this approximation the z-subproblem, resulting in the new subproblem
gk+1_ argmin =rgmminff(t) + (VS2(**), ) - 2t) + 211l== +| 141
+ +1 + N= + 13
We refer to a generalized Newton step. The intuition for the name is made plain when X Rd Si = 0, f2 -I, in which case the update becomes
(o* + pM M) 1 @** ff((*) - - (ū* =*).
(8)
Equation shows that the z-subproblem reduces to a linear system solve, just like the Newton update. We can also interpret GeNI-ADMM et al. 2019 2022). From this point of view, GeNI-ADMM replaces in the P-ALM step by its lincarization and adds specialized penalty defined by the -
linearized praximal augmented Lagrangian (P-ALM) method (Hermans
GeNI-ADMM also replaces the z-subproblem of ADMM with the following problem
sk+1 argmin + P ZEZ
| M + Nz + 1/1 + 2
1 ||
11
(9)
Incorporating the quadratic w term allows us to linearize the augmented Lagrangian term, which is useful when N is very complicated.
However, even with the allowed approximations, it is unreasonable to assume that 7 (9) are solved exactly
at each itcration. Indeod, the hallmark of the NysADMM scheme from Zhao et al. (2022) is that it solves
inexactly (but efficiently) using a randomized linear system solver. Thus, the GeNI-ADMM framework allows for inexactness the and z-subproblems, as seen in Algorithm 2
Algorithm 2 Generalized Newton Inexact ADMM (GeNI-ADMM)
input: penalty parameter P. sequence of psd matrices (+t h221, (c2), repeat
{O* J221, (
forcing sequences
#h+1 2 arggmin(J1 (V 2h) -|1 5* 11
f11Mx N +
gk+1 ~ argmin(g(s)) M + N2 + 11 + -||= - 1
7h+1 / =
k+ k+1 N
until convergence
output: solution (x* x*) of problem
5

---

Published in Transactions on Machine Learning Research (01/2026)
Algorithm 2 differs from ADMM (Algorithm 1 in that a) the and 2-subproblems now given by and 9 and b) both subproblems may be solved inexactly. Given the inexactness and the use of the generalized Newton step in place of the original z-subproblem, we refer to Algorithm 2 as Generalized Newton Inexact ADMM (GeNI-ADMM). The inexactness schedule is controlled by the forcing sequences {=*1x21 f )221 that specify how accurately the x and z-subproblems are solved at each ileration. These subproblems have different structures that require different notions of accuracy. To distinguish between them, we make the following definition.
Definition 1 (s-minimizer and e-minimum). Let h T T+ R be strongly-cones and let t argminger h(t)).
(e-minimizer) Given & E T, we say is an s-minimizer of minimizeng7h(()) and write
Re
argmin h(t') if and only if ||t- -tll
NET
In words, t is nearly equal to the argmin of h(t) in set T. (e-ménimum) Given t T, say gives an e-minimum of minémizere7h(() and write
argmin h(t!) if and only if h((t) - h(tt) S.
FET
In words, t produces nearly the some objective value as the argmin of h(t) in set T.
Thus, from Definition 1 and Algorithm 2 we see for each ileration k that zk+1 an ox miniiiizee of the æ-subproblem, while gKTl gives an et -i-minimum of the z-subproblem.
3.1 Related work
The literature on the convergence of ADMM and its variants is vast, so we focus on prior work most relevant our setting. Table [ lists some of the prior work that developed and analyzed the approximation strategies described in Section
GeNI-ADMM differs from all prior work in Table [ by allowing (almost) all these approximations and more. It also provides explicit rates of convergence to support choices between algorithms, Moreover, many of these algorithms can be recovered from GeNI-ADMM.
3.1.1 Algorithms recovered from GeNI-ADMM
Various ADMM schemes in the literature can be recovered by appropriately selecting the parameters in Algorithm 2 Let us consider a few special cases to highlight important prior work on approximate ADMM, and provide concrete intuition for the general framework provided by Algorithm 2
NysADMM The NysADMM scheme (Zhao et al. 2022 assumes the problem is unconstrained M I,N = I. Diamandis et al. (2023) have extended NysADMM the constrained setting with the GeNIOS solver, which we will discuss more in Section 7.1 For simplicity of exposition, we focus the original NysADMM for unconstrained problems. GeNI-ADMM specializes to NysADMM taking O = n(Hf + aal,, and V 0, where H denotes the Hessian of f at the kth iteration. Unlike the original NysADMM scheme of Zhao et al. (2022). we include the regularization term øl, where 0. This inclusion is required for theoretical analysis but seems unnecessary in practice (see Section 7.1 for detailed discussion). Substituting this information into g leads to the following update for the z-subproblem.
kktl= i (nH) (p + no)1) (Vf(**) + p(i* 2 +a))).
(10)
Sketch-and-solve ADMM M = I,N = -1, -1, v = 0, and O is chosen to be a matrix such that @* + pl is easy to factor, we call the resulting scheme sketch-ands -nd-v ADMM. The name sketch-and-sole ADMM is motivated by the fact that such a * can often be obtained via sketching techniques. However, the method works for any * not only ones constructed by sketching methods. The update is given by
k+1 x - (0+ pT) -1 (VS(**) + pl =² ++²))
6

---

Published in Transactions on Machine Learning Research (01/2026)
Augmented Lagrangian Linearization
Convergence rate
Problem class
Function approximation
Subproblem inexactness
Reference
Rekstoin &
Bertackeal
x
Convex
x absolute error
2.
[1992)
He Yuan (2012)
Ergodic (1/{t)
Couvex
x
X
Monteiro
Ergodic O(1/t)
Convex
x
Svaiter 2013
Ouyang et. sl
0(1/Vi)
Stochastic convex
stochastic first-orerr
x
2013
Ouyang et sl. (20155
Ergodic ((1{t)
Couvex
first-order
x
Deng Yin (2016)
Linear
Strongly convex
2,2
x
Ecksstein & Yao (2018) Hager & Zhang
Convex
relative crror
Ergadic Oi/t),
Convex,
(2020)
((1/t²)
Strongly convex
relative error
Yuan er al. 2020
Locally linear
Convex
x
X Convergence for quadratic f only
Zhao sl.
absolute
Convex
2022
f.g partial first-order
Ryu & Yin
x
Convex
x
2022
This work
Ergadic O(1/)),
Convex,
partial generalized second-order
21 absolute error
Linear
Strongly convex
Table 1: A structured comparison of related work on the convergence of ADMM and its variants. The "z" ("z") in the table denotes that paper uses the corresponding strategy of the column to simplify the z-subproblem (z-subproblem). In the "Function approximation" column, the "f" ("g") indicates that paper approximates function "f" ("g") in the z-subproblem (z-subproblem). "stochastic first-order" mcans a paper uses first-order function approximation but replace the gradient term with a stochastic gradient.
"partial generalized sedond-order" means a paper uses second-order function approximation as 7 but is not necessarily the Hessian.

---

Published in Transactions on Machine Learning Research (01/2026)
We provide the full details of sketch-and-solve ADMM in Section 7.2 To our knowledge, sketch-and-solve ADMM has not been previously proposed or analyzed.
Generalized ADMM Set /1 - 1.12 0, and fix @* - and Yo = v, where O and V are symmetric positive definite matrices. Then GeNI-ADMM simplifies to
g++1 argmin =EX
f(x) + || + N 1/1112 2 + 5110 x 10133
P
1
2
=2
ght argmin sEZ
g(2) +
P
|M N at 11 + 2
1|22 - 121
2
which is the Proximal/Gennn /eeneallzed ADMM of Deng & Yin 2016))
Linearized ADMM Set 6x - pM M and v = 3-11- - pN N, for all 2 1. Then GeNI-ADMM
simplifies to
gh+1 = prox,s (5t apM No + ++))
gh+l 3g (3th B (M#*+ + N + a²))
which is exactly Linearized ADMM Parikh & Boyd 2014 $4.4.2).
Primal Dual Hybrid Gradient The Primal Dual Hybrid Gradient (PDHG) or Chambolle-Pock al- gorithm of Chambolle & Pock (2011) is a special case of GeNI-ADMM since PDHG is a special case of Linearized ADMM (see section 3.5 of Ryu Yin (2022))
Gradient descent ADMM Consider two lincarization schemes from Ouyang al, (2015). The first
scheme we call gradient descent ADMM (GD-ADMM) is useful when it is cheap to solve least-squares problem with M. GD-ADMM is obtained from GeNI-ADMM by setting fi 0, f. and O# n/ for all k. The sk+1 update for GD-ADMM simplifies to
x E (pMFM + n/) (VI(*)) + AMM" N * +**))
(11)
The second scheme, linearized-gradient descent ADMM (LGDDADDM)), is useful when M is not simple, so that the update [II is no longer cheap. To make the æ-subproblem update cheaper, it linearizes the
augmented Lagrangian term by setting @ = a - pMTM M for all in addition to linearizing f. In this case, yields the gd++1 update
ght 3 a (Vf(**) + PM (Ma* + +N + +a*))
(12)
Observe in the unconstrained case, when M = I, the updates the same iterate sequences when initialized at the same point (Zhao al. 2021 Indeed, they are both generated by performing a gradient step on the augmented Lagrangian (7), for suitable choices of the param- eters. Notably, this terminology differs from Ouyang et al. (2015), who refer to (11) "lincarized "DMM" (L-ADMM) and (12) "linearized preconditioned ADMM" (LP-ADMM). We choose our terminology to emphasize that GD-ADMM accesses via its gradient, as in the literature the term "linearized ADMM" is
and 12 are equivalent and generate
usually reserved for methods that access f through its prox operator (He & Yuan 2012 Parikh & Boyd
2014
Deng & Yin 2016).
In the remainder of this paper, we will prove convergence of Algorithm under appropriate hypotheses on the sequences {@* (V"),, J.21, (5 and (et)
4 Technical preliminaries and assumptions
We introduce some important concepts that will be central to our analysis. The first is O-relative smoothness, which is crucial to establish that GeNI-ADMM benefits from curvature information provided by the Hessian.
8

---

Published in Transactions on Machine Learning Research (01/2026)
Definition 2 (O-relative smoothness). Let θ D - S++ be bounded. We say f : D IR is O-relatively smooth if there exists Le > 0 such that for all a, y E D
Le y yli@w)
(() s 1(0) + (VI()), - 2
(13)
That is, the function f is smooth with respect to the O-norm. Definition 2 generalizes relative smoothness, introduced in Gower et al. (2019) to analyze Newton's method. The definition in Gower et al. (2019) takes @ to be the Hessian of J. ,- When f belongs to the popular family of generalized linear models, then 13) holds with value of Li,, that is independent of the conditioning of the problem data (Gower et al. 2019
For instance, if f is quadratic and O(y) = Hy, then 13) holds with equality for LH, =. Conversely, we take θ = 7, which corresponds to GD-ADMM, then Le I,f, the smoothness constant of f. Our theory uses the fact that Le is much smaller than the smoothness constant Ly for methods that take advantage of curvature, and relies on Le to characterize the faster convergence speed of these methods.
The other important idea we need is the notion of an E-subgradient (Bertsekas et al. 2003 Hiriart-Urrute & Lemaréchal 1993).
Definition 3 (s-subgradient). Lel r D R be a conver function and 0. We say that D is e-subgradient for r at 2 D if, for every z' D, we have
r(z') - r(z) 2 (s 2) -.
We denote the set of e-subgradients for r at z by 0-r(z).
Clearly, any subgradient is an e-subgradicnt, so Definition provides a natural weakening of a subgradient. The e-subgradient is critical for analyzing z-subproblem inexactness, and our usage in this context is inspired by the convergence analysis of inexact proximal gradient methods (Schmidt al. 2011 We shall need the following proposition whose proof may be found in (Bertsekas et al. 2003] Proposition 4.3.1).
Proposition 1. Let r, Tı, and 12 be convex functions. Then for any 2, the following holds:
1. 0 E 0gr(z) if and only if r(() v argmin r(z',, that is gives e-minimum of minimize,:r(")). de(ri (z) c 0cr((2)
0gr2(2).
With Proposition ! recorded, we prove the following lemma in Appendix B.1 which will play a critical role in establishing the convergence of GeNI-ADMM.
Lemma 1. Let gh+1 give mi-mimmmmm of the z-subproblem. Then there erists an with ||||| < CV such that
-pNT h+1 -
+ +5 (
4.1 Assumptions
In this section, present the main assumptions required by our analysis.
Assumption 1 (Existence of saddle point). There erists optimal primol solution (x*,2") E X x Z for 1 and an optimal dual solution u² E U such that (x*, (²"")) is a saddle point of 2 Here, U c Z is closed conver set and pU = We denole the optimal objective value of 11 as p'
Assumption is standard and merely assumes that ① has a solution.
Assumption 2 (Regularity of and g). The function I is bwice-cootiimoous differentiable and is 1-relatively smooth with respect to O. The function g is finite- valued, convex, and lower semi- continuous.
Assumption 2 also standard. It ensures that it makes sense to talk about the Hessian of f and that f is relatively smooth. Note assuming Le 1 is without loss of generality, for we can always redefine O' Lo0, and f will be 1-relatively smooth with respect to O'.
9

---

Published in Transactions on Machine Learning Research (01/2026)
Assumption 3 (Forcing sequence summability and approximate subproblem oracles). Let (e and (et be given forcing sequences, assume they salisfy
20 Ex
00,
c < co.
Further we defone the conslants Ke, == supk21 Exy Ke. = sup owing to the summability hypotheses. Moreover, we assume Algorithm is equipped with oracles for solving the a and z-subproblems, which at each iteration produce approzimate solutions gh+1, zh-1 satisfying:
Observe Ke, and Ke, are finile
g (fi (Vf2(*)), bt) マ  I* 1 2
2I + N + 1²1))
#EX
g
gk+1
+ No 1²1 + 2 P || (
1 || s 1
ZEZ
The conditions on the x and a subproblem oracles are consistent with those of Eckstein Bertsekas (1992) which requires the sum of the errors in the subproblems to be summable. The approximate solution criteria of Assumption 3 are also easily met in practical applications, as the subproblems are either simple enough to solve exactly, LGD-ADMM the z-subproblem is simple to solve enough exactly, while for NysADMM the z-subproblem is efficiently solved via conjugate gradient with a randomized preconditioner with the standard stopping criteria. In general, the x and z subproblems are always strongly convex optimization problems, so classic criterion such as the norm of the gradient (subgradient) can be used to monitor convergence (Nesterov 2018). Often the structure of the subproblem naturally suggests a certain algorithm, c.g. a Krylov method such as LOBPCG for projecting onto the psd cone (Rontsis et al. 2022), in which case the subproblem solver may come with natural metric for determining when to terminate.
be efficiently solved approximately via iterative algorithms. For instance, with
Assumption 4 (Regularity of (0*) 221 and (V*)x2) We assume there enists constants Omax, Omin; tmaax: and v > 0, such that
m
I = 0 2 Omint, Vmax I = vh, w + N vI, for all h: 2 1.
(14)
Moreover, we also assume that The sequences {0*} {
|:21 satisfy
| x² 21 < (1 + ( ||bb - x² 11 1
(15)
|| z" 112 I (1 (1+(0 ( {| z² -12
where (c Ja21 is a non-negalive summable sequence, that is, Σx= 5h oc.
The first half of Assumption is standard, and essentially requires that O* and D N define norms. The strict positive-definiteness of the sequences (0*} and {T²) is crucial, as it ensures that the and subproblems in Algorithm 2 always have solution. Indeed, classical ADMM, which is recovered from Algorithum
2 with fi = ʃ and @* v 0 for all k may not even be well-defined without further assumptions. Chen et al. (2017) showed that without additional assumptions on f. M, or N, there exists an objective for which the x and 2 subproblems fail to have solutions, so that ADMM cannot be executed. For most common choices of O* and Vk the assunptions in [14] are satisfied; they can also be readily enforced by adding a small nultiple of the identity. The addition of such regularization is common practice in popular ADMM solvers, such as OSQP (Stellato et al.) 2020), as it avoids issues with degeneracy and increases numerical stability.
The second part of the assumption requires that @* (IV²) and e (1==1) eventually not differ much on the distance of E (o*) to x² (z*). Assumptions of this form are common in analyses of optimization algorithms that use variable metrics. For instance, He et al. (2002) which develops an alternating directions method for monotone variational inequalities, assumes their equivalents of the sequences (O*} and (V²* satisfy
- 1--t-110=-= - t = (1 + (1 - v x (1 x11+c*-1) (
(16)
10

---

Published in Transactions on Machine Learning Research (01/2026)
More recently, Rockafellar (2023) analyzed the proximal point method with variable metrics, under the assumption the variable metrics satisfy 16). Thus, Assumption 4 is consistent with the literat and is, in
fact, weaker than prior work, as (16) implies (15) Assumption may always be enforced by changing the
e*'s and I only finitely many times.
We also define the following constants which shall be useful in our analysis,
Tc = c & =
< 00.
A22
Note Assumption implies Tς < Moreover, for any k 2 it holds that
| x: 11 S Tell=* x 1', || =0 1 S Tc
Tell=*
2² 2"11
5 Sublinear convergence of GeNI-ADMM
This section establishes our main result, Theorem 1 which shows that Algorithm 2 enjoys the same ( ergodic convergence rate as standard ADMM. Section 5.1 formally presents the theorem, Section 5.2 shows how better Hessian approximations enhance the convergence rate, Section 5.3 outlines our proof approach, Section 5.4 establishes key lemmas, and Section 5.5 completes the proof.
5.1 GeNI-ADMM: Ergodic sublinear convergence
Before presenting the convergence result, we must define several important constants that appear in the theorem statement. The first set of constants represent the distances initial iterates of Algorithm from their optimal values:
d = x llet, du- = ||" - -u'l,, d=- = =| 1o2-221ll 2*Ilv"+pNTM
The next constant we define aggregates the effects of the distance to the optimum, the subproblem errors, and the changes in the variable metric:
1 d2
==
2 x0
p.x + +CE + O2E, + CgEc,
in Lemma Ts R (Ot) + X1 A1(1 N)).
where Or and C2
Lemma and C₃ 0 is constant no larger than
Theorem (Ergodic convergence). Instate Assumptions 12 and let pd denote the optimum of Run
A Aggoithmm 2 with p > 0, (et ket),2, ( salisfying Assumplion 3 {0) [02,, (T²)
satisfying Assumption and Ma - Then, the suboptimality gap and feasibility
4 and initialization (ū xt 2), where ūl
gaps satisfy
f(1++1) + g( p² || + NEttl| S
+ dz..
p
where
2+1
1+1
z1+1
gt+1
-
k=
k=
Consequently, after O(1/c) iterations,
f( + g(=tt1) - pp S 6, and |M NEttl|| Se.
The proof of Theorem is given in Section 5.5
Theorem shows that with appropriate forcing sequences, the suboptimality gap and the fcasibility residuals both go zero at rate of (11tt). Hence, the overall convergence rate of ADMM is preserved despite all the approximations involved in GeNT-ADMM.
11

---

Published in Transactions on Machine Learning Research (01/2026)
5.2 The benefits of using better Hessian approximation
An important consequence of Theorem i that not all approximate ADMM schemes yield the same perfor- mance. GeNI-ADMM schemes that use better approximations ot the Hessian enjoy faster convergence, To see this, let us focus on the case when f is convex quadratic function and M I. Let Hy be the Hessian of f. Consider (a) NySADMM 6* H (10) and (b) GD-ADMM O* = 7 11]. Further, suppose that NysADMM and GD-ADMM are initialized at The rates of convergence guaranteed by Theorem | for Algorithm for both methods are outlined in Table 2
In the first case, the relative smoothness constant
Table 2: Convergence rate comparison of NysADMM and GD-ADMM when initialized at 0 for quadratic f.
Method
NysADMM
(e+ = Hi)
GD-ADMM (@* =1)
Feasibility gap
( (3V Ae (Hr) ((=Tl))))))
Suboptimality gap
2 || (12,,)
o ( (H,) 11=)
satisfics Le 1, while in the second, Le = A1 (Hy), which the largest cigenvalte of Hy. Comparing the
rates in Table 2 we see NysADMM improves over GD-ADMM whenever
A (1f) | | 1
Hence NysADMM improves significantly over GD-ADMM when H, exhibits a decaying spectrum, provided x* is not concentrated on the top eigenvector of Hy. We formalize the latter property in the following definition.
Definition 4 (uv-incoherence). Let V be the eigenbasis of Hy. We say is pv-incoherent if there exists 1 pv < d such that:
|0+1|2
sup (Vv,,*))2 S nv d
(17)
Isid
Definition 4 is a weak form of the incoherence condition from compressed sensing and matrix completion, which plays key role in signal and low-rank matrix recovery (Candes & Romberg 2007 Candes & Recht 2012). In words, x" is pv-incoherent if its energy is not solely concentrated on the top eigenvector of H and can be expected to hold generically. The parameter Ve controls the allowable concentration. When f = O, wt is orthogonal to v, so its energy is distributed amongst the other eigenvectors. Conversely, the closer pvv is 1, the more x* allowed to concentrate on v.
Using py-incoherence, we can say more about how NysADMM improves GD-ADMM.
Proposition 2. Suppose x² is pv-inccherent and o = (Hf)) where t E (0, 1). Then, the following bound holds
X1 (H
d
12
pvintdim(H,)
Hence if pv + )g(H,)/A (1- - where a 2 1, then
1x 1
The proof of Proposition is given in Appendix B.2 Proposition 2 shows when x= is jy-incoherent and Hy has a decaying spectrum, NysADMM yields a significant improvement over GD-ADMM. As concrete example, consider when a = 2, then Proposition implies the ergodic convergence NysADMM is twice as fast GD-ADMM. We obscrve this performance improvement in practice; see Section g for corroborating numerical evidence. Just Newton's method improves on gradient descent for ill-conditioned problems, NysADMM is less sensitive to ill-conditioning than GD-ADMM.
2
12

---

Published in Transactions on Machine Learning Research (01/2026)
5.3 Our approach
To prove Theorem 1 we take the approach in Ouyang el al. (2015), and analyze GeNI-ADMM by viewing
Eq. ( through its formulation as saddle point problem Eq. 22. Let W = =xxXXXX e = (á, ú), and
w = (1,2, u), where w, á E W. Define the gap function
Q w) = (x) + g(2) + (pû, Mæ + Nz)] - (2) + 9(2) + (pu, Ma + N
(18)
The gap function naturally arises from the saddle-point formulation Eq. (2). By construction, it is concave in its first argument and convex in the second, and satisfies the important inequality
Q(w", , w) Lo(a, 2, u²) Lo(a* ,2 u) 20, 0,
which follows by definition of (a+ , x", ,²)) being a saddle-point. Hence the gap function may be viewed measuring the distance to the saddle w².
Further, given closed set U - Z and E Z we define
(v, w) = sup (Q w) + (u, pū) | - -0; ( f == x², == ==² 2²}
(19)
áet
f(x) + g(=) - n" + sup (pû, v (Mx + N2)).
aet
The following lemma of Ouyang et al.
2015 relates (ūù, w) to the suboptimality and feasibility gaps.
Lemma 2. For any U C 2, suppose ty (Mx+ N2, w) S < oo and Mc+ < 6, where w = (x,, 2, E W. Then
f(x) + -(2)
(20)
In other words, (x,, z) is an approzimale solution of ① with suboplimality gap and feasibility gop 8. Further, if U Z, for any v such that (v, w) < 0o and ||||| S ö, we have Mxx
Lemma 2 shows that if we can find w such that lu (Mx + N2, w) S and | + N2 S 6, then we have an approximate optimal solution to with gaps and 6, that is, (M + N2, w) controls the suboptimality and feasibility gaps.
5.4 Controlling the gap function
Lemma shows the key to establishing convergence of GeNI-ADMM is to achieve appropriate control over the gap function. To accomplish this, we use the optimality conditions of the x and & subproblems. However, as the subproblems are only solved approximately, the inexact solutions satisfy perturbed optimality conditions. To be able reason about the optimality conditions under inexact solutions, the iterates must remain bounded. Indeed, if the iterates are unbounded, they can fail to satisfy the subproblem optimality conditions arbitrarily badly. Fortunately, the following proposition shows the iterates remain bounded.
Proposition 3 (GeNT-ADMM iterates remain bound). Let (s*) (e/] (02),, (V*),2 and > 0 given. Instate Assumptions 4 Run Algorithm & are bounded. That is, there exists O, such that
then the output sequences {# Ja2) [
Ja21 Ja21
( Je21 c B(x R), {2* C B(2,,R),
{ūr c B),,
The proof of Proposition provided in Appendix B.2
As the iterates remain bounded, we can show that the optimality conditions are approxinately satisfied at each iteration. The precise form of these perturbed optimality conditions is given in Lemmas 3 and Detailed proofs establishing these lemmas are given in Appendix B.2
Lemma 3 (Inexact z-optimality condition). Instate Assumptions
Suppose $h+1 is an Ex miinimizerr 3 Then for some absolute constand C2 0 larger than
of the s-subproblem under Assumption max (L,, R, (0max + (M) L,, Ke,, (0maz P)I(MT x²) S (0* (2++1 1111_ah -²*),0-
sup= (S..x*))1. we have
(V + V. 1 --)
(21)
+ + + N + at ",,M(a" - x(+l)) + C.
13

---

Published in Transactions on Machine Learning Research (01/2026)
Lemma 4 (Inexact z-optimality condition). Instate Assumptions I 4
Suppose g++ is ---mmmmmm
of the z-subproblem under Definition [ R/ 8/VVnn Vmmin + pdmino (NT + Ket, we have
Then for some absolute constant C² > 0 no larger than
a(=)) g( 2 (-pN" + wh - - - C:Ve
(22)
When et = = = 0 the approximate optimality conditions of Lemmas 3 and 4 collapse to the exact optimality conditions. We also note while Lemma 3
(Temma necessarily holds when T++1 (E*+1) is an e ed-approximate minimizer (E5- sef-minimum), the converse does not hold. With Lemmas of the gap function for one iteration.
3 and in hand, we can establish control
Let ohtt ( gh+1 a denote the iterates generated by Algo- rithm at iteration k. Set w (x" (x".2" 2 u), then the gap function Q satisfies
Lemma 5. Instate Assumptions 4
Q(u,wüht)
1 2 (10* x01 - -11att1 - x² =10x)) + 2
1
11E**
Il live TOLTNNNN 1| 20 N)
2
+ 2 (11* - - - ull?) + Cae + C2
P
Proof. From the definition of Q;
Mxx Quw, 1 = f(ah+1)- - f(x*'*))))))))>)))) + g(2 - g(>") + (pu, Ma + + - (pūkt), Max + N2*).
Our goal is to upper bound Quu: 11)) We start by bounding / (igh1) - [(x²) as follows:
f(i )) - f(x*) = (fi (5 - fi (z()) + (fa(#*+1) - -2(()))) + (fa(1t)) - -fa(x*)
) gk+1 (
~²) + (V ((**)) ght1 - - + | - 1 + +fa(ih) =2(2")
[V gk+1 の³) ) + (V f2 ) xh+1 - -sth + 2
||aht1 1 14 + (V ). -x²)
1 | - I²h 11
(Vi( {22( .
2
where (I) uses convexity of fi and 1-relative smoothness of fe, and (2) uses convexity of f2. Inserting the upper bound on f(# into the expression for Q(w, 1) we find
1 11 11 + g(zht1) g(=²)
Q(u,w++1) <
), V22 5*+1 x²) + 2
(23)
Mp Ma ++ + N (pūnt) MMx + +N²)..
Now, using the inexact optimality condition for the z-subproblem (Lemma 3 the above display becomes
< (0"(2" - ,²),2* x² - - + p(M + N + ät M(x - x)+l)) + Cas
1 1 2
- - + +( g((²) + (pu, M + N (pūtt1, MMx + NN*).
+
Similarly, applying the inexact optimality for the z-subproblem (Lemma 4 we further obtain
Q(w, (o, < (0) _ ,*), - + h+ + N + at. M 1 x + Ca
1 + | 11 - ,
zh+1 x²) + (1 (ght1 - =,), 2 - = + C2 Ve
(24)
2
+ (pu, MM N (pö*+1 1,,1,,, Mxx + N
We now simplify 24 by combining terms. Some basic manipulations show the terms on line of (44 may be rewritten as
- p(NT a +++1 gh+1 - 2²) + pLu, Mra+1 , Ma+h1 + NN p(irt1, ( x(+1))
1 + NEh+1) - -(a/tt, MM* + No*)
p(u r+++
14

---

Published in Transactions on Machine Learning Research (01/2026)
We can combine the preceding display with the second term of line 1 in 24 to reach
P\M + No + ut,, M(x' - 1) - p(ū .Mxx' - x xb+1)) + plu - att M + N
=plitt + N - ) M( xbtl))
plattt _Mxx' )ltl)) plu a "ett,, + N
= - = Max x1+1) + plu - nht,, Mat + N
- =P(N (s -
) M(x - =btt))) + p\ū u, at -iht)).
where N = -N Insorting the proceding simplification into 24 we reach
Quu, w S (+*(t - )²,,,²² xx - x ) + pla k u, ut - 1
+ (= -
-
1 + p\N (= 22,,, a
(25)
+ - - 111 + +C + C2 V
Now, we bound the first two leading terms line of (25 by invoking the identity (a (a- b, T(c - -d) = 1/2 (Ila - dll lla cll+t + 1/2 (Ilc - blß - ||d - bllT) to obtain
(0*(2 - -zt),, )² x- - 1 + p(ūnt1 - u, at - aut1)= =
(1I=* - =1112x -1a=-=0113 ||00 +++1 12x)) - _1124 3*1 P (lii* -1la-11ätt] a1|2-11i² -a---at-111 11))
1
Similarly, to bound the third and fourth terms in 25 we again invoke (a b) d) 1/2 (Ila - dll? lla cl + 1/2 (Ile - bll? - ||d bll?)
which yields
- ), 2" - + 1 (11# - 21 11 - =*(()x)) - 2
1 1 - =
2
and
p(N (zt =x*t1), M, (itht xx))
1 (IIN- zh MM* 1 -1E 1 + ||N-~ gh+1 M N M
= -2 (ILNE* - -N - - - | + + Gl t
Putting everything together, we conclude
Quu, u(
5 2
1
(15* 111 || x² (1 + 2
1 (1E** -=- =11lxx -11 -2" 12 + N
P (l u112 - ||aht1 - u012) + Cx + O2 Cov
+ 2
as desired.
5.5 Proof of Theorem
With Lemma in hand, we are ready to prove Theorem 1
Proof. From Lemma
we have for each k that
Q(u, wi <
1 (11a* x= 211 - || x² (1xx)) + 2/2 (11** -2- 111
1
12112x -12 2" =1 N)
2
(1/a uu|2² - || - u0l2) + Cn + C2
2
15

---

Published in Transactions on Machine Learning Research (01/2026)
Now, summing up the preceding display from & = 1 to t and using w (x* ,0", u), we obtain
++
Σ Q(0 =", u; m²))
- 2 (1 x² 11.2 - || x² 112x)
71
2** 1 |
+ +ONTN - || 2²1 +
T2
t
P (117
| ++1 u1l2) +CoEz + C.E.. u1|2
k=1
TB
We now turn bounding Ti. Using the definition of Ti, we find
2 (1 x= x11... - || x² 11xz)
k=1
1 (11E - 1121 - -110t1 x= (12:) +
t
(1 11 -110* xx" x²16)-1)
2
2 k=
Now using our hypotheses on the sequence {0*} k in 15 we obtain
1 - x² 12 - -11=* x01 211 = (5* x²) x="TT((3) ( 8 0²-1)(0"
= 55 - xx" 21(1/
S + x r"I....
Inserting the previous bound into Ti, we reach
Ti -
| x= 11 + Tc
x- 115 - -x"113 2 I1 x² x1....
2
1
1 | x= 1la.
1
2 (|5) 11 Te RA, (A) (+g)
1
5
(
@1 + (+))))
2
Next, bound T2.
T2-
1
|1
- -1Ett1 -21113 11 +pNTN)
2 k=1
1
(113²
2"12"'0ONT - |1et1 2* 113++pNT
+
1 Σ
-
=1 - -118 x= 11 11laa-++ +
2
2
111a1 - 2" =11G14ANTN + TTc Σ x 1|* - 2" 2'1211
1
<
1
(112) =' + Te TCRAI (v) + SONTNNE))
2
1
(d i. + (V² + ONN'NEE) +
2
16

---

Published in Transactions on Machine Learning Research (01/2026)
Last, T3 is telescoping sum, hence
T2
(11t - u11² -dl2-1l20 -1pa-11tt1 - =ll?)
2 (la² ul1² - -Il =ul²)
2 1=1
Defining C₂ = TC (Ai( + (A)))) A1
+ NN) and using our bounds on Ti through T3. we find
Q(x ,- u: r
(1g + +cEEc)
1 de = AN
2 C C.E + C.E.
+
P
|| u11--11tt - =11²)
2
,8 + _d
+ CnEz + C.E2 + C&E + 2 (1li w/l² - -1|u't1 =)l())
2 x"
2 p.v
Now, as = E tht the convexity of Q in its second argument yields
1+1
u1 +1
Σ
,,;")",,;;")))
k=2
$ 2 , ga
+
p.x 2 + CzE + C2E, C5E + (1la - -u|3- -1 - u1(?)
(26)
Define r' = _
11 + d
+CE + CzEs + CgEc.
Since Q(w", w( 2 0, by 26 we reach
v1 P.N
2 r + de.
| un 1|
p
Let gr+1 = 1 (ū-- - t.. Then can bound || 1|2
4 T
1| S (1 u²112 1
s
du
t2 p
By (66 given the fact ät 0, we also have
Q(x , u - - p(ù²
ut+1 u)
r
p(ōtt), ,u),
where the equality follows from the definition of gt+1 Hence for any
Q(x" 2 u,,,, x1 + (6--1, pu) < r
7
and therefore
( 1 S (eee ee
1
2 Fer + CCEx + C2E. + CGEC
de
We finish the proof by invoking Lemma 2
6 Linear convergence of GeNI-ADMM
In this section, we seek to establish lincar convergence results for Algorithm convergence of ADMM relies on strong convexity of the objective function (Boyd el al. 2011 Nishihara et al. 2015 Parikh & Boyd 2014h. Consistently, the linear convergence of GeNI-ADMM also requires strong convexity. Many applications of GeNT-ADMM fit into this setting, such as clastic net (Friedman et al., 2010). However, linear convergence not restricted strongly convex problems. It has been shown that local linear convergence of ADMM can be guaranteed even without strong convexity (Yuan et al. 2020
2 In general, the lincar
17

---

Published in Transactions on Machine Learning Research (01/2026)
Experiments in Section show the same phenomenon for GeNI-ADMM: it converges linearly after couple of iterations when the iterates reach some manifold containing the solution. The linear convergence theory of GeNI-ADMM provides a way to understand this phenomenon. We first list the additional assumptions required for linear convergence:
Assumption (Optimization over the whole space). The sets X and Z in satisfy
== X, and Z = 2.
Dusumpttionsstttee that the optimization problem in [1 is over the entire spaces X' and Z, not closed subsets. This assumption is met in many practical optimization problems of interest, where X' 2 H R Moreover, it is consistent with prior analyses such as Deng & Yin 2016) who specialize their analysis to the setting of the last sentence.
Assumption (Regularity of f). The function f is finite valued, strongly conver with parameter o, and smooth with parameter Lig-
Assumption imposes standard regularity conditions on f, in addition to the conditions of Assumption 2
Assumption 7 (Non-degeneracy of constraint operators). The linear operators MM and N are in-
vertable.
Assumption 7 is consistent with prior analyses ADMM-type schemes under strong convexity, such as Deng & Yin 2016). who make this assumption in their analysis Generalized ADMM. Moreover, the assumption holds in many important application problems, especially those that arisc from machine learning where, typically, M and N --
Assumption 8 (Geometric decay of the forcing sequences). There exists constant > such that the forcing sequences {=*),21, {e satisfy
++1
S / + q), and c k+1 s 2)
(27)
Moreover, we assume Algorithm iteration produce approrimate solutions gh+1, zh+1 satisfying:
2 is equipped with oracles for solving the x and 2-subproblems, which at each
++1
(f (v ) 2h) |
x² 1
fIl No +
+
kk1 z
argmin(g(=) f M ++1 + Nz NN+ u2
1 + 1 11
*E%
Assumption replaces Assumption 3 and requires the inexactness sequences decay geometrically. Com- pared with the sublinear convergence result, linear convergence requires more accurate solutions to the sub- problems. Again, since the z-subproblem inexactness is weaker than the z-subproblem inexactness, {cf) should have faster decay rate (1 + q)² than the decay rate (1 + q) of (=11221
The requirement that the forcing sequences decay geometrically is somewhat burdensome, as it leads to the subproblems needing to be solved to higher accuracy sooner than if the forcing sequences were only summable. Fortunately, this condition seems to be an artifact of the analysis; our numerical exporiments with strongly convex (Section 8.2 only use summable forcing sequences but show linear convergence of GeNI-ADMM.
6.1 Our approach
Inspired by Deng & Yin 2016 we take a Lyapunov function approach to proving linear convergence. Let T (ī, 2, ū) and w² (x" "=""" ut). We define the Lyapunov function:
1 ||tt - x= 12 1 x -2+13 +ONTT + 1| u²1l2= 1/t w w111,
p
18

---

Published in Transactions on Machine Learning Research (01/2026)
where
0
G
tp N N
Our main result in this section is the following theorem, which shows the Lyapunov function converges linearly to
Theorem 2. Instate Assumplions and Assumptions H Moreover, suppose that miin in 14 salisfies
mmnn Lj Then there erist constants and S such that if 6,
(1+ S TT S.
(28)
Hence after h = O (² log ) ilerations,
Φ E.
The proof of Theorem 2 is deferred to Section 6.3 As G > for all k Theorem implies the iterates (#* st it") converge linearly to optimum (x* 2², w²) Thus, despite inexactly solving approximations of the original ADMM subproblems, GeNI-ADMM still enjoys linear convergence when the objective is strongly convex. The requirement in Theorem that 0 > L is not present in Deng & Yin (2016). Recall the Generalized ADMM scheme analyzed in Deng & Yin (2016) does not employ Tunction linearization and only uses fixed metrics. The additional condition on 0min arises from the linearization of f. In particular, it stems from lower bounding the term - (222(*=1) (ā**), g (*+1 x²) in Lemma which vanishes when f is not linearized f2 Given GeNI-ADMM allows for this further approximation in the z-subproblem, it is perhaps unsurprising that additional condition required to ensure convergence.
The new condition Omin always be enforced by adding damping term of to O*. However, this could be undesirable as large regularization term might lead GeNI-ADMM to converge slower. Empirically in Section S we find that GeNI-ADMM converges linearly without enforcing this condition. It is an interesting direction for future work to see if this condition can be removed while guaranteeing linear convergence.
6.2 Sufficient descent
From Theorem 2 to establish linear convergence of GeNI-ADMM, it suffices to show Φ² decreases geomet- rically. We take two steps to achieve this. First, we show that || w "1. || - 11 decreases for every iteration (Lemma 7) Socond, we show that ah+1 decreases geometrically by a factor of 1/(1 + 8)
with respect to & and some small error terms that stem from inexactness (Lemuna 8
As in the convex case, the optimality conditions of the subproblems play vital role in the analysis. Since the subproblems are only solved approximately, we must again consider the inexactness of the solutions in these two steps. For the first step, we use strong convexity of f and convexity of with appropriate perturbations to account for the inexactness. We call these conditions perturbed converity conditions, as outlined in Lemma
Lemma 6 (Perturbed convexity). Instate the assumplions of Theorem Let gk+1 and gb+1 be the ineract solutions of and 2-subproblems under Definition 7 Recall (a* ,,,,,"""" uu") is saddle point of 1 Then for some constant C 0, the following inequalities satisfied:
1. (Semi-inexact f-strong convexity)
- - xb+1 gh+l - ==) + p(N(z - + xt M(5ht] x²)) + Ce
(29)
G -1 (V (V gx#t1 -z))
2. (Semi-inexact g-convexity)
(g++1 2² 2 PNNT22 (u" -ihtl) + - -CVE..
(30)
19

---

Published in Transactions on Machine Learning Research (01/2026)
A detailed proof of Lemma 6 is presented in Appendix B.3
In Lemma 6 we call (9 and 30
semi-inczact
(strong) convexity because xx (=*) is part of the exact saddle point but -++1 (z*+1) is an inexact subproblem
solution. With Lemma G we establish a descent-type inequality, which takes into inexactness.
Lemma 7 (Inexact sufficient descent). Define E = Ex + VEZ, then the following descent condition holds.
| w w'llot - |1 w= 16 + Ce 2 | w w 1 + 201 1/12 - ==2
(31)
2
p
2 f2(bttt) f2222* j -x*).
P
Proof. Adding the inequalities
29 and (30 logether, and using the relation M( - xx²) =w++1 -tt
- - reach
(5t - gkt1 ; ghtt= - =x")e- + (3 =++1 ght1 =²) ='>++o + p(at -1t+1 ,
ght1 - u²) + C
Ty|laht! =0112-1 (VVS((ttt) ) getl x²) / + plat* - NN - =²
Recalling the definitions of w = and G and using the identity (a - b, T(c d))
1/2 (Ila ? ||a ) + 1/2 (Ile - blb - ||d bilT), arrive at
1 w' 1l ||0 w0 11 = 2 20 ||aht1 - x011 + || 2 12
+ (it - =h N((ht1/_ - =²)) - 2 ( -V2((T)), gktt x²).
Now, for the term | 113 + (ūt xhtl N( **)), Cauchy-Schwan implies
|
x 11 + (ūt -tt
_ ,NN(ttt1
=
| w6 11
|laht1 - 1p112
デ | - 13
2 1 wh 18:+
2 1 - 1
] || - "
2 1 w/ 11.....
Hence we obtain
201 |
1
| w² 11a w² -1102tt-w'112 + Ce 2
111 + 11 1=112
2 f2( ), ght1 - =x");
as desired.
Given the inexact sufficient descent condition 31
the next step in proving linear convergence is to show
31 leads to a contraction relation between th FF and t²
Lemma (Tnexact Contraction Lemma). Under the assumptions of Theorem 3 there exists constants > 0, and C such that
(1 (1+8)) (1+ (Ø* + Ceth)
(32)
The proof of Lemma S and an explicit expression for 8, appears in Appendix B.3 As in Theorem 2 the constant 8 gives the rate of lincar convergence and depends on the conditioning of f and the constraint matrices M and N. The better the conditioning, the faster the convergence, with the opposite holding true the conditioning worsens. With Lemma g in hand, we now prove Theorem
20

---

Published in Transactions on Machine Learning Research (01/2026)
6.3 Proof of Theorem 2
Proof. By induction on 32 have
k
* 30+
k M*++s) [=]
(1 + 8 v
(1)
4'
(1 (1+6)² 11+5)-122
1=1
1=1
(11+0)
(1 5-1
S T + CTc
Σ
(1+ (1+88--18 c/ S Tc + CTc
Σ
1+9
5=1
==1
CTc
S TT
T² + S,
1+8
144
where the second inequality uses Assumption g to reach o S [T+g3 and the third inequality uses > d to bound the sum by the of the geometric series. Hence, have shown the first claim. The second claim follows immediately from the first via routine calculation. D
C
7
Applications
This section applics our theory to establish convergence rates for NysADMM and skotch-and-solve ADMM.
7.1 Convergence of NysADMM
Algorithm 3 NysADMM
input:
penalty parameter P; step-size i,, regularization a 2 0, forcing sequences [0*) (0t)e21 repeat
Find ch approxiiie solution g*+1 of
(n + + no) (HH + +oT)** (S((h)) + p(= - -a*)
gh+1 argmin + ||| 2 + 11 =EZ
h+1 = /Z + Ma
s -1+1
until convergence
output: solution 2x*, of problem
We begin with the NysADMM scheme from Zhao et al. (2022). The defining aspect of NysADMM is that it lincarizes f to turn the r-subproblen into a linear system. NysADMM solves this system inexactly using the Nyström PCG method from Frangella et al. 2023
Previously Theorem 4.3 of Zhao et al. (2022). only established convergence of NysADMM in the case where f is quadratic and without providing an explicit rate of convergence. In the discussion in the paragraph below Theorem 4.3, Zhao et al. (2022) left open the question of convergence for general f, while conjecturing that strong convexity could ensure lincar convergence rate. In this subscction, we address convergence for non-quadratic by establishing O(1(t) ergodic convergence rate, when f is smooth and convex. This significantly strengthens the result of Zhao et al. (2022) by showing NysADMM enjoys the same rate
classical ADMM in this setting.
Recall MySADMM is obtained from Algorithm 2 by setting fi = 0, = S, using the exact. Hessian * = ( = T/H ol), and setting * obtain NysADMM, presented as Algorithm Compared the original NysADMM, Algorithm B adds a regularization term ol to the Hessian. In theory, when f only convex, this regularization term is required to ensure the condition * 2 Omin of Assumption the Hessian along the optimization path may fail
Instantiating these selections into Algorithm 2 we
21

---

Published in Transactions on Machine Learning Research (01/2026)
to be uniformly bounded below. The addition of the oI term removes this issue. However, empirically this seems to be unnecessary as as Zhao et al. (2022) runs Algorithm 3 on non-strongly convex objectives with a = 0, and convergence is still achieved. We observe the same behavior in all our experiments, where we use a = throughout, and convergence consistent with our theory is obtained. Hence, in practice, we recom- mend setting some small value, say o = 10- so that convergence isn't slowed by unneeded regularization. This already consistent with best practices ADMM solvers like OSQP (Stellato et al. 2020), which adds small regularization term ensure stability.
We obtain the following convergence guarantee by substituting the parameters defining NysADMM (with the added oT term) into Theorem
Corollary (Convergence of NysADMM), Instate the assumplions of Theorem Then
Let a > 0. Set fi =
0.f2 = f, 7 Lg, o = n + ol), and w =0 in Algorithm
2
r t EV
f
+ g(( - -p" F¹
|M + N
+ dh..
p
Here I' and di. are the same as in Theorem
NysADMM converges at the same ((l/t)-rate as standard ADMM, despite all the approximations it makes, Thus, NysADMM offers the same level of performance as ADMM, but is much faster due to its use of inexactness. This result is empirically verified in Section [ where NysADMM converges almost identically to ADMM. Corollary supports the empirical choice of a constant step-size 1, which was shown to have excellent performance uniformly across tasks in Zhao et al. (2022): the theorem sets 77 = Lg and L, = 1 for quadratic functions, and satisfies f,y O(1) for loss functions such as the logistic loss. We recommend setting = 1 as the default value for GeNT-ADMM. Given NysADMM's superb empirical performance in Zhao et al. (2022) and the firm theoretical grounding given by Corollary [ we conclude that NysADMM provides reliable framework for solving large-scale machine learning problems.
7.2 Convergence of sritch-and-solve ADMM
Sketch-and-solve ADMM is obtained from GeNI-ADMM by taking O* to be an approximation of the Hessian of f. We focus on the case when the approximate Hessian is computed by a sketching procedure, though
we note that * need not be obtained in this manner. The two most popular sketch-and-solvv methods are
the Newton sketch (Pilanci & Wainwright, 2017; Lacotte et al. 2021 Derezinski et al. 2021 and Nyström
sketch-and-solve (Bach) 2013 Alaoui & Mahoney 2015 Musco & Musco 2017 Frangella et al. 2023 Chen
ct al. 2025)
We briefly review these idcas, before discussing Skotch-and-solve ADMM in detail.
Newton sketch the Hessian H3 can be written in the form H = I.T for some L E Rexd which occurs for many important problems (Pilanci & Wainwright, 2017). The Newton sketch uses the approximation:
= S
where is a random sketching matrix. The sketching matrix S could be a Ganssian embedding, a fast structured random embedding, or a row sketching matrix (Pilanci & Wainwright, 2017 Lacotte et al.) 2021 Derezinski et al. 2021). If n > d, then typically s Ö(d) and y O, otherwise the order of the effective degrees of freedom of f7 Using structured
d, s < d is typically
used, with 8 being selected sketching matrix allows for A to be constructed and factored in Ö(nd + ds²) time (Pilanci & Wainwright, 2017 Lacotte & Pilanci 2020). For more details on the Newton Sketch, we refer the reader to Pilanci & Wainwright (2017): Lacotte et al. (0021): Derezinski et al. 2021
Nyström sketch-and-solvv Nyström slotch-and-solve Bach 2013 Alaoui & Mahoney 2015 Musco &
Musco 2017 Frangella et al.
2023 uses a randomized Nyström approximation GGtttens & Mahoney 2016
Tropp et al. 2017) to H..
+ = ([
22

---

Published in Transactions on Machine Learning Research (01/2026)
where S E R is random sketching matrix. Similar to the Newton Sketch, S can be standard Gaussian random mairix, a structured random embedding, or it could correspond to column selection scheme such as uniform column sampling, leverage score sampling, or adaptive randomized pivoting (Bach) 2013 Alaoui & Mahoney 2015 Tropp et al.) 2017 Musco & Musco 2017 Chen et al.) 2025p. The sketch size s is taken to be much smaller than d, so that H always a low-rank approximation to Hy. Similar to the Newlon Sketch, if S. is structured random embedding, then f7* can be constructed in O + ds²) (Tropp et al. 2017 For details Nyström -nd-slv and its implementation refer the reader to the references Bach 2013); Alaoui & Mahoney (2015); Musco & Musco [2017) Frangella et al. (003) Chen et al. (2025)
7.3
Sketch-and-solve ADMM algorithm
We now present the soelsl-and--olvv ADMM algorithm. To the best of our knowledge, this is the first time using a sketch-and-solve approach with ADMM has been formally developed and analyzed.
Our consideration of this scheme is motivated by the recent survey Bulue et al. (2022), which discusses in Section 2.3 the possibility for randomized algorithms to accelerate the solution of large-scale inverse problems. Specifically, (Buluc et al., 2022 pg.13) proposes using sketching approximate expensive lincar system solves in the ADMM subproblem associated with the data fidelity term. The idea is natural given the effectiveness of algorithms that combine sketching with Newton-type methods (Pilanci & Wainwright 2017
& Mahoney 2019 Na et al.) 2023 Frangella et al.) 2024 Jiang et al., 2024). However, no theoretical or empirical support for combining ADMM with sketching is presented. This omission is significant, as even in the simple case of quadratic smooth term, so that no linearization of ʃ in the æ- subproblem is needed, standard ADMM theory does not guarantee convergence. Indeed, classic results like those of Eckstein & Bertsckas)
19922 assume the subproblems are solved to progressively better accuracy, assumption that is not satisfied when solving the subproblem via sketching. Convergence is even less obvious when f is non-quadratic, as linearizing f is required to reduce the a-subproblem to solving linear system.
In this section, we resolve this problem by providing the first convergence guarantees for sketch-ande and-solve ADMM, extending classical ADMM theory to accommodate inexact sketched solves.
Algorithm 4 Sketch-and-solve ADMM
input: penalty parameter P; step-size 7,, {= repeat
Construct approximation fg of Ha. Find solution g*+1 of
(n + (p (p+ ) -
(ft + + ( -Vf(=+))+ + p -1t)
g argmin(g(<)) + Matt1 + 13
=EZ
+++ = tt + Ma gk+1
until convergence
output: solution (x*,²*) of problem
Sketch-and-solve ADMM presented in Algorithm is obtained from Algorithm 2 by setting
@* - (At* + ++)+)=
(33)
where A is an approximation to the Hessian H (**) at the kth iteration, and 7* 2 0 is a constant chosen ensure convergence. The term y*1 ensures that the approximate lincarization satisfies the O-relative smoothness condition when n* is chosen appropriately, in the following lemma:
23

---

Published in Transactions on Machine Learning Research (01/2026)
Lemma 9. Suppose is L--relatively smooth with respect to its Hession H.. Construct (0r 1021 as in 33 with 1. is such that one of the following conditions is salisfied:
1. Suppose that 7h 0 salisfies 7h | [+
11 for every k. Then
Lg
f(z) S f(i + (V f (V x 24) )+
-
2 211x --211 2²
2. For all & > O there erists 0 T < 1, such that
(1 (1- + , 3 ft + 7 +1+ (1) 1*
Then
L r) | x 11a..
f(z) - + 2h,
2
For the proof of Lemma 9 please see Appendix C
Lemma shows we can ensure relative smoothness by selecting >* > appropriately. Assuming relative smoothness, we may invoke Theorem | to guarantee that skotch-and-solve ADMM converges. Unlike with NysADMM, we find it necessary select 7* carefully (such as in Lemma g to ensure the relative smoothness condition holds, otherwise sketch-and-solve ADMM will diverge, see Section 8.3 for numerical demonstration. The need for this condition is different from prior sketching schemes in optimization, such as the Newton Sketch (Pilanci & Wainwright 2017 Lacotte et al. 2021 where convergence is guaranteed as long as the Hessian approximation is invertible.
7.4 Quantifying 7h required for convergence
Lemma shows that 7ht must be set appropriately to achieve convergence. We now discuss how results from the sketching literature allow us to quantify this parameter. We focus on item 2 of Lemma g as it encompasses both the Newton Sketch and Nyström
Item 1 is only of interest in the case of Nyström sketch-andd-sllv,, as the Newlon Sketch provides an unbiased approximation of H Consequently, it exhibits Monte Carlo-style errors that are independent. of the eigenvalue decay of H (Tropp) 2015), hence || can be quite large. In contrast, error guarantees for the Nyström approximation depend directly upon the spectrum of H!! (Gittens & Mahoney small when H. is approximately low-rank.
2016 Tropp et al. 2017 Frangella al. 2023), so that || is
Now, if Hx is a randomized Nyström approximation or Newton Sketch constructed via leverage score sampling or random embeddings with a sketch size of s Ö(r), with r < d, then the following is known to hold with high probability (Musco & Musco 2017 Dereziński et al. 2025 Dereziñski & Sidford. 2025):
+
H
+ + 1
A**
CH 22 H + 1 E j2r
2
j>r
1>r
9 holds with t = 1/2 and 7* = + (,(H). Hence, when H/ is approximately low-rank, only small moderate damping is needed to ensure convergence. However, if H has slowly decaying spectrum, larger regularization is required to ensure convergence. As shall see below, the size of the damping directly impacts the convergence rale.
Thus, item 2 of Lemma
7.5 Sketch-and-sole ADMM convergence guarantee
We now formally state our convergence guarantee for Sketch-and-sole ADMM.
Corollary 2. Suppose f is prrelaiively smooth with respect to its Hessian H₃ and instate the assumptions
of Theorem In Algoritho set 0 n k + x²T) with 7 1, V 0, and suppose * satisfies the
24

---

Published in Transactions on Machine Learning Research (01/2026)
conditions of item 2 in Lemma g
Then
Ls (8
+ 7:
1( + g(( - p² 2
( +r +
1-T 2.
and
2 i /V +
|M -
du..
Here variables x++1 and g++1, diameters df n Ar dz,, and di,,, and constants Cz. C2, Ex, Es, &c, and p* are all defined as in Theorem 1
Corollary 2 shows sketch-and-solve ADMM obtains an - convereeceeee rate. Compared to NysADMM, L, has been inflated by 1/(1 1/(1-r) and new error term n dz. appears, both of which stem from using an approximate Hessian H In particular, the 7 term introduces tradeoff. H can be constructed with a small sketch size to enable very fast inversion, but as Section 7.4 shows, 7 may have to be quite large to ensure convergence, especially when the spectrum of Hÿ decays slowly. Corollary 2 shows that larger y implies Sketch-and-solve ADMM suffers from a slower convergence rate relative to using the exact Hessian as in NysADMM. Conversely, y1 can be made small by using a large sketch size, but at the cost more expensive iterations. Given this tradcoff, Sketch-and-solve ADMM is expected be most useful in two scenarios: 1) problems that are highly over wver-detrrmnned, so that the Newton Sketch can be applied with sketch size ((d) and 7* 0, 2) problems for which H is approximately low-rank so that Nyström sketch-and-solve or Newton Sketch can be applied with sketch size much smaller than d with small value of 7a
The proceding considerations lead to an important observation: Sketch-and-solve ADMM can be regarded as a compromise between NysADMM (@* = (**) + +o)) and gradient descent ADMM (@* = n/), with the convergence rate improving as the accuracy of the Hessian approximation increases. In particular, if fi* provides a poor approximation (i.e., when 7 large), Sketch-and-solve ADMM may not perform much better than gradient descent ADMM. Conversely, when H} is a good approximation to H}. the method can approach the performance of NysADMM while remaining computationally efficient. This hybrid behavior predicted by Corollary 2 is confirmed in our experiments in Section
8 Numerical experiments
In this section, we numerically illustrate the convergence results developed in Section 5 for several methods highlighted in Section 3.1.1 that fit into the GeNI-ADMM framework: sketch-and-solve ADMM (Algo- rithm 4.. NysADMM (Algorithm 3), and "gradient descent" ADMM (GD-ADMM) [11. As a baseline, we also compare to exact ADMM (Algorithm [] to see how various approximations or inexactness impact the convergence rate. We conduct three sets of experiments that verify different aspects of the theory:
Section verifies that NySADMM, GD-ADMM and sketch-and-solve ADMM converge sublincarly for convex problems. Moreover, we observe fast transition to linear convergence, after which all methods but GD-ADMM converge quickly to high accuracy.
Section verifies that NysADMM, GD-ADMM, and sketch-and-solve ADMM converge linearly for strongly convex problems.
Section 8.3 verifies that, without the correction term, sketch-and-sslvve ADMM diverges, showing the necessity of the correction term Section
We consider three common problems in machine learning and statistics in our experiments: lasso Tibshi rani 1996), clastic net regression (Zu & Hastic 2005), and -llogistic regression (Hastic al.] 2015). All experiments use the realsim dataset from LIBSVM (Chang Lin [2011). accessed through OpenML (Van-
schoren et al. 2013), which has 72, 309 samples and 20, 958 features. Our experiments subsample of
25

---

Published in Transactions on Machine Learning Research (01/2026)
realsim, consisting of 10, 000 random samples, which ensures the objective is not strongly convex for lasso and Epllogistic regression.
All methods solve the z-subproblem exactly, and every method, except MysADMM, solves their z-subproblem exactly. NysADMM solves the linear system in Algorithm the following absolute tolerance on the PCG residual used for determining the termination of Nyström PCG:
@ inexactly using Nyström PCG. At each iteration,
min
k.1.5
where rd-1 and r the ADMM primal and dual residuals at the previous iteration. We multiply summable sequence by the geometric mcan of the primal and dual residuals at the previous itcration. The geometric mean of the primal and dual residuals is commonly used tolerance for PCG in practical ADMM implementations such as OSQP (Schubiger et al, 2020 despite this sequence not being apriori summable.
For NysADMM, a sketch size of 50 is used to construct the Nyström proconditioner, and for sketch-and- solve ADMM, we use a sketch size 500 to form the Hessian approximation. For sketch-and-solve ADMM, the parameter 7t in 33) is chosen by estimating the error of the Nyström sketch using power iteration.
All experiments are performed in the Julia programming language (Bezanson et al. 2017 MacBook Pro with a M1 Max processor and 64GB of RAM. To compule the "true" optimal values, use the commercial solver Mosek (ApS) 2022) (with tolerances set low for high accuracy and presolve turned off to preserve the problem scaling) and the modeling language JuMP (Dunning et al. 2017 Legat et al. 2021). The code to reproduce all experiments may be found in the anonymous repository:
https://github. howp t amanaam amandis/GeNTADDM j1
8.1 GeNI-ADMM converges sublinearly and locally linearly on convex problems
To illustrate the global sublinear convergence of GeNI-ADMM methods on convex objectives, we look at the performance of ADMM, NysADMM, GD-ADMM, and sketch-and-solve ADMM on solving a lasso and 4-logistic regression problem with the realsim dataset. Note, as the number of samples is smaller than the number of features, the corresponding optimization problems are convex but not strongly convex.
Lasso regression The lasso regression problem is minimize the l error of linear model with an & penalty on the weights:
minimize (1/2)]|Ar b11 + 7||=|11-
This can be easily transformed into the form 1 by taking ((x) (1/2)] UIL -(=)= = >|]=||, M bl xc is the value above which the all zeros vector is optimal Hastic et al. (2055). We stop the algorithm when the gap is less than 10-4, or after 500 iterations.
N = II, and X = Z = R". We set 0.05 "maxx where Ymax ||Abb|
The results of lasso regression are illustrated in Figure I Figure g shows all methods initially converge at sublinear rate, but quickly transition to a linear rate of convergence after reaching some manifold containing the solution. ADMM, NysADMM, and sketch-and-solve ADMM (which use curvature information) all converge converge much faster then GD-ADMM, confirming the predictions of Section 5 that methods which use curvature information will converge faster than methods that do not. Moreover, the difference in convergence between NysADMM and ADMM is negligible, despite the former having a much cheaper iteration complexity due to the use of inexact linear system solves.
1.055-7max: where 7mmax (1/2)]|4"1||>> is the value above which the all zeros vector is optimal. For NysADMM, the preconditioner is re- ce-constructed after every 20 iterations. For skotch-and-solve ADMM, we re-construct the approximate Hessian at every iteration. Since the z- subproblem not quadratic program, we use the L-BFGS [Liu & Nocedal 1989) implementation from the Optim.jl jl package (Mogensen & Riseth 2018) to solve the J-subproblem exact. ADMM. We use the
L1-Logistic Regression We sel.
26

---

Published in Transactions on Machine Learning Research (01/2026)
Gradient
Gradient
Primal Residual e, Norm
Sketch
Dual Residual i, Norrm
Sketch
ADMM (exact) NysADMM
ADMM (exact)
NysADMM
107
Iteration
Iteration
(a) Primal residual convergence
(b) Dual residual convergence
Gradient
Gradient
Sketch
Sketch
16
ADMM (exact)
ADMM (exact)
NysADMM
NysADMM
Dual Gap
1p"
Iteration
Iteration
Dual gap convergence
(d) Objective value convergence
Figure Convergence of lasso regression for NysADMM, sketch-and-solve ADMM, and gradient descent ADMM.
default hyperparanter settings in Optim.jl for L-BFGS. In particular, the z-subproblem is considered solved, if the infinity norm of the gradient of the z-subproblem satisfies: ||g]| S 10-8
Figure 2 presents the results for logistic regression. The results consistent. with the lasso experiment all methods initially converge sublinearly before quickly transitioning to linear convergence, and methods using better curvature information, converge faster. In particular, although sketch-and-solve-AAMMM converges slightly faster than GD-ADMM, its convergence is much slower than NysADMM, which more accurately captures the curvature due to using the exact Hessian. The convergence NysADMM and ADMM is essentially identical, despite the former having a much cheaper iteration cost due to approximating the z-subproblem and using inexact lincar system solves.
8.2 GeNI-ADMM converges linearly on strongly convex problems
To verify the linear convergence of GeNI-ADMM methods the presence of strong convexily, we experiment with the elastic net problem:
minimize (1/2)]| b12 + >||0/|/ + (n/2)
We set и 1, and use the same problem data and value of 7 the lasso experiment. The results of the clastic-nct experiment are presented in Figure 3 Comparing Figures I and 3 we clearly observe the lincar convergence guaranteed by the theory in Section Although in Figure D ADMM and NysADMM quickly exhibit linear convergence, Figure 3 clearly shows strong convexity leads to an improvement in the number of iterations required to converge. Morcover, we see methods that make better use of curvature information converge faster than methods that do not, consistent with the results of the lasso and logistic regression experiments.
27

---

Published in Transactions on Machine Learning Research (01/2026)
Gradient
Primal Residual e, Norm
Dual Residual i, Norrm
Sketch
ADMM (exact)
NysADMM
Gradient ADMM (exact)
NysADMM
Iteration
Iteration
(a) Primal residual convergence
(b) Dual residual convergence
10
Dual Gap
107
''pp
Gradient
Gradient
Sketch
ADMM (exact)
ADMM (exact)
MysADMM
Ny5ADMM
Iteration
Iteration
Dual gap convergence
(d) Objective value convergence
Figure 2: Convergence of logistic regression for NysADMM, skotch-and-solve ADMM, and gradient descent ADMM.
8.3 Sketch-and-solve ADMM fails to converge without the correction term
To demonstrate the necessity of the correction term in Section we run sketch-and-solve ADMM on lasso and l-llogistic regression without the correction term. Figure presents the results of these simulations. Without the correction term in (33), sketch-and-solve ADMM quickly diverges on the lasso problem. For the logistic regression problem, it oscillates and fails to converge. These results highlight the importance of selecting this term appropriately discussed in Section 7.2
9 Conclusion
In this paper, we have developed framework, GeNI-ADMM, that facilitates elficient theoretical analysis of approximate ADMM schemes and can aid in the design of new, practical approximate ADMM meth- ods. GeNI-ADMM encompasses prior approximate ADMM schemes as special cases by allowing various approximations to the x and subproblems, which can be solved inexactly. We have established the usual ergodic (1//t) convergence rate for GeNT-ADMM under standard hypotheses, and linear convergence under strong convexity. We have shown how to derive explicit convergence rates for ADMM variants that exploit randomized numerical linear algebra using the GeNI-ADMM framework. Specifically, we have established general convergence result with explicit rate for NysADMM from Zhao et al. (2022). which previously was only known to enjoy rate-free convergence for quadratic f. We also formally introduce sketch-and-solve ADMM, which was proposed informally in Bulue el al. (2022) without an explicit algorithm and without theoretical or empirical support. Our convergence analysis shows that sketch-and-sol standard (1/tt) rate, and also quantifies how a better (or worse) approximation to the Hessian improves (or worsens) the convergence rate. Numerical experiments on real-world data generally show an initial sublinear phase followed by linear convergence, validating the theory we developed.
ADMM enjoys the
28

---

Published in Transactions on Machine Learning Research (01/2026)
Gradient
Gradient
Primal Residual f, Norm
10
w
Sketch
Dual Residua & Norm
Sketch
ADMM (exact)
ADMM (exact)
NySADMM
NysADMM
147
18:1
Iteration
Iteration
Primal residual convergence
(b) Dual residual convergence
10
Gradient
Sketch (exact)
NysADMM
10h23
200
200
402
502
Iteration
(c) Objective value convergence
Figure 3: Convergence of clastic net regression for NysADMM, skecchan--stt ADMM, and gradient descent ADMM.
Primal Recidual Dual Residual Ity Gap
194
16"1
Primal Residual
Dual Rasidual
Duality Gap
16
Iteration
Iteration
(a) Lasso regression
(b) Logistic regression
Figure 4: We show the convergence or lack thereof for skelch-and-solvv ADMM with (solid lines) and without (dashed lines) the correction term required by the theoretical results (see section 7.2 When this term is not included, the algorithm does not converge.
Acknowledgments
The authors thank Liubomir Baicev for providing helpful comments. We also thank the AE Ahmet Alacaoglu and the anonymous reviewers for their careful reading of the manuscript and insightful comments, which helped to improve the presentation of the paper.
29

---

Published in Transactions on Machine Learning Research (01/2026)
Z. Frangella, and M. Udell gratefully acknowledge support from the National Science Foundation (NSF) Award TIS-2233762, the Office of Naval Research (ONR) Award N000142212825 and N000142312203, and the Alfred P. Sloan Foundation. T. Diamandis is supported by the Department of Defense (DoD) through the National Defense Science Engincering Graduate (NDSEG) Fellowship Program. B. Stellato is supported by the NSF CAREER Award 223977...77
References
Ahmed Alaoui and Michael W Mahoney. Fast randomized kernel ridge regression with statistical guarantees. In Advances in Newral Information Processing Systems, 2015.
MOSEK ApS. The MOSEK optimization toolboz for MATLAB manual. Version 10.0., 2022. URL http: 7/docs wwt.ss.osekkkoo... com/
cwoosk..com/..//toooooo////iiiii wttt///ooooooooee.o..o/oooo//ee. html
Francis Bach. Sharp analysis of low-rank kernel matrix approximations. In Conference on Learning Theory,
2013.
Dimitri Bertsckas, Angelia. Nedic, and Asuman Ozdaglar. Conver analysis and optimization, volume 1. 2003.
Jeff Bezanson, Alan Edelman, Stefan Karpinski, and Viral B Shah. Julia: A fresh approach to numerical computing. SIAM Review, 59(1):65-99)) 00065599-2900 2017.
Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, and Jonathan Eckstein. Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends in Machine Learning, 3:1- 122, 2011.
Sébastien Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trendso in Machine Learning, 8(3-4):231 357, 2015.
Aydin Bulue, Tamara Kolda, Stefan M Wild, Mihai Anitescu, Anthony Degemnaro, John D Jakemnnn, Chandrika Kamath, Hamnakrishnn-Rambee Kannan, Miles F Lopes, Per-Gunnar Martinsson, et al. Ran- domized algorithms for scientific computing (RASC). Technical report, Oak Ridge National LORNO,))) Oak Ridge, TN (United States), 2022.
Emmanuel Candes and Benjamin Recht. Exact matrix completion via convex optimization. Communications of the ACM, 55(6):111-11)) 119, 2012.
Emmanuel Candes and Justin Romberg. Sparsity and incoherence in compressive sampling. Inverse problems, 23(3);969, 2007.
Antonin Chambolle and Thomas Pock. A first-order primal-dual algorithm for convex problems with appli- cations to imaging. Journal of Mathematical Imaging and Vision, 40:120-145, 2011.
Chih-Chung Chang and Chih-Jen Lin. LIBSVM: library for support vector machines. ACM Transactions on Intelligent Systems and Technology (TIST), 2(3):1-27, 2011.
Liang Chen, Defeng Sun, and Kim-Chhan Toh. A note on the convergence of admm for linearly constrained convex optimization problems. Computational Optimization and Applications, 66(2):327-343, 2017.
Yifan Chen, Ethan N Epperly, Joel A Tropp, and Robert Webber. Randomly pivoted cholesky: Practical approximation of kernel matrix with few entry evaluations. Communications Pure and Applied Mathematics, -89551995111 2025.
Wei Deng and Wotao Yin. On the global and lincar convergence of the generalized alternating direction method of multipliers. Journal of Scientific Computing, 66(3):889 916, 2016.
Michal Dereziáski and Aaron Sidford. Approaching optimality for solving dense linear systems with low-rank structure. Xiv preprint or Xin:2500 1 11724, 2025.
30

---

Published in Transactions on Machine Learning Research (01/2026)
Michal Derezinski, Jonathan Lacotte, Mert Pilanci, and Michael W Mahoney. Newton-less: Sparsification without trade-offs for the sketched newton update. Advances in Neural Information. Processing Systems, 34:2835 2847, 2021.
Michal Dereziński, Christopher Musco, and Jiaming Yang. Faster linear systems and matrix norm approxima- tion via multi-level sketched preconditioning. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1972-2004. SIAM, 2025.
Theo Diamandis, Zachary Frangella, Shipu Zhao, Bartolomeo Stellato, and Madcleine Udell. Genios: an (almost) second-order operalor-spliuing solver for large-scale convex optimization. ar preprinl arXiv:2310.08322 083333 2023.
lain Dumning, Joey Huchette, and Miles Lubin. Jump: A modeling language for mathematical optimization. SIAM Review, 59(2):295 2200 2017. doi: 10.1137/15M102000 1501005555
Jonathan Eckstein and Dimitri Bertsekas. On the Douglas Rachford splitting method and the proximal point algorithm for maximal monotone operators. Mathematical Programming, 55(1):293-311 318, 1992.
Jonathan Eokstein and Wang Yao. Relative-error approximate versions of douglas rachford splitting and douglas-rachford special cases of the admm. Mathematical Programming, 170(2):417 444, 2018.
Zachary Frangella, Joel A Tropp, and Madeleine Udell. Randomized nyström preconditioning. STAM Journal on Matriz Anolysis and Applications, 44(2):718 752, 2023.
Zachary Frangella, Pratik Rathore, Shipu Zhao, and Madeleine Udell. Sketchysgd: Reliable stochastic optimization via randomized curvature estimates. SIAM Journal on Mathematics of Data Science, 6(4): 1173 1204, 2024.
Jerome Friedman, Trevor Hastic, and Rob Tibshirani. Regularization paths for generalized linear models via coordinate descent. Journal of Stalistical Soflware, 33(1):1, 2010.
Alex Gittens and Michael W Mahoney. Revisiting the nyström method for improved large-scale machine learning. The Journal of Machine Learning Research, 17(1):3977-4041, 2016.
Robert M Gower, Dmitry Kovalev, Felix Lieder, and Peter Richtárik. RSN: randomized subspace Newton In Advances in Newral Information Processing Systems, 2019.
William W Hager and Hongchao Zhang. Convergence rates for an inexact admm applied to separable convex optimization. Computational Optimization and Applications, 77(3):729-77) 754, 2020.
Trevor Hastie, Robert Tibshirani, and Martin Wainwright. Stalisticul learning with sparsily: the lasso and generolizations. 2015.
Bingsheng He and Xiaoming Yuan. On the o(1/n) convergence rate of the Douglas-Rachfore Rachford alternating direction method. SIAM Journal on Numerical Analysis, 50(2):700 709, 2012.
Bingsheng He, Li-Zhi Liao, Deren Han, and Hai Yang. A new inexact alternating directions method for monotone variational incqualities. Mathematical Programming, 92:103-118, 2002.
Ben Hermans, Andreas Themelis, and Panagiotis Patrinos. QPATM: Newton-type proximal augmented Lagrangian method for quadratic programs. In 2019 IEEE 58th Conference on Decision and Control (CDC), pp. 4325 4330. IEEE, 2019.
Ben Hermans, Andreas Themelis, and Panagiotis Patrinos. QPALM: proximal augmenned Lagrangian method for nonconvex quadratic programs. Mathematical Programming Computation, pp. 1-45, 2022.
Jean-Baptiste Hiriart- and Claude Lemaréchal. Convez Analysis and Minimization Algorithms II, volume 305. 1993.
Ruichen Jiang, Michal Derezinski, and Aryan Mokhtari. Stochastic newton proximal extragradient method. Advances in Newral Information Processing Systems, 37:90818 90852, 2024.
31

---

Published in Transactions on Machine Learning Research (01/2026)
Jonathan Lacotte and Mert Pilanci. Effective dimension adaptive sketching methods for faster regularized least-squares optimization. In Aduances in Neural Information Processing Systems, 2020.
Jonathan Lacolte, Yifei Wang, and Mert Pilanci. Adaptive Newlon sketch: Linear-time optimization with quadratic convergence and effective Hessian dimensionality. In International Conference on Machine Learnäng, pp. 1926-5936. PMLR, 2021.
Benoît Legat, Oscar Dowson, Joaquim Dias Garcia, and Miles Lubin. MathOptInterface: data structure for mathematical optimization problems. INFORMS Journal on Computing, 34(2):672 689, 2021. doi:
Dong C Liu and Jorge Nocedal. On the limited memory bfgs method for large scale optimization. Mothe- matical Programming, 45(1):503 528, 1989.
Maike Meier and Yuji Nakatsukasa. Randomized algorithms for Tikhonov regularization in linear least squares. arXiv preprint orXiv:2203.0733 2022.
Patrick Kofod Mogenson and Asbjorn Nilson Riseth. Optim: A mathematical optimization package for Julia. Journal of Open Source Soflware, 3(24):615, 2018. doi: 10.21105/josss00611
Renato DC Monteiro and Benar F Svaiter. Iteration-complexity block-decomposition algorithms and the alternating direction method of multipliers. SIAM Journal on Optimization, 23(1):475-500) 2013.
Cameron Musco and Christopher Musco. Recursive sampling for the nyström method. volume 30, 2017.
Sen Na, Michal Dereziński, and Michael W Mahoney. Hessian averaging in stochastic newton methods achieves superlinear convergence. Mathemalical Programming, 201(1):473 520, 2023.
Yurii Nesterov. Lectures on Convex Optimization, volume 137. Springer, 2018.
Robert Nishihara, Laurent Lessard, Ben Recht. Andrew Packard, and Michael Jordan. A general analysis of the convergence of ADMM. In International Conference on Machine Learning, pp. 343 352. PMLR, 2015.
Hua Ouyang, Niao He, Long Tran, and Alexander Gray. Stochastic alternating direction method of multi- plicrs. In International Conference on Machine Learning, pp. 80-88. PMLR, 2013.
Yuyuan Ouyang, Yunmei Chen, Guanghui Lan, and Eduardo Pasiliao. An accelerated linearized alternating direction method of multipliers. SIAM Journal on Imaging Sciences, 8(1):644 681, 2015.
Neal Parikh and Stephen Boyd. Proximal algorithms. Foundations and Trends in Optimization, 1(3): 127-239, 2014.
Mert Pilanci and Martin Wainwright. Newton sketch: A near lincar-time optimization algorithm with linear-quadratic convergence. SIAM Journal on Optimization, 27(1):205 245, 2017.
R Tyrrell Rockafellar. Generic linear convergence through metric subregularity in a pariabl--metrc extension of the proximal point algorithm. Computational Optimization and Applications, pp. 1-20, 2023.
Nikitas Rontsis, Paul Goulart, and Yuji Nakatsukasa. Efficient semidefinite programming with approximate admm. Journal of Oplimization Theory and Applicalions, 192(1):292 220, 2022.
Farbod
and Michael W Mahoney. Sub-sampled newton methods. Mathematical Program- ming, 174(1):293-32) 326, 2019.
Ernest K Ryu and Wotao Yin. Large-scole conver optimization: algorithms 8 analyses via monotone oper- alors. 2022.
Mark Schmidt, Nicolas Roux, and Francis Bach. Convergence rates of inexact proximal-gradient methods for convex optimization. Advances in Newral Information Processing Systems, 24, 2011.
Michel Schubiger, Goran Banjac, and John Lygeros. Gpu acceleration of admm for large-scale quadratic programming. Journal of Parallel and Distributed Computing, 144:55-61 67, 2020.
32

---

Published in Transactions on Machine Learning Research (01/2026)
B. Stellato, G. Banjac, P. Goulart, A. Bemporad, and S. Boyd. OSQP: an operator splitting solver for quadratic programs. Mathemalical Programming Compulation, 12(())637-63 672, 2020.
Robert
Tibshirani. Regression selection and shrinkage via the lasso. Journal of the Royal Statistical Society Series B, (8(1):267-288 1996.
Joel A Tropp. An introduction to matrix concentration inequalities. Foundations and TrendsB in Machine Learning, 8(1-2):1-230, 2015.
Joel A Tropp, Alp Yurtsever, Madeleine Udell, and Volkan Cevher. Fixed-rank approximation of positive- semidcfinite matrix from streaming data. Advances in Neural Information Processing Systems, 30, 2017.
Joaquin Vanschoren, Jan N. van Rijn, Bernd Bischl, and Luis Torgo. Openml: networked science in machine learning. SIGKDD Explorations, 15(2):49 60, 2013.
Xiaoming Yuan, Shangzhi Zeng, and Jin Zhang. Discerning the linear convergence of ADMM for structured convex optimization through the lens of variational analysis. J. Mach. Learn. Res., 21:83 1, 2020.
Shipu Zhao, Laurent Lessard, and Madeleine Udell. An automatic system to detect oquivalence between ilerative algorithms. arXiv preprinl ar arxx:2105504468,, 2021.
Shipu Zhao, Zachary Frangella, and Madeleine Udell. NysADMM: faster composite convex optimization via
low-rank approximation. In International Conference on Machine Learning, volume 162, pp. 26824 26840. PMLR, 2022.
Hui Zou and Trevor Hastie. Regularization and variable selection via the elastic net. Journal of the Royal Statistical Society Series B: Statistical Methodology, 622))331-, 2005.
A Appendix
B Proofs not appearing in the main paper
B.1 Proofs for Section
We begin with the following lemma, which plays a key role in the proof of Lemma For a proof, see
Example 1.2.2. in Chapter XI of Uurruyy & Lemaréchal (1993).
Lemma 10 (e-subdifforentiall of quadratic function). Let h(2) = (b. 2) + 12 where A a symmetric
posilive definite linear operator. Then
|
0ch(z)= b A(2
With Lemma 10 in hand, we now prove Lemma
Proof of Lemma 1
Proof. Observe the function defining the z-subproblem may be decomposed as G(z) = g(z) + h(2)) with
h(z) = - M + Nz + a²113 +
+ I1=
1
1
Now, by hypothesis gh+1 gives an a -é-minimum of G(z). Hence by Proposition 1
0 E 0g G(tbt) and 02y G( c detg(Ehtt)
+ 0ggh(
Thus, we have = 8y + 8 where & E 0gg((th11) and 8h E 0.hh(sh11). Applying Lemina
with A
k + N N and = pNT (Mak+1 + i - Whzt we reach
8/4 = PNT + N + -tt) + w 전イ) tv. The desired claim now immediately follows from using
8h.
33

---

Published in Transactions on Machine Learning Research (01/2026)
B.2 Proofs for Section 5
Proof of Proposition 2
Proof. Using the eigendccomposition, we may decompose H as
H = > A(H))v.d
So
|0-1 (V) + Σ X
S AH A2 (H
S Hy X((H,)) A1 (HHH)||**11
Recalling that a= (),)((H)) with r E (0, we may put everything together to conclude
(Ai(H)) 2 (1- (1) X1
X²(H))) 2 (1--) (vv (H
| H,
proving the first claim. The second claim follows immediately from the first
Proof of Proposition 3 To prove Proposition 3 we require the following lemma, which is the analogue
of Lemma 5 when the subproblems in Algorithm 2 iteration & + are solved exactly.
Lemma 11 Exxcct Gap function 1-step bound). Let w*+1 ( .++1) denote the iterates generated
by Algorithm 2 at iteration k + L, when we solve the subproblems exactly. Set w (x*,2",u) u), then the gap
function Q satisfies
Qww, wt1) s (||= - -. 11 - || x *+1 112x) +
2 (1=- =* 1 +NNTN - - *++ 11 12E+pNTN)
1
2 (1|=* - Mxxl2 - ||a 2x
P
+ 2 (11t u|12 || - -ul))-
P
Proof. As h+1 and zh+1 are the exact solutions to the and subproblems at iteration k: + 1, they satisly the subproblem optimality conditions exactly. Thus, the following inequalities hold
), (2*1()+)1) + f222 xt x²) s (0 - x² )²), - *1) + p(M +N + at M(x x(+1)), g(=*) - a(= +1) 2 (-pNTuh+) + wh (a* ,t)),, == xt1).
These the same inequalities in Lemma and Lemma only zk+1 and gh+1 have been replaced by the exact solution ++1 and 241,, so that a = 0 and of = O.
Observe the desired inequality is exactly the inequality in the conclusion of Lemma The only changes are that there are no error terms present as gd+1, gh+1, and ūt+1 have been replaced with *++1 *++ and k+1, As Lemma 3 and Lemma 4 are what were used to establish Lemma 3 we can apply the exact same argument used there using the exact optimality conditions, so that there are no error terms to conclude
Q(w, w +
2 (1|2 x² 11a2 ||1- =+1 11 + 2 (I2 2 1 12 PNN+ 11=1--- - 11 13x
1
P [11=* Ma - || M2 +
P (11i* u112 || - -ul
2
34

---

Published in Transactions on Machine Learning Research (01/2026)
Having established Lemma 11
prove Proposition 3
Proof. First, observe that item 2. is immediate consequence of item 1, so it suffices to show item 1. To this end, plugging in w wt into the inequality of Lemma 11 using Q(w", wh+t) 2 0, and rearranging, we reach
| - x11121 + 1| - =- =0 1= -NNN + pllu
u²1l
s |1 105-x11l
12 + +11# == ==' pllid u" u²1
Defining the norm ||=]|w, = v |1=1/2= + (ellle + p|lul1?, the procoding inoquality may be rewritten as I ww || w" Iw
Now, our inexactness hypothesis (Assumption 3 along with e-strong convexity of the z-subproblem (which follows by Assumption 2 implies
| x kt2 S Ex || 1 S
Using ü++1 = Ma + No + a and u+1 = Mr*+1 1 + Nott + at we find
p|latti - u+t1 S _ + C /
where C is some constant. Hence we have,
|| w" llwce I || w" llw.k + 11ah-1 - w lla.k S 1110 w lluck + C ( (c++ Vet
Defining the summable sequence ttt C(E VEt), the preceding display may be written as
|1 w/ llwck ||00 w Il et (A),
Now, Assumption implies that 11 - - Ilw, I /I+ ck - ww Combining this inequality with induction on (A), we find
k II
| w0 llw.
II v |1:0 w lw. +
II + Ç
Σ
Hence,
/mminOomin v) Mlllh+11 w01l S | w=1/ S TTC (110² - w ||: + Evo)
It follows immediately that:
TTe (1li
w Ilu.1 + Evr
|| - w0*l| } < <00,
sup
10 w= || S max
-w00|
/min Omin v)
k21
and so the sequence (wi*) 1k20 is bounded, which in turn implies 1 1220. E h220, and (ūr J420 are bounded.
Proof of Lemma 3
Proof. Throughout the proof, we shall denote by (x), the function defining the æ-subproblem at iteration k. The exact solution of the z-subproblem shall be denoted by k++ To begin, observe that:
(x) (x)) V12(=*) + ( + pMf M) x²) pMT (Mr* + N + at).
35

---

Published in Transactions on Machine Learning Research (01/2026)
Now,
(
( (1tht))) + (z ) xbt xhil 1 shtl)
(E (o ) ), xltl)
VVS) (Eh+2) ( - ghtl)
(VS (1 ), - x + (15 ) 2 - z1tl)
(1)
2 (F
(21 ), ), - kk+1) + (3 xxt11 x² x 10t+pM
+ (V (z ( ) gbt1 k + (igt1 - kt2 ghtl x kt] 7MM+
(VS (x ), 1h+1).
Here the last inequality uses VS (v) Vfi(z) V.f(t)) + (0* +M M)(x y), and that x+1 is the exact solution of the z-subproblem,
Let R be the radius in Proposition 3 and K2 sup& [ Then Cauchy-Schwand combined with fi having a Lipschitz contimuous gradient yields
(V - (z - = + (5 - kt1 x² - x k+1 - 7
(V[i(**+1) V/( (, - x1-1) + (i - k-1 , xht -
"0*+DNTT + (vS ), Jh+1)
2 L,, (fmax PM1 Re) L0 Ls, Re (9max + M)) KgE
Defining
C₂ maxxLp R, (6max + pMr(M M))R, E (Omax + pd1 (M M))c2 sup
V+
&
we conclude that
(V ( - ghtl) - Caet
The desired claim now follows by plugging *k+1 into the expression for V in the preceding inequality,
Proof of Lemma
Proof. By hypothesis, gk+1 is an at-approximate minimizer of the z-subproblem, so Lemma exists vector 3 with | I Velr such that
shows there
g(~²) (1 2 p - + 11 - ggttl + 8,2" - ghtl) - c
Rearranging, using comes
along with the boundedness of the iterates, the preceding display be-
g(2") g(( - p(N +++ + (=* - zt+1),
z -||3|||2 k+I
2²d - sk
| +llg++pNT N.R -
Ve+- - - v Imin + pdmin (N'N)
R
V Amin + (NTN
R
+ Ket =
Ve'in pdmin (NT
where the last display uses of S K5, Ver and we have defined C.
R
+ Kgg
Visin + P (NT
36

---

Published in Transactions on Machine Learning Research (01/2026)
B.3 Proofs for Section 6
Proof of Lemma 6
Proof.
1. We begin by observing that strong convexity of f implics
(VS(Et+))= 1()") - x²) 2 az|lā x=11
Decomposing f as f = fi + f2, the preceding display may be rewritten as (Vf( + fa Vf(x*), - xx) + (V (,*) gktt x²)
x=
Now, the exact solution x the z-subproblem at iteration satisfies V (x*+1) 0. Moreover, zh+1 is an & minimizer of the z-subproblem, and (ar) Lipschitz continuous. Combining these three properties, it follows there exists vector Erry satisfying:
= (a Erry Err,, where |Errell S Ce
Consequently, we have
V((( V O" 1 xhtl) + pM - + Err.
Utilizing the preceding relation, along with the fact that the iterates are bounded, we reach
(* - xb1 gu+l - x )²)0= + P(N =* + u²" ut1 M x²)) + Cs 2 - - x=112 -x-1'
(V (2 ), xkt1 =x*). D
1h+1) ) + s E 0ggg(Eh+1), we have 2. As -pN" u² E 0g(2*), and - a + 1 gb+1
g(#h+1) - g(>") 2 (-pN gk+1 20), g(x*) - g( 2 x + vh ( - )² - - -.
So, adding logether the two inequalities and rearranging, we reach
( - ,N, (u* t - v (3* gh+ + +) -
Now using boundedness of the iterates and || I C' e Cauchy-Schhie Schwarz yields
(a++1 - 2* PPN'N' (a++1 -u") + ( sk+2)) 2 C
Proof of Lemma 8 We wish to show for some ô > 0, that the following inequality holds
||w - w 11 1+ w" 12 t 2 61| w 112
To establish this result, it suffices to show the inequality
1t1 w 11 + 20s -1ll - 211 2 (V -V2((())))) kkt x²) 2 8/100 k+1 1
We accomplish this by upper bounding each term that appears in || w, 11 by terms that appear in the left-hand side of the preceding equality. To that end, we have the following result.
Lemma 12 (Coupling Lemma). Under the assumptions of Theorem 2 the following statements hold:
37

---

Published in Transactions on Machine Learning Research (01/2026)
1247 1. Let un 2 C1 Amiia (Marry. 02 Ammin (M/M))) C3 Amin (Mrry we have
4 +0
M|
Then for some constont C' 2 0,
| ="11===0lle & sagllaht1 =x11/2 + callat 112 + call - gh+ 1h 11 + Ce
2. There erists constants C1 = (1NI)ttNimss))) ||A = =c//|l11 such that
|| k+| - x² 2'11//004 S callz - 1=2 + callu ++ 11.
3. For all μ > 0, we have
D3
(V (2 -
F222(2)), -VSP)) o xx> S 41/2|2 - x=12²
1 k+ - 1111
2/1
Taking Lemma 12 as given, let us prove Lemma
Proof.
Observe Lemma 12 implics
1
f1 wh1
+
2
1|
bt x² 1-12- 1- - Vf(((*)) x -x²) 611 w. 112.
2
P
D
2 200 u2
8(c1 + ca))
|| - ||
-x"11+ +
(mii
13
8c2
18t - -
P
2p
2012
+ (1/2 8cg) 1| = = 11//p*+NNTN + (1/2 dcg) ||
a++1
-Cél
Setting #22 o,, and using Omin 13//0== = TsgT find by setting
8 = min {
os
Omin LgLL
1
1
0,
ppcc ca)
2pc2
203
20s
that
||
w0 + Cea
w 811
-
11a0.
as desired.
We now turn to to the proof of Lemma 12
Proof of Lemma 12
Proof.
1. Observe by Lyssmhhhhnsss of f, that
2 (1 - 1=1 + ||
x=1²²) 2 IV ( Vf((x*) VZ((+) - V12(2*)11
11* - xb+1 + pM N(E* 2t+1) + pMM xnt1) Err
2 o² |M (att(aat11 - un )1 1|0 - ghtl) + PM N - zhtl) + 11
Here the last inequality uses with μ = 2, the identity (valid for all μ > 1)
||a + 612² > (1 م |||a| + (1 2)
So, rearranging and using ||a + 6112 < 2||a|² 12 2|6b12 we reach
0² e ||M -²))|² < 61311 - x + 2 22 (217+ 110 1|= g2
+
- - 4/
38

---

Published in Transactions on Machine Learning Research (01/2026)
Now, using | ||? v Ca v Ce and VellNTN $ |elli//0 reach
(21g + m
1
| u²11 I p² Aminl (M | x²1
p² Amin (MMT) 11 - =22
8 8|MM12
|| g++ 11 11/004NNN + Cew
Amin (MMT)
2. This inequality is straightforward consequence of the relation
M(#*tl- -xr) x²)
h+1 at N(22 - zxt1),
Indeed, using the identity ||a + b112 2||a|| 2|1b1 we reach
s 2/| -")]|
x*1| + 2/| 113
Consequently
|| s/maae Pian (N)
| 11' 2'11//0=+4777 $2
1| 11 | x=
||A1112 + v/max /0
mmin (N)
which is precisely the desired claim.
3. Young's inequality implies for all μ > 0, that
---1--x10 1 VV22 Vfa(at))1 + -1a x=1
f2 f2(*)),, jk+1 x²)
-
2μ
The desired claim now follows from Ly-smoothness of f2.
C Proofs for Section 7
C.1 Proof of Lemma
Proof.
1. By ł relative smoothness we have,
any + i, || -* 122,
f(x) f( + (Vf(**),
|1 8* 1 (z*))
||z #* 1²1 (x-
fx $²
< o z , ||**||| 1212 - || * $13,- + 7 -
= || * 12
The claimed incquality immediately follows.
2. By our hypothesis H3 and Ar* we have
1
1
- El1,, S || 3 I0
|| 11112 1
||0
x 11
1-
The desired inequality now follows immediately from the last display.
39


Reviews:
[{"review_id": "qPeHinKbVl", "reviewer": "Reviewer_14PJ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces **GeNI-ADMM (Generalized Newton Inexact ADMM)**, a unified framework for designing and analyzing a broad class of approximate Alternating Direction Method of Multipliers (ADMM) algorithms for large-scale composite convex optimization. The framework synthesizes three common approximation strategies: (1) **Function approximation**, where the smooth part of the objective is replaced by a first- or second-order model; (2) **Augmented Lagrangian linearization**, which adds proximal terms to simplify subproblems; and (3) **Inexact subproblem solves**, where solutions are found only up to a specified tolerance controlled by forcing sequences.\n\nThe primary theoretical contributions are two-fold:\n1.  **Sublinear Convergence (Theorem 1)**: The paper proves that under standard convexity assumptions, GeNI-ADMM achieves an ergodic $\\mathcal{O}(1/t)$ convergence rate for both suboptimality and feasibility gap, matching the rate of exact ADMM despite the approximations.\n2.  **Linear Convergence (Theorem 2)**: Under the additional assumption of strong convexity, the framework guarantees a linear convergence rate via a Lyapunov analysis, though this requires an additional spectral condition, $\\theta_{\\min}>L_f^2/\\sigma_f$, on the regularization matrices (Sec. 6.1, Thm. 2).\n\nThe paper applies this framework to provide the first formal convergence guarantees for ADMM variants that use randomized numerical linear algebra (RandNLA), recovering schemes like **NysADMM** and a newly proposed **sketch-and-solve ADMM** as special cases (Sec. 7). For the latter, the analysis reveals that a specific correction term, $\\gamma_k I$, chosen to dominate the Hessian approximation error $\\|E_k\\|$, is necessary to ensure convergence (Lemma 9). This finding is validated by numerical experiments on lasso, $\\ell_1$-logistic, and elastic-net regression, which also illustrate the predicted convergence rates and transitions from sublinear to linear phases (Sec. 8.3).", "claims_and_evidence_yn": "Yes", "claims_explanation": "**Yes, with caveats.**\nThe convex $O(1/t)$ and strong-convexity linear-rate results are sound under the stated assumptions (Theorem 1/2). However, the added condition $\\theta_{\\min}>L_f^2/\\sigma_f$ is not enforced in experiments and should be either justified or relaxed.", "audience_yn": "Yes", "audience_explanation": "A unifying analysis that covers both proximal/linearized ADMM and randomized second-order variants is relevant to modern large-scale optimization, especially with clear guidance on inexactness and sketching. The empirical section is practical but would benefit from robustness reporting.", "requested_changes": "**Critical (acceptance-blocking)**  \n1. **Linear-rate condition:** Either (a) remove the claim that the $\\theta_{\\min}>L_f^2/\\sigma_f$ condition is unnecessary, or (b) strengthen Theorem 2 to avoid it (e.g., add assumptions yielding the needed lower bound) and give the exact lemma replacing the current step in Lemma 7 (Sec. 6.2–6.3).  \n2. **Open-question claim:** Cite specific prior work and state precisely what is closed now (which algorithms/assumptions). Add references at the end of Sec. 7 or in the Conclusion. \n3. **Clarify Experimental Details**: In Section 8, please specify precisely how the inexact subproblem solves were performed. State the inner-loop algorithm used (e.g., Conjugate Gradient for linear systems, L-BFGS for logistic regression) and, most importantly, the termination criteria or tolerance schedule that implements the forcing sequences $\\{\\epsilon_x^k\\}$ and $\\{\\epsilon_z^k\\}$. This is essential for reproducibility.\n\n**Major (strongly recommended)**  \n3. **Sketch dependence:** Add bounds translating $\\|E_k\\|$ in Cor. 2 to sketch size and dimension; include guidance on choosing $\\gamma_k$ with computational overhead. (Sec. 7.2) \n4. **Experimental robustness:** Report multiple seeds, error bars, and sensitivity to $(\\rho,\\eta,\\gamma_k)$ and sketch sizes (Sec. \n5. **Explicit Constants**: In Appendix B, provide more explicit bounds for the constants $C_x$ and $C_z$ that appear in the proofs of Lemmas 3 and 4 (and thus Theorem 1). Even if complex, showing their dependence on Lipschitz constants, operator norms, and the bound on the iterate norms ($R$ from Prop. 3) would make the theoretical results more transparent.\n\n**Minor**  \n6. Clarify when NysADMM’s $\\sigma I$ can be set to 0 in practice and implications for convergence. (Sec. 7.1) \n7. Quantify “linear convergence” in plots (add fitted rates/slopes). (Sec. 8.2)\n8.  **Add Broader Baselines**: To better contextualize the practical performance, consider adding at least one strong, non-ADMM baseline to the experiments in Section 8 (e.g., an accelerated proximal gradient method or a state-of-the-art coordinate descent solver for LASSO).\n9.  **Connect Sketching Rate to Literature**: In Section 7.2, add a brief remark connecting the rate in Corollary 2 to standard RandNLA rates that depend explicitly on sketch size. For instance, you could mention how bounds on $||E^k||$ can be obtained from matrix concentration inequalities.\n\n**Typos & Style**  \n8. Fix “converge converge” in Sec. 8.1. \n\n### Comparisons & Positioning\n- **To proximal/generalized ADMM (Deng & Yin, 2016):** The framework subsumes these methods; however, for **linear rates**, please state explicitly whether GeNI-ADMM’s conditions are **weaker/stronger** than Deng–Yin’s (e.g., your $\\theta_{\\min}$ condition vs. fixed proximal terms).\n- **Randomized second-order methods:** For NysADMM and sketch-and-solve, rates should expose **sketch accuracy parameters** ($\\|E_k\\|$, spectrum gaps) and **sketch size**; Corollary 2 contains $\\|E_k\\|$ inside constants but does not translate it to sample/embedding dimension. Please add standard bounds (e.g., Nyström error vs. leverage-score sample size) to quantify the iteration **and** time complexity trade-off. \n- **“Open question resolved”**: Provide concrete prior references where global convergence was unknown/unstated, and clarify which **variants** and **assumptions** your result covers.", "broader_impact_concerns": "No specific concerns beyond standard optimization research. No identifiable dual-use risks are apparent.\nThis work is foundational research in the area of convex optimization. It proposes a theoretical framework and analyzes the convergence of numerical algorithms. As such, it does not raise immediate ethical concerns or have direct societal applications that would necessitate a broader impact statement. The potential applications are general-purpose, and any societal impact would be determined by the downstream use-cases of the optimization solvers.", "additional_comments": "This is a strong, well-executed theoretical paper that introduces an elegant and valuable unifying framework for approximate ADMM. The analysis is rigorous and uses the framework to resolve important open questions about the convergence of practical randomized variants like NysADMM, leading to novel insights such as the necessity of a correction term in sketch-and-solve methods. While the work represents a clear advance in the field, some of the theoretical assumptions are strong; for instance, the condition for the linear rate appears stricter than what is observed in practice. The paper does an excellent job of positioning GeNI-ADMM relative to other ADMM variants, correctly identifying the benefits of using curvature. However, it lacks comparison to non-ADMM state-of-the-art solvers for the problems tested, which would provide a more complete picture of practical performance. Additionally, the rate analysis for sketch-and-solve ADMM, while valid, could be strengthened by connecting it more explicitly to standard RandNLA rates that depend on sketch size and problem dimensions. Despite these limitations, the theoretical results are convincing, and my recommendation for acceptance is contingent on the authors addressing the requested changes.", "extra_scores": {}, "extra_text": {}}, {"review_id": "HqsNVvL0Xv", "reviewer": "Reviewer_NGmV", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper revisits ADMM for minimizing a convex, separable function $f(x)+g(z)$, $x\\in\\mathcal{X}$, $z\\in\\mathcal{Z}$ subject to coupled linear constraints $Mx + Nz=0$. Since many ADMM variants have been proposed in the literature, the authors propose a unified framework, called GeNI-ADMM, that inlcludes them as special cases. This ADMM framework follows the classical Gauss–Seidel way of updating $x$ and $z$ sequentially.\n\nSpecifically, at each iteration, the GeNI-ADMM assumes that $f$ has a separable structure, i.e., $f=f_1+f_2$, and forumuate the $x$-subproblem as\n\\begin{equation*}\n\\min_{x\\in X}\\ f_1(x) + f_2(\\tilde{x}^k) + \\nabla f_2(\\tilde{x}^k)^T(x - \\tilde{x}^k) + \\frac{1}{2}\\|\\|x - \\tilde{x}^k\\|\\|_{\\Theta^k}^2 + \\frac{\\rho}{2}\\|\\|Mx + N\\tilde{z}^k + \\tilde{u}^k\\|\\|^2,\n\\end{equation*} \nwhere $f_1$ is kept and $f_2$ is approximately locally with a quadtratic model. This scheme unifies the function approximation appraoch and AL linearization approach.\n\nNext, this method solves a $z$-subproblem\n\\begin{equation*}\n\\min_{z\\in Z}\\ g(z) + \\frac{\\rho}{2}\\|\\|M\\tilde{x}^{k+1} + Nz + \\tilde{u}^k\\|\\|^2 + \\frac{1}{2}\\|\\|z - \\tilde{z}^k\\|\\|_{\\Psi^k}^2,\n\\end{equation*}\nwhere $\\Psi^k$ helps linearize the AL quadratic term when $N$ is a complicated matrix.\n\nThe (scaled) Lagrangian multiplier is updated \n\\begin{equation*}\n\\tilde{u}^{k+1} = \\tilde{u}^k + M\\tilde{x}^{k+1} + N\\tilde{z}^{k+1}.\n\\end{equation*}\n\nA practical advantage of this method is it allows inexact solutions to the $x$- and $z$-subproblems. Theoretically, sublinear and linear convergence for convex and strongly convex problems are established, respectively. Its applications to specific ADMM variants are discussed. Finally, numerical experiments are conducted to validate the theoretical results", "claims_and_evidence_yn": "Yes", "claims_explanation": "This paper develops a general ADMM framework that covers many existing ADMM variants. It fills the gap that some ADMM variants do not have theoretical guarantees. The paper’s fit within the existing ADMM literature is clearly discussed. The literature review and motivation sections are well written and easy to follow. Although the analysis is a bit technical, it somewhat lacks details supporting the derivations, which could be improved further.", "audience_yn": "Yes", "audience_explanation": "This paper provides a complete analysis of a practical ADMM framework for convex and strongly convex optimization problems. It allows flexible strategies for implementation and inexact solutions to the subproblems. I think the audience in the field of ADMM may be interested in these results.", "requested_changes": "Major Comments:\nPlease add more explanations to the analysis. For example on Page 30, first paragraph in the proof of Proposition 3. Please give more detailed explanations on how did you derive the first display. If one plugs in $w=w^\\star$ $Mx^\\star+Nz^*=0$ into Lemma 11, it follows that\n\n\n\\begin{equation*}\n... + \\rho \\|\\|z^{k+1} - Nz^\\star\\|\\|^2 + ... \\le ... +\\rho  \\|\\|\\tilde{z}^k - Nz^\\star\\|\\|^2 + ...\n\\end{equation*}\n\nBut how you obtain $\\|\\|...\\|\\|_{\\Psi^k + \\rho N^TN}^2$? Also, please add plugging in $w=w^*$ into Lemma 11\n\n\n\n\nMinor Comments:\n1. Page 3, After Eq. (2). Should be $Y\\subset\\mathcal{H}$?\n2. Page 4, After Eq. (6). Should be psd matrices that approximate the Hessian of $f_2$?\n3. Page 3. After Eq. (1). If later in Section 5, the case $X=\\mathcal{X}$ and $Z=\\mathcal{Z}$ is considered, should $X\\subset \\mathcal{X}$ be replaced by $X\\subseteq \\mathcal{X}$? This question also applies to $y$ and $Z$.\n4. Page 8, Definition 2. Do you mean $\\hat{L}_{\\Theta}$-relatively smooth with respect to bounded $\\Theta$? It sounds a bit odd to repeat $\\Theta$ twice here. \n5. Page 12, Lemma 5. Delete a dot after Assumptions 1-4\n6. Page 13, Second display in the proof of Lemma 5. $\\Theta_k$ should be $\\Theta^k$.\n7. Page 13, Second display in the proof of Lemma 5. The $1$-relative smoothness of $f_2$ should give you $\\nabla f_2(\\tilde{x}^k)^T(\\tilde{x}^{k+1} - \\tilde{x}^k)$?\n9. Page 13, Proof of Lemma 5. Delete the equation number (24), and also (25) if they are not used.\n10. Page 14. Second display. Please adjust the space for the two identities. You may add \"and\" between them.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "5E34StlMFo", "reviewer": "Reviewer_N9oM", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper provided comprehensive convergence analysis for the inexact ADMM for solving large-scale composite convex optimization problems. The papers proposed GENI-ADMM that solves second-order approximation of the associated subproblems, which covers many existing algorithmic framework. Overall, the paper is well-written, and the contributions are significant.", "claims_and_evidence_yn": "Yes", "claims_explanation": "1. The proofs conducted in the paper are overall correct, to the best of my knowledge.\n2. The paper provided numerical experiments to support the theoretical findings. \n3. The paper is well-organized.", "audience_yn": "Yes", "audience_explanation": "Large-scale composite convex optimization represents one of the most fundamental models in the literature and ADMM stands the most widely used first-order methods for solving such problems with numerous real-world applications. How to develop efficient and scalable ADMM-type algorithms is of significant interest.", "requested_changes": "1. Can you clarify the motivation of using Newton-type methods for solving ADMM subproblem instead of apply them to the augmented Lagrangian subproblem directly. The ALM shares faster convergence properties and if one can afford to apply second-order-type methods, what is the reason of using ADMM?\n2. Can you explain how the inexactness conditions are implementable, i.e., how to verify them in practical computation?\n3. Can you also comment on the convergence Issus of ADMM without ensuring the solvability of the subproblems? It is expected that when your algorithm reduced to the classical ADMM, some additional assumptions are needed. A related paper is provided here:\n    - Chen et al. A note on the convergence of ADMM for linearly constrained convex optimization problems.", "broader_impact_concerns": "NA", "additional_comments": "NA", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)