Semi-infinite Nonconvex Constrained Min-Max Optimization
Authors: Cody Melcher
Zeinab Alizadeh
Lindsey Hiett
Afrooz Jalilzadeh
Erfan Yazdandoost Hamedani
Venue: NeurIPS 2025 poster ()
Keywords: Semi-infinite Programming
Nonconvex Constrained Optimization
Min-Max Optimization
Primary area: optimization
TL;DR: Developing and analyzing a novel inexact dynamic barrier primal-dual algorithm for solving nonconvex min-max optimization problems with infinite constraints.

Abstract: Semi-Infinite Programming (SIP) has emerged as a powerful framework for modeling problems with infinite constraints, however, its theoretical development in the context of nonconvex and large-scale optimization remains limited. In this paper, we investigate a class of nonconvex min-max optimization problems with nonconvex infinite constraints, motivated by applications such as adversarial robustness and safety-constrained learning. We propose a novel inexact dynamic barrier primal-dual algorithm and establish its convergence properties. Specifically, under the assumption that the squared infeasibility residual function satisfies the Lojasiewicz inequality with exponent $\theta \in (0,1)$, we prove that the proposed method achieves $\mathcal{O}(\epsilon^{-3})$, $\mathcal{O}(\epsilon^{-6\theta})$, and $\mathcal{O}(\epsilon^{-3\theta/(1-\theta)})$ iteration complexities to achieve an $\epsilon$-approximate stationarity, infeasibility, and complementarity slackness, respectively. Numerical experiments on robust multitask learning with task priority further illustrate the practical effectiveness of the algorithm.

Semi-infinite Nonconvex Constrained Min-Max Optimization
Cody Melcher
Zeinab Alizadeh
School of Mathematical Sciences
Systems and Industrial Engineering
The University of Arizona
The University Arizona
Tucson, AZ 85721 cmelcherr@rizzona edu
Tucson, AZ 85721 zal salizadeh@arizona edu
Lindsey Heitt
Afrooz Jalilzadeh
Systems and Industrial Engineering
Systems and Industrial Engineering
The University of Arizona Tucson, AZ 85721 lhiett90arizona. edu
The University Arizona
Tucson, AZ 85721 afrooz0arizona edu
Erfan Yazdandoost Hamedani Systems and Industrial Engineering
The University of Arizona Tueson, AZ 85721 er arfanyCarizona. edu
Abstract
Semi-Infinite Programming (SIP) has emerged powerful framework for mod- eling problems with infinite constraints, however, its theoretical development the context of nonconvex and large-scale optimization remains limited. In this paper, we investigate a class of nonconvex min-max optimization problems with nonconvex infinite constraints, motivated by applications such as adversarial ro- bustness and barrier primal-dual algorithm and establish its convergence properties. Specifi- cally, under the assumption that the squared infeasibility residual function satisfies the ł.jjasiewicz inequality with exponent 0 (0, 1), we prove that the proposed method achieves O(E-3) O(e -60) and O(e (10((1)))) iteration complexities achieve an e-approximate stationarity, infeasibility, and complementarity slackness, respectively. Numerical experiments robust multitask learning with task priority further illustrate the practical effectiveness of the algorithm.
learning. We propose a novel inexact dynamic
Introduction
Recent advances in artificial intelligence (AI), particularly foundation models for language, vision, and multimodal reasoning, have revealed impressive capabilities and critical vulnerabilities at the same time. These models are often susceptible adversarial perturbations, leading concerns about their reliability and safety in high-stakes applications [26]. Similarly, ensuring robustness in domains such supply chain management and autonomous control systems requires optimization frameworks that can account for worst-case scenarios across a continuum of uncertainties. Semi- Infinite Programming (SIP), which naturally models problems with infinite constraints, provides powerful tool for addressing these challenges. However, despite its rich and extensive theoretical
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

and algorithmic development, comparatively less attention has been devoted to designing efficient first-order methods for emerging applications in modern Al and Operations Research.
Motivated by this gap, in this paper, we consider the following min-max optimization with infinite constraints:
min max p(2, v): #E8" NEY
s.t. (xx w) S O, Ve E W,
where < R R R and vb R" X R + R are continuously differentiable functions. Moreover, Y C Rm W C R are convex, non-empty, closed sets. Problem (1) arises in wide range of applications, including robust optimization [5, 7], distributionally robust learning [59], and adversarial machine learning [50, 60]. In these settings, we aim to optimize against worst-case scenarios while ensuring that an infinite family of constraints is satisfied. Such constraints often encode safety, fairness, or robustness requirements that must hold uniformly over a continuous set of parameters.
To develop efficient algorithms for solving problem (1), it is critical to recognize the distinctive structural complexities introduces and why existing approaches are insufficient. The problem combines features of min-max optimization and SIP, resulting in constrained min-mac optimization problem with an infinite set of nonlinear constraints. While min-max problems and SIPs have been studied independently, their intersection in (I) poses unique challenges. Standard first-order algorithms for solving min-max problems typically assume finite-dimensionll constraints without nonlinear constraints, whereas SIP approaches often assume convexity lack the nested max structure in the objective. Moreover, the presence of inner maximizations in both the objective and constraints renders traditional gradient-based methods constraint sampling techniques inadequate, particularly when & and/or 1a are nonconvex in J. This calls for new algorithmic strategies that can simultaneously handle the nonconvexity, the infinite constraint set, and the nested structure of the problem.
In the following, we review relevant literature in each of these areas to highlight existing methods and identify the challenges that arise tackling problem (1).
1.1 Literature Review
Nonconvex constrained optimization.
Consider the following constrained optimization problem zeX
min f(z)
s.t. 9(x) <
where f: RR + R and g: 1 R are continuously differentiable, but not necessarily convex, and X C R" is a closed convex set. When f(-) is nonconvex and the constraints gi 's are either linear or convex inequalities, a range of algorithms have been proposed, including penalty methods, Lagrangian methods, and augmented Lagrangian methods [30, 33, 28e. study of optimization algorithms for non-convex constrained problems has a long history, including analyses of the global asymptotic convergence of methods such as Augmented Lagrangian method [6], Augmented Lagrangian trust- region [14), and Sequential Quadratic Programming [20], among others. However, due to the nonconvexity of the constraints, these methods may converge to infeasible stationary points. To ensure convergence to feasible stationary points, additional assumptions are typically required. For instance, assuming access to (nearly) feasible solution, several methods have been developed to find an KT point within O O(e-a) iterations [49, 40, 66). With further regularity conditions, the complexity can be improved to O(e-3) for these methods and others, such as [39, 47].
More recently, the dynamic barrier gradient descent (DBGD) method [25] has emerged principled alternative, incorporating barrier functions that smoothly penalize the constraint violation. The proposed algorithm has been studied in continuous time and shown achieve O(1/l) convergence rate in terms of KKT residuals, assuming the dual iterates remain bounded. However, this assumption may not hold in practice, and when X, is unbounded, the convergence slows down. In such cases, the KKT violation decays at a rate of O (mma((1/t//5 (/e(())) where 1 is user-defined parameter controlling the dynamic barrier.
Min-max optimization. Min-max optimization, rooted in von Neumann's foundational work [69], has become increasingly central in modern applications such as adversarial learning, fairness, and distributionally robust optimization [64, 22, 58]. Classical convex-coneet problems have

---

been well-studied using primal-dual and gradient- gradient-based algorithms [18, 16, 27]. In recent years, nonconvex -stronyyy concave (NC-SC) problems have received sigmificant attention, with algorithmss such as gradient descent ascent (GDA) and alternating GDA achieving rates of ((x2e=2) [57, 73, 42], where 6 denotes the condition number. Proximal point methods combined with acceleration further improve the rate to Ō(yKe" - rate shown to be optimal under standard complexity assumptions [77, 38, 43J. For the more general nonconvex-coneav (NC-C) setting, the convergence rates are typically reduced to O(e- due to the absence of strong concavity, e.g., see [48, 71, 11] and the references therein. Despite recent studies, existing methods assume convex and easy-to- to-pjeeect constraints. To the best of our knowledge, there is no work on nonconvex- (strroogyy concave min-mas max problems with nonconvex nonlinear constraints.
Robust Optimization. Robust optimization (RO) provides a framework for decision making under uncertainty by introducing an uncertainty sets Y, W and requiring any candidate solution & remain feasible for all realizations in the uncertainty set, leading to problems of the form minzex x supyer fzz y) s.t. supwew ((z,, w) I 0. When suitable regularity conditions hold, the inner supremum admits convex dual reformulation [5, 7]. In more general cases, RO is addressed through cutting-set methods [53, 4] or scenario-basee based approaches that approximate Y, W with finite sample [12, 133. Building on RO, distributionally robust optimization (DRO) defines an ambiguity set P of probability distributions and yields the formulation min, sup PEP Ex ((x {)] [59, 36]. In structured convex scenarios, duality can transform the min-mas problem to a single-level program [21, 52, 54J. However, these approaches do not extend to the general setting considered in this paper.
Semi- Programming Semi-infinite programming (SIP) was introduced in the 1960s through the foundational work of Charnes, Cooper, and Kortanek [17], and has since evolved into a versatile framework with applications in functional approximation [65]. finance [19], and multi-objective learning [67]. For convex SIP, three main approaches have been developed: discretization [8. 61], cutting surface methods [29, 51], and penalty methods [41, 74]. These methods often entail solving non-trivial subproblems, which makes them computationally expensive in large-scale settings. On the theoretical side, duality and sufficient optimality conditions have been established [62, 34). In contrast, the theory and algorithms for nonconvex SIP remain less developed, reflecting the greater difficulty of the nonconvex setting [23]. Recent work has explored new discretization strategies [68] and min-max reformulations of SIP constraints that motivate primal-dual algorithms [57, 31]. However, none of these approaches address our setting fully, with the closest being recent work by Yao et al. [75], which develops first-order primal-die dual schemes with -on-asymptotic guarantees under convex regime.
1.2 Applications
Robust Multi-Task Learning with Task Priority. Multi-task learning (MTL) is a paradigm in machine learning that aims to simultaneously learn multiple related tasks by leveraging shared information among them [15]. The key idea is to enhance generalization performance by enabling tasks to learn collaborativlly rather than in isolation. Specifically, let (T.) represent a collection of I tasks, each associated with its training dataset (D where the feature space is shared across tasks. Each task T, is characterized by a loss function (zx D!r). ) where x denotes the shared parameters learned across all tasks. In applications where one task is prioritized, the problem can be formulated by minimizing its loss while enforcing the losses of the remaining tasks to stay below specified thresholds r;. Most existing MTL formulations assume uniform distribution over training samples when computing task- specifici losses; however, in real-world applications, the underlying data distributions are often uncertain or unknown. To address this, one standard approach is utilize the distributionally robust optimization (DRO) [59], and define the loss function for task i as the
weighted over the training dataset Ee V/ ex Eg) where the weights {u,"
( 1 lies in an uncertainty set Y. c.g., Y. = ty E Am, : VV, m. 1m.) S p} where V V(Q, P) denotes the divergence measure between two sets of probability measures Q and P and Am - {y E RT Σ 844 = 1} represents the simplex set [54]. This leads to base MTL formulation with task prioritization:
(3)
min max ZER
Σ Vj
(x,
E
Σ
(((,E)))) S
Vy Vie E (2....,T). .)).
s.t.
DDD
3

---

Robust, Energy-Constraing Deep Neural Networks Training (DNN), This problem involves optimizing model performance while limiting the total energy consumed during training [72]. This constraint arises in resource-constrained environments such as edge devices or large-scale systems where power efficiency is critical. In partieular, the goal is to train a deep neural network that performs reliably under worst-case distribution uncertainty, while satisfying energy and sparsity constraints under hardware-induced uncertainty. Consider a neural network with L layers and let W [w(t). w( denote the collection of weights of all the layers, and 5 [s(), ..... s(0j represent the collection of the non-sparse weights of all the layers. The goal is to train the model by minimizing worst-case loss under distribution uncertainty y E Y, while ensuring compliance with resource constraints described by (22 S Phudget. This problem can be formulated as follows:
min (W.S) VEY
Σ (E) s.t. (p((w()) S s(("), SIED...
(P2(S) S Ebudget: Yu E {1, (I....,,4) L)
where fo (w)()) calculates the sparsity in layer with the sparsity level s("), (02(S) represents the energy consumption of the DNN, which is usually a non-convex function, and the constant Ebudget is the threshold of the maximum energy budget.
Contributions. In this paper, we study a class of semi-infinite constrained min-max optimization problems. Unlike existing methods, our framework accommodates both nonconvex objectives and constraints defined over infinite cardinality constraint sets, thereby significantly broadening the scope of both min-max optimization and semi-infinite programming (SIP). We propose novel Inexact Dynamic Barrier Primal-Duse (iDB-PD) method, which performs gradient-based updates on the primal variables simultaneously reduce the objective function and the infeasibility residual, formulated through quadratic programming subproblem. To regulate the behavior of the search direction near the feasible region, we introduce an indicator function that ignores the constraint when it is satisfied and adjusts the direction to focus solely on minimizing the objective. Assuming that the squared inexact infeasibility residual [r wr)² satisfies the łojasiewiez inequality with exponent 0 E (0, 1) for any E W. we establish the first global non-asymptotic convergence guarantees for the class of problems where the objective and constraint functions are smooth and are either strongly concave or satisfying Polyak- Lojssiwwwii (PL) in their second component. In particular, we show that our method attains an c- K-K solution within O(c-a) D(c-0)), and O(c O(c-39((1-0) in terms of first-order stationarity, feasibility, and complementarity slackness, respectively. Finally, we demonstrate the effectiveness of our algorithm on real-worke data by applying it to robust multi-task learning (MTL) with task priority across various datasets.
Preliminaries
This section introduces the notations, definitions, and assumptions used throughout the analysis.
Notation. Throughout the paper, || denotes the Euclidean norm. We use R to denote the nonnegative orthant. For E IR", we adopt [x]] IR to denote max(x, OJ. where the maximum is taken componentwise. For any convex set C C IR" and point x E C, the normal cone is denoted by (x) A (p E R. p" 2 p² y, for all y E C)- For a differentiable vector-valued function f: IR + Rm the Jacobian is denoted by Jf IR + Rmxx defined as the matrix of gradients.
Next, define the Lojasiewicz property. Intuitively, this inequality controls the behavior of the gradient near critical points, preventing it from vanishing too quickly unless the function value is close to its critical value.
Definition 2.1 (Lojasiewicz inequality). f:
R be a differentiable function open subset of IR", and let x² E R" be a critical point of f. i.e., ff(=") = O. We say that f satisfies the Lojasiewiez inequality at x" if there exist constants 0 E [0, 1), e O, and neighborhood U of xt such that for all x E U.
[[[()) < [V)())]
The constant 0 E [0, 1) is called the tojasiewicz exponent.
tojasiewiez property and its extension for nonsmooth functions [10] (also known as the Kurdyka- Lojasiewicz (KL) property) plays central role in non-convex optimization and has been extensively

---

studied in the literature 2. 70], including its special case for 8 = 1/2, also known as the Polyak- Lojasiewiez (PL) inequality [32]. The fundamental contributions this concept are attributed to Kurdyka [37] and Łojasiewicz [45]. A broad class of functions has been shown to satisfy Lojasiewicz property, including real analytic functions [46], functions definable in o-minimal structures, and differentiable subanalytic functions [37]. In the context of DNN training, networks constructed by common components such as linear, polynomial, tangent hyperbolic, softplus, and sigmoid activation functions; squared, logistic, Huber, cross-entropy, and exponential loss functions satisfy the Lojasiewicz property [70, 76].
Next, we present the assumptions regarding the objective and constraint functions.
Assumption 2.1 (Objective function). (i) Function o(:-)) is continuously differentiable and there exist constants L L 2 0 and Lgy such that for any 2, E RD and y. B Y.
I V.o(E,y) v) 2Z 71 -
L am
x - æ1| + L lly Ul1
V (2x,) - V V 011 2 - - L lly øl1-
(it) V & is bounded, i.e. there exists Co > 0 such that VV g)1l I for all x E R" and y E Y. (ii)) For any fixed IR"", p(2;) .) is either St-Strongly concave function cg-PL. with Y = R Assumption 2.2 (Constraint function). (i) Function :b(:;.) is continuously differentiable and there exist constants L L 20 0 and Law > 0 such that for any x. T E TRm and w, w E WWW
[V w) (I, w)ll S L | =1| + L Iw W|| V (=, V WI, TI|l S L 11 - m|| + L w|w llI (ii) whth is bounded, i.e,, there exists a constant C& > O such that [V, S Co for all x E R" and w E W. (iii) For any fixed x E R,, ((z, -) is either Th -trrnngy concave function on a closed convex set W C Re or cy-PL over the entire space (i.e., W
2.1 Regularity Assumption and Connection to Existing Literature
Finding a global/local solution of Nonlinear Programming (NLP) (2) with nonconvex constraints is generally intractable. As such, most existing methods aim for finding stationary solution known as the Mrush-Kun--Tie Tucker (KKT) point, i.e., finding x E X such that
0 V fx() + Jg(z) X - Nx) g(z) S 0, )=g(()) = 0, Ai
for some À E IR. Even finding such a stationary solution a daunting task, as one of the primary challenges lies in identifying a feasible solution when the constraint is nonconvex. In this setting, researchers have explored different assumptions and problem structures to ensure convergence of optimization algorithms to fcasible stationary point. For instance, assuming that the algorithm can start from a (nearly) feasible solution, several studies (e.g.. [49, 40, 66]) have established convergence guarantees for obtaining an approximate KKT point. Another widely adopted assumption in the literature a regularity condition, which posits the existence of a constant ja > 0 such that [['g(() [+]| < 1 (ddit(Jg(z)) [9(x)]+, -Nx (z)).
In the special case where X R., this simplifies to
[|I())))+I|
L 2
(1]0(()) [o(x)]+1l.
Denoting the squared infeasibility residual function by p(æ) A [[g(z))+I] this condition can be written equivalently as p(x) S n² p/(x)(( Assuming that a feasible solution exists, we have min, p(x) = O, making clear that the above regularity condition equivalent p(-) satisfying the PL condition, that is, the Lojasiewicz inequality with exponent 0 = 1/2.
In this work, we consider more general regularity condition based on the Lojasiewicz inequality (3) with an exponent E (0, 1) for the residual function [s),, w))2 for any index parameter E W. Under this condition, we establish a uniform convergence guarantee for the proposed algorithm, which depends explicitly on the parameter 0. We now formally introduce our regularity assumption.
Assumption 2.3. Consider the constraint function si R x R R in problem (1). We assume that (=)(- ) satisfies Lojasiewicz inequality for any given w E W. iee, there exist μ > 0 and 0 E (0, 1) such that for any fixed W. the following holds
[bbx,,) < p 22 w)|b(a, w)1+1b
Vx E R..
(6)
5

---

Remark 2.1. We would like to highlight that this assumption generalizes existing regularity conditions in the nonconvex constrained optimization literature for any parameter A (0, Notably, when the index set W is singleton and 0 = 1/2, this condition reduces to the classical regularity condition (5) for a single constraint. Furthermore, Assumption 2.3 satisfied in variety of practical applications. including the DRO-MTL described in Section 1.2. In particular, using results from the calculus of real analytical and semialgebraic functions [63, 35, 9], one can verify that Assumption 2.3 holds for (6xx,, w) Σ, w wy((x; E,), where {(=:E) is smooth loss function, such as those used in DNNs with smooth activation functions. However, Assumption 2.3 may not hold for neural networks with nonsmooth components such as ReLUU, and one needs to use the smoothed variant, e.g., softplus, to ensure it holds.
3 Proposed Approach
In this paper, we introduce a novel dynamic barrier method tailored for min-max problems with semi-infinite, nonconvex constraints. Our proposed iterative scheme generates approximated gradient- based directions to update the triplet of variables (I,, y, w²) Specifically, to minimize the ob- jective function o(x,)) with respect to Σ, we aim to follow direction close to V=δ(ZR,, yk). Moreover, to encourage feasibility, this direction should either improve (b w) in x or avoid moving far away from the feasible region, i.e., max ((Ix+1, S max (x w) + for a small and controllable error & > 0. Indeed, we show that given a "good" estimate wk w² (Ix) E argmax#ew (x w), can satisfy this condition by imposing straint (, wx)" du + aup(zz, wx) S O, where p(...) is inexact min-max dynamic barrier function. Intuitively, function p(::-) encourages the search direction dg to align with -V Lb wx)- Accordingly, we define p( wx) := | W wIl]l. The direction de is then obtained by solving the following quadratic program (QP):
affine con-
d3 = argmin, dd + VRO(KK: yw)ll?
s.t.
V wx) T d + axploz, wx) S 0.
This QP admits a flomed-form solution and can be computed efficiently at each iteration. More specifically, da- = V ( yn) As VaNb(TA wx) where A is the dual multiplier corresponding to the constraint in the above QP updated as follows:
V wx ||2 V wa) TV VVD(ERR yk) + axpp(ak, ww)l+
(8)
The main issue with the update of dual multiplier Ay is that its value goes infinity as V/Va,, wx)ll vanishes. To resolve this issue, our idea is to introduce an indicator function (la, w) & [2, +|]]+I/V=+0(1 w)ll. Note that Ç(x, w² (x)) = 0 indicates that the point x is feasible or critical point of the constraint function. However, under Assumption 2.3 and using the definition of (1x, w) = | = (z, w) [z, w)l+ |l. we can conclude that Ç(z, w²) O implies that x is feasible. In this case, due to feasibility, we only wish to reduce the objective function and move along the direction de- = - -V.((IR, )..). hence, we would like to enforce A = O. However, computing the exact value of ((r,, w" (Ix)) may not be possible. To resolve this issue, we use an estimated value (( w&) measure of criticality and fcasibility of the constraint which indicates whether A is updated based on (8) or set to zero. In other words, when (( wx) = the constraints are treated as inactive. The maximization variables y and are subsequently updated using N₂ and M2 steps of (accelerated) gradient ascent, respectively. A full description of the algorithmic steps is presented in Algorithm 1.
Remark 3.1. We would like to point out that the proposed approach is related the dynamic barrier gradient method introduced in [25]. While there are some conceptual similarities, we emphasize that the two methods differ significantly in both algorithmic design and convergence analysis. In particular, apart from addressing inexactness and incorporating maximization component, two key distinctions of our approach are: (1) Introduction of the indicator function <(..)), which serves as a metric to regulate the behavior of the dual multiplier dІ_ This leads to a modified update rule that enables convergence to a KKT point without requiring the boundedness the dual iterates, unlike the assumption in [25]. (2) Our choice of barrier function differs: specifically, p(x, w) 1|V2v( w)ll corresponds to T = in their framework. However, this parameter choice does not yield a convergence rate guarantee in their method see Proposition 3.7 in [25].

---

Algorithm Inexact Dynamic Barrier Primal-Dual (iDB-PD) Method for Semi-Infinite Min-Max
1: Input: 20 E R" 7a E (0, 1), on > O, NR, M& 2
2: for 0 : do
V mm V (IR, wx) VZ ya) + aup(as, wa)l+ if ((TN, wx) > 0
3: d 5
o.w.
4: ds f V yk)) A V (2x, wk)
5: Ik+1 + Ik + nx
using N₂ steps of (accelerated) gradient ascent 7: Wk+1 s argmax 15 (( w) using M2 steps of (accelerated) gradient ascent
6:
Mk+1 x argmax VEY x(
8:
end for
Convergence Analysis
In this section, analyze the convergence of the iDB-PD algorithm. Indeed, problem (1) can be viewed as an implicit nonconvex constrained optimization problem min f(x:) s.t. g(z) I 0, where fx) - maXyeY (xx, y) and g(x) max (6(r, w). Based on Assumption 2.1-(iii) and 2.2-(iii), can show that f and g are continuously differentiable functions (see Section A. for proof); hence, we can establish the gap function based on the KKT solution of the implicit problem. Specifically,
our goal is to find e-KKT solution, i.e., find & R" and À 2 0 such that
IV)()) + AVg(T) e, [o(3)]+ S (Ag(3))
Our first step of analysis to provide a descent-type inequality for the objective and constraint functions. This requires first analyzing the modified dual multiplier λe. The reason why we call it modified dual multiplier that Au-update is modified based on the value of the indicator function [(xx,, wx). In effect, this modification can be translated into how we construct the QP subproblem. In particular, when ( wx) > 0, dę is updated based on the QP in (7), otherwise de is updated based the unconstrained variant of (7) i.e., d₃ argming || + V Vz Øg. yx)ll Nevertheless, we can upper bound |[dx] and Ag. In particular, using
Schwartz and triangle incqualities, one verify that AxI V (1),, w&)) V/V,, 3/k) ag for any k > O. This relation, along with Lipschitz continuity of f allows us to prove the following result regarding the objective function,
((xx+)) + (Ca + ax)) Liu
1i (2x))
7k ||dall?. (9)
where (x(x) = (y-(2) (1%) and (*) = argmax o(x, y).
To obtain a descent-type inequality for the constraint, we define the infeasibility residual function p(x) [g(x)] Note that this function is continuously differentiable whose gradient, i.e., Vp(z) =
2V is locally Lipschitz continuous with constant Lx(x) e 2C L p(z)
Lemma A.4 for details and proof. Although dę is not directly feasible solution of the QP subproblem in (7) (it is only feasible if ((IN, wx) > 0), we can show the following important inequality for k 0,
[K( wx)l+ V Va wh) T d4 S -aulubba wx))+ wx) = -au(( wk).
Combining these results and conducting some extra analysis, we can show the following result regarding the infeasibility residual function:
p(æx+1) S p(xx) - 27kan5(I wx) + 27 (Kx, wk) wx)][lda] (Tx) + 2T
t p(*k) |w0 w" (2x) 7/ (T,
(10)
||dx 112
where w² wxx (w) (w&) and W*(x) argmax (2, w). The detailed statements and proof of the results in (9) and (10) are presented in Section A.3.
Although these results provide some bound on the progress of the next iterate with respect to objective and constraint functions, (10) may not immediately lead to convergence rate result due to the dependencies of non non-negative terms the right-hand side to p(xx) esspccilly notice the effect of
7

---

p(ax) in (xt)). To address this, we show that by carefully selecting the algorithm's 's parameters the sequence (7x|ldg]]])>>> is summable and {p(**) }=20 a bounded sequence see Lemma A.7. As side result, we can conclude that there exists constant Lp that can upper bound the local Lipschitz constant (x) uniformly along the sequence {xx }220 generated by Algorithm 1. Through this critical result, we can show the following theorem, establishing convergence bounds on ||dy I| and [g(x)))++
Theorem 4.1. Suppose Assumptions 2.1, 2.2, and 2.3 hold. Let {KK, Aktk20 be the sequence generated by Algorithm/ such that {arRh is non-increasing sequence and Vi S (I.g + T. Then, for any T 2 L,
T-1
2(f(xo) - (((T))
T
T-1
(1)
Th 1dlldl??
TRou TROM (Co + as) +
Σ
84
(11)
PT
TT
TT
k2
0=
k=
k=0
(II)
1
Σ
11
Σ
(p(ZE)
p((Ftt))
Σ
AT
AT
7k
7
AT k=
k=
k==
plL, + 2L
(12)
2AT
k=
for some summable sequences {E%, g J820 C R2,, where I'r & Eto To and AT & Eheo an.
Proof. See Section A.4 in the Appendix.
Theorem 4.1 provides upper bound on the accumulation of sequences of direction de and infeasi- bility measure [. While these quantities are not initially expressed in terms of KKT residuals, the following theorem establishes their connection to e-KKT conditions and derives the resulting complexity guarantees for the proposed algorithm.
Theorem 4.2. Suppose Assumptions 2, 2.2, and 2.3 hold. Let {ark As JTD T-1 be the se- 73/3 quence generated by Algorithm 1 such that for any k 2 0, On = (k+2) for some
small w > 0, Thk = = Ommin( Ti,, + Lgg) (1)) Ne = Olog(k + 1)), and (w)]40-2))) if ((x,, wk) > O, otherwise, Mr.
Ms- (imaxxmax({1 1
20 log(T), log(TT
Ommxx11, 28 log(T)) Then, for any > O, there exists t {0, .............................. T 1} such that
1. (Stationarity) [[) A V e within T (22) iterations;
2. (Feasibility)) [g(x+))+ S within T = 0 (क)
(1 iterations;
3. (Slackness) [>e((=:)] within T = (
(,p ④5) iterations.
Proof. See Section A.4 in the Appendix.
Remark 4.1. We would like state some important remarks regarding the complexity result in the above theorem.
(i) Convergence result: We highlight that the obtained complexity results are, to the best of our knowledge, the first established non-asymptotic complexity bounds for nonconvex semi-infinite min-max problems. Owing modest assumptions and simple algorithmic structure, the proposed method is broadly applicable to problems, including those involving instances of DNNs.
(ii) Special case of 0 1: The results of Theorem 4.2 simplify significantly when 0 1, which corresponds the PL condition on the squared inexact infeasibility residual [ı(z, w)] for any w E Wesee Assumption 2.3. In this case, we have M₁ (log (T)). and the complexity for all three metrics improves to (1)c²), matching the best known results in [39, 47] for nonconvex optimization problems with finitely many constraints.
(iii) Selection M₁: The choice of Mr depends on the inexact infeasibility residual function when 0 E (0, 1), arising from the infinite cardinality of constraints. Here, M₁. controls the accuracy of estimating the iterate Wi from this collection. As the iterates approach the approximate feasible region, increasingly accurate estimates are needed to ensure convergence to the true feasible region.
8

---

Numerical Experiments
In this section, we evaluate the performance of the proposed iDB-PD algorithm on the Robust Multi- Task 2 problem with a task priority, as introduced in Section 1.2. All experiments were implemented in PyTorch and executed on Google Colab, using a virtual machine equipped with an NVIDIA A100-SXMM GPU (40 GB), an Intel Xeon o CPU @ 2.20 GHz, 87 GB of RAM, and running Ubuntu 22.04.4 LTS with Python 3.12. We consider the following robust MTL formulation, where the goal is to learn two related tasks by optimizing shared parameter vector. Specifically, the objective is to minimize the worst-case loss of a prioritized task while ensuring that the loss of the remaining task remains below specified threshold denoted by > 0, formulated follows:
min max re yEAn.
Σ
vill (x,
On (n((v)
(13a)
s.t. Σ (2 (22)) - 9m (w) Sr,
Vw E Ams
(13b)
where An and Am are simplex sets. Note that, (n( An bly 1n1 and (m)() Ama || 1 1m 11 are regularization terms that restrict the worst-case distributions from deviating significantly In
2
from the uniform distribution. Here, 1 denotes the all-ones vector. We consider five different datasets and, for each, evenly partition the labels into two disjoint subsets, and the goal of each task is to learn the corresponding labels. We consider fully connected neural network with one hidden layer and tanh activation functions. The output layer is a softmax with a cross-entropy loss function (z())
Our experiment includes five datasets as sum- marized in Table 1. We used Multi-MNIST and Multi-Fashion-MNII
Table 1: Summary of datasets used in the experi- ments.
from Lin et al. (2019) [44]', which were constructed from the origi- nal MNIST dataset. For these datasets, each data point is constructed by randomly sampling two different images from the original MNIST (rashion-MNIST dataset and combining them into single image, placing the two digits (or articles of clothing) on the top left and bottom right corners, resulting a 36 36 image. Yeast, Coronary Heart Disease, and 20NuwsGroup datasets were accessed via the Multi-Label Classification Dataset Repository hosted by Universidad de Córdoba'. For each of these datasets, we evenly divide the label set in two, with one half learned in the objective and the other half learned in the constraint. Here, we report our results on Multi-MN MNIST and CHD49, while results on the remaining datasets Multi-Fashion MNIST, Yeast, and 20NG) are included in Appendix A.5.
Dataset
Instances
Features
Labels
Mukii-MNIST
20000
1296
10
CHD49
555
Multi-Fashion MNIST
20000
1296
10
Yeast
2417
14
2UNG
19300
1006
20
In this experiment, we compare iDB-PD with adaptive discretization method, which iteratively adds the most violated constraints to form finite approximation of the semi-infinite min-max problem following Blankenship and Falk [8]. The resulting discretized problem is then solved by COOPER [24], a PyTorch library for constrained optimization that implements first-order, Lagrangian-basee update schemes. From Figure we observe that proposed method (iDB-PD) consistently achieves convergence in infeasibility, stationarity, and slackness, whereas the adaptive discretization fails to reduce infeasibility and diverges in stationarity. This result underscores the advantage of iDB-PD over more classical discretization methods.
Experiment 1.
Datasets by Lin et al. (2019): http://gihalccom///PPPPaottTTTT

---

Figure 1:
iDB-PD vs. Adaptive Discretization with COOPER on Multi-MNIST (top row) and CHD49 (bottom row), evaluated in terms of stationarity, infeasibility, and slackness.
Experiment 2. In this experiment, we compare the performance of the model in (13) with an alternative model in which the objective function is a weighted summation of loss functions with a DRO formulation. This results in the following min-max problem formulation
m Σ
9m mm((w) )
min max #ER WEA. WEAm
Σ (1, -((()) + p
w 1,, (5-)
For fair comparison, we applied the Gradient Descent Multi-Ascent (GDMA) method [31, to solve this reformulated min-max problem, testing several values E {1, 10). We evaluated both approaches in terms of the metries corresponding (13), i.c. the objective function value, infeasibility, and stationarity. Note that the first two metrics correspond to the training losses of task I and task 2, respectively.
Baratton
Poination
Figure 2: iDB-PD vs GDMA on multi-MNIST (top row) and CHD49 (bottom row), evaluated in terms of stationarity, infeasibility, and objective loss.
In Figure 2, we observe that iDB-PD consistently converges in both feasibility and stationarity, whereas GDMA with small p achieves low stationarity, but fails to reduce infeasibility, and GDMA with large p exhibits unstable behavior. These results highlight the difficulty of selecting appropriate loss weights (p) to balance the tasks and confirm the robustness of our semi-infinite constrained min-max formulation, where such weight is dynamically adjusted by the algorithm.
10

---

Acknowledgments and Disclosure of Funding
This work is supported in part by the National Science Foundation under Grants ECCS-2515979 and 2231863.
References
[1] Hédy Attouch, Jéröme Bolte, Patrick Redont, and Antoine Soubeyran. Proximal alternating minimization and projection methods for nonconvex problems: An approach based on the kurdyka-tojasiewiczz inequality. Mathematics of operations research, 35(2):438 457, 2010.
[2] Hedy Attouch, Jérôme Bolte, and Benar Fux Svaiter. Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized gauss-seide seidel methods. Mathematical programming. 137(1):91-129, 2013.
[3] Heinz H Bauschke, Patrick L Combettes, Heinz H Bauschke, and Patrick L Combettes. Correc- tion to: convex analysis and monotone operator theory in Hilbert spaces. Springer, 2017.
[4] Aharon Ben-Tai Tal, Elad Hazan, Tomer Koren, and Shie Mannor. Oracle-based robust optimization via online learning. Operations Research, (3(3):628-633) 2015.
[5] Aharon Ben-Tal and Arkadi Nemirovski. Robust cotimiization-mmtoooooeo and applications. Mathematical programming. 92:453 480., 2002.
[6] Dimitri P Bertsekas. Constrained optimization and Lagrange multiplier methods. Academic press, 2014.
[7] Dimitris Bertsimas, David Brown, and Constantine Caramanis. Theory and applications of robust optimization. SIAM review, 53(3):664-501, 2011.
[8] Jerry W Blankenship and James Falk. Infinitely constrained optimization problems. Journal of Optimization Theory and Applications, 19(2):261-211, 1976.
[9] Jacek Bochnak, Michel Coste, and Françoira Roy. Real algebraic geometry, volume 36. Springer Science & Business Media, 2013.
[10] Jérôme Bolte, Aris Daniilidis, and Adrian Lewis. The lojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems. SIAM Journal on Optimization, 17(4):1205-1223 2007.
[11] Morteza Boroun, Zeinab Alizadeh, and Afrooz Jalilzadeh. Accelerated primal-dual scheme for class of stochastic nonconvex-concat saddle point problems. 2023 American control conference (ACC), pages 204-209. IEEE, 2023.
[12] Marco C Campi and Simone Garatti. The exact feasibility of randomized solutions of uncertain convex programs. SIAM Journal on Optimization, 1213;12211-223 2008.
[13] Marco C Campi and Simone Garatti. A sampling-andddiscarding approach to chance-constrained optimization: feasibility and optimality. Journal of optimization theory and applications, 148(2):257-280, 2011.
[14] Coralia Cartis, Nicholas IM Gould, and Philippe I. Toint. On the evaluation complexity of composite function minimization with applications nonconvex nonlinear programming. SIAM Journal on Optimization, 21 21(4): 2011.
[15] Rich Caruana. Multitask learning. Machine learning, 28:41-75, 1997.
[16] Antonin Chambolle and Thomas Pock. On the ergodic convergence rates of first-order primal-dual algorithm. Mathematical Programming, 159(1):253-277, 2016.
[17] Abraham Charnes, William W Cooper, and Kortanek. Duality in semi-infinite programs and some works of haar and carathéodory. Management Science, 9(2:2099-228, 1963.

---

[18] George HG Chen and R Tyreell Rockafellar Convergence rates in SIAM Journal on Optimization, 7(2):421-444) 1997.
splitting.
[19] Sören Christensen. A method for pricing american options using semi-infinite linear program- ming. Mathematical Finance: An International Journal of Mathematics, Statistics and Financial Economics, 24(1):156-173) 2014.
[20] Frank E Curtis and Michael L Overton. A sequential quadratic programming algorithm for nonconvex, nonsmooth constrained optimization. SIAM Journal on Optimization, 22(2):474- 500, 2012.
[21] Erick Delage and Yinyu Ye. Distributionally robust optimization under moment uncertainty with application to data-driven problems. Operations research, 58(3):595 2010.
[22] Yuyang Deng, Mohammad Mahdi Kamani, and Mehrdad Mahdavi. Distributionally robust federated averaging. Advances in neural information processing systems, 33:15111-15122 2020.
[23] Hatim Djelassi, Alexander Mitsos, and Oliver Stein. Recent advances in nonconvex semi-infinite programming: Applications and algorithms. EURO Journal on Computational Optimization, 9: 9:100006, 2021.
[24] Jose Calllgo-Pooaade Juan Ramirez, Meraj Hashemizadeh, and Simon Lacoste-Julice Cooper: library for constrained optimization in deep learning. arXiv preprint arXiv:2504.01222. 2025.
[25] Chengyue Gong, Xingchao Liu, and Qiang Liu. Automatic and harmless regularization with constrained and lexicographic optimization: A dynamic barrier approach. In Advances in Neural Information Processing Systems, volume 34, pages 29630-29642. Curran Associates, Inc., 2021.
[26] Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversar- ial examples. arXiv preprint arXiv:1412.6572, 2014.
[27] Erfan Yazdandoost Hamedani and Necdet Serhat Aybat. A primal-dual algorithm with line search for general convex-concave saddle point problems. SIAM Journal on Optimization, 31(2):1299-1329, 2021.
[28] Magnus R Hestenes. Multiplier and gradient methods. Journal of optimization theory and applications, 4(5):303-320, 1969.
[29] Rainer Hettich and Kenneth Kortanck. Semi-infinite programming: theory, methods, and applications. SIAM review, 35(3):380-429, 1993.
[30] Mingyi Hong, Zhi-Quan Luo, and Meisam Razaviyayn. Convergence analysis of alternat- ing direction method of multipliers for a family of nonconvex problems. SIAM Journal on Optimization, 26(1):337-364, 2016.
[31] Chi Jin, Praneeth Netrapalli, and Michael Jordan. What is local optimality in nonconvex- nonconcave minimax optimization? In International conference on machine learning, pages 4880 4889. PMLR, 2020.
[32] Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the polyak-tojasiewi condition. In Joint European conference machine learning and knowledge discovery in databases, pages 795-811. Springer, 2016.
[33] Weiwei Kong, Jefferson G Melo, and Renato DC Monteiro. Complexity of a quadratic penalty accelerated inexact proximal point method for solving linearly constrained nonconvex composite programs. SIAM Journal on Optimization, 29(4):2566-2533, 2019.
[34] Olga I Kostyukova and Tatiana V Tchemisova. Sufficient optimality conditions for convex semi-infinite programming. Optimization Methods & Software, 25(2):279-99 297, 2010.
[35] Steven G Krantz and Harold R Parks. A primer of real analytic functions. Springer Science Business Media, 2002.
12

---

[36] Daniel Kuhn, Soroosh Shafiee, and Wolfram Wiesemann. Distributionally robust optimization. Acta Numerica, 34:579-804 804, 2025.
[37] Krzysztof Kurdyka. On gradients of functions definable o-minimal structures. In Annales de l'institut Fourier, volume 48, pages 769-783, 1998.
[38] Haochuan Li, Yi Tian, Jingzhao Zhang, and Ali Jadbabaie. Complexity lower bounds for nonconvex-stronggyyconeav min-max optimization. Advances in Neural Information Process- ing Systems, 34: 34:1792-1804, 2021.
[39] Zichong Li. Pin-Yu Yu Chen, Sijia Liu, Songtao Lu, and Yangyang Xu. Rate-improved inexact aug- mented lagrangian method for constrained nonconvex optimization. In International Conference on Artificial Intelligence and Statisties, pages 2170-2178. PMLR, 2021.
[40] Qihang Lin, Runchao Ma, and Yangyang Xu. Complexity an inexact proximal-poing penalty method for constrained smooth non-convex optimization. Computational optimization and applications, 82(1):175-2244 2022.
[41] Qun Lin, Ryan Loxton, Kok Lay Teo, Yong Hong Wu, and Changjun Yu. new exact penalty method for semi-infinite programming problems. Journal of Computational and Applied Mathematics, 261:271-2866 2014.
[42] Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent ascent for nonconvex Senconnex-concann concave minimax problems. In International conference on machine learning, pages 2020.
PMLR,
[43] Tianyi Lin, Chi Jin, and Michael I Jordan. Near-optimal algorithms for minimax optimization. In Conference on learning theory, pages 2738-2779. PMLR, 2020.
[44] Xi Lin, Hui-Ling Zhen, Zhenhua Li, Qing-Fu Zhang, and Sam Kwong. Pareto multi-task learning. Advances in neural information processing systems, 32, 2019.
[45] Stanislaw Lojasiewicz. Une propriété topologique des sous-ensembles analytiques réels. Les équations aux dérivées partielles, 117(87-89), 1963.
[46] Stanislaw Lojasiewicz. Sur les trajectoires du gradient d'une fonction analytique. Seminari di geometria, 1983(1984):115--11 1982.
[47] Songtao Lu. single-loop gradient descent and perturbed ascent algorithm for nonconvex functional constrained optimization. In International conference on machine learning, pages 14315-14357. PMLR, 2022.
[48] Songtao Lu, Ioannis Tsaknakis, Mingyi Hong, and Yongxin Chen. Hybrid block successive approximation for one-sided non-convex min-max problems: algorithms and applications. IEEE Transactions on Signal Processing, 68:3676-3691, 2020..
[49] Runchao Ma, Qihang Lin, and Tianbao Yang. Quadratically regularized subgradient methods for weakly convex optimization with weakly convex constraints. International Conference on Machine Learning, pages 6554 6564. PMLR, 2020.
[50] Gabriel Resende Machado, Eugênio Silva, and Ronaldo Ribeiro Goldschmidt. Adversarial machine learning in image classification: A survey toward the defender's perspective. ACM Computing Surveys (CSUR), 55(1): 2021.
[51] Sanjay Mehrotra and Dávid Papp. A cutting surface algorithm for semi-infinite convex pro- gramming with an application to moment robust optimization. SIAM Journal on Optimization, 24(4):1670-1697, 1697, 2014.
[52] Peyman Mohajerin Esfahani and Daniel Kuhn. Data-driven distributionally robust optimization using the wasserstein metric: Performance guarantees and tractable reformulations. Mathemati- cal Programming, 171(1):115-16) 2018
[53] Almir Mutapeic and Stephen Boyd. Cutting-set methods for robust convex optimization with pessimizing oracles. Optimization Methods & Software, 24(3):381-406 2009.
13

---

[54] Hongseok Namkoong and John C Duchi. Stochastic gradient methods for distributionally robust optimization with f-divergences. Advances in neural information processing systems, 29, 2016.
[55] Ion Necoara, Yu Nesterov, and Francois Glineur. Linear convergence of first order methods for non-strongly convex optimization. Mathematical Programming, 175:69- 175:69-107, 2019.
[56] Yurii Nesterov et al. Lectures on convex optimization, volume 137. Springer, 2018.
[57] Maher Nouiched, Maziar Sanjabi, Tianjian Huang, Jason D Lee, and Meisam Razaviyayn. Solving a class of non-convex min-max games using iterative first order methods. Advances in Neural Information Processing Systems, 32, 2019.
[58] Luca Oneto and Silvia Chiappa. Fairesss in machine learning. In Recent trends in learning from data: Tutorials from the inns big data and deep learning conference (innsbdd12019) pages 155-196. Springer, 2020.
[59] Hamed Rahimian and Sanjay Mehrotra. Frameworks and results in distributionally robust optimization. Open Journal of Mathematical Optimization, 3:1-85, 2022.
[60] Maziar Sanjabi, Jimmy Ba, Meisam Razaviyayn, and Jason D Lee. On the convergence and robustness of training gans with regularized optimal transport. Advances in Neural Information Processing Systems, 31, 2018.
[61] Tobias Seidel and optimization problems with quadratic rate of convergence. Optimization, 71(8):221 1-2239, 2022.
Küfer. An adaptive discretization method solving semi semi-infinite
[62] Alexander Shapiro. Semi-infinite programming, duality, discretization and optimality conditions. Optimization, 58(2) 2009.
[63] Masahiro Shiota and Masahiro Shiota. Geometry of subanalytic and semialgebraic sets, volume
150. Birkhäuser Boston, 1997.
[64] Aman Sinha, Hongseok Namkoong, Riccardo Volpi, and John Duchi. Certifying some dis- tributional robustness with principled adversarial training. arXiv preprint arXiv:/110.1057/ 2017.
[65] Oliver Stein. Bi-level strategies in semi-infinite programming, volume 71. Springer Science Business Media, 2003.
[66] Kaizhao Sun and Xu Andy Sun. Dual descent augmented lagrangian method and alternating direction method of multipliers. SIAM Journal on Optimization, 34(2):167--1777, 2024.
[67] Xiangkai Sun, Kok Lay Teo, and Xian-Jun Long. Some characterizations of approximate solutions for robust semi-infinite optimization problems. Journal of Optimization Theory and Applications, (21(1):2113311 2021.
[68] Evren M Turan, Johannes Jäschke, and Rohit Kannan. Bounding- focused discretization methods for the global optimization of nonconvex semi-infinite programs: Em turan, j. j-jäschke, kannan. Computational Optimization and Applications, pages 1-34, 2025.
[69] J v. Neumann. Zur theorie der gesellschaftssiile.. Mathematische annalen, 100(1):295-32) 1928.
[70] Yangyang Xu and Wotao Yin. A block coordinate descent method for regularized multiconvex optimization with applications nonnegative tensor factorization and completion. SIAM Journal imaging sciences, 6(3):1758-179) 2013.
[71] Zi Xu, Huiling Zhang, Yang Xu, and Guanghui Lan. A unified single-loop alternating gradi- ent projection algorithm for nonconvex nonconvex-concave concave and convex-nonconeave minimax problems. Mathematical Programming, 201(():635-706, 2023.
[72] Haichuan Yang, Yuhao Zhu, and Ji Liu. Fce: Platform-independeen energy-constrained deep neural network compression via a bilinear regression model. Proceedings of the IEEF/VVF Conference Computer Vision and Pattern Recognition, pages 11206-1 1215, 2019.
14

---

[73] Junchi Yang, Negar Kiyavash, and Niao He. Global convergence and variance reduction for class of nonconvex nonconcave minimax problems. Advances in Neural Information Processing Systems, 11111113116,3 2020.
[74] Xiaoqi Yang, Zhangyou Chen, and Jinchuan Zhou. Optimality conditions for semi-infinite and generalized semi-infinite programs via lower order exact penalty functions. Journal of optimization theory and applications, 169:984-1012, 2016.
[75] Yao Yao, Qihang Lin, and Tianbao Yang. Deterministic and stochastic accelerated gradient method for convex semi-infinite optimization. arXiv preprint arXiv:2310. 10993, 2023.
[76] Jinshan Zeng. Tim Tsz-Kit Lau, Shaobo Lin, and Yuan Yao. Global convergence of block coordinate descent in deep learning. In International conference on machine learning, pages 7313-7323. PMLR, 2019.
[77] Siqi Zhang, Junchi Yang, Cristóbal Guzmán, Negar Kiyavash, and Niao He. The complexity of setneee-sstrongly-connnn minimax optimization. In Uncertainty in Artificial Intelligence, pages 482-492. PMLR, 2021.
15

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: clearly stated our contributions in the introduction, aligned with the main claims in the abstract.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [NA]
Justification: This is a theoretical work with standard assumption.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: Our paper provides the full set of assumptions Section 2 and the proofs in Sections and 1.2.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: The experimental results are stated in Section 5. The implementation details are included in Section A.5. The code and data are attached in the supplementary material.
5. Open access to data and code
Question: Does the paper provide open tions to faithfully reproduce the main experimental results, as described in supplemental material?
the data and code, with sufficient instruc-
Answer: [Yes]
Justification: The code and data are attached in the supplementary material.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: We explained the details of algorithm implementation in Sections 5 and A.5.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
The algorithm is designed for a deterministic setting, and does not include any randomness.
Justification:
8. Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time exccution) needed to reproduce the experiments?
Answer: [Yes]
16

---

Justification: The compute resources are stated in Section 5.
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: : http///eurrppppppeee wwtpppbicc/tticsseiiiiiieeeeeeee
Answer: [Yes]
Justification: The paper conforms, in every respect, with the NeurIPS Code of Ethics.
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is societal impact of the work performed in this paper.
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
12. Licenses for existing assets
Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: The paper does not use existing assets.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects. 15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality the research, declaration not required.
Answer: [NA]
Justification: The core method development this research does not involve LLMs as any important, original, or non-standard components.
17

---

A Technical Appendices and Supplementary Material
A.1 Analysis of the maximization variables
Consider the following parametric maximization problem
h (x) _ max h(,, u), uEU
(14)
R + RR is a continuously differentiable function, and U S Ih is closed, convex set. We are interested in the conditions under which the value function h h"(x) is Lipschitz differentiable and an approximate solution of the above problem can be found using (accelerated) gradient ascent method. Indeed, using the classical result in the optimization literature [32, 56, 55, 57], it can be deduced that both these properties are satisfied when h(a, :) is strongly concave or satisfies PL inequality when U = IRm In the following, we will restate these results unified statement and later specify them for our proposed algorithm. particular, we first value function.
for a given E R where h(---) R"
state the linear convergence result under these conditions, and then state the differentiability of the
Proposition A.1 ([32, 56, 55]). Consider problem (14), and assume that h(-,-) is a continuously differentiable function, such that for any fixed h(r, is either strongly concave (or satisfies PL inequality (see Def. 3 with f 2) with U = RR.. J. Let {ux TT-1 Tk=0 C 2.mh be sequence generated
by the (accelerated) gradient ascent method. Then, for any x E R", there exists ó E (0, 1) and A 2 > O such that we huve the following results for T 2 1,
|ur w² (x))l² I A,8",
h(2, UT) S h (x) S ((x UT) + A28".
where u² (x)= & (u-(=)(UT), and (x) argmaxueu u).
Proposition A.2 ([57) Lemma A.5). Consider problem (14), and assume that h(:,)) is a continuously differentiable function, such that for any fixed x, h((,,)) is Thh -trsoroggly concave (or Ct-PL (see Def. 2.1 with 0 = - with U "),, it follows that
(x) = Vah(z,"") for any o² E (x).
where (x) & argmax, h(x, u... Moreover, (x) has (L + (L) gradient where Th (or c.
Now, we apply the above propositions to the objective and constraint functions in problem (1) to derive the error of estimating the maximization components according to the updates Algorithm 1, which will be used in the analysis. Recall that f(x) = maXyey Φ(x, y) and g(x) = max 4/(x,, w). Based on Proposition A.2 and Assumptions 2.1 and 2.2, we have the following properties
1. f is continuously differentiable and has Lipschitz gradient with constant Ly A 4y
(2
2. g is continuously differentiable and has a Lipschitz gradient with constant Lg & L
(2
where if n when (xx,,)) is -tr-tnny concave or if 2 when (fx,,)) is cy. (1g is defined similarly).
Moreover, based on Proposition A.1, there exist uniform constants AV. Ar AW E (0, +00) and 5y. 8n E (0, 1), such that for any 1: 2 O,
18 3² (xx) 2 < A
(15)
|w - w (xx) < A " MM,
(16)
(T wx) & (( & (K wx) + A 8MM
(17)
where NR, M2 denote the number of (accelerated) gradient ascent steps to maximize the functions 6(2,-) and (xx, -), respectively.
18

---

A.2 Required Lemmas
This section states two important lemmas regarding the proposed method and the implicit constraint function. First, we show some bounds on the modified dual multiplier λ corresponding to the subproblem (7) based on the update of Algorithm Next, we establish local Lipschitz continuity of the infeasibility residual function p(x:) _ [g(x)] Later, we show that by carefully selecting the stepsize, this local constant can be upper bounded by global one.
Lemma A.3. Suppose Assumptions 2.1 and 2.2 hold, and let {æ AuI be the sequence generated by Algorithm 1 such that {av J220 C R__ non-increasing sequence. Then, for any 2 0 we have that >xp(2KK, w&) I &Z0(Z yk)ll + Otg- Furthermore, if Assumption 2.3 hold, then for any k 2 0.
{x(o(a=)]+ (4 CA x M [1b(,,, ())],,))))]+ 4-20 where C _ plCo + oa).
Proof. Recall that p(arg, wa) [Va wx)ll and ((IR, wx) [vb wx) wx]]- V a ( wx)ll- Note that if 0g- = O, the bound holds trivially. Now suppose, ((Ik,, wi) >> O, then using the update of A we have that
>ap(EE, (x)) V (aRK wx II
[- Vi [-Va wx) V VaΦ(IR.VE vk) aup(IR: wx)] [+
Taking the absolute value from both sides, using the fact that max{a, bY S |a| +16 for any b E R. followed by the triangle and Cauchy-Schward inequalities, we conclude that V yx)ll s
< Ik)ll + Ork-
Similarly, from the definition of d and Assumption 2.3 we conclude that
[o(xx)]+ (ark wx)l (Il ( vx) ov.))
S ulg(ax)) +]+ (IK: wx)]+ 20 (IIV oo ys)) axk)
S (IU(IK, w + A. 8
[v( wn)ll+ (IIV ,0 yk)ll + ao)
S 1 (1oxx)))
A 5 [1k w/ w1) 21 (II _ yk)l + av))
where in the penultimate inequality we used the second inequality in (17) and that ag is a non- increasing sequence. The last inequality above follows from the first inequality in (17). Finally, the result follows from the boundedness Va see Assumption 2.
Lemma A.4. Suppose Assumption 2.2 holds. Let g(x) & max (xx w) and the infeasibility residual by p(x) [=(=)] Then p(-) is a continuously differentiable function and Vp(x) is locally Lipschitz continuous with constant (1) & 203 + 12 + [g(x)]
Proof.
Differentiability of p(-) follows from differentiability of g established in Property 2 and its gradient can be calculated by the chain rule as Vp(æ)) = 2V [o())]+ Therefore, we have that
[V(x)) vp(u))l [[][x())]+ Vy(x)- V[o(v))+V
(V((() ( V bobb)llbbc=))111+200000lllll
(o())++11 I1.
where in the second equality we added and subtracted 2(g(=)) + Vg(v). Note that based on Assump- tion 2.2-(ii), we have that Vg(x) = VzΦ(Z, w wx()) is bounded by Cg. hence, is CxpLiphchitz continuous. Therefore.
VV(x)) vp(n))l & (2L + 203) || - yll-
From Young's 's inequality, we can bound |L < 4 [g(z)]] Therefore, the following holds Vp(>) Vp(z)) < (2C + 1 + [o( ell-
19

---

A.3 Proof of one-step analysis
In this section, we prove the one-step analysis for the objective and constraints.
Lemma A.5. Suppose Assumptions 2.1, 2.2, and 2.3 hold. Let {Ik, k be the sequence generated by Algorithm such that {axs) 3. is a non-increasing sequence and Yik S (Ls L -1 Then, for any k 2 0
L
7k || S f(xx) (((++1) + TRax(Cs + tak) + A7O
(I)
(18)
2
2
(II) Tooa wx) I p(xx) p((x+1)
2 2 + 7x 8M Cip (2C + 0z)
L p(
+ 1e + 20
|d
(19)
Proof. Part (I): Using Lipschitz continuity of gradient of as established in Property and update of 2 we have that
Ttf
f((x+1) = f(xx) + vf(x)) (x -xx) +
2
| - xxl1
f((x) + 7t ( Tdx+ T2
||dx!1? "
dx =f(x)) + 7h ( 9k) + +kk) dx +
(RELs
7h l|dall
2
+7kllV V Illllld
S f(())) - 7h V wx) du (R
||cb|l| + Yk: Loyllyx - o (xx) 7i
2
where in the last inequality we used dz. - VZ yk) de v (a ws). (
Vo y² (ra)), and Lipschitz continuity of the gradient of function s Moreover, from com- plementarity slackness condition we know that A (V=U(IE,, wx) de + axp(Ix, wx)) = 0, hence we obtain
[(x+11) [(ax)
T2.
||dı|| + meox>ep(a wk) nx D. 8" (xx))ll|d&
7k
LE
||dı||2 (Cs + aas) + I. ( (xx)))]
Yyk
L 16
||dx|| (Cs ax) L'y 1lue llue D² (xxx))1 22 || 11?
7kk
(20)
2
where the penultimate inequality follows from the application of Lemma A.3 and || Øz, v) I Ca. moreover, the last inequality is due to Young's 's inequality (where
2). Now, rearranging the
terms and selecting 7/ (Ly )
-1 lead to the result of part (I).
Part (II): Recall that (( wx) = [ wx)) wx)]++1l I/V 2 (x,,,, wx)ll and p(zR, wa) = || (x wx)ll Based on Lemma A.4 and the update rule of gh+ 1 oa yade, have that
p(#x+1) p(xx))
< (Vp(zn), #441 xx) xx) + (p(xk)
| xx1
de 22 (x((k))))
27H1g(0x)) ) [ T
||
2
27A (n(())))))) ))+ V (x wk) ) T
27 (x(xxx)))))))))))))) (Vg(az) Var(au wx)) ds + المييااعح ||cd 1|
3 27H V wx) T du +2 -i
- - |+ + بلعاااعه | ||
tenn (a)
(21)
20

---

Considering term (a), from (17) one can observe that
Va wx)) dx S [xb, wx)]+ V (Z wx) dR IV VV
we
I axl ws p ws) + A M || 1 (Z wP) ||l
I (x wx) + A
5 t (2C + an).
(22)
where in the second inequality we use the fact that de feasible solution of the QP subprob- lem if [( w&) 0, hence, [1, wx)]4 Varb<E,, wx)" ds I -ax [ wx wx]]+ p(Zx, wx)
( Wk), otherwise the inequality holds trivially. Moreover, the last inequality follows from Assumption 2.1-(i) and Lemma A.3 and one can easily verify that I|dæ || S 2Co + oo and from Assumption 2.2 we have || (T wx)ll S C.. Therefore, combining (22) with (21), we obtain
p(xx+1) p(xx)= < - 2 (Tr,, w&) 2% AT 8 C2C +00)
+ 2% Li (2 )1 1| w (ox) |||d + 7 (p(()())
||
2
S -2 wi) - 2y AT Mr Co -xa)
(L + +2L%
((w)((z))lurg - w (xxx)
(2xx) (=>) +
|| 31
Next, rearranging the above inequality, dividing both sides by 2, lead to the desired result.
A.4 Proof of Theorems 4.1 and 4.2
Before proving Theorems 4.1 and 4.2, we present a technical lemma the recursive relation of non-negative real-valued sequence that will be used in our convergence analysis.
Lemma A.6 ([3) Lemma 5.31). Let {vx), {ug), {au)) {Bx} be sequences of nonnegative reals with Ek=o OA < 0o and k= 8k < oo such that u&+1 S (1 + ax) u4 + BR. for all k. Then, { converges and E Ug < co.
Using this result, we first show that the sequence {7 ll d& 1 is summable and (p(Tx) J& is bounded sequence.
Lemma A.7. Let { v be the sequence generated by Algorithm I such that Σtzo OK < +00, Eteo NNaa < to0, and +00 8Ma < +oo. Under the premises of Lemma A.5, we have that (i) Eteo Th || < +00; (ii) (p(x=)]<20 is bounded sequence, i.e., there exists Cg > 0 such that g(Tx)) + & Cg for any k 2 0.
Proof. (i) Consider Part (I) of Lemma A.5 by rearranging terms one can obtain:
L 2ik |d 7ao aR)) AWO
((T+1) f(xx)
Since ag is non-increasing sequence and it is assumed that Σx=0 makk +00, ver- ify that Ete Sa < k=
< +oc, we have O (mar (C& + an) + A/ < +00. Therefore, applying Lemma A.6, conclude that Ete 7k de < +0c.
kk < +00. Moreover, since Σx &N4. Le
y
(ii) Similarly, from Part (II) of Lemma A.5, multiplying both sides by 2, using L,(x) 203 12 p(x) from Lemma A.4, and rearranging terms yields:
p(x++1) S (1 + L
A
M w
Me
+
2k ( C wx)
2
120 &
+ I.
2L
+ 23, A &M (2C + ao) +
||d 112
2
b
21

---

From the assumptions in the statement of the lemma and the result of part (I) and that Y E (0, 1), we have that Σt a < +o0 and Eizo by < +oo.Hence, the conditions of Lemma A.6 are satisfied, and we conclude that the sequence {p(a2) F220 converges. Therefore, {p(r)) is bounded, i.c. there exists Co > 0 such that [a(xx)]+ I Cg for all k 0.
Now, we are ready to prove Theorem 4.1. First, we restate the statement with full details here.
Theorem A.8 (Restatment of Theorem 4.1), Suppose Assumptions 2.1, 2.2, and 2.3 hold. Let ( A J220 be the sequence generated by Algorithm such that {or Ja is non-increasing sequence
and 7 S (I.g + Iyyy) Then, for any T 2 and k 2 1,
T-1
- f((T)) 1T
1 T-1 ma + +ak) +
L A
T-1
(I)
7 11
8
TT
TT
(23)
T-1
T-1
(II)
1 Σ AT
Σ
(xx
AT k=0
1
p(ax)
p(az 11)
p(2
+
Aq
7h
+ 20x (Ax)
M20M 2
k=
k=
Mlpp
+ 2L
T-1
aw
mh |d
(24)
2AT
k=0
for some Å > O, where r & ETSo nh and Ar 2 Ekzo ag.
Proof. Part (I) follows immediately from Lemma A.5-Part (I) by summing over l 0 to T 1 and dividing both sides by a Σi 7k-
To prove Part (II), first note that from Lemma A.7 we have [g(xx)]+ S C, which from Lemma A.4 we conclude that there exists a constant L, & 2C w + L + C2 that upper bounds the local Lipschitz constant (2( uniformly along the sequence { J220- Therefore, we can simplify the bound in (19) as follows
p((xk)
p(2R+1))
(KO wx) S
+ 7x AnA (2C + oo)
2
2
L
+ RLL + +
+ 2
||dx|?
4
Using Assumption 2.3, we can lower bound the left-hand side of the above inequality by 2aat (IK, wx]] Moreover, from (17) and that 0 (0,1) we have that [ 20 is
[1( w + (Ag) 8200 which leads to
ykokk 2p 10(x))1
p(an) p(1++1)
+ AT AMA + as)
L C CgArON
&M
2
2 (T, +
2T
7h 2 28028820M. |
4
Finally, multiplying both sides by 24//7s, summing over i 0 to T dividing by Ar, and defining A (2C, + on) lead the desired result.
Now, we restate and prove Theorem 4.2.
Theorem A.9 (Restatment of Theorem 4.2). Suppose Assumptions 2.1, 2.2, and 2.3 hold. Let
(IK,, Aa20 be the sequence generated by Algorithm I such that for any k: 2 0,
T1/3 ()- 7k 7 min( uC22
Ti73 (L. (gg))-1 N₂ 1-6, log(k: 1), and Mj. I- max/max 1 log(T) (o,lloo(((h wx)] 2)) if [1((,, wx) 1I)) wx)ll |ll > oth-
erwise, Ms T- max (1, 28 log(T)) Then, for any e > 0, there exists E {O...., T 1} such
that
1. (Stationarity) [V]) + Ae < within T = 0(5) iterations;
22

---

2. (Feasibilityy) [g(z:)] S within T = ( 1.) iterations;
3. (Slackness) [xg((=))] S within T = Ol (am))))))) iterations.
Proof. Before starting the proof let us define L
argmingstgT-1 [axx +
AE Vg( [x(x))+++ [Aeg(=)))) (A Moreover, the selection of parameters ag. Yks Ng. and Mr implies that the conditions of Lemma A.7 hold, and we can invoke its result within the proof.
Part First, we show the result for e-stationary condition. From the definition of da and comparing it with f((x)) + d Vg(rk) we observe that if ((IR, wx) = 0 then d 0 and [Vx))x))
A Vg(=))12 I 2 1l -V" -y" (xx) I 2||d&|| 2 2 " o which by selecting Nu as in the statement of corollary, we obtain [[a)( + >u (xxa)ll I 2| 2g 2 (k+1)²
If (( wx) > O, then
+ +x
I 3| +| V V2 + - Vn VoN(
s 12 3/ + ( 33
+
< + Ao + C32 (2 wx ) (L )2 2
1
1
s 3| + 2 A
(k: 1)z 3/2¹ 2 0² ) T
''
(25)
where in the second inequality we used Lipschitz continuity of V. and Va th as well as the relations in (15) and (16). The third inequality follows from Lemma A.3 and Assumption 2.3 which shows that As= S (I wx)ll-1 I Cy (1ra,, wx) [4 for some C > 0. The last inequality is obtain by plugging the selection of N₂ and Mj as in the statement of corollary and noting that 1 2 1/ (0g)) for any d E 10.
On the other hand, from Theorem A.8 part (I), by selecting 7 O(1/21/3) and aq (k+2) and noting that 1 ET- ag = (1/T2//3) we conclude that 1 Σ K-1 combining the result with (25) we obtain
T1/3
|| 1| > (1//2/33). Therefore,
T
1
AA AA
(L
[V+) + Vo(=))1 S
E k=
A < 0
mn0
T2/3
T
By taking the square root of both sides of the above inequality, the result of part 1 follows immediately.
Part 2. From Lemma A.7, we observe that there exists D > 0 such that D = Σ k= 7lldR 11 < +00. Considering the result of Theorem A.8-part (II), selecting 7k = O Tu73 ) and p(x) 2 0, we have that
T
On (2 <
1 p(zo) p(zo)
+
1
T
Σ
Mr +
20 29 820M2
MTTTp + 2L D 2A1
AT
Arn
Ar
k==0
k=0
1
D
AT7
AT
where the last inequality follows from plugging in Mj since max (8M 8828
Therefore, from the above inequality, noting that AT = (TT133 and the definition of at the heginning of the proof we conclude that [9(2 S O ( which completes the proof of part 2.
Part 3. Finally, to calculate the complexity of finding e-complementarity slackness, recall the update
of >₂ in Algorithm 1. Recall that ((TA, (Z)),, wx)]= V wy)ll- If ((TK, wx) = 0. then A = 0, hence, \xg(xx) = O. Suppose C( wx) > 0, then we observe that g 2 (0 (x) > 0. Therefore, from Lemma A.3 we have that 0 < ^xg(#*) = {x[g(Ix)]+ < C[g(zx)] CAySM [e)(xx, w 12122 Combining the two scenarios, for any k 2 0, we have that [ N
28 + CA. &M (1b( wx) [ 1- for some C' > 0. Therefore, based on selection of Mr. Clg( 112-26
we obtain (x)) S ( Ta о.7 + +) from which the result follows.
23

---

A.5 Experiment Details and Additional Plots
select the regularization parameter À 10-3 and the maximization variables y, w are updated by running N₂- - 2 log(k 6 + 2)] and Mr 10flog(k (A: + 2) steps of the projected gradient ascent method. The stepsize y is tuned by selecting the best per- formance among {10-2 2.5 x 10-1, 5 x 10-1, 10-3 5, x 10-a, 10-3} and the parameter set og ak/k 2)1.001 for E (0.1, 0.2, 0.5, 1). Hyperparameter choices follow Theorem 4.2 and tuned via targeted grid search to ensure robustness. Furthermore, to determine the threshold value
Experiment Details: In all experiments,
solve the robust learning task in the constraint, i.e, min, max Σラ=1 (2(2,5,)) 9m (w), separately using the unconstrained variant of our method for some iterations. The resulting objective value is then used in the original problem as the threshold value.
The oscillations that occur in plots reflect the difficult trade-off between minimizing the objective, forcing feasibility under infinitely many functional constraints, and satisfying the <-KTT conditions, behavior common in both convex and nonconvex problems with functional constraints [27].
Clia pal't
Iteraion
1400
308
28"18"7
1-13
Stancee (0k
Obpecivv Teo
Lev30
370
13
Elarcton
Preration
2.5
2.20
Easation
Sanaion
Tarratio
Figure 3: iDB-PD vs. GDMA on multi-Fashion MNIST (top row), Yeast (middle row), and 20NG (bottom row), evaluated in terms of stationarity, infeasibility, and objective loss.
24

---

2x12
1803
Iteraion
2330
Itro00o
Alpis deoosiarti
St0cHnos (A4 30t mV.13
34000 aanorratyy 18681
1x
terraion
taration
Iaration
Sut to Q041
Rec00on
Rtro02e
Recation
Figure 4: iDB-PD vs. Adaptive Discretization with COOPER on multi-Fashion MNIST (top row), Yeast (middle row), and 20NG (bottom row), evaluated in terms of stationarity, infeasibility, and slackness.
Across the three additional datasets, iDB-PD broadly outperforms all GDMA variants and the adaptive discretization method with COOPER, iDB-PD drives infeasibility and stationarity down quickly while maintaining competitive objective values. In contrast, GDMA requires large penalty values cost of stability. Further, adaptive discretization struggles with instability and struggles with matching iDB-PD's stationarity and infeasibility performance. These results confirm the robustness of our DBPPD method which effectively balances feasibility, optimality, and stability.
to approach feasibility, frequently
25


Reviews:
[{"review_id": "sbfhmrP4FF", "reviewer": "Reviewer_hjym", "summary": "The paper develops an optimization algorithm for a min-max problem with a nonconvex objective that depends jointly on the minimization and maximization variables, while the minimization variables must also satisfy a semi-infinite family of constraints. The authors introduce a first-order dynamic barrier primal-dual method that behaves like a single-loop primal-dual gradient scheme augmented with a barrier term, and prove strong convergence rates under a uniform Łojasiewicz property, required since there is no convexity imposed. The authors further demonstrate that distributionally robust multi-task learning and related applications can be formulated within this framework and efficiently solved by the proposed algorithm.", "questions": "- Would Assumption 2.3 not hold for NNs in general?\n- Do the authors believe simplex constraints are representative enough for $\\psi$ in the numerical experiments?", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "The paper is written very well. I was able to follow most of the results presented. I believe the subject is of interest to our community, and I thank the authors for this work. The convergence guarantees look appealing.\n\nI have some concerns that I am listing below. I would like to discuss the following points with the authors during the rebuttal phase.\n\n- Firstly, a lot of times, the paper specifies that semi-infinite optimization is underdeveloped. I disagree with this statement. SIO is one of the most well-studied concepts in robust optimization and related fields. A lot of important citations and discussions are missing in this work. For example, the book by Anderson and Nash (\"Linear Programming in Infinite-dimensional Spaces\") is missing. The citations in robust optimization are also not usual in my view, especially since Ben-Tal's book is missing (which has a lot of useful SIO results). \n- There are a lot of works in distributionally robust optimization (*e.g.*, \"regularization via mass transportation\") where such min-max problems look nonconvex but the inner problem can be dualized and we can still tractably solve the problem. In those cases, the inner \"convex maximization\" problem can still be dualized with some modeling tricks. Such approaches are not really discussed in this work, and all the existing results are discarded by using \"nonconvexity\" as an argument.\n- The approach proposed in this work can actually be useful, since I agree that the assumptions are very mild. However, numerical experiments have no benchmark to compare against. The paper originally claimed that this is a very important class of problems, but I find it difficult to be convinced by the importance of the class of problems if numerical experiments do not have any benchmarks. In my view, to motivate the proposed sophisticated algorithms, we should get strong numerical evidence. Some benchmark thoughts: we can solve one task in the multi-task learning setting and test the performance of our trained models on the other task (an extreme approach). We can use local optimization solvers with multiple starts simulated. We can use bilevel optimization solvers. We can try to linearized the objective function (e.g., approximate $\\psi$ with piece-wise affine functions).", "was_revised": true, "final_justification": "The literature review still feels underdeveloped. I do not know why the authors cannot have any benchmarks, since there are so many SIO problems in RO. The rest looks good.\n\nNote: the authors' second reply is much more thorough. I increased my score to 5. No more confusion on my end.", "rebuttal": "**1. The paper specifies that semi-infinite optimization is underdeveloped. I disagree with this statement. A lot of important citations and discussions are missing in this work. The citations in robust optimization are also not usual in my view, especially since Ben-Tal's book is missing.**\n\n**R1.** \nWe would like to thank the reviewer for their thoughtful and constructive comment. Our intention was certainly not to overlook or diminish the extensive theoretical and algorithmic contributions in the SIP literature. Rather, we aimed to emphasize that, despite its rich development and broad applications in various areas such as robotic and control theory, comparatively less attention has been given to methods tailored for modern AI and Operations Research problems, which often involve different structural features (e.g., min-max objective functions) and require different computational approaches (e.g., fully first-order methods). To clarify this point, we will revise our statement as follows: *\"Despite its rich and extensive theoretical and algorithmic development, comparatively less attention has been devoted to designing efficient first-order methods for emerging applications in modern AI and Operations Research.\"* Additionally, we expand our literature review to include more classical works in SIP, including those kindly suggested by the reviewer.\n\nOur work introduces **the first fully first-order algorithm** for **nonconvex semi-infinite constrained min-max optimization**, that provides **explicit global non-asymptotic convergence guarantees** for finding an approximated stationary solution. Unlike prior SIP methods which are often second-order, require feasible initialization, and offer only asymptotic or local convergence results, our iDB-PD algorithm ensures convergence from any starting point, with provable iteration complexity bounds of $\\mathcal{O}(\\epsilon^{-3})$, $\\mathcal{O}(\\epsilon^{-6\\theta})$, and $\\mathcal{O}(\\epsilon^{-3\\theta/(1-\\theta)})$ for stationarity, feasibility, and complementarity, respectively. In contrast, classical methods like exchange algorithms or adaptive discretization (e.g., [Ref 1], [Ref 2]) either lack convergence rate analysis or provide only local rates (e.g., quadratic convergence near optimality under strong assumptions), and robust optimization frameworks (e.g., Ben-Tal et al.) solve restricted convex subclasses without iterative rate analysis. Thus, our method uniquely bridges the gap between theoretical rigor and broad applicability, advancing the state of the art in semi-infinite programming.\n\n[Ref 1] Seidel, Tobias, and Karl-Heinz Küfer. \"An adaptive discretization method solving semi-infinite optimization problems with quadratic rate of convergence.\" Optimization 71.8 (2022): 2211-2239.\n\n[Ref 2] Floudas, Christodoulos A., and Oliver Stein. \"The adaptive convexification algorithm: a feasible point method for semi-infinite programming.\" SIAM Journal on Optimization 18.4 (2008): 1187-1208.\n\n\n---\n\n**2. There are a lot of works in distributionally robust optimization. In those cases, the inner \"convex maximization\" problem can still be dualized with some modeling tricks. Such approaches are not really discussed in this work.**\n\n**R2.** \nWe appreciate the reviewer’s comment. While we acknowledge the extensive literature on distributionally robust optimization (DRO), including approaches such as “regularization via mass transportation” where the inner maximization can be dualized under convexity assumptions, our work addresses a fundamentally different setting: nonconvex-concave semi-infinite min-max problems where such dualization does not lead to a tractable convex reformulation. Unlike prior DRO methods that rely on strong duality and convexity to enable tractable solutions, our goal is to develop a fully first-order method with global non-asymptotic convergence guarantees. We will explicitly incorporate this distinction and relevant DRO references in the revised paper.\n\n---\n\n**3. Numerical experiments have no benchmark to compare against. In my view, to motivate the proposed sophisticated algorithms, we should get strong numerical evidence.**\n\n**R3.** \nThank you for your comment and great suggestion. The main reason that we originally did not use any baseline method was that classical SIP methods mainly focus on minimization problems, and we are not aware of any method that can address a semi-infinite min-max structure in a nonconvex setting. Moreover, those that can handle non-convex problems generally focus on a discretization technique, however, these methods suffer from the curse of dimensionality by construction, as the number of required grid points to accurately represent the infinite constraint naturally grows with the dimension of the constraint space and is not effectively implementable on our numerical examples involving neural networks in high dimension (dim($x$)$\\approx 2M$). \nFor the baseline comparison, we consider an additive robust MTL model where the objective function is the weighted summation of task-specific losses. More specifically, we consider solving $\\min_{x}\\max_{y\\in \\Delta_n}\\max_{w\\in\\Delta_m}\\phi(x,y)+\\rho\\psi(x,w)$ where $\\rho>0$ is the weight parameter. This problem can be solved via min-max optimization methods such as gradient descent multi-step ascent (GDMA) [Ref 3,Ref 4]. We compare the performance of our method GDMA for different values of $\\rho$ in terms of the first task loss, i.e, $\\phi(x_k,y_k)$, and feasibility $[\\psi(x_k,w_k)-r]_+$, where $r$ is the single task threshold as discussed in our paper. Below you can find the result of the experiment on Multi-MNIST dataset.\n\n**iDB-PD (our method)**\n\niteration = 0001: Obj Loss = 2.4279 Feasibility = 1.0807 \n\niteration = 1000: Obj Loss = 2.8115 Feasibility = 0.2393 \n\niteration = 2000: Obj Loss = 2.7242 Feasibility = 0.0387 \n\niteration = 3000: Obj Loss = **2.5080** Feasibility = **0.0010** \n\n**GDMA ($\\rho=1$)**\n\niteration = 0001: Obj Loss = 2.4073 Feasibility = 1.0576 \n\niteration = 1000: Obj Loss = 2.2709 Feasibility = 0.9157 \n\niteration = 2000: Obj Loss = 2.1412 Feasibility = 0.7698 \n\niteration = 3000: Obj Loss = 2.0615 Feasibility = 0.6823 \n\n**GDMA ($\\rho=2$)**\n\niteration = 0001: Obj Loss = 2.4556 Feasibility = 1.1168 \n\niteration = 1000: Obj Loss = 2.3824 Feasibility = 0.6930 \n\niteration = 2000: Obj Loss = 2.2876 Feasibility = 0.5165 \n\niteration = 3000: Obj Loss = 2.2276 Feasibility = 0.3941 \n\n**GDMA ($\\rho=5$)**\n\niteration = 0001: Obj Loss = 2.4700 Feasibility = 1.0810 \n\niteration = 1000: Obj Loss = 2.6608 Feasibility = 0.3444 \n\niteration = 2000: Obj Loss = 2.6859 Feasibility = 0.0352 \n\niteration = 3000: Obj Loss = 2.7191 Feasibility = 0.0000 \n\n**GDMA ($\\rho=10$)**\n\niteration = 0001: Obj Loss = 2.4803 Feasibility = 1.0565 \n\niteration = 1000: Obj Loss = 3.1297 Feasibility = 0.0000 \n\niteration = 2000: Obj Loss = 3.4119 Feasibility = 0.0000 \n\niteration = 3000: Obj Loss = 3.5966 Feasibility = 0.0000 \n\n\nWe observe that our proposed approach reaches the lowest value for the first task loss among the approaches that satisfy the constraint within an accuracy $\\epsilon=10^{-3}$. Note that while GDMA with $\\rho=1$ yields a lower objective loss, it fails to meet the feasibility requirement within the desired accuracy threshold. The full details and corresponding plots for the experiment will be added to the revised manuscript.\n\n[Ref3] Jin, Chi, Praneeth Netrapalli, and Michael Jordan. \"What is local optimality in nonconvex-nonconcave minimax optimization?.\" International conference on machine learning. PMLR, 2020.\n\n[Ref4] Nouiehed, Maher, et al. \"Solving a class of non-convex min-max games using iterative first order methods.\" Advances in Neural Information Processing Systems 32 (2019).\n\n ---\n\n **4. Would Assumption 2.3 not hold for NNs in general?**\n\n**R4.** \nWe thank the reviewer for this insightful question. While Assumption 2.3 holds in many practical NN architectures involving smooth components as noted in Remark 2.1, it does not extend to general NN architectures with nonsmooth components such as ReLU activation function, and one needs to use the smoothed variant, e.g., softplus, to ensure Assumption 2.3 holds. \n\n\n ---\n **5. Do the authors believe simplex constraints are representative enough for $\\psi$ in the numerical experiments?**\n\n**R5.** We thank the reviewer for raising this question. As a simplex set describes a discrete probability distribution domain, it is a natural structure arising in distributionally robust models for capturing uncertainty when probabilities are unknown. Note that the regularization term in the robust MTL model considered in our numerical experiment finds the worst-case distributions in the neighborhood of the uniform distribution. This formulation is commonly used in DRO literature [Ref 5] and numerical examples for min-max optimization methods [Ref 6,Ref 7].  \nFurthermore, the simplex set satisfies convexity and compactness, which help make the resulting optimization problem computationally manageable. \n\n[Ref 5] Namkoong, Hongseok, and John C. Duchi. \"Stochastic gradient methods for distributionally robust optimization with f-divergences.\" Advances in neural information processing systems 29 (2016).\n\n[Ref 6] Zhang, Xuan, Necdet Serhat Aybat, and Mert Gurbuzbalaban. \"Sapd+: An accelerated stochastic method for nonconvex-concave minimax problems.\" Advances in Neural Information Processing Systems 35 (2022): 21668-21681.\n\n[Ref 7] Mehta, Ronak, Jelena Diakonikolas, and Zaid Harchaoui. \"DRAGO: Primal-Dual Coupled Variance Reduction for Faster Distributionally Robust Optimization.\" Advances in Neural Information Processing Systems 37 (2024): 134770-134825.\n\n ---\n\nWe hope our responses address your concerns and would be happy to clarify anything further if needed."}, {"review_id": "gRY2c6nuh9", "reviewer": "Reviewer_DGYP", "summary": "This paper studies a challenging class of min-max optimization problems with infinitely many nonconvex constraints, motivated by applications such as adversarial robustness and safety-constrained learning, as presented in eq. (1). It considers the setting where the min-max objective $\\phi(x,y)$ is Lipschitz in x, and PL or strongly-concave (SC) in y,  and the inequality function $\\varphi(x,y)$ is  $\\theta$-Lojasiewicz and Lipschitz in x and PL or SC in w. The authors propose an Inexact Dynamic Barrier Primal-Dual (iDB-PD) algorithm and establish non-asymptotic convergence guarantees under the Łojasiewicz inequality. Theoretical results are supported by experiments on robust multitask learning with task prioritization.", "questions": "1. In the first paragraph of the introduction, several applications are mentioned without citations. Could references or concrete examples be added?\n\n2. In lines 36–37, the problem structure is emphasized before motivating applications are introduced. Could a simplified application be included earlier?\n\n3. Line 42 introduces nonconvexity in $\\phi$ and $\\psi$, yet convergence relies on the Łojasiewicz inequality. Why is this assumption not highlighted sooner?\n\n4. Assumption 2.2 sets $W = \\mathbb{R}^l$, but in Equation (1), $w \\in W$. Please clarify the domain and generality of $W$.\n\n5. Do the applications in Section 1.2 and experiments rigorously satisfy the PL or Łojasiewicz conditions?\n\n6. How does the algorithm's complexity compare to existing SIP or constrained min-max solvers, even heuristically?\n\n7. Is it possible to include baselines or ablation studies to better evaluate the practical performance of the method?", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength:\n\n1. The paper addresses a novel and underexplored intersection between semi-infinite programming (SIP) and nonconvex min-max optimization.\n\n2. It provides the first non-asymptotic complexity guarantees for this class of problems, representing a significant theoretical advancement.\n\n3. The algorithm is thoughtfully designed, notably avoiding the common but restrictive assumption of dual boundedness.\n\n4. The theoretical results are rigorous, well-structured, and clearly presented.\n\n5. The application to robust multitask learning is both relevant and practically meaningful.\n\nWeaknesses:\n\n1. The introduction lacks citations to support its claims regarding real-world applications.\n\n2. Motivating applications are introduced too late, which makes the early sections abstract and harder to engage with.\n\n3. The Łojasiewicz inequality assumption plays a critical role but is not adequately emphasized or discussed in the main text.\n\n4. There is inconsistency in the definition of the constraint domain $W$, particularly between Equation (1) and Assumption 2.2.3.\n\n5. The strong assumptions, such as PL and Łojasiewicz conditions, are not verified or discussed in the context of the examples or existing literature.\n\n6. The paper lacks experimental comparisons with baseline or approximate methods, leaving questions about scalability and practical computational cost unanswered.", "was_revised": true, "final_justification": "I will keep my positive score.", "rebuttal": "**1. In the first paragraph of the introduction, several applications are mentioned without citations. Could references or concrete examples be added?**\n\n**R1.** \nWe thank the reviewer for this helpful suggestion. We agree that the applications mentioned in the opening paragraph would benefit from concrete citations to better support the context and motivate the relevance of semi-infinite programming (SIP). \nAccordingly, we have revised the paragraph to explicitly cite representative works for each application area. \nSpecifically, we now reference foundational works highlighting adversarial perturbations in AI models [Ref 1], [Ref 2], robust optimization in supply chain management [Ref 3], and safety and control under uncertainty in autonomous systems [Ref 4].\n\n\n[Ref 1] Goodfellow, Ian J., Jonathon Shlens, and Christian Szegedy. \"Explaining and harnessing adversarial examples.\" arXiv preprint arXiv:1412.6572 (2014).\n\n[Ref 2] Zhang, Xingwei, Xiaolong Zheng, and Wenji Mao. \"Adversarial perturbation defense on deep neural networks.\" ACM Computing Surveys (CSUR) 54.8 (2021): 1-36.\n\n[Ref 3] Ben-Tal, Aharon, et al. \"Retailer-supplier flexible commitments contracts: A robust optimization approach.\" Manufacturing and Service Operations Management 7.3 (2005): 248-271.\n\n[Ref 4] Dutta, Raj Gautam, Xiaolong Guo, and Yier Jin. \"Quantifying trust in autonomous system under uncertainties.\" 2016 29th IEEE International System-on-Chip Conference (SOCC). IEEE, 2016.\n\n ---\n\n **2. In lines 36–37, the problem structure is emphasized before motivating applications are introduced. Could a simplified application be included earlier?**\n\n**R2.** Thank you for the suggestion. We agree that introducing a motivating application earlier can improve readability. We will revise the manuscript to include a brief mention of relevant applications with appropriate references, before presenting the problem structure.\n\n ---\n\n **3. Line 42 introduces nonconvexity in $\\phi$ and $\\psi$, yet convergence relies on the Łojasiewicz inequality. Why is this assumption not highlighted sooner.**\n\n**R3.** Thank you for this observation. To clarify, Line 42 only motivates the development of new methods for addressing nonconvexity in both objective and constraint functions under min-max setting as a general direction. Moreover, Łojasiewicz condition is only required for the $\\psi$ function with respect to $x$, which we explicitly discussed in the contribution section. We will revise the earlier sections to make this distinction more explicit and avoid potential confusion.\n\n---\n\n**4. Assumption 2.2 sets $W\\in \\mathbb R^\\ell$, but in Equation (1), $w\\in W$. Please clarify the domain and generality of $W$.**\n\n**R4.** Thank you for pointing this out. We agree that the notation could be made clearer.\n\n* When $\\psi(x, \\cdot)$ is $\\eta_\\psi$-strongly concave, $W$ can be any closed convex subset of $\\mathbb{R}^\\ell$.\n* When $\\psi(x, \\cdot)$ is assumed to satisfy the Polyak-Łojasiewicz (PL) condition with constant $c_\\psi$, we require that $W = \\mathbb{R}^\\ell$ to ensure the PL condition holds over the entire space.\n\nWe will revise the assumption to make this distinction more precise in the revised version.\n\n---\n\n**5. Do the applications in Section 1.2 and experiments rigorously satisfy the PL or Łojasiewicz conditions?**\n\n**R5.** We thank the reviewer for this question. Both applications in Section 1.2 satisfy the Łojasiewicz inequality if the loss functions chosen are real analytical, definable in $o$-minimal structures, or differentiable sub-analytical functions. Common constraint loss choices in both problems include cross-entropy, squared loss, $\\ell_1$, and Huber loss, all of which satisfy one of the above functional categories and therefore, the Łojasiewicz inequality as well. Our neural network in all of our experiments is connected by hyperbolic tangents with a softmax activation function, so the network satisfies the Łojasiewicz inequality, as we note in the discussion after Definition 2.1.\n\n---\n\n**6. How does the algorithm's complexity compare to existing SIP or constrained min-max solvers, even heuristically?**\n\n**R6.** We appreciate the reviewer noting this. Classical SIP methods that can handle non-convex problems generally focus on a discretization technique. However, these methods suffer from the curse of dimensionality by construction, as the number of required grid points to accurately represent the infinite constraint naturally grows with the dimension of the constraint space. Given our numerical examples involve neural networks in high dimension (dim($x$)$\\approx 2M$), our proposed method offers a clear advantage by relying solely on first-order information. Other common SIP methods, such as cutting planes or exchange methods, rely on a convexity assumption and do not offer convergence guarantees in the non-convex setting.\nCommon constrained min-max methods, such as gradient-based primal-dual methods require the constraint set to be tractable via projection or evaluation. However, in our semi-infinite constraint setting, there are no guarantees that either will hold. \n\n---\n\n**7. Is it possible to include baselines or ablation studies to better evaluate the practical performance of the method?**\n\n**R7.** We thank the reviewer for their suggestion. The main reason that we originally did not use any baseline method was that classical SIP methods mainly focus on minimization problems, and we are not aware of any method that can address a semi-infinite min-max structure in a nonconvex setting. For the baseline comparison, we consider an additive robust MTL model where the objective function is the weighted summation of task-specific losses. More specifically, we consider solving $\\min_{x}\\max_{y\\in \\Delta_n}\\max_{w\\in\\Delta_m}\\phi(x,y)+\\rho\\psi(x,w)$ where $\\rho>0$ is the weight parameter. This problem can be solved via min-max optimization methods such as gradient descent multi-step ascent (GDMA) [Ref 5,Ref 6]. We compare the performance of our method GDMA for different values of $\\rho$ in terms of the first task loss, i.e, $\\phi(x_k,y_k)$, and feasibility $[\\psi(x_k,w_k)-r]_+$, where $r$ is the single task threshold as discussed in our paper. Below you can find the result of the experiment on Multi-MNIST dataset.\n\n**iDB-PD (our method)**\n\niteration = 0001: Obj Loss = 2.4279 Feasibility = 1.0807 \n\niteration = 1000: Obj Loss = 2.8115 Feasibility = 0.2393 \n\niteration = 2000: Obj Loss = 2.7242 Feasibility = 0.0387 \n\niteration = 3000: Obj Loss = **2.5080** Feasibility = **0.0010** \n\n**GDMA ($\\rho=1$)**\n\niteration = 0001: Obj Loss = 2.4073 Feasibility = 1.0576 \n\niteration = 1000: Obj Loss = 2.2709 Feasibility = 0.9157 \n\niteration = 2000: Obj Loss = 2.1412 Feasibility = 0.7698 \n\niteration = 3000: Obj Loss = 2.0615 Feasibility = 0.6823 \n\n**GDMA ($\\rho=2$)**\n\niteration = 0001: Obj Loss = 2.4556 Feasibility = 1.1168 \n\niteration = 1000: Obj Loss = 2.3824 Feasibility = 0.6930 \n\niteration = 2000: Obj Loss = 2.2876 Feasibility = 0.5165 \n\niteration = 3000: Obj Loss = 2.2276 Feasibility = 0.3941 \n\n**GDMA ($\\rho=5$)**\n\niteration = 0001: Obj Loss = 2.4700 Feasibility = 1.0810 \n\niteration = 1000: Obj Loss = 2.6608 Feasibility = 0.3444 \n\niteration = 2000: Obj Loss = 2.6859 Feasibility = 0.0352 \n\niteration = 3000: Obj Loss = 2.7191 Feasibility = 0.0000 \n\n**GDMA ($\\rho=10$)**\n\niteration = 0001: Obj Loss = 2.4803 Feasibility = 1.0565 \n\niteration = 1000: Obj Loss = 3.1297 Feasibility = 0.0000 \n\niteration = 2000: Obj Loss = 3.4119 Feasibility = 0.0000 \n\niteration = 3000: Obj Loss = 3.5966 Feasibility = 0.0000 \n\n\nWe observe that our proposed approach reaches the lowest value for the first task loss among the approaches that satisfy the constraint within an accuracy $\\epsilon=10^{-3}$. Note that while GDMA with $\\rho=1$ yields a lower objective loss, it fails to meet the feasibility requirement within the desired accuracy threshold. The full details and corresponding plots for the experiment will be added to the revised manuscript.\n\n[Ref 5] Jin, Chi, Praneeth Netrapalli, and Michael Jordan. \"What is local optimality in nonconvex-nonconcave minimax optimization?.\" International conference on machine learning. PMLR, 2020.\n\n[Ref 6] Nouiehed, Maher, et al. \"Solving a class of non-convex min-max games using iterative first order methods.\" Advances in Neural Information Processing Systems 32 (2019).\n\n\n---\n\nWe hope our responses address your concerns and would be happy to clarify anything further if needed."}, {"review_id": "nJRFouTZFW", "reviewer": "Reviewer_E7VL", "summary": "This paper studies semi-infinite constrained min-max optimization problems and proposes a novel method that does not rely on the commonly assumed convexity of the objective function and constraint functions, as required by many prior works. \nThe author(s) also prove that their algorithm achieves an $\\epsilon$-KKT solution within a finite number of iterations. \nFinally, they demonstrate the effectiveness of their approach by applying it to a multi-task learning problem.", "questions": "Please see weaknesses", "limitations": "N/A", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "#### Strengths\n- The author(s) study semi-infinite nonconvex constrained min-max optimization problems and propose a solution approach that does not require the commonly assumed convexity of the objective or constraint functions.\n- The author(s) provides detailed proofs.\n\n#### Weaknesses\n\n- Since the proposed method is designed to handle both convex and non-convex functions, it is unclear how it compares to discretization or cutting surface approaches in the convex setting. On the other hand, the authors stated that \"most classical SIP metnods assume convexity or rely on simplifications such as discrete approximation ...\" So even for non-convex cases, simple discretization should be possible. Shouldn't it be used as a baseline in the experiments for comparing both performance and efficiency? Currently, the authors did not compare with any methods.\n\n- The experimental section formulates multi-task learning as a non-convex DRO problem and applies the proposed method to solve it. \nWhile this is an interesting direction, it is not evident whether this setup provides clear advantages over more standard approaches, such as minimizing the sum of task-specific losses.\n\n- To achieve $\\epsilon$-KKT conditions, the proof heavily relies on the appropriate selection of hyperparameters such as $\\alpha_k$, $\\gamma_k$, $N_k$, and $M_k$. \nHowever, in the experimental section, the author(s) did not verify whether the chosen values for these hyperparameters satisfy the theoretical assumptions.\n\n- In Section 3, the author(s) propose the indicator function $\\zeta(x, w)$ and claim that if this function is zero, then the point $x$ is feasible (i.e., the residual is zero) and a critical point of the constraint function (i.e., the gradient value is zero).\nHowever, this claim is incorrect, as $\\zeta(x, w^*(x)) = 0$ only guarantees that at least one of the two terms in the indicator function is zero, but not necessarily both.", "was_revised": true, "final_justification": "The direction is new and worth exploring, but on the other hand, it's a bit unclear to me yet if the proposed approach will eventually be widely applied.", "rebuttal": "**1. How it compares to discretization or cutting surface approaches in the convex setting? Even for non-convex cases, simple discretization should be possible. Shouldn't it be used as a baseline in the experiments for comparing both performance and efficiency?**\n\n**R1.** We appreciate the reviewer's comment. Classical SIP methods focus on minimization problems, and we are not aware of any method that can address min-max structure in the objective function in a nonconvex setting. Moreover, those that can handle nonconvex problems generally focus on a discretization technique, however, these methods suffer from the curse of dimensionality by construction, as the number of required grid points to accurately represent the infinite constraint naturally grows with the dimension of the constraint space and is not effectively implementable on our numerical examples involving neural networks in high dimension (dim($x$)$\\approx 2M$). On the other hand, our proposed method offers a clear advantage by relying solely on first-order information. Other common SIP methods, such as cutting planes or exchange methods, rely on a convexity assumption and do not offer convergence guarantees in the non-convex setting.\nCommon constrained min-max methods, such as gradient-based primal-dual methods require the constraint set to be tractable via projection or evaluation. However, in our semi-infinite constraint setting, there are no guarantees that either will hold. \n\nFor the baseline comparison, we consider an additive robust MTL model where the objective function is the weighted summation of task-specific losses. More specifically, we consider solving $\\min_{x}\\max_{y\\in \\Delta_n}\\max_{w\\in\\Delta_m}\\phi(x,y)+\\rho\\psi(x,w)$ where $\\rho>0$ is the weight parameter. This problem can be solved via min-max optimization methods such as gradient descent multi-step ascent (GDMA) [Ref 1,Ref 2]. We compare the performance of our method GDMA for different values of $\\rho$ in terms of the first task loss, i.e, $\\phi(x_k,y_k)$, and feasibility $[\\psi(x_k,w_k)-r]_+$, where $r$ is the single task threshold as discussed in our paper. Below you can find the result of the experiment on Multi-MNIST dataset.\n\n**iDB-PD (our method)**\n\niteration = 0001: Obj Loss = 2.4279 Feasibility = 1.0807 \n\niteration = 1000: Obj Loss = 2.8115 Feasibility = 0.2393 \n\niteration = 2000: Obj Loss = 2.7242 Feasibility = 0.0387 \n\niteration = 3000: Obj Loss = **2.5080** Feasibility = **0.0010** \n\n**GDMA ($\\rho=1$)**\n\niteration = 0001: Obj Loss = 2.4073 Feasibility = 1.0576 \n\niteration = 1000: Obj Loss = 2.2709 Feasibility = 0.9157 \n\niteration = 2000: Obj Loss = 2.1412 Feasibility = 0.7698 \n\niteration = 3000: Obj Loss = 2.0615 Feasibility = 0.6823 \n\n**GDMA ($\\rho=2$)**\n\niteration = 0001: Obj Loss = 2.4556 Feasibility = 1.1168 \n\niteration = 1000: Obj Loss = 2.3824 Feasibility = 0.6930 \n\niteration = 2000: Obj Loss = 2.2876 Feasibility = 0.5165 \n\niteration = 3000: Obj Loss = 2.2276 Feasibility = 0.3941 \n\n**GDMA ($\\rho=5$)**\n\niteration = 0001: Obj Loss = 2.4700 Feasibility = 1.0810 \n\niteration = 1000: Obj Loss = 2.6608 Feasibility = 0.3444 \n\niteration = 2000: Obj Loss = 2.6859 Feasibility = 0.0352 \n\niteration = 3000: Obj Loss = 2.7191 Feasibility = 0.0000 \n\n**GDMA ($\\rho=10$)**\n\niteration = 0001: Obj Loss = 2.4803 Feasibility = 1.0565 \n\niteration = 1000: Obj Loss = 3.1297 Feasibility = 0.0000 \n\niteration = 2000: Obj Loss = 3.4119 Feasibility = 0.0000 \n\niteration = 3000: Obj Loss = 3.5966 Feasibility = 0.0000 \n\n\nWe observe that our proposed approach reaches the lowest value for the first task loss among the approaches that satisfy the constraint within an accuracy $\\epsilon=10^{-3}$. Note that while GDMA with $\\rho=1$ yields a lower objective loss, it fails to meet the feasibility requirement within the desired accuracy threshold. The full details and corresponding plots for the experiment will be added to the revised manuscript.\n\n[Ref 1] Jin, Chi, Praneeth Netrapalli, and Michael Jordan. \"What is local optimality in nonconvex-nonconcave minimax optimization?.\" International conference on machine learning. PMLR, 2020.\n\n[Ref 2] Nouiehed, Maher, et al. \"Solving a class of non-convex min-max games using iterative first order methods.\" Advances in Neural Information Processing Systems 32 (2019).\n \n\n---\n\n\n**2. It is not evident whether this setup provides clear advantages over more standard approaches, such as minimizing the sum of task-specific losses.**\n\n**R2.** We appreciate the reviewer’s comment. In our revised experiments, we include a comparison with the robust formulation that minimizes the sum of task-specific losses. As detailed in our response to Question 1, our proposed method, iDB-PD, consistently achieves lower loss values across both tasks compared to GDMA with $\\rho = 1$, highlighting the effectiveness of our formulation.\n\nFurthermore, recent studies [Ref 3, Ref 4] have demonstrated the benefits of explicitly modeling task priorities in multi-task learning. Minimizing the unweighted sum of task-specific losses inherently assumes equal importance for all tasks, which limits the model’s ability to adapt to task-specific needs or real-world constraints where some tasks may be more critical. In contrast, our robust MTL formulation enables more flexible and effective optimization across heterogeneous tasks. \n\n[Ref 3] Cheng, Zhengxing, et al. \"No More Tuning: Prioritized Multi-Task Learning with Lagrangian Differential Multiplier Methods.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 39. No. 11. 2025.\n\n[Ref 4] Guo, Michelle, et al. \"Dynamic task prioritization for multitask learning.\" Proceedings of the European conference on computer vision (ECCV). 2018.\n\n\n---\n\n\n**3. In the experimental section, the author(s) did not verify whether the chosen values for these hyperparameters satisfy the theoretical assumptions.**\n\n**R3.** Details of our experimental setup and hyperparameter selection are provided in Appendix A.5. We selected the hyperparameters based on Theorem 4.2 and performed a grid search over a carefully chosen range of values, which is a common approach in the optimization literature, ensuring both theoretical consistency and empirical robustness. \n\n---\n\n\n**4. In Section 3, $\\zeta(x,w^*(x))$ only guarantees that at least one of the two terms in the indicator function is zero, but not necessarily both.**\n\n**R4.** We thank the reviewer for pointing this out. The correct statement should be: *“then the point $x$ is feasible (i.e., the residual is zero) **or** a critical point of the constraint function.”* However, under Assumption 2.3 and using the definition $\\zeta(x, w) = ||\\nabla_x \\psi(x, w) [\\psi(x, w)]_+||$, we can indeed conclude that $\\zeta(x, w^*(x)) = 0$ implies that $x$ is feasible. We will clarify this point in the revised manuscript by expanding the explanation and explicitly connecting it to Assumption 2.3.\n\n---\n\nWe hope our responses address your concerns and would be happy to clarify anything further if needed."}, {"review_id": "blI8g85K7j", "reviewer": "Reviewer_2zSA", "summary": "This paper proposes the iDB-PD method, which adaptively adjusts the search direction based on the satisfaction of the constraint functions. This method is designed for a class of nonconvex minimax optimization problems with nonconvex infinite constraints. This paper further establishes theoretical convergence guarantees under certain assumptions, such as smoothness, strong concavity, or the Polyak–Łojasiewicz (PL) condition.", "questions": "1. To approximate the value of $\\zeta(x_k, w^{*}(x_k))$, this work uses $\\zeta(x_k, w_k)$ where $w_k$ is attained by multi-step gradient ascent and this seems work well under the assumption $\\eta_{\\psi}$-strongly concavity or $c_{\\psi}$-PL condition. However, I believe the number of steps for the multi-step gradient ascent should depend on constants like $\\eta_{\\psi}$ or $c_{\\psi}$ to guarantee the attained value is well-approximated. Additionally, the required number of steps seems related to the value of $\\theta$. Since these problem-dependent constants are not given a priori, how can the exact number of steps, $M_k$, be practically selected? \n2. The performance in the Multi-MNIST experiment described in Figure 1 exhibits significant oscillation. It would be helpful if the authors could provide some explanation for this behavior. \n3. (Minor) There appears to be a typo on line 240; it should likely be \"whether.\"", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. This work establishes global non-asymptotic convergence guarantees under a more generalized regularity condition. \n2. This paper is well organized and effectively presents the key differences, making it easy for the reader to follow. \n\nWeaknesses: While the theoretical results are well-developed, it is not entirely clear how they can be effectively applied in practice; see the following question for more details.", "was_revised": true, "final_justification": "The author has provided satisfactory answers to my questions and concerns regarding both the practical selection of hyper-parameters and explanations of the given experiment. Therefore, I will maintain my positive score.", "rebuttal": "**1. The number of steps for the multi-step gradient ascent should depend on constants like $\\eta_\\psi$ or $c_\\psi$. Additionally, the required number of steps seems related to the value of $\\theta$. How can the exact number of steps, $M_k$, be practically selected?**\n\n**R1.** \nWe thank the reviewer for their comment. The multi-step parameters $M_k$ and $N_k$ indeed depend on problem-specific constants associated with the maximization component, such as $\\eta_\\psi$ and $c_\\psi$. Details regarding the selection of these parameters are provided in Appendix Theorem A.9 ( Restatement of Theorem 4.2). Additionally, the dependence of $M_k$ and $N_k$ on the parameter $\\theta$ has an intuitive interpretation: $\\theta$ reflects the complexity of the infinite constraint set, where values of $\\theta$ closer to 0 indicate easier subproblems and faster convergence, while values near 1 correspond to more challenging scenarios and slower convergence rates -- See Remark 4.1.\n\nIn practice, although the exact problem constants may be unknown, the theoretical results in Theorem 4.2 suggest that $M_k$ and $N_k$ should grow at a rate of at least $\\mathcal{O}(\\log(k+2))$ or $\\mathcal{O}(\\log(T+1))$, where $T$ denotes the total number of iterations. One practical strategy is to choose a slightly more aggressive growth, e.g., $\\lceil (k+2)^{0.1}\\rceil$ or $\\lceil \\log^2(k+2)\\rceil$, ensuring that beyond some iteration index $T_0$, their values exceed the theoretical threshold. As a result, the convergence guarantees of the proposed method remain valid after a certain warm-up phase.\n\n\n---\n\n\n**2. The performance in the Multi-MNIST experiment described in Figure 1 exhibits significant oscillation. It would be helpful if the authors could provide some explanation for this behavior.**\n\n**R2.** This behavior indeed stems from the inherent complexity of the problem. As noted in lines 359–361, our robust Multi-Task Learning formulation gives rise to a challenging nonconvex optimization problem with infinitely many functional constraints. Although our method is supported by provable convergence guarantees, the observed oscillations are a natural manifestation of the algorithm's iterative efforts to balance three competing goals: minimizing the objective function, enforcing feasibility with respect to the robust constraints, and satisfying the KKT optimality conditions (including stationarity and complementarity slackness). These oscillations reflect the algorithm's trajectory as it alternates between improving feasibility and achieving stationarity. This behavior commonly arises in both convex and nonconvex optimization problems with functional constraints, e.g., see the experiments in [Ref1].\n\n[Ref1] Yazdandoost Hamedani, Erfan, and Necdet Serhat Aybat. \"A primal-dual algorithm with line search for general convex-concave saddle point problems.\" SIAM Journal on Optimization 31.2 (2021): 1299-1329.\n\n---\n\n\n**3. (Minor) There appears to be a typo on line 240; it should likely be \"whether.\"**\n\n**R3.**\nWe thank the reviewer for pointing out this typo. All typos will be corrected in the revised version of the manuscript.\n\n---\n\nWe hope our responses address your concerns and would be happy to clarify anything further if needed."}]

Author rebuttal:

Meta-review: The paper studies a class of "semi-infinite nonconvex min-max optimization" problems, where the objective is nonconvex in the primal variables, strongly concave or satisfies the PL condition in the dual variables, and on the primal side is subject to a semi-infinite family of constraints that are possibly nonconvex but satisfy certain regularity conditions. This family of problems is motivated by applications in adversarial robustness and safety-constrained learning. 

The paper introduces a first-order method that is guaranteed to converge to eps-approximate solutions (in terms of stationarity, complementary slackness, and feasibility) in poly(1/eps) iterations. While there is a broad literature on semi-infinite programming, this is the first result of its kind (first-order algorithm, nonasymptotic convergence guarantees). Despite initial concerns, there was broad support for the paper's acceptance, especially since there is potential for leading to further developments in this area. The concerns regarding practical impact of the results were downweighted, as the paper makes solid theoretical contributions, as pointed out in the reviews.
Decision: Accept (poster)