The inexact power augmented Lagrangian method for constrained nonconvex optimization
Authors: Alexander Bodard
Konstantinos Oikonomidis
Emanuel Laude
Panagiotis Patrinos
Venue: Accepted by TMLR ()

Abstract: This work introduces an unconventional inexact augmented Lagrangian method where the augmenting term is a Euclidean norm raised to a power between one and two. The proposed algorithm is applicable to a broad class of constrained nonconvex minimization problems that involve nonlinear equality constraints. In a first part of this work, we conduct a full complexity analysis of the method under a mild regularity condition, leveraging an accelerated first-order algorithm for solving the Hölder-smooth subproblems. Interestingly, this worst-case result indicates that using lower powers for the augmenting term leads to faster constraint satisfaction, albeit with a slower decrease of the dual residual. Notably, our analysis does not assume boundedness of the iterates. Thereafter, we present an inexact proximal point method for solving the weakly-convex and Hölder-smooth subproblems, and demonstrate that the combined scheme attains an improved rate that reduces to the best-known convergence rate whenever the augmenting term is a classical squared Euclidean norm. Different augmenting terms, involving a lower power, further improve the primal complexity at the cost of the dual complexity. Finally, numerical experiments validate the practical performance of unconventional augmenting terms.

Published in Transactions on Machine Learning Research (10/2025)
The inexact power augmented Lagrangian method for con- strained nonconvex optimization
Alexander Bodard
olezonder. bowardkkuleuuen.neuo
ESAT-STADIUS & AI, KU Leuven
Konstantinos Oikonomidis
ESAT-STADIUS & Aeuven.AI, KU Leaven
Emanuel Laude
elaude@@rnaiimofssiin.com
Prozima Fusion GmbH
Panagiotis Patrinos
panos. manoo.petrinos@kkuueeee.bbb
ESAT-STADIUS & Al, KU Leaven
Reviewed on OpenReview: https: oppnreeveee, net/ forum? id- 63AND4r7EM
Abstract
This work introduces an unconventional inexact augmented Lagrangian method where the augmenting term is a Euclidean norm raised to a power between one and two. The proposed algorithm is applicable to broad class of constrained nonconvex minimization problems that involve nonlinear equality constraints. In first part of this work, conduct full complexity analysis of the method under mild regularity condition, leveraging accelerated first-order algorithm for solving the Hölder-smooth subproblems, Interestingly, this worst-case result indicates that using lower powers for the augmenting term leads to faster constraint satisfaction, albeit with slower decrease of the dual residual. Notably, our analysis does not assume boundedness of the iterates. Thereafter, we present an inexact proximal point method for solving the weakly-convex and Hölder-smooth subproblems, and demonstrate that the combined scheme attains improved rate that reduces to the best- known convergence rate whenever the augmenting term is a classical squared Euclidean norm. Different augmenting terms, involving a lower power, further improve the primal complexity at the cost the dual complexity. Finally, numerical experiments validate the practical performance unconventional augmenting terms.
1 Introduction
We consider nonconuer minimization problems with possibly nonlinear equality constraints of the form
min p(x) = f(z) + g(x) s.t. A(z) 0.
(P)
Here f R denotes nonconvex continuously differentiable function, g R > proper, Isc and
convex function, and A R" R
continuously differentiable mapping. Inequality constraints B(x) <
be incorporated into P by introducing slack variables s e R subject to B(x) = 0 and 0.
The general formulation incorporates. wide variety of problems arising in areas such as machine learning
Kulis et. al. 2007 Ge el al. 2016 Tepper et al. 2018 and computer science (lbaraki & Katoh 1988
Zhao et al. 1998). Typical examples include generalized eigenvalue problems, nonconvex Mture-Moonteio
reformulations (Burer & Montciro 2003 2005), and Neyman-Pearser classification (Neyman et al. 1997)
while recently this formulation has also been considered for neural network training (Sangalli al.
2021
Evens al.] 2021 Liu et. al. 2023).

---

Published in Transactions on Machine Learning Research (10/2025)
This work focuses first-order methods for solving (l) as they scale well with the problem dimensions and require significantly less memory compared to higher-order methods. These advantageous properties become increasingly important, particularly in applications that involve large amounts of data. Whereas existing works usually focus on problems with simple ('proximable') constraints, recent works also analyze first-order
methods that handle more complicated constraints, see, e.g., Xu 2021
Li et al. 2021 Lin el al. 2022
This paper proposes an unconventional augmented Lagrangian method (ALM) solve P and analyzes its complexity under mild regularity condition (cf. Assumption 4 while taking explicitly into account the inexact solutions of the subproblems. Notably, our framework is the first to conduct such an analysis in the presence of a generic convex term under Assumption 4 (cf. subsection 2.1 without assuming compactness
of dom @ (cf. Lemmaa 2), and under relaxed smoothness assumptions.
1.1 Background and motivation
Penalty and augmented Lagrangian methods Penalty methods address penalty function Φ m + IR, sequence of problems of the form
P by solving, for some
minimize + Bo(((x)) =Ele"
in which the penalty parameter 3 > 0 is gradually increased. A common penalty function is the squared Euclidean norm, i.c., Φ(+) = 112.113. However, it is well-known that quadratic penalty methods are empirically outperformed by ALMs. This last class of methods is based on the augmented Tagrangian (AT.) function Lg R" Imm + R, which, for penalty parameter 3 > 0 and squared Euclidean norm Φ, reads
Lo(2, = x(x) + (w A(x)) + (o((()))
(1)
The AL involves penalty term and an additional term (y. A(x)), where y E E are called the dual variables multipliers. Every classical ALM iteration updates the primal-dual pair (x* v²) by alternatingly minimizing La with respect to the primal variable, and consccutively taking a dual ascent step Lg, i.c.,
xit arg min Le(x,y"), g y² + A(x
for some dual step size 2 The primal ALM update can in general only be computed by means of an inner solver, and hence inexactly. In recent years, various works have taken this inexactness explicitly into account when analyzing the complexily of the method, which is then referred to as ineract ALM (iALM), see e.g., (Sahin et al. 2019
An unconventional penalty term In this work we consider an iALM based on a generalization of the classical AL [ in which the penalty term equals
11t1,
V' E (0, 1].
(3)
To distinguish from the classical setup v 1, we refer to this the power AL, and corresponding method.
Connection to high-order proximal point methods In the convex setting (Rockaflllar 1976) showed that classical ALM is equivalent. to the prozimal poinl method (PPM) applied to the negalive Lagrange dual function 0, in the sense that {y heeN generated by
A+l J+ -prox prooxo(("") = arg min e(v) + 23 yERm
lly - 1²112
(4)
coincides with the sequence of multipliers defined by 2 with dual step size a B. More recently, (Oikono- midis et al. 2024b) showed that in the convex regime similar dual interpretation exists for the so-called power ALM (2) with Φ as in (3) if the dual update is modified to y = n² (Vb(A(r**t)) where
Vo(z)
T 2
(5)
2

---

Published in Transactions on Machine Learning Research (10/2025)
for all * 0 and Vo(0) O. More preciscly, the convex power ALM corresponds to high-order PPM
which is obtained by replacing the quadratic penalty in (4) with higher power 3F(r+T] p+1 p 2 1 of the Euclddaa norm - such that 8-1
1 = 1. The proposed nonconvex power augmented Lagrangian - + p+1
1 reduces to the convex one when &p is convex and A is affine (Oikonomidis et al. 2024b Example 2.1).
Although the connection to higher-order methods does not extend to the nonconvex upt considered in this
work, it motivates considering augmenting terms & as in (3 Moreover, the rapid advancements regarding
first-order methods for Hölder-smooth objectives over the past decade (Nesterov 2015 Lan 2015) potentially
allow for faster solutions of the inner problems, which are Hölder smooth in this setting (cf. Lemma 3
Connection to sharp Lagrangians The proposed power AL interpolates between a classical AL with v and sharp AL with v = 0 (Rockafellar & Wets 1998 Example 11.58). The latter are appealing because they support exact penalty representations under mild conditions (Rockafellar & Wets 1998 Example 11.62).
1.2
Related work
The augmented Lagrangian method, initially introduced in 1969 by Hestenes 1969
Powell 1969 is
popular algorithm that allows one to cast the constrained problem P into sequence of smooth problems.
Over the years it has been studied extensively, see o.g., the monographs [Bertsokas] 1982 Birgin & Martínez,
2014). ALM is also closely related to the popular Alternating Direction Method of Multipliers (Gabay
& Mercier 1976 Glowinski & Le Tallec 1989), which has recently been studied for nonconvex equality
constrained problems (Cohen et al. 2022 El Bourkhissi et al. 2023). In the convex regime, ALM was shown to be equivalent to the proximal point method (PPM) applied to the Lagrangian dual problem (Rockafellar 1976). However, in the nonconvex regime this interpretation is lost at least globally (Rockafellar 2023). Instead, we assumee validity of mild regularity condition (El Bourkhissi et al. 2025) (Assumption [4] to establish global convergence of the proposed scheme. An alternative approach that requires (closc to)
feasible initial point, is explored by Grapiglia & Yuan (2021] | Grapiglia (202)).
Inexact ALMs explicitly take into account inexactness in the primal update. They have been analyzed following the paper (Sahin et al. 2019), which establishes an O(a=t) complexity for finding an e-stationary point of (P under a slightly different regularity condition see subsection 2.1 for details. More recently, et al. (2021) employ triple-loop scheme, based on an inexact proximal point method to solve the iALM
subproblems, and obtain an improved complexity Ö(e-3) under this regularity condition. This is the best- known rate of convergence of first-order method for solving P Moreover, Lu (2022) proposes single-loop primal-dual method that attains the same Ö(=-a) complexity under a similar condition. We also mention that Lin et al. 2022) present a penalty method that attains the same Õ(E-3) complexity.
To the best of our knowledge, the 'nonlincar' or higher-order proximal point mothod (using prox-term p+1 |++1 p 2 1) was first studied in (Luque 1987), which also analyzed its dual counterpart, the 'nonlinear' ALM (Luque 1986). Besides being restricted to the convex case, these works provide only a local complexity analysis of the outer loop, neglecting the inherent difficulty of the Hölder-smoote subproblems - a challenge addressed by this paper. Recently, (Nesterov) 2023) studied the joint global complexity of high-order proximal point methods in the convex case; see also (Ahookhosh Nesterov 2021 2024). Its dual counterpart, the power ALM for convex optimization has been recently studied in (Oikonomidis al. 2024b).
Since the power augmented Lagrangian is the sum of a Hölder-smooth function (cf. Lemma and convex function, a first-order method that tackles such problems is desired. Besides the universal optimal methods by Nesterov 20155;; Lan (2015) for convex problems, we highlight the accelerated methods by Ghadimi & Lan (0166;; Ghadimi et al. (2019) for the convex and nonconvex setting respectively. Interesting developments in this area include the linescarch-free adaptive method by Li & Lan| (2024) for convex problems, as well as a recent family adaptive
-rradiint methods by Malitsky & Mishchenko Latafat Latafat al. (2024)
which were recently shown to also converge for locally Holder-smooth problems OOikonoiidis et al. 2024a
3

---

Published in Transactions on Machine Learning Research (10/2025)
1.3 Contributions
We propose a novel inexact augmented Lagrangian method (iALM) with unconventional powers E (0, 1] of the augmenting term & (ef. (3)) for solving a general class of nonconvex problems with nonlinear constraints. The case v = 1 reduces to the standard iALM (Sahin et al. 2019). The complexity of the proposed mothod is analyzed, taking explicitly into account distinct primal and dual tolerances EA, > 0. Notably,
Under mild regularity condition (Assumption we prove convergence first-order stationary points at a rate of w- and show that the constraint violation decreases at faster rate of a w-// where & is the number of (outer) iterations and w determines the rate of increase of the penalty parameters. The joint complexity is then analyzed with the accelerated first-order method from GGhadimi et al. 2019) as an inner solver for the nonconvex and Hölder-smooth subproblems. For == 1, we subsume the complexity of (Sahin et al.) 2019]; for v < 1, we obtain faster constraint satisfaction at the cost of a slower decrease in suboptimality. Thus, the sharper penalties of the AL. are reflected in the complexity analysis.
Our complexity analysis improves upon existing results even for == by relaxing the standard Lipschitz smoothness assumption on f to local Hööler smoothness, by not assuming boundedness of the iterates, and by including generic conver term g in the objective.
Under slightly more restrictive assumptions on and A, present novel inezact prozimal point method to exploit the structure of the weakly-convex and Hölder-smooth subproblems. Using this inner solver, we further strengthen our complexity analysis to match the best-known O(e-3) rate of convergence for the case = 1. As before, V < yields a better primal complexity at the cost of a worse dual complexity. The complexity is further improved when A(r) is a linear mapping.
Finally, numerical simulations indicate that unconventional powers v < 1 also perform well in practice.
1.4 Notation, definitions, and technical assumptions
We denote the Euclidean inner product and norm on R" by (: and || |l, respectively. For matrices || II denotes the spectral norm. The Euclidean distance from a point x to set X denoted by dist(æ, X) mingeæ |||- Given differentiable mapping A R= + R" we denote its Jacobian at by Ja(x) Rm The O-notation suppresses logarithmic dependencics. We denote by : := R U (+oc) the extended real line. For extended-valued function g : R I we denote by domg = {i R" g(x) < oo) its domain and say that g is proper if dom g * 0. A function is lower semi-continuous or simply Isc if its epigroph is closed [Rockafellar & Wets, 1998 $1B). For a convex function I2" + æ.. we denote by Ög(x) its (convex) subdifferential at x E R". : A function
R" + E is called level-coercive if yp is bounded below on bounded sets and satisfies lim inf [1|-+0 p(x)/|=a]| > 0. For a closed, convex set X' we define for any x E TR the normal cone X' at x as (x(x) = E R" (v. 10:yyzz) z) S 0, Vy E }), if x E X, and Nx(x) = 0 otherwise. We define by C (I²) the class of contimuously differentiable functions on R" We say that a mapping is H-Hölder continuous of order E (0, on X T if F(x)) F(x)]] < HI|as' - =||" for all x, E X where H 0. We say that differentiable function f : R R is (H, v-)-Hölder smooth X' if Vf(x) is y-Höölder-continnouss of order on X. When omitted, assumee X' R", and sometimes simply write y- y-Hölder smooth. Finally, the function is Lipsschtt smooth on X' if it is (L,, 1)- Hööder smooth on X.
Rn Rm
Optimality conditions
P has a local minimizer x E R satisfying the constraint qualification
[x]( E NNom (2). A(x) =
y= 0,
(CQ)
Theorem 10.6) in similar way as in Rockafellar & Wets 1998 Exercise 10.7) there exists a vector R such that
then - this follows by applying the subdifferential chain rule (Rockafellar & Wels 1998
A(z) = 0, fz)( JJ (x)y 0g(z).
This set of (generalized) equations, describing the stationary points of P is naturally extended accommodate approximately stationary points. In this paper we introduce two distinct tolerances for
4

---

Published in Transactions on Machine Learning Research (10/2025)
0g(=)) and ||A(z)]], leading to the definition of Esstttianty points. We refer to ελ as the primal residual tolerance and to Ep as the dual residual tolerance.
dist
Definition 1 ((Ep, EA -sttttitio points). Given Ep 2 0 and aΛ 2 0, point E IR" is called an (A), stationary point of P if there is a vector E R such that
||(x))] S cA.
and dist (-Vf(x)
(o)))Og(z)) S Ex.
(6)
Existing analyses for iALMs consider the case Ep = EA > 0, as the obtained complexities depend only on min( In contrast, our analysis reflects that 'sharper' penalties with v < yield faster constraint satisfaction (cf. Theorem 2). which nicely agrees with the exact penalty representation of sharp ALs (Rock- afellar & Wets 1998 Example 11.62). Also in practice, distinct primal and dual tolerances Ep > are relevant. Indeed, absolute tolerances are sensitive to a rescaling of the objective and constraints, and distinct tolerances can be used to compensate this. In fact, and dual tolerances for this reason. Moreover, it is not uncommon to analyze convergence for distinct primal and dual tolerances, e.g. (Hermans et al. 2022 for a proximal ALM for quadratic programming problems. Yet, it appears unique that the primal and dual tolerance have distinct effect on the worst-case complexity.
solvers lypically support distinct primal
Assumptions Throughout this work, we make the following assumptions on f, and A. Assumption 1. For any nonempty compact set S S domg, there exist positive constants Hy, HA, Amax, Jmaxx Mmax such that the following statements hold:
(i) There exists an Vy E (0,1] such that [IV - vs(()) S Hylla' =lI"t for all a, E
(ii) There exists an E [0, such that [[A((²) - Ja(I) S Malla' - I||aA for all x, x, E E;
(iii) [V((') & Vmax. ||Ax))]| < Amax and |Ja(T)] S Amaxx for all x E.
Assumption 2. The function 9 is proper, Isc and conver, and dom g has nonempty interion. For any nonemply compact set S C dom 9, there erists G 2 O such that llg((') g(5)ll || I G'Ila' - =ll for all x. E S. Assumption 3. The function 9 f + g is leeel-coercive.
Assumption is very mild: the conditions on f hold when f is differentiable with locally Hölder continuous gradients, and likewise the conditions on A hold when A has locally Hölder continuous Jacobians. Slightly more restrictive smoothness assumptions, i.e., with vf = VA = 1, have been used various related works, see e-g.; |aahin eagg, et al. (2019); Li al. (2021): Lu 2022). Also Assumption
2 is very mild: a proper, Ise and convex function g is Lipschitz continuous on any nonempty compact subset of int dom g (Rockafellar 1970)] Theorem 24.7). Therefore, any potential issue arises at relative boundary points of the effective domain, exemplified by the function x + -V. We highlight in particular that indicators of closed convex sets, and real-valued convex functions all satisfy Assumption 2 Finally, note that yp is level-coercive if either f or g Exercise 3.29). Alternatively,
is level-coercive while the other is bounded below (Rockafellar & Wets 1998
it suffices that vp is coercive, as the case when dom = dom g is bounded.
Notably, and contrary to related works (Sahin et al., 2019: Li et al., 2022 Lu 2022 El Bourkhissi et al. 2025), no compactness of dom y or boundedness of the iterales is assumed, which makes the smoothness assumptions on f and A truly local. Moreover, we incorporate generic convex term g. Also (ahhn et al. b2019h El Bourkhissi et al. (2025) have done this, but, respectively, under regularity condition which may not be ideal (cf. subsection 2.1 or under additional technical assumptions which may be hard to verify in practice. When analyzing the complexity of power ALM with the proximal point method as inner solver in section 3 we restrict our assumptions to match those of Li et al. (2021): Lu (0022). Table summarizes our assumptions and compares them against those in similar works.
2 The inexact power augmented Lagrangian method
In this section we present the ineract power augmented Lagrangian method (power ALM), of which the pseudocode is shown in Algorithm 1 This method generalizes the inexact augmented Lagrangian method
5

---

Published in Transactions on Machine Learning Research (10/2025)
Table Comparison of the assumptions in this work against those in existing works.
Peualty term
Smoothnes
Nonsmooth term !
Boundodness iterates
Regularity condition (RC)
of f and A
Remark
RC not ideal for generic of. subsection 2
Sahin al.
2019
Lipschitz
generic convex
assumed
Assupption
Li el
2021
2022
Lipschitz
convex indicator generic noneouvex
compact doun y assumed
Assumption
E1 Bourk
2025
Lipsclitz
Assumption
lecunical conditions
Ours (Alg.
e E (0, 1
Hölder (loral)
generic convex indirator
level-coerciiity compact dom
Assumption
Ours (Alg
Lipschitz
Assumption
that was proposed and analyzed by Sahin et al. 2019 ei al. 2021 to settings where v + 1. To adequately exploit the composite structure of the augmented Lagrangian Lo(x, v), we define
L v) == f() (A(x).)) y) + - A(z))l**
(7)
and note that the augmented Lagrangian ()) = و y) g(() is the sum of a smooth and a nonsmooth term. The ALM subproblem step entails inezactly minimizing the augmented Lagrangian, i.e.,
Algorithm Inexact power augmented Lagrangian method
Require: x R", y' E R", À > 0, w > 1, 01, B1 > 0, E (0, 1]. 1: for == 1,2,..... do
2: Update the tolerance Ek+1 \/ and obtain ++1 X such that
dist V v/a. (x++1, y²), (gg((h))) I Ek+1-
(8)
[|(()))11* 10g)
3: Update the dual step size as 0k+1 = 01 min(1, Update the multipliers yk+1 = yk + 0 Va(A(A (1(x)))))) Update the penalty parameter B = wBz.
() (og²
end for
minimize Lg, (r, 58 = ths (x,, v0) + g(x); #ER"
until the condition is satisfied. Observe also that the dual step size update rule (step 3 is constructed in a way that ensures boundedness of the multipliers. This is captured by the following lemma.
Lemma The sequence {y²) Jee generated by Algorithm is bounded, iee, there exists a ymmax E R, such that ll S ymax for all 1.
The proof is given in Appendix A.1 We remark that the results in this work can be extended to incorporate unbounded sequences of multipliers, by following the proofs of Li et al. (2021). The next lemma establishes
that the iterates of Algorithm D remain in compact set as long as the inner solver in step 2 monotonically
decreases its objective. Hereby, and contrary to existing works (Sahin et al. 2019 Li et al. 2021 El Bourkhissi
et al. 2025), no compactness assumption is required on dom g. A proof given Appendix A.1
Lemma 2. Suppose that Assumption 3 holds, and let Jeen, fyrt JuEN, (33) keN be generated by Algorithom For any B E IR, y E 1.m x E dom 9, the sublevel set (ay(T)) = fx R" La(z, v) I Lo(ā,y) is nonempty and compact. If, additionally, Ls. (x++11 ",th,,))))) < Lg, (x* (x*,y²) for k 2 1, then:
(i) the sublevel sets satisfy t (1*+1) S fe for 1;
(ii) the ilerates )eeN remain in the (compact) initial subleved set, iee., rhtl E Ler for k 2 1.
2.1 Complexity analysis
We analyze the computational complexity of Algorithm| ! under regularity condition involving the nonlinear mapping A and the normal cone Ndomg; which also naturally arises in the constraint, qualification (CQ).

---

Published in Transactions on Machine Learning Research (10/2025)
Assumption 4 (regularity). For any nonempty compact set S C dom 9, there erists an R > 0 such that for all x S.
(itt) (x)) 2 [||A(=)]l
(R)
Assumption was used by El Bourkhissi et al. (025 to analyze the complexity of an ALM. If g has full domain, then Assumption
on the feasibility problem minimize, A(x)]l2 (Sahin et. al. 2019), and is consequence of the uniform regularity condition by Bolte et al. (0118 Definition 3) in the so-called information zone. On the other hand, if g 6x is the indicator of closed convex set X, and if the constraint qualification [CQ] - which is itself a generalization of the Mangasarian--rrooviii condition (Rockafelarr 1993) holds at a point I E IR", then (R) holds for the singleton S = {ā}- Assumption moreover assumes the existence of a uniform constant R > 0 such that (R) holds for any E domg. g. Existing works on iALMs, such as Li et al. (2021); Lu (2022). typically only deal
reduces to a
with the case g = ōx. and analyze the corresponding complexity under Assumption 4 Sahin et al. (2019) use condition similar to (R) involving the subdifferential 0g(x:) instead of Wdomg(a)
g dx, then this
is equivalent because Ög(xz) NNom (a) = (x(xx) for x E X. However, if g has full domain and is strictly continuous, it has been argued by El Bourkhissi et al. (2025) that Assumption 4 should not involve g, which
is the case if Ndom g is used, but not for dg. We refer to El Bourkhissi et al. (2025 $5) for an extensive
discussion and comparison to other regularity conditions.
Various problems satisfy Assumption 4. as shown by Sahin el al. (2019) for g = 8x, including clustering, basis pursuit and others. Moreover, Li et al.] (2021) demonstrate that affine equality constrained problems with additional polyhedral constraint set ball constraint set also satisfy this condition. Some intoresting constraint functions A do not satisfy this condition globally. For example, (Bolte et al., 2018 Example 5) 0 and for spherical constraints A, ( only holds if S is bounded away from the origin.
show that for
Our first result describes the number of power ALM iterations to obtain an approximate stationary point. Theorem 1 (Outer complexity). Let {a JaeN denote the sequence of iterates generated by Algorithm If Assumptions 1 to 4 hold, and if there erists a nonempty compact set S S domg g containing the iterates (a*) Juen, then x+1 is a 3,
Q1
Qa )-slationary point of P with
Q, X J JAmax
Emac +G- JAmas Vimxx t
Q^ = [ +G+ Dmaae
(SfuactG+ R
(10)
The proof is given in Appendix A.1 We highlight that there exists a nonempty compact set S containing the iterates Jeen when the inner solver in step 2 of Algorithm monotonically decreases its objective (cf. Lemma 2h. If dom g is compact, then this condition is always satisfied, regardless of the inner solver.
Theorem I states that if such a nonempty compact set S exists, then A Minds a first order stationary point of at a rate of wr where w > 1 determines the rate of increase of the penalty parameters. This is identical to the result Sfahnn et al. (2019) for iALM. Remarkably, in the case of Algorithm 1 the constraint violation ||(+*)]]| decreases at a faster rale of wk/y, However, it is important to note that the described rates are only in terms of the number of iterations of power ALM, i.e., the number of calls to the inner solver in step [ To obtain a full complexity analysis of the method, we must specify the inner solver and require an estimate of its computational cost. This is related to the Hölder smoothness of x + (
Lemma 3 (Augmented Lagrangian smoothness). Let Assumption | hold. Then, for any y E R", and on any nonemply compact set S C IR"", the function tha(;;)) v) as in (7) is -)Hödder smooth for some H3 2 0 which depends on S with q min [u,, UA, (0. In particular,
have for all x., x' S that
[Va45(Zz y) V b)ll S Hal -x119.
where the modulus of Hölder smoothness H3 depends on Hy. HA, JAmses and thus on S, and is given by
H1 = U1 + Halllll + ( + A Ha)) max {1, D1 with D == sup
| x'
xx ES
The proof is given in Appendix A.1 objective, i.e., the sum of a nonconvex and Hölder-smoot. function and a convex function. Minimizing such
A.1
The ALM subproblems of the form 99 in step 2 thus involve a composite
7

---

Published in Transactions on Machine Learning Research (10/2025)
objective typically results in higher computational cost than its counterpart with bi Lipschitz-smooth [Grimmer 2024). The unified problem-parameter free acceleraedd gradient (UPFAG) method of Ghadimi
et al. (2019) appears one of the only accelerated first-order methods for which a worst-case complexity analysis has boen derived under both nonconvexity and Hölder smoothness. We proceed by deriving the total complexity of power ALM when UPFAG used in step 2 For ease of notation we write Lx == L.s, (z, )²).
Remark that the value _ == min [x(x)= > -0 finite, and hence the inner problems (9) in Algorithm 1
step SarP2aare are well-defieed. Indeed, from Assumptions and and Lemma 2 LA is proper, Isc and level-bounded
Lower boundedness then follows from (Rockafellar & Wets 1998 Theorem 1.9). Moreover, since the UPFAG
method enforces a monotonic decrease on its objective, Lemma 2 ensures that all UPFAG iterates remain in the compact initial sublevel set va (x*). In the remainder of this section, we therefore define the smoothness constants from Assumptions and with respect to this set, without further mention.
The following lemma upper bounds the number of UPFAG iterations to inexactly solve an inner problem.
Lemma 4 (Inner complexity). Suppose that Assumptions 7 to hold. Then the total number of (inner) ilerations performed by the UPFAG method, with a small enough step size and initial iterate x to obtain an Ek+1- -saalioary point to the power ALM inner problem (cfr. Algorithm slep 2 is bounded by
144
1/q Ia (a("")) 1 14 o (11
(
(11)
This result follows by the complexity result in (Ghadimi et al. termination ion criterion than the original work, we provide an explicit proof in Appendix A. for completeness. We can now describe the complexity of power ALM in terms of UPFAG iterations.
2019
Corollary 5). Since we require a different
Theorem 2
(Total complexity). Suppose that Assumptions
A hold and the UPFAG method from Ghadima in the setting of Lemma 4 Given Epp 0 and E >
ce al. (219)) is used for solving Algorithm 7 step Algovithm finds an (Eup, &A),&&)=aa s))-salioonary point of after at most T max (T,, UPFAG ilerations, where for q mi,,
To =5=0 -
Evp
5182 29
TA ŌA=Ō = ((A)
3w(++g)
2q
(12)
The proof is given in Appendix A.1 In the Lipschitz smooth setting, our analysis subsumes the one from Sahin et al. (2019): if we choose v =1 and S. = A E, we obtain T, = TA = Ô 0 (s-1). In the same setting, by choosing // < we get a worse convergence rate for the dual residual and a better one for the primal. This result is line with the intuition behind choosing a sharper augmenting term for the AL. function, which highly penalizes the constraint violation. Finally, we highlight that the average nunber of gradient evaluations per UPFAG iteration is bounded by a constant (Ghadimi et al. 2019). It follows that Theorem 2 also describes the number of first-order oracle calls for finding an (A):=A))stationna) stationary point of (P)
3
An inexact proximal point inner solver with improved complexity
This section presents an inexact proximal point method for solving the inner problems of Algorithm 1 The proposed scheme is essentially a double-loop algorithm that uses an accelerated gradient method for computing the proximal point updates, inspired by Kong et al. (2019: Li et al. (2021) and adapted to the Hölder smooth setting of our paper. However, we emphasize that this extension is not straightforward, since a Hölder-smooth subproblem cannot be made strongly convex by adding sufficiently large quadratic term, and strong convexity of the inner-most problem is essential in obtaining an improved overall complexity. Henceforth we restrict Assumptions I to as follows.
Assumption 5. The function g âx is the indicator of a non-empty, conver and compact set X C R with diameter D > 0. There exist positive constants L,,, LA, Auax, JAmax: V fmax such that:
(1) [V/((')) - -f(x)) < T-yl2²' x:ll for all x. E X;
(i) [Ja(x'') Jx(x)] & LAlla' xill for all x. E X;
8

---

Published in Transactions on Machine Learning Research (10/2025)
(ii) |V V fmax: max: |A(x)]] I Amax and [Ja(x)] Jmaax for all x E X.
Under Assumption we have Vj = VA 1, and hence by Lemma the power AL has Hólder-contimuous gradients of order q q= on X. Moreover, in this setting the power AL function is weakly-conwerr
Lemma 5. Suppose that Assumptions 4 and 5 hold. Then, for any y E Rm Ls(t,)) v) is p-weakly convex on X, with p = Ly LA (llll + ).
T the power augmented Lagrangian
The proof is given in Appendix A.2 Therefore, every subproblem in Algorithm
step is of the form
(<x) Lo(x, (). #EX
min
(13)
for some IR, where v is (Hg, -o--Hölerr-smoth and p-weakly convex on the compact set X. The weak
convexity of & motivates the use of an inexact proximal point method, described in Algorithm 2 Note that the inexact proximal point updates entail minimizing a strongly convex and Hölder smooth function over compact set and thus we can utilize the Fast Gradient Method (FGM) from [Devolder et al. (2014)
compute them. Our approach differentiates from standard analyses in that the objective function of 13 has qualitatively distinct lower and upper bounds, obtained from the weak-convexity and Hölder-smoothness, respectively. To the best of our knowledge, the forthooming analysis of the proposed inexact proximal point method is the first to exploit this, and as such enables an improved total complexity of Algorithms and
Algorithm Inexact proximal point method for 11
Require: I E R", Lolerance & > 0.
1: for A = 1, 1.2.... do
2: Let F()) = (-) + pll -x and obtain xh11 E such that
dist( (ist(-F((**t) Nxx s 5/4.
3:
2p|1=*t1___ - x01 1 S then return ++1
4: end for
3.1 Complexity analysis of the inexact proximal point method
The computation of proximal point update, defined in Algorithm step
involves a problem of the form
min F(x) ZEX
(14)
where F: R" + R (Hr, -older--r-oo with HF = Hg 2p max D2-9), and p-strongly convex. We denote the minimizer of F over X by x² arg minzex F(x). The following thcorem describes the number of FGM iterations needed to obtain point satisfying the inequality in Algorithm 2 step 2 and is based on (Devolder et al. 2014 $6.2). Its proof also handles the different termination criterion that we require compared to (Devolder et al. 2014 $6.2), and for this reason becomes rather technical.
Theorem 3. Let F be as in Algorithm 2 step 2 and suppose that Assumption 5 hold. Then, we need at most T FGM iterations to oblain a point x E X that salisfies dist(- dist(-VF(at)) Nx(xt))
S e, where
T ==
# p
1ir
30
with
H H-
(2H (1
The proof is given Appendix A.2 The next theorem, adapted from [Li et al. 2021 Theorem 1), provides an upper bound on the number of iterations the inexact proximal point method presented in Algorithm 2 needs in order to terminate. Its proof is also found in Appendix A.2
Theorem 4. Suppose that Assumption holds. Then, Algorithm 2 stops within T iterations, where T 32g (w(++) - + + +1, and the oulput Tf Rm satisfies
(T) Nx(x²)) S.

---

Published in Transactions on Machine Learning Research (10/2025)
3.2 Joint complexity analysis of Algorithms and 2
Having described the complexity of Algorithm 2 now move to the total complexity of the joint scheme,
which is the main result of this section. We highlight that this result improves upon Theorem 2 For v = 1 it subsumes the complexity result in (Li et al. 2021 Theorem 2), whereas for v < 1 better primal complexity is obtained at the cost of a worse dual complexity. proof is given in Appendix A.2
Theorem 5 (Total complexity). Suppose that Assumplions and hold, and let {x² JKEN denote the ilerales of Algorithm 1 If Algorithm 2 is used to solve the subproblems in Algorithm | step B and if the incract
prozimal point updates in Algorithm & are computed using FGM, then an (Epp E ----ssiissooaryy point of (P) is
obtoined after at most T max Ta} FGM iterations, where
To = 0 (
-3- -3-1 (1+ (422)))) (1))))
)
Ta = -
-3v- I13r (3x+22
Eip
EA
As described in Appendix C an FGM iteration requires a single gradient evaluation of f and two projections onto X. Consequently, Theorem also describes the number of first-order oracle calls needed to find an (Ep; Ca)-stationary point of (P.
3.3 Improved complexity for linear constraints
Theorem describes the joint complexity of the triple-loop version of power ALM: Algorithm in which the primal update in step 2 is obtained through Algorithm 2 and where in turn the inexact proximal point updates are computed using the FGM. If the constraint mapping A is linear, this worst-case complexity can be further improved. It is obtained by following the exact same steps as in the proof of Theorem 5 and by remarking that is lincar, then LA = 0. By Lemma 5 we have = Ly + L L + 344ma)) and hence = 0(1) if is linear, instead of p= O(3) for nonlinear constraints. The following result subsumes
p == 1,f 1=
the Ō
complexity of (Li al. 2021 Theorem 2) for v 1. proof is given in Appendix A.2
Theorem 6 (Total complexity). Suppose that the conditions of Theorem hold, and additionally assume that the mapping linear. If Algorithm 2 is used to solve the subproblems in Algorithm ] step 2 and if the ineract prozimal point updates in Algorithm point of obtained after at most T = max (T TA} FGM iterations, where
2 are computed using FGM, then an aa)-Eaattioooayy
Txp =
E4
-2-2 Lu tie
1430 "
1430
TA =Ō = -2v-2 (1+1) 1250
EA
4 Numerical results
In this section, we compare the practical performance of power ALM (Algorithm 1 for various choices of the parameter 1] to illustrate the empirical behavior of the proposed method in practice. Recall that the choice = reduces to the iALM from (ahin et al. (2019). and therefore is always included as a baseline comparison. All experiments are run in Julia on an HP EliteBook with 16 cores and 32 GB memory, and the source code is publicly available Unless ment ioned otherwise, the subproblems in Algorithm 1 step 2 are solved using the UPEAG method of Ghadimi et al. 20019). In our experience, this approach works well in practice, and does not usually underperform when compared to the presented triple-loop scheme basod Algorithm 2 despite the improved worst-case convergence rate of the latter approach. Some additional experiments are included in Appendix
10

---

Published in Transactions on Machine Learning Research (10/2025)
-10*
144
10
# UPPAC Mooss
1.2
[4(x]]
10"1
10"1
10"4
10:1
0.8
0.77
UPFAG toes
-101
UPFAG iters
Powwer
(a) Constraint violation
(b) Suboptimality
(c) UPFAG iters, Ep = Ex = 10
Figure 1: Comparison of power ALM with various powers v on solving the clustering problem with
Sashion-MNIST data Xiao et al. 2017 The case v/ = 1 corresponds to iALM from Sahin et al. (2019)
-10
0.5
10a
# UPEAC Ite
0.5
[Mcil
10--
20-1
10
20-1
0.2
0.3
0.5
0.5
0.2
0.4
0.6
0.5
0.65
0.7
0.75
0.8
0.85
0.0
0.55
UPEAG
100
UPEAG
20*
(a) Constraint violation
(b) Suboptimality
(c) UPFAG iters, Eg EA 10
Figure 2: Comparison of power ALM with various powers solving the clustering problem with MNIST 1 corresponds to iALM from Sahin et al. (2019).
data Deng 20122. The case
4.1 Clustering
First, we consider clustering problem which, following Sahin et al. 2019 can be reformulated in the form through rank-r Burer-Monteiro relaxation with
f(x) ΣΣ (eg(
A(x) [o] El. 1, , a E Tq. -
Here := I E Rm with v; E R' for i E nI, and X is the intersection of the nonnegative orthant with the Euclidean ball of radius Vs. The scalar denotes the number of clusters, and D E Rx* is a distance matrix generated by some given data points p ie., such that Di = -
We test Algorithm on two problem instances, being the MNIST datasct Deng 2012) and the Fashion- MNIST dataset, Xiao al. (2017). The setup similar to that of Sahin al. (2019 which is in turn based Mixon et al. (2016). In particular, simple two-layer neural network was used to first extract features from the data, and then this neural network was applied to 1000 random test samples from the dataset, yielding the vectors {z* {=*)==1000 that generate the distance matrix D. We define = 10, r = 20, tune σ₁ = 10, A = 10-3 3, 5, w = 1.1, and impose a maximum of = 1500 UPFAG iterations per subproblem. Note that |ahin et al. (2019) showed that Assumption 4 satisfied for this clustering problem. The results are visualized in Figures and 2 We observe that the unconventional powers 0.7 and 0.8 perform best, requiring less than half the number of UPFAG iterations to converge to 10- point when
compared to the iALM of Sahin et al. (2019) (v 1).
4.2 Quadratic programs
Second, consider nonconvex quadratic programs (QPs) of the form P with
f(x) = 2 Qx + (g.x), X = fo x
A(x) = Cr
11

---

Published in Transactions on Machine Learning Research (10/2025)
Here Q R C Rmxn b R", and q R", with Q symmetric and indefinite, are randomly generated, and x² = -5 and 3' 5 for i E [..]- We sample the entries of diagonal matrix A E R from a Gaussian (0, 50), and the entries of a matrix 2 E Ruxa from the standard Gaussian. Then, we normalize E = =/ and define Q = ETAS AΣ. The entries of of C' are sampled from the standard Gaussian. We construct vector μ E R with standard Gaussian entries, and define := Cp. A maximum of N = 10 UPFAG iterations per subproblem is imposed, and the parameters 31 = 5, w = 1.1, 10-3, σ1 = 10 follow the tuning from the previous subsection. We use tolerances Ep = = = 10-3, Remark that the AL function with penalty 3y has I|Q + 3 C'Ipsipschitz continuous gradients for 1. We highlight that the dual residual can be efficiently computed by following the procedure described by (Nedeleu el al. 2014 Eq. 2.7 and below).
sampled from Gaussian 20,, and the entries
We generate 100 random QP instances of size iterations and the objective value at the returned points by means of violin plots in Figure 3 We observe that v = 0.8 and v = 0.9 perform best in terms of UPFAG iterations. Yet, we also nole the more robust performance of v = 0.6. Regarding the quality of the (local) solutions, Figure 3b indicates that the use of unconventional powers v does not yield siguificantly better or worse solutions than the classical choice v =
200,
10, and visualize the total number of UPFAG
-10
500
UPEAC iters
-1,00
1,500
0.6
0.7
0.8
0.9
0.6
0.7
0.8
0.9
Power
Power
(a) Number UPFAG iterations.
(b) Objective value.
Figure 3: Power ALM for various powers on solving 100 random QPs of size n 100, m 200
Table reports the number of UPFAG iterations performed by power ALM for the first 10 randomly generated QPs, and also includes the obtained primal and dual residuals. The power 0.8 performs well compared to the classical setup 1, and requires roughly 25% fewer inner iterations average. Note that the best primal residuals are attained by the smaller powers v, and the best dual residuals by the higher powers For E = 0.6 and 0.7, the inner solver often attains the maximum number of inner iterations N. In our experience, further increasing for these powers works counterproductivel and increases the total number of UPFAG iterations.
Table 2: Power ALM with UPFAG inner solver on solving random QPs of size 100, = 20.
0.5
0.7
0.8
0.0
1.0
trial
pies
doess
Hens
poss
dres.
Hots
pres
dees
Iters
pees
dres
# Itees
p00s
dres
Hets
10
7.5-
75,063
5.8 10-4
1.5 10
81,302
10-1
1.0 10-5
61,910
5.6
2,7 10-
46,000
7.2 10
1- 10-
58 58,003
15.740
10-
55,571
10-7
0.9 10
6.3- 10
1.3
10
5.9 10
10
10
8.3 10-7
1.2-107 10a
6 10-7
1-
8.7
6.5 10
1.3 102
7.5 10
3.4 36
500000
8.4 30
3: 10
600000
9.4 30
1.6
69.508
9:3-10
1.1 10
66,502
8.8 10
2.0 10
1.1-110
8-6 10
4.4-
50,000
6.4 10
4.2 10
60,000
1.1-10
4.7 10
42,728
8.6
8.8. 10
1.6. 10
9.7
7: 7-10"
2.1-10"
2.5
55,738
0.7 10
1.4-
57,214
10-
51/065
6.9
45,508
8-
1.4- 10-1
51,917
10
10
10-
10-1
10-
37,796
10-1
5.5- 10
1.5- 10
80,000
10--
1.4 10
70,000
7.8- 10
1.4-10-6
68,184
5.8-10
1.1-10 10-1
74,075
88: 10
8.2 10
87,008
4.7 10
8.9 10
500000
3.3 10
1.4 10
60,000
3.8 10
1.9 10-6
48.242
45-100*
1.2 10-
42,636
9.8 10
7.5 10
44,826
5.6 10
2.9
61.004
6.7 30
2:
72.50M
5.1 10
1.9 10
54.368
5.1
1.0
46,028
8.7 10
1.2 10
55,486
08g
5.2-
10
2.5
10-3
65,000.5
86- 10
8- 10-5
76.583.8
60--10-
4.8-10-6
61,940.3
6.0-10-
1.6 10
68,543
7.9- 10
2- 2-10
65,588.3
We now compare these results to Table 3 which is similar to Table 2 but uses the triple loop version of power ALM, i.c., Algorithm | in which the primal update in step 2 computed using Algorithm 2 (iPPM). The inexact proximal point updates computed using the accelerated adaptive proximal-gradient
12

---

Published in Transactions on Machine Learning Research (10/2025)
algorithm presented in (Mlitskky & Mishchenko, 2020 Algorithm 2), which, although a heuristic, significantly outperforms the other methods we tried. We tuned 81 1, = 1.1, = 0.01. Although the triple-loop version of power ALM has a better worst-case complexity, in practice we find that it is usually outperformed this table. We do, nevertheless, observe that the triple-loop
by its doublc-loop variant, as confirmed method more stable, the sense that the number gradient calls fluctuates less between QP realizations. in Li et al. (2021). Moreover, remark that as decreases, the primal residual
This was also observed for or constraint violation also decreases, thus qualitatively confirming our theoretical results that decreasing v yields faster constraint satisfaction.
Table 3: Power ALM with iPPM inner solver on solving random QPs of size 100, m 20.
11.5
0.7
0.S
0.9
1.0
trihl
pres
dree
grade
press
dres.
A grads
pres
dres
grads
prw
dres
2 grads
pcvs
drcc
# grads
1.4 10
0.7- 10
1.2 10
3.8
8.4 10-
1.2
1.2 10
9.4 10000
1.4-1 10"
9.3 10
1-10
1.3 100
1.3 10
0.4 10
1.1
10
4.7
7-10-4
109
3.6
10
10-4
10a
10-1
10-
1.4
8.6
10-4
1.6.
1-6 10
0.1 10
299 10
5.7 10
7.2 7-2-10-
1- 10
1.3 10
4.8-10
96,070
1.8-10-
7,0 10-4
57.422
7.1 10
7.1 10
1.2 10a
9.5 10
0.77 10
1.7-10f
2.9 10-7
9.6 1
1.9 162
1.5 10
8.1-10
2.2 10
1.7-10
3-10
1.6 16"
3.4-
8.7 10
1.9 10
5- 10
9.8 10
9.5 10
9.5 10
1 10
1.6
18
9.9
1.3 10F
1.8 10
9.4 10
1.2 110
7.0 30
9.5 10
1.3. 10
10
9.4
2.5
10
9.3
1.3 100
1.1 10
8.5
2.7 10
10
10-1
95,543
10-1
2.511-11
5.2-10
10--10-4
10-3
10-1
1.2-10
8.5- 10
0.7- 10-1
8.7- 10
2.5- 10-3
9.8-10-4
3- 10
2.7-10-5
9.--10-
1.1-10
4 1-10-
8.5-10-1 10-4
1.3-10"
166 16-10-1
10-4
16-10"
10
2.7 10
4.2 10
89,998
6.3 6.3-10-3
7-10-4
87,063
1.7 10-5
9-10-1
1.1-10
9.5-10-2
8.4 10-4
1.6
7.8-101
0.1-10
1.1-10"
2w0g
3.3
10
8.1- 10
6.4 10
8.3- 10
8-10-
1.6
1.7-10
7.9
1.5
1.6-10
7.7 10
1.5 10"
366 10
8.5- 10-100
1.4-10
5
Conclusion
In this paper introduced and analyzed an inexact augmented Lagrangian method for nonconvex problems with nonlinear constraints, involving potentially sharper penalty function. Taking into account the com- posite utructure of the corresponding augmented Lagrangian function, we study the joint complexity of the scheme using two different subproblem oracles. One of these oracles a novel proximal point scheme that exploits the specific structure of the subproblens, of which the objectives are Hölder smooth and wcakly convex. The proposed augmented Lagrangian method generalizes existing works with conventional penalty terms that attain the best known convergence rate for nonconvex minimization with first-order methods. Notably, we proved that unconventional penalty terms yield faster constraint satisfaction at the cost of a slower decrease of the cost, thereby reflecting the sharper penalties in the complexity analysis. It is note- worthy that our analysis also improves upon existing works by considering a generic convex term in the objective, and by not assuming boundedness of the itcrates. Numerical experiments indicate that also in practice such penalty terms perform well.
Acknowledgments
This work was supported by: Research Foundation Flanders (FWO) research projects G081222N, G033822N, GOA0920N; Rescarch Council KU Leuven C1 project No. C14/24/103; and EuroHPC Project: 101118139 Inno4Scale.
References
Masoud Ahookhosh and Yurii Nesterov. High-order methods beyond the classical complexity bounds, II: inexact. high-order proximal-point methods with segment search, September 2021.
Masoud Ahookhosh and Yurii Nesterov. High-order methods beyond the classical complexity bounds: inexact high-order proximal-point methods. Mathemalical Programming, January 2024.
Amir Beck and Mare Teboulle. A Fast Iterative Threhshoogggrr Algorithm for Linear Inverse Prob- lems. STAM Journal on Imaging Sciences, 2(1):183 202, January 2009.
Dimitri Bertsekas. Construined Optimization and Lagrange Multiplier Methods, Academic Press, January 1982.
13

---

Published in Transactions on Machine Learning Research (10/2025)
Ernesto G. Birgin and José Mario Martínez. Practical Augmented Lagrangian Methods for Constrained Oplimization. Society for Industrial and Applied Mathematics, Philadelphia, PA, May 2014.
Jérôme Bolte, Shoham Sabach, and Marc Teboulle. Nonconvex Lagrangian- Based Optimization: Monitoring Schemes and Global Convergence. Mathematics of Operations Research, 43(4): (1)4:)210-122))) November 2018.
Samuel Burer and Renato D.C. Monteiro. A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Mathemalical Programmingg 95(2):329 357, February 2003.
Samuel Burer and Renato D.C. Monteiro. Local Minima and Convergence in Low-Rank Semidefinite Pro-
gramming, Mathematical Progromming, 103(3): 444, July 2005.
Eyal Cohen, Nadav Hallak, and Marc Teboulle. A Dynamic Alternating Direction of Multipliers for Noncon- Minimization with Noulinear Functional Equality Constraints. Journal of Optimization Theory and Applications, (13(1):324-38) 323--33,, June 2022.
Li Deng. The MNIST Database of Handwritten Digit Images for Machine Learning Research [Best of the Web]. JEEE Signal Processing Magazine, (9(6):141114 142, November 2012.
Olivier Devolder, François Glineur, and Yurii Nesterov. First-order methods with inexact oracle: the strongly convex case, March 2014.
D. Drusvyatskiy and C. Paquette. Efficiency of minimizing compositions of convex functions and smooth maps, Mathematical Programming, 178(1):503 558, November 2019.
Lahcen El Bourkhissi, Ion Necoara, and Panagiotis Patrinos. Lincarized ADMM for Nonsmooth Nonconvex Optimization with Nonlinear Equality Constraints. In 2023 62nd IEEE Conference Decision and Control (CDC), pp. 7312-7317, December 2023.
Lahcen El Bourkhissi, Ion Necoara, Panagiotis Patrinos, and Quoe Tran-Dinh. Complexity of Linearized Per- turbed Augmented Lagrangian Methods for Nonsmooth Nonconvex Optimization with Nonlinear Equality Constraints, March 2025.
Brecht Evens, Puya Latafat, Andreas Themelis, Johan Suykens, and Panagiotis Patrinos. Neural Network Training as an Optimal Control Problem : - An Augmented Lagrangian Approach In 2021 60th IEEE Conference on Decision and Control (CDC), pp. 5136-5143, December 2021.
Daniel Gabay and Bertrand Mercier. A dual algorithm for the solution of nonlinear variational problems via finite element approximation. Computers & Mathematics with Applications, 2(1):17 40, January 1976.
Rong Ge, Chi Jin, Sham, Pranceth Netrapalli, and Aaron Sidford. Efficient Algorithms for Large-scale Generalized Eigenvector Computation and Canonical Correlation Analysis. In Proceedings of The 33rd International Conference on Machine Learning, pp. 2741-2750. PMLR, June 2016.
Saeed Ghadimi and Guanghui Lan. Accelerated gradient methods for nonconvex nonlinear and stochastic programming. Mathematical Programming, 156(1):59-99, March 2016.
Saced Ghadimi, Guanghui Lan, and Hongchao Zhang. Generalized Uniformly Optimal Methods for Nonlincar Programming. Journal of Scientific Compuling, 79(3):1854 1983)11854-1881 June 2019.
Roland Glowinski and Patrick Le Tallec. Augmented Lagrangian and Serntor-Splitting Methods in Non- linear Mechanics. Studies in Applied and Numerical Mathematics. Society for Industrial and Applied Mathematics, Jamuary 1989.
Geovani N. Grapiglia and Ya-xiang Yuan. On the Complexity of an Augmented Lagrangian Method for Nonconvex Optimization. IMA Journal of Numerical Analysis, 41(2):1546-155) 1568, April 2021.
Geovani Nunes Grapiglia. Worst-cas evaluation complexity of quadratic penalty method for nonconvex optimization. Optimization Methods and Software, 38( 38(4):781-80) July 2023.
14

---

Published in Transactions on Machine Learning Research (10/2025)
Benjamin Grimmer. On optimal universal first-order methods for minimizing heterogeneous sums. Opti- mizalion Letters, 18(2):427-4433 445, March 2024.
Ben Hermans, Andreas Themelis, and Panagiotis Patrinos. QPALM: proximal augmented lagrangian
method for nonconvex quadratic programs. Mathematical Programming Computation, 14(3):497-54 541, September 2022.
Magnus R. Hestenes. Multiplier and gradient methods. Journal of Optimization Theory and Applications, 4 00,000-320, November 1969.
Toshihide Ibaraki and Naoki Katoh. Resource allocation problems: algorithmic approaches. MIT Press, Cambridge, MA, USA, May 1988.
Weiwei Kong, Jefferson G. Melo, and Renato D. C. Montciro. Complexity of Quadratic Penalty Accelerated Inexact Proximal Point Method for Solving Linearly Constrained Nonconvex Composite Programs. STAM Journal on Optimization, 29(4):2566-2 2593, January 2019.
Brian Kulis, Arun C. Surendran, and John C. Platt. Fast Low-Rank Semidefinite Programming for Em- bedding and Clustering. In Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics, pp. 235-242. PMLR, March 2007.
Guanghui Lan. Bundle-level type methods uniformly optimal for smooth and nonsmmoohh convex optimiza- tion. Mathematical Programming, 149(1):1-48) February 2015.
Puya Latafat, Andreas Themelis, Lorenzo Stella, and Panagiotis Patrinos. Adaptive proximal algorithms for convex optimization under local Lipschitz continuity of the gradient. Mathematical Programming, October 2024.
Tianjiao Li and Guanghui Lan. A simple uniformly optimal method without line search for convex opti- mization, August 2024.
Zichong Li, Pin-Yu Chen, Sijia Liu, Songtao Lu, and Yangyang Xu. Rate-improved inexact augmented Lagrangian method for constrained nonconvex optimization. In Proceedings of The 24th International Conference Artificial Intelligence and Stalistics, pp. 3170-2178. PMLR, March 2021.
Qihang Lin, Runchao Ma, and Yangyang Xu. Complexity of an inexact proximal-point penalty method for constrained smooth non-convex optimization. Computational Optimization and Applications, 82((): 175-224, May 2022.
Wei Liu, Xin Liu, and Xiaojun Chen. An Incxact Augmented Lagrangian Algorithm for Training Leaky ReLU Neural Network with Group Sparsity. Journal of Machine Learning Research, 24(212):1 43, 2023.
Songtao Lu. A Single-Loop Gradient Descent and Perturbed Ascent Algorithm for Nonconvex Functional Constrained Optimization. In Proceedings of the 39th International Conference on Machine Learning, pp. 14315-14357. PMLR, June 2022.
Javier Luque. The nonlinear poximal point algorithm and multiplier methods, 1986.
Javier Luque A nonlinear proximal point algorithm. In 26th IEEE Conference on Decision and Control, volume 26, pp. 316-817, December 1987.
Yura Malitsky and Konstantin Mishchenko. Adaptive Gradient Descent without Descent. In Proceedings of the 37th International Conference on Machine Learning, pp. 6702-6712. PMLR, November 2020.
Dustin G. Mixon, Soledad Villar, and Rachel Ward. Clustering subgaussian mixtures by semidefinite pro- gramming, May 2016.
Valentin Nedeleu, Ion Necoara, and Quoe Tran-Dinh. Computational Complexity of Inexact Gradient Aug- mented Lagrangian Methods: Application to Constrained MPC. SIAM Journal on Control and Optimiza- -1333343,,,,,
lion, 52(55:3109 3134, January 2014.
15

---

Published in Transactions on Machine Learning Research (10/2025)
Yurii Nesterov. Universal gradient methods for convex optimization problems. Mathematical Programming. 152(():381-404, August 2015.
Yurii Nesterov. Inxaact accelerated high-order proximal-pee point methods. Mathematical Programming, 197
1-26, January 2023.
Jerzy Neyman, Egon Sharpe Pearson, and Karl Pearson. IX. On the problem of the most efficient. tests of statistical hypotheses. Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of Mathematical or Physical Character, (21664606):28--338873 337, January 1997.
Konstantinos Oikonomidis, Emanuel Laude, Puya Latafat, Andreas Themelis, and Panagiotis Patrinos. Adaptive Proximal Gradient Methods Are Universal Without Approximation. In Proceedinggs of the 4 4sst International Conference on Machine Learning, pp. 18663-38653 PMLR, July 2024a.
Konstantinos A. Oikonomidis, Alexander Bodard, Emanuel Laude, and Panagiotis Patrinos. Global Conver- gence Analysis of the Power Proximal Point and Augmented Lagrangian Method, July 2024b.
Michael JD Powell. A method for nonlinear constraints in minimization problems. Academic Press, pp. 283-298, 1969.
R. Tyrell Rockafellar. Augmented Lagrangians and Applications of the Proximal Point Algorithm in Convex Programming. Mathematics of Operutions Research, 1(2):97 116, 1976.
Ralph Tyrell Rockafellar. Convex Analysis: (PMS-28). In Conver Analysis. Princcton University Press, 1970.
Ralph Tyrell Rockafellar. Augmented Lagrangians and hidden convexity in sufficient conditions for local optimality. Mathematical Programming, 198(1):159-194) March 2023.
Ralph Tyrell Rockafellar and Roger J. Wets. Varialional Analysis, volume 317 of Grundlehren der mathematischen Wissenschaften. Springer, Berlin, Heidelberg. 1998.
Ralph Tyrrell Rockafellar. Lagrange multipliers and optimality. SIAM Review, 35(2):183-25) -28,, 1993.
Anton Rodomanov and Yurii Nesterov. Smoothness Parameter of Power of Euclidean Norm. Journal of Optimization Theory and Applications, 185(2):303 326, May 2020.
Mehmet Fatih Sahin, Armin Eftekhari, Ahmee Alacaoglu, Fabian Latorre, and Volkan Cevher. An Inexact Augmented Lagrangian Framework for Nonconvex Optimization with Nonlincar Constraints. In Advances in Neural Information Processing Systems, volume 32, 2019.
Sara Sangalli, Ertunc Erdil, Andcas Hötker, Olivio Donati, and Endor Konukoglu. Constrained Optimization Train Neural Networks on Critical and Repre--ee Classes. Advances Neural Information Processing Systems, volume 34, pp. 25400 20412, 2021.
Mariano Tepper, Anirvan M. Sengupta, and Dmitri Chklovskii. Clustering is semidefinitely not that hard: Nonnegative SDP for manifold disentangling. Journal of Machine Learning Research, 19(82):1-30, 2018.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-MNIST: Novel Image Dataset for Benchmarking Machine Learning Algorithms, September 2017.
Yangyang Xu. Iteration complexity of inexact augmented Lagrangian methods for constrained convex pro- gramming. Mathematical Programming, 185(1-2):199 244, Jamuary 2021.
Qing Zhao, Stefan E. Karisch, Franz Rendl, and Henry Wolkowicz. Semidefinite Programming Relaxations for the Quadratic Assignment Problem. Journal of Combinatorial Optimization, 2(1):71-109, March 1998.
16

---

Published in Transactions on Machine Learning Research (10/2025)
A Proofs
A.1 Proofs of section 2
Proof of Lemma I
Proof. By consocutively using the multiplier update (step 4 update rule (step 3) we obtain that
the triangle inequality, and the dual step size
1ly
11
1¹ o,A(x') ((AZ))(((()
$ 11y +
0. 0.1l (>>')l
||A(**) || (log
s 11 + Σ
i (log(i + 1))²
lly + co |1(x)))) (log 2) =: Ymax:
where c= -i (1og1(++1) < 00.
Proof of Lemma 2
We first establish the following lemma.
Lemma 6. Let {a JeEN, ty" JAEN, (8* be generated by Algorithm 1
Then for any a E dom g and k 2 1,
L (a) S L (x)
Proof. From the definition of the augmented Lagrangian, the multiplier update and the penalty parameter update with w we have for k 2
Li (x) p(x)) + (A(x), + 3x+1 ||A(x))
x(x) + (A(x), /²) + +0+))|A(=)) + w BK |1(()))
2
2 p(x) + (A(x), 2/ + 3g [A(
2
(x).
It follows immediately that
C ( C L (x:).
We now provide proof for Lemma 2
Proof. The nonemptyness claim follows from the observation that Lz)( always holds by definition of the sublevel set. For the compactness claim, recall that the augmented Lagrangian can be expressed
Lo(x, y) = x(x) + (A(x), y) + à [A())] By (Rockafellar & Wets 1998. Corollary 3.27), it suffices to establish level-coercivity of Lg(2,0) y) with respect to the primal variable. sufficient condition for this is that tp is level-coercive, as guaranteed by Assumption 3 and that x + (A(x), v) + 1 Azx)ll is bounded below (Rockafellar Wets 1998 Excrcise 3.29 (b)). Note that ()(x).)) + 3 [I[A(=)))* 2 [|A())]] +
g [[x))))]++1 If [| < Illl the claimed boundedness follows from the fact that
(A(x).)) v) + 3 [(
2- 1-32(11) [vvl || + [ [1 > 2 (2 ||vll-
17

---

Published in Transactions on Machine Learning Research (10/2025)
Else ||A(z)]l*> 3 Illll, and hence
82 -I[A())] 2,3 |
(A(z), 2 [())))+++
which also implies the claimed boundedness.
We now show Lemma 2(1) by induction. First, observe that the assumption Log (2tt2, Lin (xt,
implies for k 2 that
C (x (x=+t) S Cau
(15)
The base case k = follows by consecutively applying Lemma and 15 i.c.,
C (x S CB..s (x²) S L (x)))
Suppose that Lemma 2(i) holds for some l 2 1. Then by Lemma we have
L 11 (x 1 C L (x 11 S Lan (x*),
where again we applied Lemma and
15
This establishes Lemma 2(1)
Finally, Lemma 2ii follows by consecutive application of Lemma 2(i and by compactness of La (x²). 7
Proof of Theorem
Proof. We first prove the claimed rate of EA := 2a, and then that of Ep,4+1 == Bx
Qr
From Algorithm
0
step 2 we have that
dist dist(-Vzziae (x++ )g(((())))) S Ek+1, Ak 2 0.
(16)
By definition of the we therefore have that Wk: 2 0
dist - f(a(t) - JI (x***1))) > BaJ (o( ag((tt)))) & Ex+1
which yields, after application of the triangle inequality,
dist(-Be.J] (1 Vo(())))((())))))))))))) ag(()))(()))) s IIV + [JJ (xx+1)) E8411-
(17)
By (Rockafellar 1970 Theorem 25.6) it follows that for all x E R",
dg(x) cl(conv S(x)) Ndom
where S(z) is the set of all limits of sequences of the form Vg(z1), Vg(az),.. such that is differentiable at Iy and i; - x, and cl(conv S(z)) is the closure of the convex hull of S(x). By Assumption the function G-Lipschitz contimuos on S, and therefore any u E cl(conv S(x)) satisfies |||||| s G.
By again applying the triangle incquality
17 we obtain
dist(-Ba (a *+1 Vo(A(==++)))) Naom (1))
IV +
I|| G (1
ex+1-
Since Vo(A(a*+1)) ||A(x*+1) u-- A(x we can further lower bound the lh..s. of the previous inequality. We have that dist(az, Naom o (x (I)) N (2) Jaz - 2|| = minge
Naom m (rk1 || &ll for a > 0
and thus since Ndom (2++1) is a cone, using Assumption we obtain
[Vf(2 + || ( +e++1
3x 3.11A (|) dist(-J] (x=
Naom & (z)+1))
R/3 A(t *
Therefore, have the following inequality
||(
|V
+ G [| (x+ Ex+11
Ex+1
(18)
R.
18

---

Published in Transactions on Machine Learning Research (10/2025)
By Lemma 1 we have that | I Umax for all & 2 0. Thus, the constraint violation is upper bounded by
V max + G + JAmaxUmax + Ek+1 1/v
||
(19)
R,3
where we have used the Sauchy-Schward inequality. The claim regarding 8,,4+1 now follows from the fact that ck+1 S Ek. Now for Ep, we have by the triangle inequality that
dist(- Uh (I k-1 1, )g(x*+1))
S dist (eet(-V/a V 1hs t )²),, og(x + VV (a--1 ,htt) V (I .
The first term of the r.h.s. upper bounded by Ek+1 due to Algorithm step i.c., Dist(-Vzzl (x .v"). (gg(x++1) S Ext1
and for the second lerm we have that
[V (x*+1 + Vathe (x (t bz7) = ||J] (2*tt) r²) S J Jmmaxlly t 8²1l
= JAmax Th+1 1 A|
Therefore, in combination with 18 we obtain
dist(-Ve VV (x y x+1, (g() s Ek+1 + T V max + G Amaaxhuax Ek+1
R3g
Thus, since σk S 01, Ek-1 S Ek and Ek41 A/3 we conclude that x+1 is (EpAtti with
multiplier yh+1 + B8 Vo (1))
Proof of Lemma 3
Proof. Since the gradient of the with respect to its first argument, evaluated at (x, (), is given by
VaVa(a, = v/(=)+
+ JI()y (J
(20)
it follows for x, x' S that
(e -
< (/) JA())) llll
+
(21)
Using Assumption [ and Lemma I
the first two terms are bounded by
-
& Hy |z' - =11"1,
(22)
[|Ja(z') - Ja(I) |bll| & Hallyll -1 - -
(23)
As for the third term in 21 we have that
-
< A||A(>')|I +20 VO(A(T))
s 1I= -2| + AJ / - Vo(A(=))
(24)
where we have used consecutively the triangle inequality, the fact that [Vo(A(z)) = A(('')|,, Assump- tion and the boundedness of ||JA|l on S. light of (Rodomanov & Nestcrov 2020 function (2--v Hööder smooth. Hence, follows that.
Theorem 6.3), the
Vo(A(>))) Vo(A(>)) < 2'-11AA(2)) A(x))l" < 21-"JA" x11"
19

---

Published in Transactions on Machine Learning Research (10/2025)
where in the last inequality we also used the Lipschitz continuity of A on S. Putting this back into obtain
24 we
V JI (+)((((()) A ||' xr| 30|| s 2 33 ntxx 1| x11"
(25)
Finally, the claim follows by summing the previous incqualitics and using the fact that
||'' - = = || - =|| || =/1 v D - =|I I max {1, D'- [] | 1=11
||a' - x æ|| = ||aa - ==1 || 2215 I D 0||2 =||$ max {1, (1, 8) | ==10
||a' z = =1|æ' - =11" ||=' z|1" I " z|| I max (1, [1, ||= ==1%.
Proof of Lemma 4
Proof- We first remark that UPFAG monotonically decreases the objective, and hence by Lemma 2 the iterates remain in compact set. Let { Jee
jie and {xE") be the sequences of iterates generated by the Algorithm 2) when applied to th. Let {%hken be the
UPFAG method described in (Ghadimi et al. 2019
sequence of stepsizes defined in (Ghadimi et al. 2019 Equation (3.6)). Then in light of GGaadimi et al.
2019. Equation (3.33)), after discarding some constants, we need O H Lx(a LA ag
inner iterations Equation (3.8) we
to obtain point | have that
11/7 I
Ek+1 2 Now, note that from Ghadimi et al. 2019
98 2
arg min (ex( + g(u) + "ER"
1 2x,
|u
ag x
1|2
and from the optimality conditions for this minimization problem (Rockafellar & Wets 1998
Theorem 6.12):
-Vén(ofE 34 (2 -x 20 E 0g(x;55
By adding and subtracting (T,*s we further have:
-1 + (ex(a,") - (x 1 (I
x E 0g(x,") ax)
Therefore, incquality
V (. Veb(( 1 (Z..8 2 1),,), 0g(و,²6) = and from the triangle
(,, ,,, < [+,55 - Vehaa (2 4g )ll +
ag 2
S Ha 1| - 1l + E1ut1
2 Hg,
E441 2
24
where in the third inequality we used the bound || - - ll/ S 2 and the Hölder continuity of Velk. (1-41/0
Lemma 3 Therefore, by choosing S (21- we obtain the claimed result.
Proof of Theorem
Proof. Remark that by Lemma 2 the iterates remain in compact set. Let us start by defining the first power ALM (outer) iteration KA for which
$ ==
V Max +G+ A +&
QA
EA EAKAt1
(26)
RAKa
3K
or, equivalently, for which 3K, 2 Qa. Since KA is the smallest iteration index for which this holds and Ba
5x
is increasing, it follows that 3KA-1 < Lg. It follows from
[A(*Ka+1)]) [/mex + G + JAmax +
(27)
RIKa
20

---

Published in Transactions on Machine Learning Research (10/2025)
that also ελ 2 ||(x=***])))) holds. From the update rule for Bk we have that
w Kx
<
1 84
QA 31
4AA
(28)
After taking the logarithm of both sides, we obtain that
QA1 EaA
KA =
log
+
(29)
Now, the number of total UPFAG iterations needed to obtain point x K satisfying (27 is upper bounded by the sum of the calls to UPFAG for all outer (power ALM) iterations. Note that since Br is increasing geometrically, the Hölder smoothness modulus defined in Lemma 3 is determined by it for large enough k. Therefore, in light of Lemma we require at most TA UPFAG iterations, where
Ka Σo TA
[x(a*) L
144
o H
|
Ex+1
1t3
=0
K KAOkk 31/3//
[Do+1
Bxxl
114 24
0
KA
(w (WAA) 2/9
Do+1
w
QA E
37
4/9 EAA
Qx K^
QA*
3
0.33x KAQA 1
D
(+
D
u/q
1+4
3w(l+t) E
E
where the first equality follows by Lemma and by the fact that ek+1 = 2/33. The second equality follows by unrolling the sum and the first inequality by the fact that Gr wB
Qs
Thus, we obtain
Ex
Ta 0
log.
L'1
5+33 24
D
g) 20
δ
Q
(1=2²
24
Bw1l+9)
3w(1+g)
A
E
Regarding the suboptimality tolerance, we can in similar way define the first power ALM (outer) iteration K.p for which
1 ( J JA v V max + G + J Ammax Vmax E1 EΦ 2 kp,K, 3K,
Qf
(30)
R
3Kg
or, equivalently, 3x 2 L1 Since K₂ is the first iteration for which this holds, it follows that BK,-1 1 From the update rule for Br we have that
Q1
Eo.
E
1 Qr
0
Ko-2 <
=
(31)
Exp
B1
Epp
After taking the logarithm on both sides, we obtain
2'
K₂ = log.
+ +
(32)
Exp
21

---

Published in Transactions on Machine Learning Research (10/2025)
Hence, require at most T UPFAG iterations to obtain point x xx+1 satisfying 30
where
K Σo
Libe
K
Tp = 0
Lx(x")
Li
24
Σ 0
8//9
[Da+t
[k]
2
Ek+1
k=1
k=1
0
Kp
Dat
1t
0
Q
Da+
Q1
37
1/9 E44
Epp
Q// 1/9
[a+1)
3(yt 2q
K
5t-3u by 29
D
(1+a)2
29
K
D
1/4 Eig
Mig+1) 2g
5433
Ep
Ei" 24
and the sequence of bounds follows from similar arguments as for TA. Thus, we obtain
logw
9'
D
(1+a)² 29
Q
S+
24
2
Tp 0
Exp
Ô
f
513
E
E
A.2 Proofs of section 3
Proof of Lemma 5
Proof. The function f is Ly-weakly convex, since it is Ly-Lisschitz smooth, ie. for any I, e X the
following inoquality holds:
f(x) (V x-) -')- by 12 a'112
(Vf(x),
(33)
Moreover, following the proof of (Drusvyatskiy & Paquette and y E Rm that
2019 Lemma 4.2), have for any x, xf E X
A(x)) = (v, A(x)) + (y. A(x') - A(x))
2 (v. A(x)) + (y. (z) - -x)) Lallull | - x01
(v. A(r)) + (x)(, (x' -x)) LAIlul| || - x12
(34)
2
where the inequality follows from the Lipschite-continuiity of JA, i.e., from the fact that ||A(x') - A(x) (a(x)(=' - =>)l= I LAll z112. Likewise, for any 2, E X we have that
Bo(A(x)) 2 3O(ALE))+ -
(V(A4))) x()) ( 2
||
2'112
-x') AL
max
2'112
x
(35)
by consocutively exploiting convexity of & between points A(x) and A(x'). Lipsciitzsmmothness of A and the fact that []V](A())) = [[(())]I* < A Summing up 33 (34 and 35
we obtain:
(z (z' 3) + (VzLo(x', v) x²) I. Allll
4 || 2'1
These observations directly imply that for any y E R. the augmented Lagrangian is p-weakly convex on X in its first argument, with
p := Lg + Lalllll + B.
22

---

Published in Transactions on Machine Learning Research (10/2025)
Proof of Theorem 3
The proof requires the following series of lemmata. Note that F is defined in Algorithm 2 (Hr, HHöller smooth and p-strongly convex function.
step
and is
Lemma 7. Let E X and define the point xt = arg min (VF(x), u x)) + 2 x with
Hp 149
s <> 0. Then,
+ x=12 S F(x) F(x H
(36)
Proof. The inner problom in the definition of x+ is --strongly convex and as such for any u E X' we obtain
(VF(x), - -x) + 2 +1x - x|I2 S (VF(r), x u) + 2 || ul1² 27 11xx ull?
By choosing x E d' get
0 (VF(2), x 22) + + - x=|2
(37)
In light of Young's incquality we have for any a, b 2 that ab S a² + 6r2
with +
Choosing
Pi = T4u Tou. P2 = T it follows for = = -
1 that
| x1| v ي tre | 2=|2
-
(38)
Note that for v = the inequality becomes an equality and thus the case v = 1 is also covered. Therefore, from the Hölder smoothness incquality for F between points n, x+ X we get:
F(x*)= < - (VF())((F())))))) x) +
Hr u+I
1| - x1|
S F(x) (VF(x,, x) + HF E 1 |xx - 221 +
1-v Hy 142 2
(39)
Substituting 39 in 37
obtain:
0 F(x))) + b/ 11x - -x|12
1- HE It 2
which proves the claim.
Lemma Suppose that a point x E satisfies F(x) FF(x)) S E for some 0. Let y Hr e 1+v
and
x+ = arg min (V((x), x) + 2 I|u - x/|2 Then, |10-- 77 < 2HHr(1 + #o.
Proof. From Lemma and F(x) F(x+) < F(x) - F(x*) S E it follows that
x
1|
( c
HF
(40)
72
7
2
2H pp 1
HF
(41)
2
Therefore, we obtain
1x
x||2
< 22 + H..
2
Lemma Suppose that point x E X salisfies F(x) F(x*) S e for some 0. Let 7 Hr
1 e tt and
b = arg min (VF(x), u- x) + 27
1 -|| - x0|2. Then,
Aist(vF((*t) Nx(x+)) < (H2 + HF)) + (2H+(1 + Hr)) e
23

---

Published in Transactions on Machine Learning Research (10/2025)
Proof. By the optimality conditions of the inner minimization in x arg min (VF(z), u u- 1//1/==11 we have that
- E
which implics that
VF(x*)+ + - -
- - E (x(x)))
Observe that from the triangle inequality and the Hölder smoothness of F, we have
[VF(x*)) VF(x) - - -1)ll
HF 1= xl|" + + x2ll
(42)
and by Lemma we can further bound
Hallæ* x²I" + 111x0 - x|| $ 7" HF | =xl|" + 11120 - x||
= = HF (2Hp(1 HF)) v किक
+ (1 HF
)e IIv
Hr (2H HP)) (2Hr(1 + 22
HE
Hr)) $ + (2H Hr))
The result then follows by the fact that (F))) s dist(VF((t)) VF(x) + 2). Nx(x)) = - - (x x)|l
Proof. Consider a point x E such that
Hi
F(x) - F(x)) =::= H
Then, it follows from Lemma 9 that for
1
@T 1F
1-n
11 g the point x+ satisfies
Hp
Nx(x+)) S HET =6.
Thus, in light of (Devolder et al. 2014 $6.2 ), it takes at most T iterations of the FGM, and single proximal-gee gexainal-rrddeett step with stepsize to find such a point xt, where
7 T
P
1+.30
I-m
(43)
33441
F
143u
H
E
14
1430
(44)
9+1
1T
H 3T
H
14u 1-v
v
1430
14t
17
(45)
sil
p3r41
Proof of Theorem 4
Proof. Let Fs(x) == (xx)) + p|/x - 11 Since ab is p-wcakly convex and has (H, H-Höldr continuous
gradients, it follows that F₂ is p-strongly convex and has (HF, -Hölder continuous gradients on X, with Hr + p mmxx D1-)..
We can now trace the steps of (Li et al. most
2021
Theorem 1) to conclude that Algorithm 2 terminates after
32p
T
(w(x') - -b)) + +1] 2
24

---

Published in Transactions on Machine Learning Research (10/2025)
iterations and that the output satisfies vist(-Vv(z), S
Denote henceforth F = minsex Fx(x). By Algorithm 2 step 3 and (Rockafellar & Wets 1998 Theorem 10.1) we have that d0st(0, of Fk and convexity of 5x we have that
= V +1) (x S j. and by p-strong convexity
x² - chtl Gllo0tt - x²1 - g E O(F + (x F (x + (oM+1 ,,"
Combining these two inequalities yields Fa(xhtl)- - Fb v 1² - (x**)*
d² and hence we obtain tb(thtt + plla
32p
< o² Thus,
32p
T | 2 2 S (T -1)
E²
((*") - (xxx)()))))))))) +
32p
1
E²
(T 1) min
|| 2
(T 1)
+ [+(x*)
+xx
IskST
p
32p
E²
P p(((x²) 1
2p min 15kST-1
|
x111 5 21
32
T-1
For 1- (v((*)) x²*) this yields
2p min 11 - xx1| ISKST
8 2
meaning that Algorithm
2 must have terminated. Demote by xF the iterate returned by Algorithm 2 upon a/B and dist(0, ((00,0((F-:))) 8x) (x²)) S E, conclude that
termination. Since 2p|lat x² --1 <
dist(0, 0 + 6x ()) v Diit(0.,((Fr-..) 5x )x(x²))) 2p|2= - -11-11 Se. SE.
This concludes the proof, since 0 + 5x)() +
Proof of Theorem
Proof. We denote the t-th iterate Algorithm (iPPM) within the k-th power ALM outer itcration by =t. Al ut, Nesterov's FGM is used to minimize Fi = L,,, x*) + -=/11= which pe-strongly convex
and H))-Heerr smooth with HF. = H4 + ph max 1, D r). In light of Theorem 3 we require most T. iterations to find 5k+1 stationary point of F 5x, with
H
142
14 1-P ExT
PGG =
H
1938
1F36
(46)
Pk
where H₁ HH- (1+H+))) +2HH,, +
1/2 Remark that T.GM is independent of t. Since
Pk = 0(3k), Hr. = (3x), H. O(3e), this expression simplifies to
T.GM =ō
3
FFFF (1+
E E++1
1730
Likewise, at 2. the iPPM is used minimize Lg, (s. y*), which Ak-weakly convex. By Theorem we
require most PPM iterations of Algorithm 2 find a point satisfying the update rule of step Algorithm 1 where
2
32pp (vx(( - +h) + +1]
T TPPM
(47)
2-1
25

---

Published in Transactions on Machine Learning Research (10/2025)
From 18 we have that ||A( =
(Vimus +G+ + AmexNmasst E&A R
for all & 2 1 and using 3x. w we obtain
Bx BxllA(="11'' Sw Vmma + AmaxXuna + Ek
(48)
R
and hence we oblain the following bound for k 2 2:
BR
vx(x*)) - f(x²) + (w, A(x*))
1 1+ |A(x*))|
V max G + J. A Umax Ex ||A(**)]|
S fmax + Vmax ||(x))
+ 1+v
V Vimax + G Jmaxxfmux +
S fmax + Ymax
R
Vf + G AmaxUmax + ck
V max G + J AmaxUmax + ok $
1+v v
R
R
S Smax + Imax + Vmnux G + J AmaxHlax + 81
R331
w
mm + JmaaxUmux + Ei
(V + + JAmaxVmax + E1 C.
1-v
R
R31
The first inequality follows by being continuous the compact set X, f(**)* I max f(z) == fmaxs and
48h and the second one by 19 The last inequality follows by < <1 and Br > B1. Moreover, we have for
all x E X
(x) 2 ((x) + (g) A(x)) 2 -fmax Umax Amax
and such we can bound
(1<(**) w S C fmax + Munx Amax-
Using this expression and Lemma
5 can rewrite the number of iPPM iterations
Bk
T
TPPM Ō
6
We now define the first power ALM (outer) iteration KA for which
V max + G + A Umnx t
QA
EA EAKA++1
(49)
R3KA
1/v
РKa
and from we have that.
Q'
KA
log.
2.
Hence, we require at most TA total FGM iterations to obtain a point x KAt1 where
TA
T
T.P PPPM FGM
KA
Ka
g
1-
140
142 I-v
1+ 1-
(1+ (1+))))
142 1-P
1430
3
3
1430
Ex+1
b+1
R=
Ka
3+ 11a0
(1+2 +
(1+2
k=1
2ō
K KABKa
Ka
3+ 3 (1+2
1
1-2 (1+2
26

---

Published in Transactions on Machine Learning Research (10/2025)
By substitution of 3K. WBKA-1 Qa this yields
Ta δ (6(e) 33 1430 (3ert2) (80))
E
In similar way to the proof of Theorem
we can define the first power ALM (outer) iteration K₂ for which
1
^ J. Amax 01
max + Amaxxlma + +ēI
= Q1
Eg 2 Ep
3Kp
R
3x,
and obtain
Q
K
log
+
Exp
Tp = Ö -
(5
1 1-2
T- 11+242
By substitution of 3K, wBK,-1 <
Qr this yields
2p
Tp Ō (
-3- 1-0 1450
(1+ )
Ex
Proof of Theorem 6
Proof. We denote the t-th iterate of Algorithm (iPPM) within the k-th power ALM outer iteration by zt. At zt, Nesterov's FGM is used to minimize F La, (,,8)) + -of.1=2..1f which is Px-strongly convex
smooth with HF. H2 Ps max 1, D DI-). In light of Theorem 3 require at most fb+1 T FGM iterations to find an 4 stationary point of F 5x, with
and
1430
TPGM =
FL
H
s441
(50)
1436
Pk
( r2 (1+ 1/22) Remark that T.FGM is independent of t. Since Pk 0(),, Hr. 0(3)), = 03x,, this expression simplifies
where HA = H2H (1 HF,))
T FGM = =Ō 1
E Ex+1
Likewise, at 2 the iPPM is used to minimize La (s,"r) which is Ps-weakly convex. By Theorem we require at most T TPPPM iterations Algorithm to find a point satisfying the update rule step in Algorithm 1 where
32pp (xbx(x** - +b) + +1
TPPM
(51)
Following the same steps in the proof of Theorem
bound for C 0,
vhe(x*)) 3 S C + fmax + Vmnax Amax-
Using this expression and Pk = O()) (cf. Lemma we can rewrite the number of iPPM itcrations as
TPPM Ō (Ext1)
27

---

Published in Transactions on Machine Learning Research (10/2025)
We now define the first power ALM (outer) iteration KA for which
2/2
V Vmmax max + Jmmaxmmax + +E1
QA
EA EA,KA+1
(52)
1/u
KA
and from 29 we have that
4'1
AA
log
+
E'A
Hence, we require most TA total FGM iterations to obtain a point Kat1 where
Ka
Ta
T
PPMMTGM
K
Ka
Lle
1e
11
11
E k+
-2
IT x
1836 Ex41
173r
8
3
30
113
0
1130
k=1
k=1
1-v 1+u 1730
Σ
k=1
2421+30 Hle
1-30 11
<ō
KARKa
=
KK
1430
By substitution of 3K. = WBKA-1 < Q+ this yields
Ta = δ S
2v (1-
1:
In similar way the proof of Theorem 2 we can define the first power ALM (outer) iteration K₁ for which
1
v max + JAmaxPmax t1
Qf
Eg Epp
a JAmax
3K,
3Kg
and obtain
Q' Exp
Kg =
logw
+
T. = Ō
-
2222 I- 14
1:
1730
By substitution of 3K, = wBk,-1 <
21 this yields
8,
T. = Ō
2 22
2- 1- 14 1230
Ex
28

---

Published in Transactions on Machine Learning Research (10/2025)
B Additional experiments
B.1 Generalized eigenvalue problem
We consider the generalized cigenvalue problem (GEVP)
min T Cr s.t. x Bx = ZER
where B, C' E R=x" are symmetric matrices and B is positive definite. Clearly, the GEVP is the form and satisfies the regularity condition Assumption Sahin et al. (2019). We sample the entries of a matrix Ō E [R" from a Gaussian (0, 0.1) and define = [CC The matrix is defined as QTQ, where Q is the orthonormal matrix in the QR-decomposition of a random matrix with entries sampled uniformly from the unit interval. We use the classical accelcrated proximal gradient method (APGM) by Book Teboulle (2009) an inner solver and tune its step size 0.5/(10||C]] 5000 + 5003). Although APGM has no convergence guarantees that fully cover setting, i.e., nonconvex and Hölder-smooth objectives, it appears that convergence issues can be mitigated by sufficiently decreasing the step size. We follow the tuning of Li et al. (2021) $1 0.01, = 3, = 0, 10, and impose maximum of N = 10 APGM iterations per subproblem.
Table reports the number of gradient calls that power ALM requires to attain an (Ep: E --statioonayy point with Ey = SA = 10-3 for various powers a E (0, 1]. Also the constraint violation ||(())] and the suboptimality [f(x) - f* are listed. Every trial denotes random realization of the GEVP with 500, and the first trial is further illustrated in Figure We observe that smaller values of v perform significantly better than larger values, with 0.4 requiring order of magnitude fewer gradient evaluations than 1.
The figure corresponding to the first realization confirms that both constraint violation and suboptimality decrease steadily, even for a small power v = 0.4.
10F
10
US
0.6
Gradinnts
MMc1
0.4
10-1
10-4
20-22
20
10
30-4
0.2
0.5
0.4
0..5
1..6
0.7
0.8
0.9
Gradients
Gradiente
20
(a) Constraint violation.
(b) Suboptinality.
(c) # gradients, Exp
10
Figure 4: Comparison of the proposed power ALM with various powers solving representative GEVP with = 500. The case v corresponds to the iALM from Sahin et al. (2019)
Table 4: Performance power ALM with APGM inner solver on solving random GEVPs of size n 500.
B.6. 20-4
2.1
----
2.4 10-4
30.908
2.8 10-4
4.6 10-1
70,000
5.7 10
8.0. 10-4
2.5 107
2,5 10-4
4.5. 10-4
3.8 10P
1.6-
2.5- 10-4
1-10P
8-10-1
4- 10
$1.540
3.1 10-1
4.9-10 10-1
1- 100
6.2- 10
9.00
2.5 117
5- 10
4.6- 10
6.1
2.3
10-4
307
3.9
9.1
2.5
4.5-
1.7
20-4
1-10F
1-10-
3.2 10
25.301
3.1 10
45 10
$8.925
6.2 30
9.66 10
2,5 10
3: 10
4.5- 10-
6.2 10F
1.9-
2.9
1-10"
111
7-
35,529
3.2 10
5.1-10
1.6 10
1.7-
9.9-
32-
6.8
108
5-10-4
1:5 10
2.8-1004 10m
1-10P
1-10-4
10--
33:362
3.1 10-4
10-
10P
0.2: 10
9.5- 10-4
S-10#
10
4.6- 10-4
6.5-10
- 00
20--10-4
1-
47 10-1
6.7- 10->
1.3 10P
3.1 10
57 10-1
2.3 -07
0.1 10
9.5- 16-1
4.4-10"
29-10- 10-4
4.6- 6.6-1--
7.8 10P
8U6-
2-10P
25.407
80,230
10
27--10"
wng:
102
107
644-10
29

---

Published in Transactions on Machine Learning Research (10/2025)
C
Inner solvers
For completeness, this section summarizes the universal pebblem-parameter free accelerated gradient method Ghadimi et al. 2019. Algorithm 1) method and the fast gradient method (Devolder et al. 2014 Algorithm
3), which are, respectively, used as inner solvers sections and
First, we consider the ALM subproblem in Algorithm Line which are of the form
minimize v (x) = (x) + g(x). SER
(53)
Here, & 1²" is Hölder-smooth and g R R is convex. Algorithm specifies the UPFAG method Algorithm 1) for problems of the form (53)
Ghadimi al. 2019
Algorithm Unified problem-parameter free accelerated gradient (UPFAG) method (Ghadimi et al. 2019)
Require: zo E R", 71, 72, 73 E (0, 1), accuracy parameter 5 > 0.
1: Set 20 = To, and Ag = 0. for k = 1, 2.... do Choose initial stepsize d > 0 and find the smallest integer Ti 2 such that with
The
Tk v 1h
+
47
Ax-1
b and
As
Σ A
2
A
the solutions obtained by
md
(1 ax + --
k
Ik prox (Ik-1 d (e((x))))
k (1 ax axx=2k az + ax.tt
satisfy the condition
( < (x( oa (Vbb(x (f ), xk-1)
Oi 2
|| Fk-1 + 8oa.
Choose initial stepsize 3x > 0 and find the smallest integer T2 2 0 such that with
3x = Bu Th.t and ,h = prox Big (2 Bx ( (x)=1))
satisfy the condition
V ((
(1
2,3g
k
5: Choose z such that
V(xft) min (M= ). (x
1 (2))))
end for
Second, consider the proximal point updates in hm 2 Line 2 which are of the form
minimize Fxx). x
14 rev.)
Here, F Rd IR is set X' C R" closed and convex. Algorithm 4 specializes (Devolder al. 2014 Algorithm 3) problems
and p-strongly convex with H, 2 0, > and v E (0, 1]. The
of the form [14h for the standard Euclidean prox-function.
30

---

Published in Transactions on Machine Learning Research (10/2025)
Algorithm 4 Fast gradient method for strongly convex, Hölder smooth functions (Devolder et al 2014)
Require: zg X accuracy parameter O, constants p> 0, H3 2 0, v E (0. 1].
1: Sct = and = f
H 1-E 25
and let far be such that ag = and L + Ei
== a; = Lo
1+t
E.5
for k 0, ..... do
yk arg x (VF ; x mK) + -11l 1x
2k arg min x zull? Σx=o as (v:( x mz) + 211 2:11?1
Fk+1 Th2k + Tk Tx)8k where т Σts
end for
Note that the first step is standard projected gradient update y ( - VF(())) whereas the second step can be written as
Lao + 1 Eimo 0,34 Ei a VF(x;))
- projx
L μt 21 ai
We highlight that per iteration Algorithm only requires a single gradient evaluation of F (at TR), and two projections onto X.
31


Reviews:
[{"review_id": "hGVGx6REVU", "reviewer": "Reviewer_hcPb", "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 considers nonconvex optimization with nonlinear constraints and a potentially sharper penalty function. The authors first propose a novel inexact augmented Lagrangian method for such problem, followed by a novel inexact proximal point method for solving the inner problems. The paper provides a detailed complexity analysis for the proposed methods and validates the empirical performance of unconventional augmenting terms.", "claims_and_evidence_yn": "Yes", "claims_explanation": "I do not check the proofs in the appendix, but the theoretical results seem reasonable and solid. The complexity of Algorithm 1 matches the one from Sahin et al. (2019) in the Lipschitz smooth setting. If the inner subproblem is solve by Algorithm 2, the authors show that the total complexity nearly matches the complexity result in (Li et al., 2021).", "audience_yn": "Yes", "audience_explanation": "Nonconvex minimization problem with nonlinear constraints is an important problem in the fields of optimization and machine learning. Researchers in optimization area, in particular, will likely be interested in the findings of this paper.", "requested_changes": "1. To enhance the self-containment of the paper, I recommend that the authors include the UPFAG and FGM algorithms in the appendix.\n2. Follow the previous point, I think the paper should provide the complexity of first-order oracle instead of the complexity of the iterations of the UPFAG and FGM algorithms. Readers may not be aware of how many first-order oracle calls occur in a single iteration of these algorithms.\n3. It seems that the paper does not provide a definition for lsc functions. Some readers may not be familiar with this concept, so it would be beneficial to include a brief explanation.\n4. The paper may discuss whether Algorithm 1 can finds a second-order stationary point if a second-order solver is used for the inner iterates.", "broader_impact_concerns": "No broader impact concerns", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "kjwkmG8ZPK", "reviewer": "Reviewer_ewE5", "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 an inexact power augmented Lagrangian method (iALM) for solving constrained nonconvex optimization problems with nonlinear equality constraints $ A(x) = 0 $. The method extends the classical augmented Lagrangian by introducing a penalty term of the form $ ||A(x)||^{1+\\nu} $ with $ \\nu \\in (0, 1] $. When $ \\nu = 1 $, the approach naturally reduces to the classical augmented Lagrangian method. This generalization offers a novel trade-off between primal and dual residual tolerances, providing additional flexibility in balancing constraint satisfaction and suboptimality reduction.\n\nThe proposed iALM achieves linear convergence in the number of outer iterations to a stationary point, while the constraint violation decreases at a faster rate when $ \\nu < 1 $.  For problems where $ \\nabla f $ and $ A $ are locally Hölder continuous, the subproblems are solved using the existing UPFAG algorithm. This recovers the state-of-the-art complexity result of $ \\tilde{\\mathcal{O}}(\\epsilon^{-4}) $ for the overall method.\n\nAdditionally, under a stronger constraint qualification, the paper introduces a new subroutine for solving the Hölder-smooth subproblems. This subroutine combines the proximal point algorithm with an accelerated gradient method, leading to improved overall complexity results. Specifically, for $ \\nu = 1 $, the method achieves $ \\tilde{\\mathcal{O}}(\\epsilon^{-3}) $ complexity, matching the best-known rates in the literature. For linear constraints, the complexity is further improved to $ \\tilde{\\mathcal{O}}(\\epsilon^{-2.5}) $.", "claims_and_evidence_yn": "Yes", "claims_explanation": "Most claims in the paper are supported by rigorous proofs. However, I have the following questions and concerns:\n\n1. In Lemma 1, the boundedness of the dual variable $ y_k $ is established by using a very small, normalized step size. However, I find it unusual that, having a bound for $ y_k $, then the Lagrangian term $ \\langle A(x), y \\rangle $ appears to play a minimal role in the proof of Theorem 1. It seems to me that the main force enforcing the constraint comes from the penalty term $ \\|A(x)\\|^{\\nu+1} $. This raises the question: what happens if we simply fix $ y_k = y $ for all iterations? Would the convergence results in Theorem 1 still hold? Additionally, in Theorem 1, the algorithm is shown to converge at a rate of $ \\omega^{-k} $, where $ \\omega $ can be arbitrarily large. Does this imply that the algorithm could theoretically converge in a single iteration if $ \\beta $ is chosen to be sufficiently large? \n\n2. Assumption 1 only requires local Hölder continuity/smoothness, meaning that the constants $ H_f $ and $ H_A $ depend on the local compact set $ S $. For the inner complexity results (Lemma 3 and Lemma 4), I am unclear about the set $ S $. Specifically, with respect to which set $ S $ are the constants $ H_f $ and $ H_A $ defined? \n\n3. What are the implications when $A$ is linear and Assumption 5 holds?", "audience_yn": "Yes", "audience_explanation": "The findings of this paper would likely interest TMLR's audience, as it introduces an inexact augmented Lagrangian method with theoretical advancements and practical implications for constrained nonconvex optimization—a topic relevant to researchers in machine learning and optimization.", "requested_changes": "Please refer to my questions above. My main concern is the effect of updating y after simply bounding it.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "65SUl3krHj", "reviewer": "Reviewer_uuHq", "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": "No", "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": "### Strengths\n\n1. The paper introduces an unconventional inexact augmented Lagrangian method (iALM), using a Euclidean norm raised to a power between 1 and 2. The paper claims that the choice can provide more flexibility and improved performance in balancing primal and dual complexities.\n2. Under mild regularity assumptions, the authors establish rigorous convergence results to first-order stationary points, which can be applied to quantify the trade-off between primal feasibility and dual optimality.\n3. An inexact proximal point method tailored for weakly-convex and Hölder-smooth subproblems is presented with convergence guarantees.\n4. The paper is well-organized and well-written and the convergence analysis is overall correct, to the best of my knowledge.\n5. Numerical experiments are provided to validate the theoretical findings.\n\n### Weaknesses \n1. *Motivation for the unconventional iALM approach is not fully convincing*. The contribution appears incremental as the convergence analysis heavily leverages existing results, and numerical experiments exhibit only marginal improvement.\n2. *Excessive assumptions with unclear relation to existing literature*. The paper introduces numerous assumptions without adequately clarifying their necessity or explicitly contrasting them with standard assumptions in prior works.\n3. *Unclear rationale behind defining the $(\\epsilon_\\phi, \\epsilon_A)$-stationary point*. The introduction of the joint stationary point criterion seems arbitrary or insufficiently motivated from a theoretical or practical perspective.\n4. *Gap between theoretical analysis and numerical results*. APGM, used as an inner solver in numerical experiments, may not converge under the stated theoretical conditions, causing discrepancies between theoretical guarantees and experimental validations.", "claims_and_evidence_yn": "No", "claims_explanation": "Some claims are not fully supported by clear evidence. Please see the weaknesses above.", "audience_yn": "Yes", "audience_explanation": "The (iALM) is among the most influential and widely-used algorithms for solving large-scale convex and nonconvex nonlinear programming problems, particularly due to its strong theoretical foundations and broad applicability. It has found extensive use in diverse fields including optimization, operations research, and modern machine learning applications. Given its practical importance, analyzing the convergence properties and complexity of iALM, especially under realistic and relaxed assumptions, remains a significant and active area of research. Establishing rigorous complexity guarantees and convergence rates provides deeper theoretical insights and drives the design of efficient computational algorithms, contributing directly to solving increasingly challenging real-world optimization problems.", "requested_changes": "1. Clarify specific scenarios or classes of problems where the proposed unconventional augmenting terms clearly outperform existing methods. Provide more compelling numerical evidence showcasing significant advantages in constraint satisfaction or complexity reduction, highlighting real-world relevance.\n2. Include a dedicated discussion (e.g., a table summarizing the differences) explicitly comparing each assumption to those commonly adopted in related literature. Justify explicitly why each newly introduced or relaxed assumption is necessary and how it contributes uniquely to the theoretical or practical improvement of the method.\n3. Provide a clear motivation or practical scenario demonstrating why considering separate primal and dual tolerances, e.g., when it is reduced to the classical $\\epsilon$-stationary point, what are the main differences.\n4. Clearly state and justify the choice of APGM, such as conditions under which convergence is assured or acknowledging the potential limitations explicitly. Alternatively, conduct additional experiments using theoretically guaranteed solvers (e.g., the methods analyzed in the paper) to close the gap and reinforce theoretical claims.", "broader_impact_concerns": "NA", "additional_comments": "NA", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)