Dual Optimistic Ascent (PI Control) is the Augmented Lagrangian Method in Disguise
Authors: Juan Ramirez
Simon Lacoste-Julien
Venue: ICLR 2026 Poster (2026)
Keywords: Constrained Optimization
Min-max Optimization
Augmented Lagrangian Method
Optimistic Gradient Method
Primary area: optimization
TL;DR: We show that dual optimistic ascent (PI control) on the Lagrangian is equivalent to gradient descent–ascent on the Augmented Lagrangian

Abstract: Constrained optimization is a powerful framework for enforcing requirements on neural networks. These constrained deep learning problems are typically solved using first-order methods on their min-max Lagrangian formulation, but such approaches often suffer from oscillations and can fail to find all local solutions. While the Augmented Lagrangian method (ALM) addresses these issues, practitioners often favor dual optimistic ascent schemes (PI control) on the standard Lagrangian, which perform well empirically but lack formal guarantees. In this paper, we establish a previously unknown equivalence between these approaches: dual optimistic ascent on the Lagrangian is equivalent to gradient descent-ascent on the Augmented Lagrangian. This finding allows us to transfer the robust theoretical guarantees of the ALM to the dual optimistic setting, proving it converges linearly to all local solutions. Furthermore, the equivalence provides principled guidance for tuning the optimism hyper-parameter. Our work closes a critical gap between the empirical success of dual optimistic methods and their theoretical foundation in the single-step, first-order regime commonly used in constrained deep learning.

Published as a conference paper at ICLR 2026
DUAL OPTIMISTIC ASCENT (PI CONTROL) IS THE AUG-
MENTED LAGRANGIAN METHOD IN DISGUISE
Juan Ramirez*
Simon Lacoste-Julien
Mila Quebec Al Institute
DIRO, Université de Montréal
F Canada CIFAR AI Chair
ABSTRACT
Constrained optimization a powerful framework for enforeing requirements on neural networks. These constrained deep learning problems are typically solved using first-order methods on their min-max Lagrangian formulation, but such ap- proaches often suffer from oscillations and can fail to find all local solutions. While the Augmented Lagrangian method (ALM) addresses these issues, practitioners often favor dual optimistic ascent schemes (PI control) the standard Lagrangian, which perform well empirically but lack formal guarantees. this paper, we establish a previously unknown equivalence between these approaches: dual op- timistic ascent on the Lagrangian equivalent to gradient descent-ascenn on the Augmented Lagrangian. This finding allows to transfer the robust theoretical guarantees of the ALM to the dual optimistic setting, proving it converges linearly all local solutions. Furthermore, the equivalence provides principled guidance for tuning the optimism the empirical success of dual optimistic methods and their theoretical foundation in the single-step, first-order regime commonly used in constrained deep learning.
Our work closes a critical gap between
INTRODUCTION
Machine learning problems frequently lead to constrained optimization formulations, where the objective function encodes the learning task, and the constraints guide optimization toward models with desirable properties such as sparsity (Gallego-Posade et al., 2022), fairness (Cotter et al., 2019a), or safety (Dai et al., 2024). Alternatively, learning can be incorporated directly into the constraints, as in SVMs and Feasible Learning (Ramirez al., 2025b).
widely adopted approach for solving constrained optimization problems involving deep neural networks is to formulate their associated Lagrangian and seek its min-max points (Elenter et al., 2022; Hashemizadeh et al., 2024; Hounie et al., 2023b; Kotary and Fioretto, 2024). This is typically done through gradient descent-ascent: descent on the problem (primal) variables-ofe variants such as Adam (Kingma and Ba, 2015)-and ascent on the Lagrange multipliers (dual variables). This first-order Lagrangian approach is popular in constrained deep learning because empirically handles non-convex problems and scales efficiently to models with billions of parameters.
with adaptive
However, gradient descent-ascent on the Lagrangian suffers from two major limitations: ! in the non-convex setting, it may fail to converge to certain local solutions of the problem problem-convergencce is guaranteed only for solutions that correspond local min-max points of the Lagrangian (Bertsekas, 2016, Prop. 5.4.2); and ( it often exhibits oscillations, where iterates repeatedly move in and out of the feasible set, slowing down convergence (Platt and Barr, 1987).
A seminal approach that addresses these limitations is the Augmented Lagrangian method (ALM), which incorporates a quadratic penalty term on the constraints (Hestenes, 1969; Powell, 1969; Rockafellar, 1973). With suitable hyperparameter choices, this method converges to all strict and regular local solutions of non-convex constrained problems, while mitigating oscillations.
Despite these advantages, the Augmented Lagrangian method is not the standard in constrained deep learning. Instead, the community largely relies on the original Lagrangian approach, mitigating its os- cillatory behavior with alternative Lagrange multiplier updates such as the PI control strategy (Sohrabi
"Correspondence juan, rami rez@mi 1 quebec

---

Published as a conference paper at ICLR 2026
et al., 2024; Stooke et al., 2020), also known as generalized optimistic gradient ascent (Mokhtari et al., 2020). These dual optimistic ascent methods have shown strong empirical performance in reducing oscillations, but their convergence properties remain largely underformalized.
This paper addresses this gap. We establish a simple yet previously unknown result: gradient de- scent-optimistic ascent on the Lagrangian is equivalent to gradient descent- ascent the Augmented Lagrangian. For equality-constrainee primal iterates (Theorem 1). For general inequality constraints, we prove that both methods converge to the same set of
problems, the equivalence holds exactly at the level of matching
all local solutions of the constrained problem (Theorem 2).
In $4, framework. We show that it strietly improves over standard GDA on the Lagrangian by recovering all local problem solutions (Theorem and provide local convergence guarantees to these solutions (Corollaries 2 and 3). We further characterize the role of the optimism coefficient (proportional gain), formally showing that larger values reduce oscillations but may induce ill ill-conditioning ($4.3). Finally, in $5, we provide experimental results validating our theoretical findings.
this equivalence formalize properties of the dual optimistic ascent (PI control)
Taken together, these results imply that dual optimistie ascent principled only insofar as it mimies the Augmented Lagrangian method in the single-step, first-order regime. In more general settings- such as those employing multiple primal steps or second-order primal optimizers -tii equivalence no longer holds, and dual optimistic ascent fails to inherit the robust convergence guarantees of the ALM; in such cases, we advocate for the explicit Augmented Lagrangian method instead.
Scope. All results are presented in the context of constrained optimization. Our claims about the optimistic gradient method are restricted to: ! its role in maximizing the dual player in a Lagrangian formulation (i.e.,& linear player in non-convex -onvex min-max problem), and @ its application only to that player; for the non-convex primal player, we generally assume a different method used.
2 BACKGROUND
2.1 CONSTRAINED OPTIMIZATION
Let f: Rd R. g: Rd + R", and l : Rd R" be twice-differentiable functions. We consider
the following family of constrained optimization problems:
min wER
f(x) subject g(æ) 3 0, h(x) = 0,
(CMP)
where 3 denotes element-wise inequality. We refer to f as the objective function, and to and h as the inequality and equality constraints, respectively.
Definitions. A point æ is feasible it satisfies all constraints. point x is a local constrained minimizer if it is feasible and there exists an 0 such that f(x*) S f(x) for all feasible with
--=xx1] x=|| S e. A global constrained minimizer is a feasible point that satisfies this inequality for all feasible An inequality constraint (xx) < 0 is active
if it holds with equality, i.e., 9: (x)))) 0.
We denote the set of active inequality constraint indices at x: by Az = (i (x = -}. Equality constraints are always considered "active" when satisfied.
Solving constrained optimization problems. A general approach to solving differentiable con- strained optimization problems find min-max points of their associated Lagrangian (Arrow et al., 1958), which correspond to solutions of the original problem (Bertsekas, 2016, Props. 4.3.1 & 4.3.2):
x² X² n E arg min max L(x, X, 1)) & f(x) A (((x)) p h(x),
(Lag)
RER A=0,
where z and μ are the Lagrange multipliers associated with the inequality and equality constraints, respectively. We refer to æ the primal variables, and to À and μ the dual variables.
simple algorithm for finding min-max points of Eq. (Lag) alternating' (projected) gradient descent-ascent (GDA): descent æ and (projected) ascent on À and μr:
Pt41 & b4 + Meual h(xz),
A+11 +
>x + Muual g g(xx)
(Lag-GDA)
Ø141 2t The f((z)) + X Vg(x.) + IT. Vh(z.))
Alternating updates often preferred over simultaneous updates for constrained optimization because they provide stronger convergence guarantees when the Lagrangian strongly convex (Zhang al., 2022), without adding computational overhead (Sohrabi et al., 2024).
2

---

Published as a conference paper at ICLR 2026
where [++ denotes projection onto the non-negative orthant enforce À ž O, and Ta. Mual > 0 are the primal and dual siep-sizes. The primal update direction is a linear combination of the objective and constraint gradients, weighted by the current multipliers, which are typically initialized to zero. In practice, the descent step is often replaced with adaptive first-order schemes such as Adam. We refer Eq. (Lag-GDA) as the first-order Lagrangian approach, simply the Lagrangian approach.
Constrained deep learning. Applying constraints to deep neural networks where the parameters can number in the billions-is challenging due to the non-convexity and scale of the resulting optimization problems. Classical approaches that exploit problem structure or require costly opera- tions, such as methods involving projections (Goldstein, 1964; Levitin and Polyak, 1966), feasible directions (Frank and Wolfe, 1956; Zoutendijk, 1960), or standard SQPs (Han, 1977; Powell, 1978; Wilson, 1963), are either inapplicable to non-convex deep learning or impractical at this scale.
By contrast, the Lagrangian approach in Eq. (Lag- (Lag-GDA) has become a dominant method for con- strained deep learning. with applications across wide range of domains (Cotter al., 2019a; Elenter et al., 2022; Hounie et al., 2023a;b; Ramirez et al., 2025b; Robey et al., 2021; Zhang et al., 2025), and integration into popular frameworks such as PyTorch (Paszke et al., 2019) and TensorFlow (Abadi et al., 2016) via libraries like Cooper (Gallego- Poolegg et al., 2025) and TFCO (Cotter et al., 2019b).
Its popularity stems from its convergence properties and computational scalability. It provides local convergence guarantees to min-mas points of the Lagrangian, even in the non-convex setting (Bertsckas, 2016, Prop. 5.4.2), while remaining computationally efficient SaallegoPPosadee 2024; Ramirez et al., 2025a). Its overhead relative to unconstrained deep learning is negligible, limited to storing and updating the multipliers?
Limitations. In the non-convex regime, the Lagrangian approach faces several drawbacks. Not all local constrained minimizers xt of Eq. togethr with their corresponding optimal multipliers min-max points of the Lagrangian L. In particular, x² need not minimize C( X f²") =²),²² ) and the Hessian V (xx("" X" (4") may fail to be positive definite. In fact, the Lagrangian can be strictly concave in some infeasible directions- precludes optimality in unconstrained problems, it can arise at constrained optima (Bertsekas, 2016, Prop. 4.3.2). Such non-conved stationary points cannot be reached via Eq. (Lag-GDA)
A 2 0 and μ necessarryyyy correspond
strict concavity
Despite this limitation. Eq. (Lag- (DDg has proven effective in practice for a wide range of non- convex constrained deep learning applications. However, another challenge limits its applicability: the optimization dynamics often induce oscillations in the multipliers and their associated constraints, causing the primal iterates to repeatedly move in and out of the feasible set (Platt and Barr, 1987). These oscillations slow convergence and can be critical in settings where infeasibility cannot be tolerated-for for example, when violations disrupt physical systems or compromise safety.
These limitations have motivated two main strategies for improvement. The first is the Augmented Lagrangian Method, which makes the (Augmented) Lagrangian strictly convex at all strict and regular constrained minimizers of Eq. (CMP). The second replaces simple gradient ascent the multipliers with generalized optimistic gradient ascent, which mitigates oscillations in the dynamics. These methods are discussed in $2.3 and $2.2, respectively. In $3, we prove that they are, in fact, equivalent.
2.2
DUAL OPTIMISTIC ASCENT
The oscillatory behavior inherent in the dynamics of Eq. (Lag-GDA) has motivated alternatives to plain gradient ascent for updating the dual variables. prominent class of such methods is based on optimism (Rakhlin and Sridharan, 2013). In this work, we adopt the generalized optimistic gradient method of Mokhtari et al. (2020), applying it solely to À and μ. Combining this with standard gradient descent on and alternating updates where the multipliers are updated first first-yields:
1e+1 +- lht + Mdtall h(x)) w [h((a))) h(xx-1)]
Ae+1 + Ax Kuual g (x:) + w (x(;)) g g(
(Lag-GD-Or
Et+1 Et The V (x:)) + 1 Vg(a:) + MT+ Vh(x:)
"This overhead is negligible for two reasons: the number of constraints-and and thus multipliers- is typically much smaller than the number of model parameters, adding minimal memory overhead; and the dual gradients correspond to constraint values, requiring no extra backward passes and thus negligible compitational overhead. 'Even solutions that minimize alaiht strictly-may not correspond to limit points of Fq. (Lag-GDA).
3

---

Published as a conference paper at ICLR 2026
where >> is the optimism coefficient. To avoid undefined evaluations at 0, set the "previous" constraint violations equal to the current ones-neeee h(x-1) = h h( and g(x-1) g (z)). Under this convention, the first dual update reduces to standard (projected) gradient ascent step with step-size "/aual, ensuring that Eq. (lag-GI-OOA) is well defined at / == 0.*
While optimism is often applied to both players in general min-max optimization (i.e., optimistic gradient descent- ascent; OGDA), we follow the more general approach of Sohrabi et al. (2024); Stooke et al. (2020)² for constrained problems by applying optimism only to the dual variables. This preserves flexibility in the choice of the primal update, allowing to retain task-specific training pipelines-suse as standard Adam without optimism. Such flexibility is especially important in deep learning, where model training pipelines are often highly specialized, making it undesirable to modify them solely to accommodate alternative dual optimization algorithms.
Dual (generalized) optimistic updates have been applied to stabilize optimization dynamics of constrained deep learning problems across reinforcement learning (Moskovitz et al., 2023; Stooke et al., 2020), unsupervised learning (Shao et al., 2022), and supervised learning (Sohrabi et al., 2024).
Intuitively, the optimistic update in Eq. (Lag-GD-OA) dampens oscillations by adjusting dual ascent steps with information from past constraint violations; specifically, by adding the optimistic term (g(e)) - g (1) When violations shrink across iterations, this correction term is negative, acting brake: the multiplier increases more conservatively. avoiding an "overshoot" beyond its optimum. This prevents over wver-penalization of the constraints in later primal steps, thereby stabilizing the dynamics and reducing oscillations. For further discussion, see Sohrabi et al. (2024, $4.3). In $3, we show that this stabilizing behavior is not accidental: in the single-step. first-order regime we consider, dual optimistic ascent is simply an Augmented Lagrangian method in disguise.
Literature gaps. While successful empirically, dual optimistic ascent on the Lagrangian remains largely underformalized. It lacks convergence guarantees and is supported exclusively by empirical demonstrations of its ability to mitigate oscillations.
Despite the vast literature on optimistic methods, most existing results do not directly apply to the dual optimistic ascent algorithm in Eq. (Lag-GD-OA). For general min-max games, OGDA is known to expand the set of stationary points which it can converge relative to standard GDA (Daskalakis and Panageas, 20. While this set can include the global solution in bilinear games, the nature of these additional points remains largely uncharacterized in general non-convex-now non-ex-xo--oo games. Moreover, the established convergence guarantees for OGDA- -scch as global linear convergence under strong convexity-stree strong concavity (Gidel et al., 2019), sublinear convergence under convex- ity-concayity (Gorbunov et al., 2022), and sublinear convergence for non-convex-(stronggl concave settings (Mahdavinia et al., 2022>-are are derived in frameworks incompatible with our own.
The inapplicability of these findings stems from two key issues. First, the cited results concern different algorithm that applies optimism to both players, not just the dual player as in Eq. (Lag-Gr GD- OA). Second, the underlying assumptions mismatched-ther are either too restrictive, requiring (strong) convexity for the minimization player, or too general, assuming a con--oovex-coneen game that fails exploit the specific con-convex-linend structure of the Lagrangian.
2.3 THE AUGMENTED LAGRANGIAN METHOD
The (HPR) Augmented Lagrangian function (Hestenes, 1969; Powell, 1969; Rockafellar, 1973) adds a quadratic penalty to the standard Lagrangian to penalize constraint violations:
Cx X. (u) A f(x) +
1 [| ch(2)ll - |1 + A + cg(x)) 2c
(AL)
where > 0 is penalty coefficient. Expanding the squared norms in Eq. (AL) reveals that constraint violations are penalized by both a linear term involving the multiplier and a quadratic term scaled by c.
AAlternativey,, one can set h( = 0 and g( 1) = 0. which case the first dual step a projected gradient ascent update with effective step size TJamal + w. Both conventions are equivalent for our purposes the
difference can be absorbed into the initialization of (Ao: (4)) without affecting our theoretical results.
'The generalized optimistic gradient method is special case of the algorithms in both papers; specifically, it corresponds to a Proportional-Itteral (PI) controller on the multipliers.
'Moreover, known convergence results for OGDA seldom consider the generalized case where w A Naall with the notable exception of Mokhtari al. (2020) for bilinear games.
4

---

Published as a conference paper at ICLR 2026
The projection [-]+ creates one-sided penalty for inequalities: it penalizes violations (g.(x) > 0) but avoids pushing iterates deeper into the feasible region once a constraint is sufficiently satisfied (g)(x) I -x//c). This ensures that optimization focuses only on violated nearly- constraints.
The set of min-mmx points of L.. The Augmented Lagrangian preserves and enhances the solution set of the standard Lagrangian. Since the two functions share the same set of stationary points (Rock- afellar, 1973, Cor. 3.4), they have an identical pool of candidate solutions. Furthermore, every local min-max point of C remains local min-max point of Le, ensuring that any solution attainable with the standard Lagrangian approach remains attainable within the Augmented Lagrangian framework.
More importantly, under regularity assumptions, every strict local constrained minimizer x²" admits threshold& E 2 0 such that, for all с 2 č, the Augmented Lagrangian Le is strictly convex at æ", even if the original Lagrangian C is not convex there (Bertsekas, 2016, $4.2.1). Consequently, all striet local constrained minimizers of Eq. (CMP) are upgraded to local min-max points of Le.
Two important algorithmic consequences follow: ! all striet local constrained minimizers become strict local min-mat man-mmx points of Le. for which GDA enjoys local linear convergence guarantees (Bert- sekas, 2016, Prop. 5.4.2); and ② the sets of strict local constrained minimizers Eq. (CMP) and strict local min-max points of f.: coincide, ensuring that GDA on the Augmented Lagrangian converges to-and only to stationarr points corresponding to solutions of Eq. (CMP). Further benefits of the Augmented Lagrangian approach- including its ability to mitigate oscillations are discussed in $4.
The Augmented Lagrangian Method seeks min-max points of the Augmented Lagrangian function:
x² x", , E arg min max Ca(æ, X, μ).
(I)
#ERd Az
The classic algorithm for solving this problem the Method of -ttraaiiess- performs:
Ft+1 E arg min fee Ae, pt), M441 = b4 + ce h(x++1), Ae+1 = [A + c g( (2)
=rlld In this method, the primal minimization is typically performed approximately, either for a fixed number of optimization steps or until a numerical tolerance is reached. The subsequent dual updates correspond to gradient ascent steps the standard Lagrangian L with step-sizes ez. The penalty coefficients are chosen as decresccgg sequence Ct-1 2 Ct > O, often updated according to a schedule-for example, increasing et when constraint violations are not reduced sufficiently across successive iterations (see, e.g., Birgin and Martínez (2014, Eq. 4.9 in Alg. 4.1)).
The Augmented Lagrangian method is seminal approach for solving non-convex constrained optimization problems, with variants implemented in numerous optimization libraries across different programming languages (Conn et al., 2013; Gallego-Poss Possada et al., 2025; Johnson; Pas et al.. 2022). Its success spans a broad range of scientific problems, and it has become a key tool in constrained deep learning, applied in works ranging from seminal contributions to recent advances (Brouillard et al., 2020; Kotary and Fioretto, 2024; Lokhande et al., 2020; Platt and Barr, 1987; Shi et al., 2023).
In deep learning, where full (or even approximate) minimization of L. is computationally infeasible, it is often replaced by one or more steps of first-order optimizer, such as Adam. Accordingly, in this paper we consider the following family of Augmented Lagrangian algorithms: alternating gradient Desccent((rojecter gradient ascent L., with the primal update performed first.
01+1 < Dt - 7h [((.)) + De + cg(xx)) T Vg(az)) + (pr + ch(x))) Vh(m:))
(AL-GDA)
M1+1 +- Me + Tduual h(x+11)
A1+1 (1 Tikeel
A
Thaal A + ceg(x++))
where 0 < Mual I cnd 7 > 0 are fixed step-sizes. The algorithm first takes single primal gradient descent step on Le, then performs a dual gradient ascent step on the multipliers with step-size Tuuull which is independent of the penalty c. Notably, the X-update is convex combination of the previous iterate X, and a new estimate [), + eg( (xt+1)) +)+++ Setting M/uil = e recovers the standard dual updates of the Method of Multipliers in Eq. (2). This method is therefore more specific than Eq. (2) by replacing the full primal minimization with a single gradient step and more general, as it decouples the dual size from c. For full derivation of these updates, see Appendix B.
The primal update in Eq. (AL-GDA) can be viewed as a gradient descent step on the standard Lagrangian, using multiplier estimates that differ from their latest iterates. These estimates simulate a (projected) ascent step on L. acting as a proactive "lookahead" to calibrate the primal updates. Recognizing this is the key insight behind the equivalence with dual optimistic ascent shown in $3.
5

---

Published as a conference paper at ICLR 2026
3 DUAL OPTIMISTIC ASCENT (PI CONTROL) IS THE AUGMENTED LAGRANGIAN METHOD IN DISGUISE
In this section, we show that the Augmented Lagrangian method (Eq- (AL--DDA $2.3) and dual optimistic ascent (Eq. (Lag-GD-OA) in $2.2) are equivalent for equality-constrainne problems when c = w, in the sense that their primal iterates coincide (Theorem in 13. This equivalence does not extend to problems with inequality constraints. Nevertheless, Theorem in $3.2 establishes that both algorithms share the same set of locally stable stationary points. Consequently, they achieve the same fundamental objective: ensuring that all strict and regular local constrained minimizers of Eq. (CMP) are limit points of their dynamics. We discuss further implications of these results in $4.
3.1 EQUALITY CONSTRAINTS
We first show that, for equality problems, the primal iterates of Eq. (Lag-GD-OA) and Eq. (AL-GDA) coincide when w = c and the initialization is chosen appropriately.
Theorem 1 (Equivalence for equality- by primal-first GDA on the Augmented Lagrangian (Eq. (AL-GDA)) and dual-firs gradient de- scent-optimistic ascent on the Lagrangian (Eq. (ag-GDDOA)) for an equality constraind problem match, provided that: ① the penalty and optimism coefficients are constant and equal, w > and ② their respective initializations are chosen as (æo: Mo) and (Zo, Po + (c Nduual h (xxo)).
problems). The primal iterates { [æ, ) generated
Proof. See Proof of Theorem / in Appendix D.
Note that Theorem 1 applies to any first-order optimization algorithm used to minimize the (Aug- mented) Lagrangian, not only gradient descent. This holds because both algorithms generate the same sequence primal gradients. In particular, the result extends to primal updates performed with first-order deep learning optimizers such as Adam.
3.2 GENERAL CONSTRAINED PROBLEMS WITH INEQUALITY CONSTRAINTS
Unlike the equality-constrained case, the iterates Eq. (AL-GDA) and Eq, (Lag-GD-OA) do not coincide for problems with inequality constraints. This difference arises from the placement of projections on the inequality multipliers updates: in Eq. (Lag-GDo GD-OA, they are applied only once during the update, whereas in Eq. (AL-GDA), they applied twice- -one--onceee to update the multiplier and again to compute the "lookahead" estimate for the primal gradient. Nevertheless, as shown in Theorem 2, the algorithms share the same of locally stable stationary points. In this sense, both are equally powerful-as and strictly more so than Eq. -DA).
First, we establish that both algorithms share the exact same of stationary (fixed) points:
Proposition 1 (Equivalence of Stationary Points). The set of fixed points for algorithms Eqs. (AL- GDA) and (Lag-GD-OA) are the same, and correspond to the set of KKT points of Eq. (CMP).
Proof. See Proof of Proposition in Appendix D.
Having identified the fixed points, we now examine whether the algorithms actually converge to them. We rely the standard notion of local stability:
Definition 1 (Local stability). Consider algorithm
F+41 & F(I,, A Mc),
A4t1 & G(x,, Me),
pe+1 +- H de, P1).
(3)
A fixed point ( Jacobian I of the joint operator [F, G, H), evaluated at (x* x", ,²),, has spectral radius strictly less than one, i.e., p(T) 1.
x²,x²))) of this algorithm called a locally stable stationary point (LSSP) if the
standard result states that an algorithm exhibits local linear convergence to of its LSSPs (Bertsekas, 2016, Prop. 5.4.1). To analyze the stability of our two methods, therefore study their respective operator Jacobians: JAL. for the Augmented Lagrangian method Eq. (AL-GDA) and Joa for dual optimistic ascent Eq. (lag-GG-OA). These derived in Lemmas 2 and of Appendix D.

---

Published as a conference paper at ICLR 2026
Theorem 2 (Equivalence of LSSPs inequality constraints). Let (x* X²) be stationary point of problem, satisfying strict complementary slackness
the Lagrangian for an inequality (see Assumption 1 in Appendix A). Then Eq. (AL-GDA) with penalty coefficient converges locally to (x" x²) if and only if Eq. (Lag-GD--AA) with optimism coefficient w = c also converges locally to that point. Moreover, the spectral radü of the Jacobians of the two algorithms satisfy
p(Jxr) imax(p(Joc), - -Tduut /c).
Proof. See Proof of Theorem 2 in Appendix D.
By combining the results for equalities ($3.1) and inequalities (Theorem 2), we arrive at the following general equivalence covering mixed constraints:
Corollary (Equivalence of LSSPs). The algorithms in Eqs. (AL-GDA) and (Lag-GD-OA) share the same set of locally stable stationary points satisfying Assumption 1.
Proof. The result follows by applying the same logic in the proof of Theorem 2, where equality constraints are treated as a special case of active inequality constraints.
IMPLICATIONS AND DISCUSSION
This section builds on the equivalence results from $3 to establish formal properties of the dual optimistic ascent method (PI control), including a characterization of its locally stable stationary points in terms of solutions to the constrained problem ($4.1), 1), convergence guarantees ($4.2), and practical guidelines for tuning the optimism hyperparameter (84.3).
These results apply specifically to the single-step. first-order dynamics of Eq. (Dag-GD-OA), In $4.4, we explain how the equivalence breaks down once these assumptions are relaxed and argue that, in such settings, classical Augmented Lagrangian methods are the more principled approach.
4.1 CHARACTERIZING THE STABLE POINTS OF DUAL OPTIMISTIC ASCENT
We now show that dual optimistic ascent offers a principled approach to constrained optimization: it recovers all regular, strict local constrained minimizers of Eq. (CMP). Although the method has been applied constrained problems before, this property has not been previously identified formalized.
Subsequent results rely on three standard assumptions, which we state formally in Appendix A: strict complementary slackness (Assumption 1), the second-order sufficiency condition (Assumption 2), and the linear independence constraint qualification (Assumption 3). We now recall the following classical results for the Augmented Lagrangian method:
Proposition 2. (Bertsekas, 2016, $4.2. Let x:" be strict local constrained minimizer with corre- sponding Lagrange multipliers X > O and μe, satisfying Assumptions to 3. Then there exists ē > O such that, for every c the Augmented Lagrangian L. is strictly convex in at (x" X ,²)).
Proposition 3. (ALM finds all constrained minimizers) For any strict local constrained minimizer x satisfying Assumptions to 3, there exist c > O large enough and qax Adual small enough such that xx is an LSSP of Eq. (AL-GDA).
Proof. This is well-known for simultaneous GDA in gquality-constrannett problems (Bertsekas (2016, 6, Prop. 5.4.2)). For a proof specific to Eq. (AL-GDA), see Proof of Proposition in Appendix D.
The converse also holds: the LSSPs of ALM dynamics are precisely the local constrained minimizers of Eq. (CMP), indicating that Eq. (AL-GDA) does not converge spurious stationary points of Ce.
Proposition 4. (ALM finds only constrained minimizers) Let (x" X², n²) be LSSP of Eq. (AL- GDA) for some Mas Uduat e > O. Then x² is a local constrained minimizer of Eq. (CMP). Proof. See Proof of Proposition in Appendix D.
We now characterize the solution set of dual optimistic ascent.
Theorem 3 (LSSPs of dual optimistic ascent). Let x" satisfy Assumptions 1 and 3. Then x" is a strict
local constrained minimizer of Eq. (CMP)-thee is, it satisfies Assumption 2 2- and only if there exists an optimism coefficient @ 2 O such that for all w 2 w. there exist learning rates na Maaal > O small enough for which x² is LSSP of the dual optimistic ascent dynamics Eq. (Lag-GD-OAA
7

---

Published as a conference paper at ICLR 2026
Proof. This follows directly from the equivalence results in Corollary together with the properties of Eq. (AL-GDA) given in Propositions 3 and 4 above.
Theorem 3 establishes dual optimistic ascent principled framework for constrained optimization. While it is known that optimistic methods converge to a broader set of stable points than standard GDA (Daskalakis and Panageas, 2018), our result refines this for the constrained setting by precisely characterizing which additional stable points arise from (dual) optimism: it recovers all strict and regular local constrained minimizers of Eq. (CMP) and only such solutions." This makes it strictly more powerful than simple Eq. (Lag-GDA)) For an analysis of how large w = c must be to guarantee convergence given x", see Bertsekas (2014, Prop. 2.7).
4.2 CONVERGENCE RESULTS FOR DUAL OPTIMISTIC ASCENT
Non-convex problems. Our equivalence results allow us transfer the well-understood convergence guarantees of the Augmented Lagrangian method to the dual optimistic ascent framework.
Corollary 2 (Local convergence rate of dual optimistic ascent). For appropriate hyperparameter exhibits local linear convergence to all strict local constrained minimizers of Eq. (CMP) satisfying Assumptions I to 3. Whenever Adull is sufficiently close to w = c (so that 1 ndmat/ e < p((J))), the convergence rate of Eq. (Lag-GD-OA) matches that of Eq. (AL-GDA).
choices, Eg.
Proof. Local linear convergence follows directly from Theorem 3. The spectral norm relationship between p(Toc) and ((JAL) established in Theorem 2 links the convergence rates of the two algorithms for inequality mnequalitycconstrinnee constrained problems. Note that equality constraints can be treated locally as active inequalities, and thus the same relationship between spectral norms holds in that case. 0
This result also implies that for problems where specific convergence rate is known for Eq. (Lag- GDA), & that rate transfers directly to Eq. (Lag-GD-OAl GD-OA), provided Noual is sufficiently close to c.
Global convergence, however, is more delicate. While the matching primal iterates for equality- constrained problems (Theorem 1) suggest that convergence guarantees may transfer directly across al- gorithms, this is not the case for inequality constraints. There, our equivalence is only local- ensuring the same set of LSSPs (Corollary 1) but not the same global behavior.
Even for equality constraints, key obstacle prevents from proving global convergence of dual optimistic ascent using known results for the Augmented Lagrangian method. Classic ALM results, such as the Q-linear rate in Bertsekas (2014, Prop. 2.7). apply the Method of Multipliers (Eq. (2)) and rely on each primal step yielding sufficiently accurate (local) minimizer of Le. In contrast, our equivalence holds only for single-step step first-order updates, which do not meet this requirement.
One might then consider performing multiple primal minimization steps per dual optimistic ascent update to meet this condition. However, this breaks the equivalence to Eq. (AL-GDA) and instead amounts to multi-step minimization of the standard Lagrangian L. Since L may fail to be locally convex near a solution, such a procedure lacks convergence guarantees.
It may still be possible to establish global convergence of Eq. (Lag-GD-OA) for non-convex problems directly-following for example, strategies developed for OGDA in nonconvex-conese games (Mahdavinia et al., 2022). However, this lies beyond the scope of our work.
Convex problems. In the convex setting, our equivalence theorems yield global convergence guarantees for dual optimistic ascent on equality-constrained problems. Extending these guarantees to inequality constraints remains an open direction for future work.
problems). Consider problem with a convex, smooth objective f(x) and affine equality construints h(x)) = Ba + b. Assume the problem has a unique solution x: and that LJCQ is satisfied (Assumption 3), i.e., B has full row rank. Then, for any >> O and sufficiently small step-sizes Namals qa. Eq. (Lag-GD-OA) converges globally at a linear rate to the optimal pair (x", 1²)). The exact rate depends on the properties of f and B; see Alghunaim and Sayed (2020, Theorem for precise characterization.
Corollary 3 (Global linear convergence for convex
"Tiis highlights a key difference with general min-max games (c.g., GANs), where new equilibria stabilized by optimism can he spurious. constrained optimization, these "spurious" " solutions are feature, not bug. 'There is no general closed-form expression for the iteration complexity of the Augmented Lagrangian method in Eq. (AL-GDA)); such rates can only be established under additional assumptions on f. g, and h.
8

---

Published as a conference paper at ICLR 2026
Proof. This follows from the equivalence in Theorem 1, and Alghunaim and Sayed (2020, Theorem 1), which establishes global linear convergence for Eq. (AL-GDA).
This global convergence guarantee hinges on the strong convexity of the Augmented Lagrangian Co on 2;, which is induced even when the original objective f is merely convex. In contrast, the standard Lagrangian remains only convex in æ, and GDA is not guaranteed to converge on the resulting convex-concave problem (Gidel et al., 2019). Dual optimistic ascent avoids this failure mode by inheriting the favorable convergence properties of the Augmented Lagrangian method.
4.3 PRACTICAL IMPLICATIONS FOR HYPER-PARAMETER PARAMETER TUNING
Our equivalence result provides practical guidance on choosing the optimism hyper-paramese This parameter introduces a critical trade-off analogous to the coefficient c in the Augmented Lagrangian method:
larger values of are beneficial they I expand the set of attainable solutions and @ dampen oscillations in the optimization dynamics. However, 3 excessively large values can lead to an ill-conditioned problem, which may in turn slow convergence. We now formalize these points.
Corollary 4 (Monotonic inclusion of solutions). The set of strict local minimizers of Eq. (CMP) that are LSSPs of the dual optimistic ascent dynamics is monotonically non-decreasing in w. For sufficiently large w, this set coincides with all local minimizers satisfying Assumptions I to 3.
Proof. This follows from the equivalence result in Corollary 1 and Prop.
generally unclear what value of w is sufficiently large to turn given solution x" into an LSSP; this would typically require knowing x" itself. This practical uncertainty motivates a simple strategy: to ensure all solutions are attainable, one may consider taking w + oc.
In practice, however,
Dampening Oscillations. A key motivation for moving beyond standard GDA on the Lagrangian L is the presence of oscillations. Whenever the Hessian V2. is indefinite, the dynamics are characterized by imaginary cigenvalues, an effect observed in practice (Sohrabi et al., 2024; Stooke et al., 2020) and expected in theory (Benzi and Simoncini, 2006, Prop 2.5 & Remark 2.8).
The Augmented Lagrangian method is classical solution: the penalty coefficient c the eigenvalues of its dynamics become purely real, eliminating oscillations (Benzi and Simoncini, 2006, Remark 2.9). Our equivalence result (Corollary 1) shows that Eq. (Lag-GD Lag--DDONN inherits this damping property, formalizing the insight that larger values of w produce a more heavily dampened system.
Proposition (Dual optimistic ascent dampens oscillations). Let (x", X*) be a strict local con- strained minimizer satisfying Assumptions to 3. There exists finite threshold w such that for all optimism coefficients w 2 w, the eigenvalues of the Jacobian JoG are purely real. Furthermore, under degeneryyyy conditions, as approaches ās from below, the maximum imaginary part of the eigenvalues decays as O(Va- - -W).
Proof. See Proof of Proposition in Appendix D.
As before, the exact threshold for w to fully remove oscillations depends on problem-specift properties at x²" making unknown in practice. This again motivates selecting a generously large w.
Conditioning trade-off. However, while these observations may suggest that increasing the optimism coefficient beneficial, we emphasize another aspect: Bertsekas (2014, Eq. 16 in $2.1) shows that as + co, JAL-and hence Jog becomes increasingly ill-conditioned.
Corollary 5 (lllcoonitioning of dual optimistic ascent). As w + co, the condition number of the operator Jacobian JoG also tends to infinity.
Proof. This follows from our equivalence result (Corollary 1) and the known ill-conditioning of the Augmented Lagrangian for a large penalty c (Bertsekas, 2014, see Eq. 16 in $2.1).
This reveals critical trade-off: the optimism coefficient must be large enough to recover all solutions, yet not so large that it induces ill-conditioning. Since the optimal value depends on local properties an unknown solution x" and may not generalize across the optimization landscape, must be tuned in practice. Our equivalence provides a principled path forward: practitioners can use well-established ALM penalty-scheduling techniques to dynamically tune the optimism coefficient.

---

Published as a conference paper at ICLR 2026
4.4 WHEN THE DISGUISE FAILS: LIMITS OF DUAL OPTIMISM
While Eq. (Lag-GD-OA) and Eq. (AL-GDA) are equivalent, this equivalence relies critically on their single-step, first-order structure. The core mechanism is that dual optimistic ascent effectively performs descent steps on the Augmented Lagrangian (see $2.3), providing principled basis for solving constrained optimization problems.
Once these assumptions are relaxed, this mechanism breaks down. Performing multiple primal steps between dual updates means the equivalence holds only for the first step; from the second step onward, the algorithm minimizes the standard Lagrangian with frozen multipliers. As discussed in $2.1, this is flawed for non-convex constrained optimization: the Lagrangian need not be locally convex in a neighborhood of a constrained minimizer, so this inner minimization may fail to converge to the desired solution.
The situation is similar for second-order primal methods. Our change of variables aligns the gradients of the two objectives, but not their Hessians: the Augmented Lagrangian includes extra positive curvature from the penalty term that the standard Lagrangian lacks. Consequently, Newton or quasi- Newton steps on the standard Lagrangian- even even with optimistic multipliers differ from those of ALM and do not inherit its local convexity convergence guarantees.
In both cases, the algorithm effectively reverts to minimizing the standard Lagrangian, with all its associated stability issues and without the guarantees obtained via the ALM equivalence. In such settings, we therefore advocate for the explicit Augmented Lagrangian method, which enjoys Q-linear convergence when the subproblems are solved to sufficient accuracy (Bertsekas, 2014, Prop. 2.7).
EMPIRICAL VALIDATION
We provide empirical support for our theoretical findings in Appendix C. First, we numerically verify the exact equivalence of primal iterates for equality constraints (Theorem 1) on non-convex ID example. As illustrated in Figure 1 (Appendix C.1), the trajectories of dual optimistic ascent and the Augmented Lagrangian method coincide. Second, we demonstrate the practical utility of this equivalence in Appendix C.2 by showing that classical ALM penalty scheduling strategies can be directly applied to the optimism coefficient w to stabilize convergence (Figure 2).
Beyond these synthetic examples, our theory rationalizes the empirical success of dual optimistic ascent reported in the deep learning literature. Specifically, the recovery of all strict local solutions (Theorem 3) explains success where standard GDA fails (Ramirez et al., 2025a, Table 1), and the spectral analysis (Prop. 5) provides a rigorous basis for the oscillation dampening observed in reinforcement learning (Stooke et al., 2020) and constrained classification (Sohrabi et al., 2024).
6 CONCLUSION
In this paper, we establish that dual optimistic ascent (PI control) on the Lagrangian is, in fact, the Augmented Lagrangian method in disguise. This equivalence bridges gap between theory and practice: it allows us to transfer the formal guarantees of the ALM to the widely used dual optimistic ascent method. Furthermore, our work provides principled interpretation of the optimism hyperparameter w, reframing it from a heuristic knob into a formal regulator of the trade-off between solution accessibility and numerical conditioning.
Crucially, our analysis also delineates the boundaries of dual optimistic ascent. We show that it is theoretically well-founded only in the single-step, first-order regime common in deep learning. Once one departs from this regime-for for instance, by employing multi-step primal updates or second-order optimizers- the equivalence vanishes. In such cases, there no guarantee that dual optimism will recover all local constrained solutions, and the explicit Augmented Lagrangian method remains the superior, principled framework.
A natural direction for future work is to explore whether similar principles apply to optimistic methods in general min-max games, potentially offering new insights into the stabilization of GANs and other adversarial formulations. Additionally, the connection established here opens the door to transferring hyperparameter tuning techniques from control theory (PI gains) to constrained optimization (penalty schedules), promising more robust automated tuning strategies.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGEMENTS AND DISCLOSURE OF FUNDING
This work was supported by the Canada CIFAR AT Chair program (Mila), the NSERC Discovery Grant RGPIN-2025-05122, by an unrestricted gift from Google, and by Samsung Electronics Co., Ltd. Simon Lacoste-Julien is a CIFAR Associate Fellow in the Learning in Machines & Brains program.
We thank Jose Gallego- Pasaaa and Ioannis Mitliagkas for insightful discussions that ultimately led to this work; their observation that dual optimistic ascent and the Augmented Lagrangian method exhibit similar stabilizing effects was a key motivation for this investigation.
STATEMENT ON THE USE OF LARGE LANGUAGE MODELS
Large Language Models (LLMs) were used to assist in the preparation of this manuscript. Their role was that of research assistants: aiding in the literature review, cross-checking proofs, and evaluating the soundness of technical arguments. They were also employed improve the clarity of the text.
REFERENCES
M. Abadi et al. TensorFlow: A system for Large-Scale Scale machine learning. In 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI 16), 2016. (Cit. on p. 3)
S. A. Alghunaim and A. H. Sayed. Linear Convergence of Primal-Dute Gradient Methods and their Performance in Distributed Optimization. Automatica, 2020. (Cit. p. 8, 9)
K. Arrow, L. Hurwiez, and H. Uzawa. Studies in Linear and Non-linear Programming. Stanford University Press, 1958. (Cit. on p. 2)
M. Benzi and V. Simoncini. On the Eigenvalues of a Class of Saddle Point Matrices. Numerische Mathemarik, 2006. (Cit. on p. 34)
D. Bertsekas. Nonlinear Programming. Athena Scientific, 2016. (Cit. on p. 1, 1, 6, 13)
D. P. Bertsekas. Constrained Optimization and Lagrange Multiplier Methods. Academic press, 2014. (Cit. on p. 8, 9,9, 10)
E. G. Birgin and J. M. Martínez. Practical Augmented Lagrangian Methods for Constrained Optimization. The SIAM series Fundamentals of Algorithms, 2014. (Cit. p. 5, 20)
P. Brouillard, S. Lachapelle, A. Lacoste, S. Lacoste-Julien. and A. Drouin. Differentiable Causal Discovery from Interventional Data. In NeurlPS, 2020. (Cit. on p.
A. R. Conn, G. Gould, and P. Toint. LANCELOT: a Fortran Package for Large-Scale Nonlinear Optimization. Springer Science & Business Media, 2013. (Cit. on 5)
A. Cotter, H. Jiang. M. R. Gupta, S. Wang, T. Narayan, S. You, and K. Sridharan. Optimization with Non-Differrnniiabe Constraints with Applications to Fairness, Recall, Chum, and Other Goals. JMLR, 2019a. (Cit. on p. 1,
A. Cotter et al. TensorFlow Constrained Optimization (TFCO). https://github: com/ 2019h. (Cit. on
3)
J. Dai, X. Pan, R. Sun, Ji, X. Xu, M. Liu, Y. Wang, and Y. Yang. Safe RLHF; Safe Reinforcement Learning from Human Feedback. In ICLR, 2024. (Cit. on p. 1)
C. Daskalakis and Panageas. The Limit Points of (Optimistic) Gradient Descent Min-Max Optimization. In NeurIPS, 2018. (Cit. on p. 4,
J. Elenter, N. NaderiAlizadeh, and A. Ribeiro. A Lagrangian Duality Approach to Active Learning. In NewriPS, 2022. (Cit. on p. 1,3)
M. Frank and P. Wolfe. An Algorithm for Quadratic Programming. Naval Research Logistics Quarterly, 1956. (Cit. p.
11

---

Published as a conference paper at ICLR 2026
J. Gallego-Posada. Constrained Optimization for Machine Learning: Algorithms and Applications. PhD Thesis, University of Montreal, 2024. (Cit. on p. 3)
J. Gallego- Posada, J. Ramirez, A. Erraqabi, Y. Bengio, and S. Lacoste-Julien. Controlled Sparsity via Constrained Optimization or: How Learned to Stop Tuning Penalties and Love Constraints. In NeurlPS, 2022. (Cit. on p.
Gallego-Posada, J. Ramírez, M. Hashemizadeh, and S. Lacoste-Julien. Cooper: Library for Constrained Optimization in Deep Learning. arXiv preprint arXi::2504001112, 2025. (Cit. on 3, 5, 19)
G. Gidel, H. Berard, G. Vignoud, P. Vincent, and S. Lacoste-Julien. A Variational Inequality Perspective on Generative Adversarial Networks. ICLR, 2019, (Cit. on p. 4, 9)
A. A. Goldstein. Convex Programming in Hilbert Space. University of Washington, 1964. (Cit. on 3)
E. Gorbunov, A. Taylor, and G. Gidel. Last-Iterate Convergence of Optimistic Gradient Method for Monotone Variational Inequalities. In NeurIPS, 2022. (Cit. on p. 4)
S.-P. Han. A globally convergent method for nonlinear programming. Journal of optimization theory and applications, 1977. (Cit. on p.
M. Hashemizadeh, J. Ramirez, R. Sukumaran, G. Farnadi, S. Lacoste-Julien, and J. Gallego-Posada. Balancing Act: Constraining Disparate Impact in Sparse Models. In ICLR, 2024. (Cit. p.
M. R. Hestenes. Multiplier and Gradient Methods. Journal of Optimization Theory and Applications, 1969. (Cit. on 1, 4)
I. Hounie, L. Chamon, and A. Ribeiro. Automatic Data Augmentation via Invariance Learning. In ICML, 2023a. (Cit. on 3)
I. Hounie, Elenter, and A. Ribeiro. Neural Networks with Quantization Constraints. In ICASSP. 2023b. (Cit. on 3)
S. http://github com/ com/stevengj/nlopt. (Cit. on 5)
G. Johnson.
The NLopt
nonlinear-opsimmzzation
package).
D. Kingma and J. Ba. Adam: A Method for Stochastic Optimization. In ICLR, 2015. (Cit. p. 23)
J. Kotary and F. Fioretto. Learning constrained optimization with deep augmented lagrangian methods. arXiv preprint arXiv:2-03..33454 2024. (Cit. on p. 5)
F. S. Levitin and B. T. Polyak. Constrained Minimization Methods. USSR Computational mathematics and mathematical physics, 1966. (Cit. on p. 3)
V. S. Lokhande, A. K. Akash, S. N. Ravi, and V. Singh. FairALM: Augmented Lagrangian Method for Training Fair Models with Little Regret. ECCV, 2020. (Cit. on p. 5)
P. Mahdavinia, Y. Deng. H. Li, and M. Mahdavi. Tight Analysis of Extra-gradient and Optimistic Gradient Methods For Nonconvex Minimax Problems. NeurIPS, 2022. (Cit. on p. 4, 8)
A. Mokhtari, A. Ozdaglar, and S. Pattathil. A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach. In AISTATS, 2020. (Cit. on p. 2, 4)
T. Moskovitz, B. O' O'Donoghue, V. Veeriah, S. Flennerhag, Singh, and T. Zahavy. ReLOAD: Rein- forcement Learning with Optimistic Ascent-Descent for Ltst-Iterate Convergence in Constrained MDPs. In ICML, 2023. (Cit. on p. 4)
Pas, M. Schuurmans, and Patrinos. Alpaqa: A matrix-frec solver for nonlinear MPC and large-scale nonconvex optimization. In European Control Conference, 2022. (Cit. on p.
12

---

Published as a conference paper at ICLR 2026
A. Paszke et al. PyTorch: An Imperative Style, High-Performance Deep Learning Library. In NeurIPS, 2019. (Cit. on 3, 19)
J. C. Platt and A. H. Barr. Constrained Differential Optimization. In NeurIPS, 1987. (Cit. on p. 3, 5)
M.J. Powell. Method for Nonlinear Constraints in Minimization Problems. Optimization, Academic Press, 1969. (Cit. on p. 4)
M. Powell. The convergence of variable metric methods for nonlinearly constrained optimization calculations. In Nonlinear programming 3. Elsevier, 1978. (Cit. on 3)
A. Rakhlin and K. Sridharan. Online Learning with Predictable Sequences. In CoLT, 2013. (Cit. on p.3)
Ramirez, M. Hashemizadeh, and S. Lacoste-Julien. Position: Adopt Constraints Over Penalties in Deep Learning, arXiv preprint arXiv:2505.20626 2025a. (Cit. on p. 3, 10)
J. Ramirez, I. Hounie, J. Elenter, J. Gallego-Posada, M. Hashemizadeh. A. Ribeiro, and S. Lacoste- Julien. Feasible Learning. AISTATS, 2025b. (Cit. on p. 1,3)
A. Robey, L. Chamon, G. J. Pappas, H. Hassani, and A. Ribeiro. Adversarial Robustness with Semi-Infinite Constrained Learning. In NeurlPS, 2021. (Cit. on p.
R. T. Rockafellar. A Dual Approach Solving Nonlinear Programming Problems by Unconstrained Optimization, Mathematical Programming, 1973. (Cit. on p. 1, 4,
H. Shao, Y. Yang, H. Lin, L. Lin, Y. Chen, Q. Yang, and H. Zhao. Rethinking Controllable Variational Autoencoders. CVPR, 2022. (Cit. on p. 4)
X. Shi, Y. Xu, G. Chen, and Y. Guo. An Augmented Lagrangian-Basn -Based Safe Reinforcement Learning Algorithm for Orrented Optimal Scheduling of EV Aggregators. IEEE Transactions Smarl Grid, 2023. (Cit. on p.
M. Sohrabi, J. Ramirez, T. H. Zhang, S. Lacoste-Julien, and J. Gallego-Posada. On PI Controllers for Updating Lagrange Multipliers in Constrained Optimization. ICML, 2024. (Cit. on p. 1, 2, 4, 9, 10)
A. Stooke, J. Achiam, and P. Abbeel. Responsive Safety in Reinforcement Learning by PID Lagrangian Methods. ICML, 2020. (Cit. on p. 2, 4, 9, 10)
R. B. Wilson. A simplicial algorithm for concave programming. PhD Thesis, Graduate School of Bussiness Administration, 1963. (Cit. 3)
B. Zhang. S. Li, Hounie, O. Bastani, Ding, and Ribeiro. Alignment of large language models with constrained learning, arXiv preprint arXiv:2505. 2025. (Cit. on p. 3)
G. Zhang, Y. Wang. L. Lessard, and R. B. Grosse. Near-optimal Local Convergence of Alternating Gradient Descent-Ascent for Minimax Optimization. AISTATS, 2022. (Cit. on p. 2)
G. Zoutendijk. Methods of Feasible Directions: A Study in Linear and Non-linear Programming. Elsevier Publishing Company, 1960. (Cit. on p. 3)
13

---

Published as a conference paper at ICLR 2026
Appendix
Assumptions and Further Results
15
A.1
Assumptions
15
Dual Optimism on the Augmented Lagrangian A.2
15
On the Augmented Lagrangian Method
16
B.1
Gradients of L.
16
B.2
The Hessian of L.
16
B.3
Primal-first alternating gradient descent-ascent on Le
17
Experiments
19
C.I
Primal Iterates Match for Equality Constraints Scheduling of w in Dual Optimistic Ascent
19
C.2
20
Proofs
D.1
Equivalence Proof for Equality-constrail constrained Problems Equivalence Proof for
23
D.2
Problems
D.3
Further Proofs
14

---

Published as a conference paper at ICLR 2026
A ASSUMPTIONS AND FURTHER RESULTS
This section provides the formal definitions for the key assumptions used the main text (Ap- pendix A.I). We also present additional result showing that applying dual optimism directly the Augmented Lagrangian function produces compounding o-optimistic/penalyy effect, rather than giving rise to a completely new method (Appendix A.2).
A.1 ASSUMPTIONS
Assumption 1 (Strict complementary slackness). A stationary point (x*, X", ,²) of the Lagrangian said to satisfy strict complementary slackness if:
X and gi gx(")) or \ガ and gi(x") O, Vi I...., m..
(5)
Assumption (Second-orde sufficiency condition). A stationary point (a* x μ²") of L satisfies the second-order sufficiency condition if the Hessian of the Lagrangian is positive definite on the tangent space of the active constraints. That is,
d' V2 f(x"" p p O, Ad ERR {0) such that VgA, (a* and Vh(x*)d (6)
Note that any KKT point (x", A (²) satisfying Assumption 2 is a local constrained minimizer of Eq. (CMP) (Bertsekas, 2016, Prop. 4.3.2).
Assumption (Linear independence constraint qualification). point æ e Rd satisfies the linear independence constraint qualification if the matrix
[Vg., (x) Vh(x) has full row rank.
A.2 DUAL OPTIMISM ON THE AUGMENTED LAGRANGIAN
We further show that, for equality constraints, applying dual optimistic ascent to the Augmented Lagrangian produces compounding optimistic effect in the dual updates, without introducing any new phenomena.
Proposition 6 (Dual optimism on the Augmented Lagrangian equalities). Consider applying dual optimism to the Augmented Lagrangian La via primal-first alternating gradient rescenttoptimiist ascent with optimism coefficient w. The resulting primal iterates are equivalent to those of Eq. (AL- GDA) Lets and to those of Eq. (Lag-Ghl DDg-GDDOA) with optimism coefficient of +
Proof. See Proof of Proposition 6 in Appendix D.
This result demonstrates that the two frameworks are fully interchangeable for equality problems; one can reproduce the dynamics of the other by adjusting the hyperparameters accordingly.
While this equivalence is formally established only for equality constraints, we hypothesize that similar relationship holds for problems with inequality constraints. A formal analysis of this more general case is left for future work.
15

---

Published as a conference paper at ICLR 2026
B THE AUGMENTED LAGRANGIAN METHOD
For the reader's convenience, in this section we provide computations of the gradient, Hessian, and stationary points of the Augmented Lagrangian function (Eq. (AL)).
Recall the Augmented Lagrangian function:
Cx A. p) f(x) + || + ch(x)1l²
1
| + ||A + cg(x)]++12 |
(8)
2c
= f((x)= + 1 h(x)) + 2 |n(xx)12 Σ
(z) + {z)(()), A + cg.(a)
20 0
/c,
otherwise
(9)
B.1 GRADIENTS OF Le
The primal gradient corresponds to:
Vh(x)+ ). Vf(x)+ (m, + +ch())))VV(())++++++++)))+))++ Σ
m
if (c)
0,
otherwise
(10)
Vf(x)) + (me+ ch(x)) Vh(x) (Vh())))TV(()))>>+ [ + cg(x)) Vg(x)) Vg(x))
(11)
The dual gradients
= x)
(12)
and
m
gi (x),
if +cg(())
(.,
Σ
(13)
otherwise
1
(x),
if +c) 2
(14)
-dis
otherwise
1=1
\ + cg)(
if A +cg((x) 2 0
+
(15)
0.
otherwise
i=1
1
+ A + cg(x))]
(16)
Gathering these together, get:
V.C.(v, A, 1) Vs(x) + (ch())) (()()))))(((()++)))))))))))))))) + [A. +eg(a)]]
VeL,l2, A, 11) = h(x))
VxL,(2,
Σ
m
(ı()), if
(17)
ds/c,
otherwise
1=1
X
- c
B.2 THE HESSIAN OF L.
As can be observed in Eq. (17) in Appendix B.I, the gradients of L. with respect to and À not differentiable whenever some X; + cg.(x) is exactly 0. Therefore, we will compute the following Hessian derivations exclusively for (æe, X, (1) tuples with X; + cg)(==) of for every 1,..., m.
16

---

Published as a conference paper at ICLR 2026
Note that at any stationary (KKT) tuple (a: X 1²) of Le satisfying strict complimentary slackness (Assumption 1) falls in the set points with well defined Hessian, for all 0.
The Hessian of Le can be represented as a 3 x 3 block matrix:
V e
V Vaule
P&C
Am Lr
V A
V2 fic
(18)
Mam Le
V Ce
V rep ec
Let TA, be the set of indices for which X, tegi(x) 2 0, and let Ia_ = diag((A,) be the diagonal matrix containing these indicators.
The Primal-Primas Block C2). Le yields the Hessian of the standard Lagrangian evaluated extrapolated multipliers, plus quadratic terms:
V2C V2L A+e ( [h(x>) + Vg(z) Vg((t))
(19)
where V2 the Hessian the standard Lagrangian L:
[+tcg(e)) v2 f(x) (A + cg(x)) (u (++ch(x)) cg( g(xx)) (V (20)
The Primal-Dual Inequality Blocks Le yields the Jacobian of inequality constraints for those satisying the inequality A + cg. 2 and O for the rest:
L. and Va Co). Differentiating VaLa with respect to À
Va Vg(x) LA_
(21)
It also follows that
VhoLo = LAg Vg(x)) [2
(22)
The Primal-Dual Equality Block (V2 Cu and V Lod. Yields the Jacobian of the equality constraints:
2 vap = Vh(x))
(23)
with
V2 CocCe C. Vh(x) [V [o
(24)
The Dual-Dual Inequality Block (V Co)) Differentiating VxCa with respect gives:
1 (LA_ (IA--1 - - (A-
V
(25)
All other blocks are zero as the corresponding gradients do not depend the other dual variables:
Vy = VuuCe = 2 us = 0.
(26)
Combining all the blocks gives the full Hessian of the Augmented Lagrangian function:
V2C.
Vg(x)
Vh(x)
A IA Vg(=)
I
0
(27)
Vh(x)
0
0
B.3 PRIMAL-FIRST ALTERNATING GRADIENT DESCENT-ASCENT ON L.
Primal- first alternating gradient descent-projected gradient ascent on the Augmented Lagrangian Ea has the following structure:
Ee+1 <- Tt 1/m V C. dt, Me)
Pu+ <- it + 1huul V Vu de, pe)
(28)
A <- A + Tdual VXLo X4 Me)
17

---

Published as a conference paper at ICLR 2026
Using the gradients computed in Appendix B.1, produce the primal gradient descent update:
x++1 t It ? Vf(z)) + (m + cc(xz))) Vh(xz) + [ t Vg(zi)
(29)
Moreover, the dual ascent updates correspond to:
p1+1 < Pe + Naual / (I(+1);
(30)
and
d + [r cg(x++1)1+ 1
A411 f
de + Ndual
(31)
Ikhnal
A +
Vkiual
A + ccg
(32)
A
Miäull
A + cg(at+1)
(33)
The last step follows from the fact that the update before the projection consists of convex combina- tion of two non-negative terms whenever Muual S c, and thus it itself remains non-negative.
Note that the ascent update with respect À reduces to the usual Augmented Lagrangian Method ascent update whenever 7ddual
c:
[A cg(
A41
(34)
Gathering these together, we get the gradient descent-ascent updates on L. from Eq. (AL-GDA),:
01+1 f- xz 1h
vf(x)) + (m + ch(xx)) Vh((x)) + [hx (((x:)]]
(35)
M441 f- fh "N
(36)
A441 f- (1 Rdual
A +
Ndual
de + cg(
(37)
c c
18

---

Published as a conference paper at ICLR 2026
C EXPERIMENTS
We consider a simple ID equality-constrale problem to illustrate our theoretical results. In Appendix C.I, numerically corroborate the equality-constrriined equivalence Theorem 1; in Appendix C.2, we support the hyperparameler--uninn discussion in $4.3 by applying classical Augmented Lagrangian penalty schedule the optimism coefficient dual optimistic ascent.
We consider the following constrained optimization problem:
1 x² subject ex x 2
min
(38)
We formulate the constraint as h(x) = ex e rather than the linear form x 1= This ensures that the constraint gradient Vh(z) e" depends the iterate, creating nonlinear optimization landscape where the equivalence hetween methods is non-trivial. The solution is x = 1.
All experiments the hyperparameters in Table 1 and were implemented in PyTorch (Paszke et al., 2019) with Cooper (Gallego-Posada et al., 2025). Our code is available at https://gttuub.com juan-Shamireezpi-ccotto-.ii alm.
Table Hyperparameters used for all experiments.
Primal Optimizer
Momentum
Ndmll
w/c
Zo
ALM multipliers
GD + Polyak Momentum
0.01
0.5
0.1
1.0
2.0
0.0
We use gradient descent with Polyak momentum (rather than vanilla GD) for the primal optimizer to emphasize that our findings extend beyond the simple GD setup: any first-order primal optimizer preserves the equivalence (including Adam).
We initialize the multipliers for dual optimistic ascent and the Augmented Lagrangian method according to the change-of-variabhe varriablls rule in Theorem to ensure matching primal iterates:
HOGA
ALM HO
(c Idual) h(zo).
(39)
C.I PRIMAL ITERATES MATCH FOR EQUALITY CONSTRAINTS
Figure 1 numerically illustrates Theorem 1, comparing dual optimistic ascent in Eq. (Lag-GD- Augmented Lagrangian method in Eq. (AL-GDA), using the
OA) with the gradient-descent-ase hyperparameters from Table 1. As predicted, although the internal multipliers of the two methods differ, they produce identical primal iterates.
To provide intuition, we plot the "effective multiplier" used by each method that is, the value that enters the primal gradient when viewed from the perspective of minimizing the standard Lagrangian. For dual optimistic ascent, this is simply jst JGA, for the Augmented Lagrangian method, it is the extrapolated multiplier nn W + ch(x.).
The plots show that these effective multipliers coincide, visually reinforcing the equivalence. This cquality of effective multipliers is the key insight used in the proof of Theorem I.
19

---

Published as a conference paper at ICLR 2026
Primal Iterate (x)
Multiplier
AugLag-GDA Lag-OGA
AugLag-GDA Lag-
0.5
0.9
0.8
0.7
-0.5
0.6
Step
-1
Step
0.5
100
150
100
Effective Multiplier
AugLaa
Lag OGA
-0.2
-0.4
-0.6
-0.8
-1
Step
50
100
150
Figure I: Comparison of iterates for the Augmented Lagrangian method and dual optimistic ascent on the equality-constraine problem (e" = =e). As predicted by Theorem 1, the primal iterates Ie are identical.
C.2 SCHEDULING OF IN DUAL OPTIMISTIC ASCENT
standard way to schedule the Augmented Lagrangian penalty coefficient (cf. $2.3) is to use multiplicative heuristic (see Birgin and Martínez (2014, Eq. 4.9 in Alg. 4.1)):
7Cts
if [[++x))] > 31|h(I+11)11
c+1 =
(40)
Ct:
otherwise,
where 7 > 1 is the growth factor and E (0, 1) is the required improvement rate. It is also common to impose an absolute tolerance- not increasing e if the violation [f(x))] already below this threshold-te help avoid numerical instability.
To demonstrate that our theoretical connection useful for hyperparameter tuning, we adopt this same strategy schedule the optimism coefficient in dual optimistic ascent. Figure 2 compares dual optimistic ascent with a fixed w against a version with an adaptive schedule, using 7 2, 0.99, and an absolute tolerance of 10-2, We choose such a high because the scheduler is evaluated at every optimization step despite only one primal update occurring between checks- so the expected reduction violation per step is small, necessitating lenient improvement threshold.
20

---

Published as a conference paper at ICLR 2026
Primal Iterate (x)
Multiplier
Lag OGA (omega=
1) Lag OGA (schedulad)
Lag OGA (omega
Lag OGA (scheduled)
1.1
0
-0.2
0.9
0.4
0.8
-0.6
0.7
-0.8
0.6
-1
Step
Stop
0.5
0
50
100
150
Omega Coefficient
Lag (omega
Lag OGA (scheduled)
3
2
1
0
Step
50
100
150
Figure 2: Comparison of iterates for dual optimistic ascent with and without an ALM-inspired scheduler on the equality-constraing problem. The scheduled version reduces multiplier overshoot and allows the primal iterate to converge without overshooting the feasible solution.
D PROOFS
Lemma 1. Let k be constant. A tuple (x" X²) with X 2 satisfies:
X X + kk(g")()]
(41)
and only (x*, satisfies primal feasibility and complimentary slackness. That is,
g(x") =0 and x =0
(42)
Proof. "s." Let (x= X*) satisfy x [x* "g(x))) We analyze this relationship
component-wise, X = max (0, A + k (xx))))
If X; 0, then the equation requires X; X + k Dige (x=", which means ge gx(x") =
If N 0, then the equation becomes = max(0, 0 h (x) which requires k gg(" S O, and thus (x 0.
Combining these two cases, we have that gi (xx") S for (primal feasibility) and that for each i, either A = 0 or gx(x") = 0 or both. This is precisely the definition of complementary slackness.
"<="" Let (x: x*) satisfy primal feasibility and complementary slackness. We analyze the relationship component-wise for each i:
If X 0, then complementary slackness (x") 0) implies that (xx")) 0. In this case, the right-hand side the target equation becomes max(0, X; + = max(0, A = X The equality holds.
21

---

Published as a conference paper at ICLR 2026
If X 0, then primal feasibility implies that gi(=²) < 0. Since k > 0, we have k gxx))) _
0. In this case, the right-hand hand side becomes max + k (ggx(())) = max (0, gi(x")}
0 X The equality also holds.
Since the equality x; max(0, A; + k (x())} holds for all components i, the vector equation x A* + (g(x")) } is satisfied.
Proof of Proposition We will now show that stationary (fixed) points of algorithms Eq. (AL-GDA) and Eq. Lag--GD-OA) match, regardless of their hyper-parameter choices.
">"" Let (x', X", (x") be a fixed point of the Augmented Lagrangian dynamics of Eq. (AL-GDA). It follows that:
14 11" + (xa==))
(43)
X (1 Iduual
x + Tdual
X + cg(x*)
(44)
These equations imply primal feasibility and complimentary slackness, In fact, from the first equation, _e fe + h(=" implies that h(xx" O, and since Mddall 0, we must have h(#*) 0.
This is primal feasibility for the equality constraints.
For the second equation,
simplify:
A
=
Adual
X" +
Idiual
A- + cg(x"))
(45)
Iuall
x- ndual
X + cg(lx")) }
(46)
c
c
X = X + cz("))
(47)
As a consequence of Lemma 1, this condition implies both primal feasibility for the inequality constraints (g(x*) 0) and complementary slackness (x*") = for all i).
Primal feasibility can be used to argue:
μ¹ = 1² + cch(x"),
(48)
since > 0. Together with the fact that X 1X* cg(x") }} it follows that:
x² = xx The Vf(x") + [ + "cg(z")) vg(x*) + (μ" + +ch(x")) vh(z*))
(49)
x
vf(x") (A*) Vg(x") + (1x") vh(x")]
(50)
which corresponds to the primal stationarity condition of dual optimistic ascent in Eq. (Lag-GD-OA) and also simply means:
VaL(x" X " 0.
(51)
We have thus established that (x", A3, 1²") is a KKT point of Eq. (CMP).
Finally, we show that the dual variables are also stationary under the optimistic ascent dynamics. At the fixed point (x" X² 14",, ) we have x; = æ1-1 = The dual updates from Eq. (Lag-GD) GD-OA) therefore become:
μ 14 + Adual fe (xx) + w (h(x*) - hx(x)))
(52)
X = x Thaml g(xx) )= + (g((x") g( })
(53)
The update for μ1" simplifies ==== 11" hx=)) As primal feasibility requires h(*")
this becomes μz" = μ=",, which is trivially satisfied.
The update for stationary X simplifies to X" [X Namll g(x") } This condition holds due to
Lemma 1 and the combination of primal feasibility and complementary slackness proved above.
22

---

Published as a conference paper at ICLR 2026
Since the stationarity conditions for the primal variable and the dual variables À and all met, the tuple (x","", ,²" is fixed point of the dual-first optimistic ascent dynamics Eq. (Lag-GD- OA).
"=." Let (x', A", 14)) be fixed point of the dual-first optimistic ascent dynamics of Eq. (Lag-Gil OA). At a stationary point, the optimistic term ( g ((++-1) vanishes. Therefore, the fixed-point conditions are:
Pr μ + Thhual 12 (xx')
(54)
X X + Iauull g (a=))
(55)
x²' T [V(x2) + (2*) Vg(x") + (1*) Vh([=)]
(56)
From these three conditions, we can deduce that the tuple (x*, X (²) must satisfy the KKT conditions:
1. From the is condition, we get fx(=))
2. The À update condition, X = A + Aaual g (xx"))))))))))))()) )]] together with Lemma 1, iimplis both
primal feasibility for inequalities and complementary slackness.
3. The æ update implies that the gradient of the Lagrangian is zero: Va (*' , 0.
Now will show that this KKT point is also fixed point of the Augmented Lagrangian dynamics in Eq. (AL-GDA).
For μ.: Primal feasibility implies μ² = 1= + Vidual ft
For A: Primal feasibility and complimentary slackness imply X" [X* + cg(x"))
(Lemmaa 1). This in turn implies:
X Mdual
Thdual X" = [1-Adtml)
?ddual
Adual
x + eg(x"))
(57)
The primal update for the Augmented Lagrangian method is stationary if the gradient term is zero:
Vs(x") + [ + cg(x")) [ Vg(x") + (1r + +ch(a")) Vh(x")=+ =0
(58)
But argued before, X X cg 14 and n= n² + cc(("") Therefore:
Ví(m") + (X*) Vg(x") Vh((')) = " 11)
(59)
From the Eq. (Lag-GD-OA) fixed-point conditions, we know this term zero. Thus, the primal update is stationary.
Since the stationarity conditions for the primal and dual variables are met, the point (x" p²)) is also a fixed point of the Augmented Lagrangian dynamics. This completes the proof.
D.1 EQUIVALENCE PROOF FOR EQUALIT--CONSTRAINED PROBLEMS
Proof of Theorem 1. Consider the following primal-first alternating gradient descent-ascent updates on the Augmented Lagrangian:
L14 <- MinStep Zts Vf(x,) + (HLALM)) +ch(x,)) Vh(zz)). Tvh(z.)))T((...)
(60)
(ALM) 1+1
(ALM) Mual h (I1+1)--
<- f4:
These analogous to Eq. (AL-GDA), but stated for generic first-order primal minimization step MinStep. This step could, for instance, be replaced with Adam (Kingma and Ba, 2015), and the remainder of the proof would still hold.
23

---

Published as a conference paper at ICLR 2026
Now consider the following dual-first alternating gradient descent-optimistic ascent updates on the Lagrangian, similar to Eq. (Lag-GD-OA):
M2+1 < 14
(OGA)
(OGA)
"]duall h(x;)) w (h((a))) - ho(x:-1));
(61)
L++1 t MinStep (I vf(x,) + (1(411) Vh(xz))
Suppose w We show by induction that the primal iterates {0, j generated by the primal-first ALM algorithm and the dual-firs OGA algorithm are identical. Inductive Step. Define:
(OGA) M++1
(ALM) + ch(x))) pt
(62)
With this substitution, the primal update in Eq. (60) becomes
L(+1 MinStep Tt. ff(x)) + (MoiNN) Vh(zi)
(63)
Minstep æt; VaL (t 14+11 ((a (
(64)
i.e., descent step on the Lagrangian with multipliers M4+1 For the dual update, we have
(OGA)
Mi+1
(OGA)
14
(ALM) + +c ch(at)
(65)
11-1 + Thiml h (2t) cx(e))
(ALM)
(66)
(OGA) ch(xx=11))))) + Mumul h (xx;) + cx()))
(67)
14, (OGA)) Tadual h (x.) c(((x.)) h(x.-1))
(68)
which matches the optimistic ascent update in Eq. (126) with with Eq. (63) yields exactly the algorithm in Eq. (126). Thus, if the primal iterates generated by both algorithms match up until step they will match step + 1 under the change of variable (OGA) 1c+1 nu (AAM ch(x,).
Combining this dual update
Base Case. We establish the base case for the induction by showing that the first primal iterates, #1, identical under the specified initializations.
The primal descent update for Eq. (125) corresponds to a descent step on the Lagrangian with an effective multiplier of uo descent step on the Lagrangian with an effective multiplier of 11 (OGA) For the first step, the difference term in Eq. (126) is typically set to zero (as h(x=1) is undefined), so that
(ALM) + c (xo). The primal descent update for Eq. (126) corresponds to
#1 (OGA)
(OGA) Tiual hxxx). 14
(69)
For the primal iterates to be identical, their effective multipliers must satisfy
(ALM) + ch(o)) = 1 (OGA) + Taäml (aro)-
(70)
This equality is ensured by initializing the OGA method relative to the ALM method
Huu
(OGA)
14
(ALM) + (c Taaal lx(
(71)
With this initialization, both effective multipliers for the first primal update are identical, yielding the same first iterate for both algorithms:
Φ Minstep (2. fx + (MLALM) +ch(xo)) T (h(zz)).
(72)
Combined with the recurrence in Eq. (63), this initial condition implies by induction that all subse- quent primal iterates v, also coincide. Therefore, the two algorithms are equivalent.
24

---

Published as a conference paper at ICLR 2026
D.2 EQUIVALENCE PROOF FOR INEQUALITY PROBLEMS
This subsection provides the full proof of Theorem 2, which establishes the equivalence of the locally stable stationary points (LSSPs) for the algorithms in inequality-constrained problems. Our proof strategy is as follows: in Lemmas and 4, we first derive the Jacobians of the update operators defined by Eq. (AL-GDA) and Eq. (Lag-Gl GD-OA), respectively. We then derive their corresponding characteristic polynomials in Lemmas and 5. Finally, in the main proof of Theorem 2, we establish a relationship between the roots of these polynomials, which govern local convergence when w c.
Lemma 2. Consider primal-firs. alternating gradient descent projeettd gradient ascent the Augmented Lagrangian from Eq. (AL-GDA), applied to a problem with inequality constraints only:
1t+1 It - [f(xx)) - [2, + cg(xx)] Vg(xe)
(73)
A411 (1 Idduua d; + Ildual Ax + cg(ax++))
(74)
with Ndmnl <
(a" X²) ) be a stationary (KKT) point of Eg. (CMP) satisfying Assumption 1. The Jacobian of the update operator in Eq. (73), evaluated at (x*, x)) and acting the partitioned state
(It, At, )e,1) 1 (14+1, A4ILA A4t1,1;
is
I-
(A A c BB)
-Ta B
Jat.
Aduall (II na (A+ c I
nw Aduat BBT
(75)
0
0
(1 /duat/
Here, A = (DenAs ) partitions the multipliers into active components
At.A. {Ax (ellg((()))) 0, X > 0},
and inactive ones
= = ( <0, X; =0}-
Under the same partition, applied to the constraints g(x) (g) ,gr the matrices are
22 120( X²) v2 f(x)) + Σ x "
(76)
iEAm
B = (
(77)
Proof. The Augmented Lagrangian method in Eq. (73) alternates between primal and dual updates, beginning with the primal variables. It can therefore be written as the composition of two operators, one for each step. The Jacobian the full update is
JAL JxJa.
(78)
where Te and Jx denote the Jacobians of the primal and dual steps, respectively.
The Jacobian of the primal step (xt, A)) + (x Ac) is
Jn Th 22 7a V CexCo
(79)
I
and the Jacobian of the dual step (Ie+1, Ae) + (I++1 Aet1) is
0
JA
(80)
Ndual 2 Le Mduall V3Co
The primal Jacobian is well defined for any (æ,, A,) with X 2 0 whenever Xτ, cz,, # 0 for all constraints = 1, 1,..., m. Similarly, the dual jacobian is well defined whenever X + cc * O. In particular, both Jacobians well defined at (ax*. X²) due strict complimentary slackness.
25

---

Published as a conference paper at ICLR 2026
Multiplying gives
I 11 Ce
1/o V2 axLe
TAL.
7/e Muall V (o) Go)
(81)
V2 Aue Lo (I 1/ 1/ Vafo) I Tkdual V Cc
Vidual
To recover the structure of JAL. evaluate V Va Cox and V L. at (x* A²). Explicit forms of these terms at generic (ær, A) were already derived in Appendix B.2.
We now partition the state (ære Ae) into (æt, Ar. At,r), where Ar, corresponds active con- straints at x= and X to inactive ones. This partition is well defined under strict complementarity
The primal Hessian (VgLo) Complementary slackness implies X [ + eggl"' +++ both for active and inactive constraints (Lemma 1).
Substituting into the primal Hessian (see Eq. (19)) yields
V² + (A V g((x") "eogg""*"""Vo." cVgAu(x") VgAe(x)) (V
(82)
AA+c
(83)
The primal-dual Hessians for active constraints are
2 Vedag Lo A VgAe (x') BT,
V ze la- VgA = B.
(84)
The primal-dual Hessians for inactive constraints vanish:
V
Φx Le A = 0, V lor =0
(85)
The dual-dual Hessian for active constraints vanishes:
V Le la O.
(86)
The dual-dual Hessian for inactive constraints is
V2 Le x x
T.
(87)
Substituting all these expressions, the Jacobian JAL. evaluated at (x", A²) = (x* A 0) and acting on the partitioned state (æt, Ar.AA )t.1).
I - Te (A + BT B) Thiual B(I na (n BT B))
Ya B
0
JAL
TI Tae Jdual BBT
(88)
0
(1
Lemma 3. The characteristic polynomial
pooylyeeristicoollyomill of the Jacobian JAL at (x", X*) from Lemma 2 is
XJx (o)( (=m(o)=(1
Tddual
Leel
-1)a - A (e((1 -a) -Iduatt)) B B) det - -T - (1m
(89)
Proof. The Jacobian JAL is block lower-triangular with respect the partition between the active subsystem (æ, AAa) and the inactive subsystem År. Its characteristic polynomial is therefore the product the characteristic polynomials of these two diagonal blocks.
Inactive subsystem. The bottom-right block corresponding to the dual variables of inactive inequality constraints is
JAL.1 = (1 7iuall
I,
26

---

Published as a conference paper at ICLR 2026
whose characteristic polynomial is
X (0) = (11 /aual o) Ir
(90)
Active subsystem. The Jacobian of the active subsystem is
I- To Cc
Tle B
JAL =
(91)
Miuua - 7a ( cB I
na noull BB
This matrix is similar to
I -- A - (e + Mdmil B B B
J'L,A
(92)
Iddual
via the transformation matrix
-iäul B 9)
P
(93)
The characteristic polynomial of the active subsystem is found by computing the determinant of T J'L.Aa - aT:
T/e A
"m (c + Thimal B aT.
-1 B (1 (1-0)T)
X. (a) det
(94)
Adual B
Let the blocks of the matrix be denoted M11, M12, M21, M22. The bottom two blocks, M21 1] B
and M22 = (1 - TT commute since the identity matrix commutes with any matrix. We can therefore use the block determinant identity det(M) det(MMnMe M12
We first compute the product M22:
Mn M22 ((1 - r) - T/e A (/ + Naual) BB B) (1 -o)
(95)
=(1 o ne (1 σ)A A (c c. + Tdtual (1 - -O) B.
(96)
Next, we compute the product M22
M12 = (- (Tddm Mom B B.
(97)
Subtracting the second product from the first yields the matrix M11 M22 - M12M21
(1-a) n - o [n (c + (1dua) -1 noe ) B B.
(98)
We simplify the coefficient of the term:
The (c+ Tidual (1 (1-o) 0) Viuua The [c(1 o) Taaal (1 (1-o) Mduaal 1/ (c(--00) M)ual (99)
Thus, the characteristic polynomial of the active subsystem is
XJAL.Ae (a) det ((1 (11-))² r) The (1 o A Tie (c(1 o) Titual B)
(100)
Therefore, the characteristic polynomial of the full Jacobian JAL is the product of the polynomials for the active and inactive subsystems, X.Aa. (o) = X.Ta,, XJTr.. (o), which gives the final result.
Lemma 4. Consider dual-first alternating gradient descent-projectel optimistic ascent the Lagrangian, analogous Eq. (Lag-GD-OA), applied a problem with inequality constraints only:
A411 Xe Ndmal g g(x.)) ) + (g(x)) -((x--1))
(101)
Pt++1
The Vf(x;) Vg(x:)]
(102)
27

---

Published as a conference paper at ICLR 2026
Let (x" ,X)) be stationary (KKT) point of Eq. (CMP) satisfying Assumption 1. The Jacobian of the update operator in Eq. (101), evaluated at (x* x)) and acting on the state
(2), 1t-1; Ae x,,1) b (0 Dt, A441, X X1-1,1)
- A/ A (Tduat + w)B B Naw B
B
TJ B
T
II
Tog
(103)
(Adial + w)B
B
I
0
0
0
Here, as in Lemmas and 3, the multipliers are partitioned as x = (ainA,,e,111 where the active components are
Xe,A, {> (((xx()())))))))))))(())))) 0, x > 07,
and the inactive components are
- l:(a") <0, 1; =
Under this same partition of the constraints g(x) = I9 (x) .g(()))))))))))) TT, the matrices are once more defined
= VaL(i = f2x()) + Σ \("))(²")
(104)
iEAA
B (o')
(105)
Proof. The dual-first optimistic ascent method Eq. (101) alternates between updates of the dual and primal variables, beginning with the dual step. Accordingly, the overall update operator can be written as the composition of the two corresponding operators. Its Jacobian is thus
JoG = JnJA.
(106)
where Jn and JA denote the Jacobians of the primal and dual steps, respectively. Since the dual update depends both æ; and 1 evaluate these Jacobians on the augmented state
(ae, Bt Ac) (Z++ Brs A441).
(107)
The primal Jacobian is well defined for any (I), a. Aet1) with A4t1 ž 0. In contrast, the dual Jacobian well defined only when
A + Tamal (:())) + w (gi(x))) ge (:( # 0.
(108)
At (xt, ax" X²) this condition holds due to strict complementarity Indeed,
Xj + 7/aal gi(x=) w (gi(x=) gi(xz)) X + MMual Is (x
(xx) ) + 0.
(109)
At this point, two cases arise:
Active constraints (A; > 0 and gx(")) 0). Then
[X] Tdtul gi (x( }]+ [X]]+ A
(110)
Inactive constraints (Aī and (x(x=)) 0). Then
[ 7Jäull 9:((=" ) [w>::(>=))
X
(111)
In both cases, the projection condition reduces whether X; > 0, i.c. whether the constraint is active at x Thus, we adopt the same partition A, (Ar.A ),,)) as Lemma 2, and reuse the definitions of A and B.
28

---

Published as a conference paper at ICLR 2026
It follows that the Jacobian of the dual update, acting on the augmented and partitioned state (a), It-1, An. (1,)) + (Ie, 2t-1, A A4t1,1) and evaluated at (a", x=' A 21).
0
1
0
0
Jx
(112)
(Mdaal + w
w
1
0
0
0
while the Jacobian the primal update,
(at, Ft A d d411,) + (I++1, Rt; A A4t1,))
(113)
evaluated (x* x², Aa A7), is
- 1a BT
7a
0
0
0
Jx =
(114)
0
1
0
0
0
Multiplying the two blocks yields
7x
7/ (Niual + +w)BT B
Bowi B
B
The T
11
0
Joa
(115)
(Naml + wwB
B
II
0
0
Lemma 5, The characteristic poyyionaiisiicolyynnnil of the Jacobian Jog at (x", (x)))foro from Lemma is
XJoo(o) = (-o))mlAul+++ det ((1 ((1-)) o0) 7 o)A - 7a (w[( σ) -d B B)
(116)
Proof. The Jacobian Joa is block lower-trianullar with respect to the partition between the ac- tive subsystem (Ie, 31-1, A..Ae) and the inactive subsystem Å, Its characteristic polynomial is therefore the product of the characteristic polynomials of these two diagonal blocks.
Inactive subsystem. The bottom-right block corresponding the dual variables of inactive inequality constraints is Joa,1 = O. It's characteristic polynomial is
X (a) det((0 oT) det( Loet--oTuae oTDT) (-o)
(117)
Active Subsystem
The Jacobian of the active subsystem, which maps (we, 0z-1, demAd) + (E++1, Bt, A,.1,a),
I A noe (Mdual + B.BBB.. T B
Nnw B B
JoG.A
(118)
(Aiuual w)B
w B
I
We seek its characteristic polynomial, XJoorAa (0) det(Joo.Aa with blocks My.
o1). Let M JoG.A. oll
1x M 11- ---neA- The (Mdual + +w) oll
Naw BT B
-al 0
(119)
(Aama w) B
-w B
(1
To simplify the determinant calculation, we apply determinant column operation,
C2 C2 + oC,, which zeros the (2, 2) block:
Mi
M1a + Min
M13
M
Mia
M13
det(M)) det
-al+ all
O
det
0
(120)
Ma1
M32 + Mai
M33
M31
M/2
Maa
29

---

Published as a conference paper at ICLR 2026
where M12 M12 + oM1 and M22 = Maz + MMM. Swapping the first two block rows (corre- sponding to 21+1 and xx) multiplies the determinant by (-1)", yielding a block upper trianglaa matrix:
Mii M2z
M13 M33
A1 (0) (-1) ( det
M11
M13
(-1)) (T)(T) det
(121)
M31
M33/
Since M33 = (1 II a multiple of the identity matrix, it commutes with other blocks. We can thus compute the determinant of the remaining x 2 block matrix as det M M33 M22 Let's compute this product:
Mas M13M22
= (M12 + aMMi) M23 + oss1))
(1 -1--07 (M oM11) M13 (M32 0M33)
= =(1 (1_oo( + a(l 7 - 7a (Tduaal + w B - --ol))
((- B ( - - + 0 (Miiial + B)
= o - 0) - 7 o)A
+ [11 - 1zww o(1 Toe (fddual w) - 1lo + ofh oT w) BTD B
a(1 - 0) 1 o)A
+ 1/2 [W ow TT/cmal - ow + 0² Tddmll + oz w + JT]duual + ow) B TBD
=a - 8 - 1/ (1 - A + 1/e Idual ow(1 o)] BTD
=a - 0) 1 o)A To (w o) 7 B B.
The determinant of this d x d matrix is: det M33 - M13 Mx2) = a det ((1 0) - 11 - o A- - (w(ww(1 - -a) - -Ndual (aaat))B B3 B)
(122)
Substituting this back into the expression for XJoc.An
AJoo.Ae (a) = (-1)² aa det (...)
(123)
= (-o)² det ((1 - ((1-o)21-
n1 [1 -IA - Tae (w[(w11 o) 7mmal B B).
(124)
The characteristic polynomial of the full Jacobian Tog is the product of the polynomials for the active and inactive subsystems, X (o) X (σ) X.Ja..A, (σ), which gives the final result. O
Proof of Theorem 2. Consider the following algorithms for solving incquality-coostrained problems:
! Eq. (AL-GDA): Primal-first alternating gradient descent-projected gradient ascent on the Aug- mented Lagrangian,
3++1 It ---Yaa The [f((x))+ [Ar + +gg(x))) v
(125)
Aet1 (1- Nduul d Adual Ae + cg(
where 0 < Mual S c.
2 Eq. (Lag-GD-OA): dual-first alternating gradient descent-projected optimistic ascent the Lagrangian,
A411 +- [>ee + Muui (xx)) + ((((x))) - g(xx-1)))
(126)
014-1 f- C. Th Vf(x)) + NJ Vg((x)).
where >
30

---

Published as a conference paper at ICLR 2026
We will analyze the local convergence properties of both algorithms at stationary (KKT) point (a", A*), satisfying Assumption 1, and operating on a partition of the À = (Aa. Az) state into those corresponding to active and inactive constraints at x":
A= {xx (x(x))
0, X > 07,
and inactive ones
X {>x (:(xx)) 0, X; = 0}
Let the matrices A and B be defined the stationary point (x" A*) as
A = C(a",, X*) and B = VgAe (x");
(127)
where A is the Hessian of the Lagrangian with respect to æ and B is the Jacobian of the active constraints.
From Lemmas and 3, we know that the Jacobian JAL of the Augmented Lagrangian updates in Eq. (125), acting on the partitioned state (xe, Ae.A ),,1) (It+1. A411,A, 1,1, At+1,1) and evaluated
at (x", x²) = ( 0), is
I Fe + C B)
Va B
JAL
Mhiull (II ne (A c BTB))
II
Tae Aa BB
(128)
0
(1 Mc)aI//)III
and that the characteristic polynomial for this Jacobian is:
XJa. (a)
(1-
Minal
m
[Aul m-Aal
det ((1- 1ll-a) o) 1--1-10 71 - o)A 10))A-((((11 - -0)
O B B) (129)
Moreover, from Lemmas 4 and 5, we know that for the same choices of A and B matrices, it follows that the Jacobian JoG of the dual optimistic ascent updates in Eq. (126), acting on the partitioned state (ae, It-1, Ae,Au )e,1) + (It+1, Ft, I.A, A+t1,1) and evaluated at (x" x*) (x" x AAA
is
neA neo (Neall + w)B
New B
nw B
II
0
0
Joa =
(130)
(Ndill w)B
11
0
0
0
0
and that the characteristic polynomial for this Jacobian is:
XJoo (o) (-o))1zl+d det ((1 - o) - n 1 o)A - 1/2 (wo(1 0) Mltaal BT) B), (131)
Remark on the a = case A subtle but important point is that, although the structure of these characteristic polynomials might suggest
could be root if det B) 0, it can be shown that a 1 is in fact not an eigenvalue of either JAL or Jog under Assumptions 1 to 3 --oodiitions that are generally necessary, though not sufficient, for convergence.
We establish the equivalence of the local convergence properties of the two algorithms by setting the optimistic parameter w = c and comparing the characteristic polynomials of their Jacobians.
Upon setting in X (ar), the non-trivial determinant term becomes identical to that in XJa. (a):
det ((1 2 The (1 - σ).A - The (c(1 - a) M)mal))) B):
(132)
The roots this determinant define the set of non-trivial eigenvalues, which are shared between both methods. Local convergence of either algorithm depends whether all these shared eigenvalues lie within the unit circle.
The remaining eigenvalues given by the roots of the other factors in each polynomial:
31

---

Published as a conference paper at ICLR 2026
For the Augmented Lagrangian method, the factor (1 Mital - -o) [rl yields [T eigenvalues at a ]]uual c. Given the condition 0 TJdual c, these cigenvalues lie in the interval
(0, 1), and are thus stable.
For the optimistic ascent method, the factor (-o)l yields [ + d eigenvalues at a 0, which are also stable.
Conclusion. Since the non non-trivial eigenvalues governing convergence are identical for both algo- rithms, and the remaining trivial eigenvalues for both are stable, the spectral radius p(JAL) < and only if p(Joo) < 1. Therefore, with the choice of w one algorithm converges locally if and only if the other one does.
Moreover, it holds that:
P(TAL) = max(p(Joo), 1 -h
(133)
This implies that the shared eigenvalues dictate the convergence rate (i.e., when p(Jog) 2 1 /c), both algorithms converge at the same local rate.
D.3 FURTHER PROOFS
This subsection includes the proofs for Prop. 3 (ALM finds all constrained minimizers) and Prop. (ALM finds only constrained minimizers).
Proof of Proposition Let X 2 0 and j=" the optimal Lagrange multipliers for xt such that (xx", X², (x") form KKT point of Eq. (CMP). Since x" satisfies Assumption 3, these multipliers exist and are unique.
By Lemma 2, the Jacobian of algorithm Eq. (AL-GDA), acting the partitioned state
(we, Ae.Au Ac,1) + (#i+1, A441,A; Act1,7) and evaluated at (x* X*) (x Xi 0), is
I The (A + BTD) BB) Thdual BB nh (A CBBBBB B)) - The Tdual BB
Ta B
JAL
(134)
0
(1 T/dma//c)ll
where
A= V=
B = (g
(135)
This Jacobian is well-defined thanks to Assumption 1.
We now proceed by grouping equality constraints with active inequality constraints, considering the Jacobian on the state partitioned as (æ,, (Ar,Ag Ms), Ar.1). This yields the same Jacobian JAL. except B is redefined as
(VgA( Vh(x*)
A
B
(136)
We will now prove that under Assumptions 2 and 3, there exist c >> 0 large enough and T/e- M small enough such that all eigenvalues of JAL. lie within the unit circle.
>
JAL is block Nower-trianullan so its eigenvalues are the union of the eigenvalues of its blocks. The eigenvalues of the inactive inequality block Eq. (AL-GDA) that Naual S c, these satisfy |a| < 1.
1 qdta//c cc Under the assumption of
Setting 7) nr. Mdmi for simplicity, the upper-left block is
I- + BTB. B)
-1B
JAL.AA
(137)
I- 172 BBT
32

---

Published as a conference paper at ICLR 2026
As in Lemma 3, Aa is similar to
1 -1- 11---A(c+++ B)BBL B
-n I
JhinAe
(138)
nB
A + (c 1)) B B
=I-1
(139)
B
1) M.
(140)
By Prop. 2, under Assumptions and 3, there exists e such that A + cB B is positive definite. Hence + (c++n) B B also positive definite. By Bertsekas (2016, Prop. 5.4.2), M has eigenvalues with positive real parts, for sufficiently small r > all eigenvalues of JAL,A, satisfy lo 1.
Combining this with the inactive block, we conclude p(JAL. 1, completing the proof.
Proof of Proposition 4. Let (xx X .J=") be an LSSP of the algorithm in Eq. (AL-GDA). By Prop. 1, (xx" X², 11" is KKT point of Eq. (CMP). Moreover, we know that p(JAL) < 1, where
I na (A c B)
Ta B
0
JAL
Thiual
B(I na (A + e B
TTB. B)) I qa Kdual BB
(141)
0
(1 1dual /c)II
and
VgAA
v2 X²)),
B =
(142)
Vh(x")
as in the Proof of Proposition 3. The assumption p(JAL) < implics that p(Thi..A.) < 1, where
T JAL,Ao = -1- 1A- 17(c + B)B B
-1B
(143)
BB
I
similar the upper-left block of JAL. Here we set 7) 1/2 /uual for simplicity.
We proceed by contradiction. Suppose that x" is not a local constrained minimizer of Eq. (CMP).
Then (a: X² 14*)) must violate the second-order sufficiency conditions of Assumption 2 (Bertsekas, 2016, Prop. 4.3.2).
This implies the existence of nonzero vector E Rdd in the null space of such that
d Ad < 0.
(144)
By the Rayleigh-Rite theorem, choose d normalized eigenvector [|d]| 1) corresponding the smallest cigenvalue, of A restricted to the subspace {d Bd = 0}. By the assumption, S 0.
Consider the action of JAt.,Ae on the vector [d..0]] ,0]=
JAu (
(T 14 nlc+ B)B B)d nBd
-(d-nAd) nAd
(145)
using =d=0. 0.
Then
1
= ||d - sadll1 = ||d 2ny(d Ad) + A = 2naa + | 2 1,
(146)
since a 5 0 and ||d||== 1.
Thus, have found vector [d_, ,0] with unit norm for which T JAL.AA is non-contractive, contra- dicting the assumption p(JAt.) <
Therefore, our initial assumption that Assumption 2 is violated must be false.
33

---

Published as a conference paper at ICLR 2026
Proof of Proposition 5. This result adapts the spectral analysis of Benzi and Simoncini (2006), which assumes simultaneous updates, to our alternating- setting. Moreover, we explicitly derives the decay rate of the imaginary parts.
By Corollary 1, the cigenvalues of Jog are either trivial zeros- are always real- or coincide with the non-trivial eigenvalues of the Augmented Lagrangian Jacobian JAL. These non-trivial eigenvalues lie in the active subsystem (which we consider as including the equality constraints), denoted JA. Setting common learning rate 7/ T/e Voual for simplicity, we note that JAL.A=
is similar to JAL,A (as in the proof of Lemma 2), where
ThLiA (w) = - - (W),
(147)
with
M(w) ( A [ B
B ))
(148)
-B
where A and B are defined in the Proof of Proposition 3:
Vg (24))
A Vall"" X", H²),
B
Vh(x*)
(149)
Consequently, the eigenvalues (w) are real if and only the eigenvalues of (ww) are real.
Let a be an eigenvalue of M (w) and = [u u JJ= * 0 be its eigenvector. First, consider the case
0. The eigenvalue equations Mz oz become:
B v 0 and
ov.
(150)
If * 0, the second equation forces v 0 so 0, a contradiction. Hence any eigenpair with
= 0 must have a = O, which is trivially real, and we therefore disregard this case and assume
M 7 from now on.
We normalize such that u² 1. As shown in Benzi and Simoncini (2006, Prop. 2.5), satisfies:
o² - oouu u (A (w + + B)u n B Bu 0.
(151)
These eigenvalues are real if and only if the discriminant A,, (., 2 where:
(w) (A (w n) B)u 4u" Bu.
(152)
As function of w. (w( is quadratic with a positive leading coefficient (u" BT Bu)² whenever
Bu # hence, it is convex in w. Note that if Bu = 0, then B Bu 0 and (151) reduces
0² u Au=
(153)
whose roots are real for all w. We thus focus on directions where Bu * O.
We demonstrate the existence of single finite threshold @ such that for every eigenvector direction with Bu * 0 and every w 2 w. the discriminant satisfies A,(w) 2 0.
Let
alu) = u u'(A + TB B)u,
b(u)= = u B" Bu.
(154)
Then for all w,
u'(A + (w BTB B)u a(u) + wb(u).
(155)
and the discriminant simplifies to:
Aa(w) = (a(u) + 2 4b(u).
(156)
Since Bu # O. we have b(u) > O.
Let Ymin and 7max denote the smallest and largest nonzero eigenvalues of T B, and let be the largest eigenvalue of A + nB¹ B (restricted to the relevant subspace). By Assumption 3, 7min >> O.
Then, for any unit with Bu #0.
7min S b(u) S Tmax and [a(u)] S
(157)
34

---

Published as a conference paper at ICLR 2026
Define
a' + 2 Tmax
(158)
7min
For any w 2 w and any unit u with Bu + 0, we have
wb(u) - |a(u)] Wimn
Tmax 2vb(u),
(159)
where we used b(u) S Tmax- Hence,
(a(u) + wb(u)] 2 wb(u) [a(u)] 2 2
(160)
Substituting this bound into the discriminant gives
(w) = (a(u) wb(u)) 4b(u) 2 (2vb(u)) 4b(u) 0.
(161)
Thus, for all w 2 w and all unit vectors u. with Bu + O, the discriminant is nonnegative and the corresponding eigenvalues
real. Hence all eigenvalues of (ww) are real for every 2 W. and therefore all non-trivial cigenvalues of JAL and Jog are real as well.
To study the decay rate of the imaginary parts as 1 w, consider complex conjugate pair of eigenvalues (w), (w) of (w) that becomes real some S W. At such a point, we must have
Au(wr) (w" = 0.
(162)
We assume generic non-degeneracy condition (ND): the corresponding eigenvalue is simple and
A n (w)
* O.
(163)
ow
Under (ND), Au(w) has a simple root at wn, and first-order Taylor expansion around w yields
(w( K w²) + ((w wn) )²)
K k
(164)
For w < wt sufficiently close to w", we have Au(w) (w) < 0. Substituting this into (151) yields a pair of complex conjugate roots whose imaginary parts satisfy
[w)(w)] // (w) OVV -w) w) t w"
(165)
Since there are finitely many eigenvalue branches-and and by construction, @ is the minimal threshold above which all eigenvalues are real-this bound is uniform over all complex eigenvalues of ((w) for w sufficiently close to a:
max (MM(
[So(w)) OVV@ w)
(166)
Finally, the eigenvalues of JAL (w) are of the form (w)) Since the non-trivial eigenvalues of (os(w) coincide with those of JAL (w)) we conclude:
(A(w)] |m]
max
[oo(w)] O(V -w)
(167)
Eope)))))))))
35


Reviews:
[{"review_id": "eqrmBWqcTd", "reviewer": "Reviewer_Wayq", "summary": "This paper considers constrained optimization problems with both equality and inequality constraints. After describing three primal-dual approaches for solving the problem (Lagrangian, augmented Lagrangian, and dual optimistic ascent), the paper then establishes theoretical equivalence results between the augmented Lagrangian method and the dual optimistic ascent approach, hence allowing the desirable properties of augmented Lagrangian to be transferred to dual optimistic ascent (also known as PI control). Discussions are also provided on the practical implications of this equivalence, including the choice of the optimism hyperparameter in dual optimistic ascent.", "questions": "- What is the downside of augmented Lagrangian (and dual optimistic ascent) compared to regular Lagrangian? If convergence properties are more desirable, why is the regular Lagrangian the most commonly used approach in practice?\n- Could you please clarify the statement on lines 224-225 on the replacement of the first dual update in (Lag-GD-OA) in practice? Is there a way to get around evaluations of $g$ and $h$ at $x_{t-1}$?\n- Is there a way to better formalize the Jacobian \"becoming real\" in Corollary 5 (e.g., via characterizing the rate of decline of the imaginary eigenvalues)?\n- I understand that this paper's contribution is primarily on the theoretical side. However, I believe some simple experiments on the differences between augmented Lagrangian and dual optimistic ascent in problems with inequality constraints, as well as dynamic tuning of the optimism hyperparameter by mirroring augmented Lagrangian penalty scheduling methods (as mentioned in lines 460-461), would be interesting and helpful additions to the paper.\n- I would suggest swapping the discussion on OGDA and ALA in Section 2 (i.e., discussing OGDA first and then ALA) for a better flow.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The paper is very well written and provides adequate background for an audience who may not be readily working in constrained optimization/learning.\n- The provided equivalence results are interesting and could lead to significant follow-up theoretical and empirical research in constrained optimization, especially in the context of modern deep learning problems.", "weaknesses": "- There was no mention of how the results connect to the *parameterized* setting, where the primal variables are the parameters of a non-convex deep neural network architecture. Do you anticipate the results to have parameterized analogs under assumptions (such as near-universality of the parameterization)?\n- The results are limited to a single primal step per iteration (although this is, I believe, what is mainly used in practice).\n- The exact equivalence of primal iterates is limited to problems with only equality constraints.\n- No empirical results are provided to corroborate/complement the theoretical findings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "bEVDmrkMPL", "reviewer": "Reviewer_GKqh", "summary": "This paper establishes a theoretical equivalence between dual optimistic ascent (PI control) and the Augmented Lagrangian Method (ALM). Specifically, it shows that for equality-constrained problems, dual optimistic ascent on the Lagrangian is identical (in primal iterates) to gradient descent–ascent on the Augmented Lagrangian when the optimism coefficient ω equals the penalty parameter c. For general inequality constraints, the two methods share the same locally stable stationary points (LSSPs), implying the same convergence targets. This equivalence allows transferring ALM’s robust theoretical guarantees—especially linear convergence—to the dual optimistic framework, previously known mainly for empirical success. The paper further analyzes implications for convergence, stability, oscillation damping, and hyperparameter tuning.", "questions": "There are no other questions.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "This submission has novel and elegant theoretical contribution. The main equivalence result is new and insightful: it unifies two popular but seemingly different optimization paradigms. The insight that “dual optimism ≈ augmented regularization” is elegant and of clear theoretical and practical significance. This bridge justifies the strong empirical performance of PI-control methods used in deep RL and constrained deep learning.\n\nThis submission is mathematically sound and grounded in classical references. The local stability analysis via Jacobians is carefully argued and well contextualized. Theorems systematically extend the equivalence to convergence, oscillation damping, and conditioning, providing a unified picture.\n\nThe practical implications for tuning the optimism coefficient ω using ALM’s penalty intuition are particularly valuable. The discussion connects to recent empirical work in reinforcement learning and fairness-constrained training. This paper has some practical use in deep learning and LLM.", "weaknesses": "The most significant weakness of this submission is that this paper lacks empirical verification from numerical experiments. Although the theory neatly explains prior empirical results, no new experiments are provided. The reviewer suggest adding a simple numerical example (e.g., a 2D quadratic constraint problem or other simple constrained optimization problem ) showing the equivalence in iterates and the damping of oscillations. With the numerical experiments results, this can significantly improve the quality of this submission.\n\nOther minor weaknesses include limited scope for inequality constraints. The equivalence for inequalities is only local, and the intuition behind the “two projections vs. one” distinction could be expanded with geometric visualization or numerical illustration. \n\nAlso the assumptions (strict complementarity, LICQ, SOSC) are standard but a little strong. The paper could benefit from discussing whether relaxed conditions (e.g., weak constraint qualification) still preserve equivalence.\n\nThis submission didn't have discussion on Multi-step or Second-order ALM Variants The authors explicitly limit equivalence to single-step first-order methods. It is suggest that adding brief discussion about how multi-step variants (as used in practical ALM solvers) might diverge, or outline what breaks in the proof.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "sau7q1UOwG", "reviewer": "Reviewer_2hch", "summary": "The paper studies dual-only optimistic ascent applied to the standard Lagrangian. The central result establishes a precise equivalence between this method and gradient descent–ascent on the Augmented Lagrangian (ALM) when the optimism and penalty parameters are aligned. This equivalence holds at the iterate level for equality-constrained problems (under specific initialization) and, for inequality constraints, extends to locally stable stationary points, transferring local linear convergence and damping properties. The work thus generalizes the theoretical foundation of ALM-based gradient methods to the dual-only optimistic ascent framework, explains the empirically observed stabilization effect of dual optimism, and offers practical guidance on parameter tuning (e.g., matching optimism and penalty parameters) through the ALM perspective.", "questions": "Could the authors provide further justification or point the reviewer to references explaining why existing theoretical analyses of general min–max optimization are insufficient for this setting? It would also be helpful to clarify what specific advantages the proposed analysis offers over prior frameworks.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This paper reduces dual-only optimistic ascent to the Augmented Lagrangian Method (ALM), establishing a theoretical foundation for its practical use in constrained deep-learning pipelines. The theoretical derivation seems sound.", "weaknesses": "The generality of the results appears limited, as the analysis focuses on the specific setting of dual-only optimism with single-step first-order primal updates. Since the reviewer is not deeply familiar with the literature on constrained optimization via dual optimistic ascent, it is somewhat difficult to assess the broader significance of the contribution, especially given that the problem formulation seems rather specialized.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)