Near-Optimal Solutions of Constrained Learning Problems

(1.1) Counterfactual fairness was not defined by us. The definition was proposed and studied in [17] (see Definition 5). We use a constrained learning formulation to tackle that problem using the COMPAS dataset [21] as in [7], [15], [22].

(1.2) In this setting, each constraint represents a requirement that the output of the classifier be near-invariant to changes in the protected features (in our case gender and race). For instance, the output of the classifier should be (almost) the same whether, for all other variables kept the same, the gender of a sample is changed from male to female (and vice-versa) or whether the race is changed from caucasian to african-american, latino to caucasian...

(1.3) While our formulation does not require objective and constraints to be defined over the same distribution, this is how the requirement of counterfactual fairness is formulated (see Definition 5 in [17]).

(1.4-1.5) The lack of boldface in the $x$ of the constraints of the learning problem are a typo. Effectively, all $x$ in the problem refer to the feature vector $\mathbf{x}$. As for the input of the function, in retrospect we must agree with the reviewer that our abuse of notation causes confusion. In an attempt to highlight the protected features, we collect them into the separate vector $\mathbf{z}$. In other words, $\mathbf{x} = [\bar{\mathbf{x}}; \mathbf{z}]$, so that we can write $f\_{\theta}(\mathbf{x}) = f\_{\theta}(\bar{\mathbf{x}}, \mathbf{z})$. This is more in keep with the notation used in fair learning rather than the invariant learning. But this distinction is unnecessary as we could define counterfactual fairness more generally, with respect to any transformation of the data, i.e., for a set of transformations~$\{\rho_i\}$,

$$\mathbb{E}\_{(x, y)} \left[ D_{KL}(f\_{\theta}(\mathbf{x}) || f\_{\theta}(\rho_i (\mathbf{x})) \right] \leq c, \: \text{for all } i.$$

If the reviewer agrees with us that this is less prone to confusion, we will reformulate the problem in those terms in the revised manuscript.

(2) We would certainly not claim this as contribution of the manuscript as it is a classical result from duality theory [23], [24], [16]. A straightforward example where this happens is in linear programs, where the Lagrangian evaluated at the optimal dual variable $L(\phi, \lambda^\star)$ is a constant (independent of $\phi$). In this case, $\text{argmin}\_{\phi \in \mathcal{F}}\ L(\phi, \lambda^\star) = \mathcal{F}$, which includes many infeasible candidates. This is why, as we mentioned our general response, it is not always possible to extract a feasible solution for $(P_p)$ from the optimal dual variables $\lambda^\star_p$ without using primal averaging (for convex problems only) or randomization (for both convex and non-convex problems). Figure 1 (left) in our work further illustrates this phenomenon: though the blue constraint is often infeasible, it turns out to be feasible on average.

We thank the reviewer for this time and detailed feedback.

(1.1) The effect of solving line 4 approximately is quite mild, as considered in Theorem 2 of [7]. Essentially, it introduces a bias on the supergradient used to update $\lambda$ in line 5. While this bias limits the precision at which the $\lambda_p^\star$ can be recovered, its effects do not accumulate over the trajectory. Indeed, suppose we replace line~4 with a $\rho-$approximate oracle, i.e., one capable of finding $f\_{\theta}^{\dagger} \in \mathcal{F}\_{\theta}$, such that

$$L(f\_{\theta}^{\dagger}, \lambda_p) \leq \min\_{\theta\in\Theta} L(f\_{\theta}, \lambda_p) + \rho$$

for $\rho \geq 0$. Then, $\ell(f_{\theta}^{\dagger})$ is an approximate supergradient of $g_p$, i.e.,

$$g_p(\lambda) \geq g_p(\lambda_p) + (\lambda - \lambda_p)^T \ell(f_{\theta}^{\dagger}) - \rho$$

Hence, Lemma 4.1 holds with an extra term depending on $\rho$, namely,

$$\lim_{t \to \infty} g_p^{\text{best}}(t | \lambda(t_0)) \geq D^{\star}_p - \left(\frac{\eta S^2}{2}+\rho\right) \quad \text{a.s.,}$$

which propagates to Proposition 4.2. We will extend our results to account for a~$\rho-$approximate oracle in the revised manuscript.

It is worth noting that, even in the non-convex case, there is a myriad of results showing that near-optimal solutions (small $\rho$) can be obtained for line 4 using gradient descent, e.g., for overparametrized neural networks [3,4,5,6]. Since this approximation affects the results in a controlled manner, we hope that this addresses the reviewer's concern.

(1.2) This issue is related to the estimation error (i) that we mention in our conclusion as potential future work as well as in our overall response above when describing the context of our paper. As we explain there, the focus of this paper is on analyzing the algorithmic error (iii) that arises from retrieving a specific model from Alg. 1 rather randomizing over its iterates. We then argue that considering other sources of error (such as the estimation error) is beyond the scope of this paper considering that (a) the approximation and estimation errors were already analyzed in detail in [7] (Section 3) and (b) analysis of the algorithmic error already involves considerable challenges and novel proof techniques (as noted by the reviewer as well as Y13X and rUm3). Naturally, we welcome further discussions with the reviewer if they believe the paper contributions are not sufficient.

That being said, we provide a potential roadmap (following [7], Prop 3.4) extending our results in order to show that estimation error, though non-trivial, is not impossible.

[7] tackled this issue in the context of the duality gap between an empirical version of $(\text{D}_p)$ and $(\text{P}_p)$ using uniform convergence. Indeed, many results from learning theory (such as those based on VC dimension or Rademacher complexity) establish that, with probability $1-\delta$ over sample draws of $N$ samples,

$$\left|\mathbb{E}\_{\mathfrak{D}}\left[\ell_i\left(f\_{\theta}(x), y\right)\right]-\frac{1}{N} \sum_{n=1}^N \ell_i\left(f\_{\theta}\left(x_n\right), y_n\right)\right| \leq \zeta_i(N, \delta),$$

for all $\theta \in \Theta$ [18]. The function $\zeta_i(N, \delta)$ establishes the sample complexity of the problem. Under uniform convergence, every optimization problem can be solved within $\zeta_i(N, \delta)$ (with high probability). The implications of this were characterized in [7] Theorem 1, where they proved a near-feasible primal solution exists, but not that it can be recovered without randomization as we do here (see [7] Theorem 3).

We thank the reviewer for acknowledging the soundness, quality of presentation and significance of the contributions of this work. In what follows, we address the weaknesses and answer the concerns raised by the reviewer.

(1) The reviewer is correct in that, unlike the unparametrized problem $(P_u)$ which is strongly dual, the constrained learning problem $(P_p)$ will display a positive duality gap ($P_p^\star - D_p^\star$). However, [7] Proposition 3.3 shows that this gap is bounded under our Assumptions 3.1-3.3 (see details general response). As also pointed by reviewer z2M9, this duality gap bound can be combined with the results from our paper to bound the near-optimality $|\ell_0(f_{\theta}(\lambda^*_p)) - P_p^\star|$. Namely, for $P^*_p - D^*_p \leq \Delta$, it holds that

$

\tag{1} | P_p^\star - \ell_0(f_{\theta}(\lambda^{\star}_p))| \leq \| \lambda^{\star}_p \|_1 \| \ell(\phi^{\star}) - \ell(f_{\theta}(\lambda^{\star}_p)) \| _{\infty} + (1 + |\lambda^{\star}_p |_1 ) M\nu + \Delta

$

Taking $\Delta$ from [7] Proposition 3.3, and the bound in our Corollary 3.9 yields the desired result. Note that, plugging these values, (1) is of the same order as Corollary 3.9, i.e., no new terms appear, only the constants are different. We will include this bound as a corollary in the revised version of the manuscript. For the reviewer's reference, we provide a sketch of the derivations below.

Using the fact that $P^{\star}_p - D^{\star}_p \leq \Delta$ and $P^{\star}_u \leq P^{\star}_p$, we obtain that

$$P_u^\star - D_p^\star \leq \Delta \Leftrightarrow \ell_0(\phi^\star) - \ell_0(f\_{\theta}(\lambda^\star_p)) \leq \lambda^{{^\star}T}_p \ell(f\_{\theta}(\lambda^\star_p)) + \Delta$$

Since $\phi^*$ is feasible [$\ell(\phi^\star)) \leq 0$] and $\lambda^\star_p \succeq 0$ we obtain

$$\begin{aligned} \ell_0(\phi^\star) - \ell_0(f\_{\theta}(\lambda^\star_p)) & \leq \lambda^{{\star}T}_p (\ell(f\_{\theta}(\lambda^{\star}_p) -\ell(\phi^{\star})) + \Delta \\\ & \leq \Vert \lambda^\star_p \Vert_1 \Vert \ell(\phi^{\star}) - \ell(f\_{\theta}(\lambda^{\star}_p)) \Vert\_{\infty} + \Delta \end{aligned}$$

To conclude the derivation of (1), we use $\nu$-universality and $M$-Lipschitz continuity (Assumptions 3.1 and 3.3) to get that there exists $\theta^\prime$ such that $\vert \ell_i(\phi^{\star}) - \ell_i(f\_{\theta^\prime})\vert \leq M\nu$. The duality gap bound then implies the approximate saddle-point relation

$$L(f\_{\theta}(\lambda^\star_p), \lambda^\star_u) - \Delta \leq L(f\_{\theta}(\lambda^\star_p), \lambda^\star_p) \leq L(f_{\theta^\prime}, \lambda^\star_p) + \Delta,$$

whose second inequality gives

$$\begin{aligned} \ell_0(\phi^\star) - \ell_0(f\_{\theta}(\lambda^\star_p)) &\geq \ell_0(f\_{\theta^\prime}) - M\nu - \ell_0(f\_{\theta}(\lambda^\star_p)) \newline & \geq \lambda^{{\star}T}_p (\ell(f\_{\theta}(\lambda^\star_p)) - \ell(\phi^\star)) - \Delta - (1 + \Vert \lambda^{\star}_p\Vert_1 )M\nu \newline & \geq - \Vert \lambda^{\star}_p \Vert_1 \Vert \ell(\phi^{\star}) - \ell(f\_{\theta}(\lambda^{\star}_p)) \Vert\_{\infty} - (1 + \Vert \lambda^{\star}_p\Vert_1 ) M\nu - \Delta \end{aligned}$$

which completes the proof.

We appreciate the feedback of the reviewer. We refer to our general response to all reviewers for clarifications of the main motivations, contributions, and challenges tackled by our work. We hope that our answers below, together with our general response, clarifies these points, but welcome any further questions they may have.

(1) While we appreciate the reviewer's point, we respectfully disagree. While it is true that "optimality" has different meanings in statistics and optimization/algorithms, we do not see why the former should take any priority over the latter. Optimization plays as key a role in modern data science and machine learning as statistics, as evidenced by the overwhelming number of theoretical and empirical results that heavily rely on optimization arguments or improvements on optimization algorithms. We do not therefore believe that what we take "near-optimality" to mean in this manuscript, which is in line with standard definitions both in optimization and computer science (e.g., [14]), is in any way misleading. That being said, we are happy to consider any alternative suggestion the reviewer might have.

(2) As explained in the general comment, two challenges must be overcome in this non-convex setting. The first one is the lack of strong duality (as pointed out by reviewer rUm3). In other words, the value $D_p^\star$ of the dual problem $(D_p)$ need not be a good approximation of the value $P_p^\star$ of $(P_p)$. The magnitude of this gap was characterized in [7] Proposition 3.3. Naturally, the quantities that characterize the feasibility of primal iterates are present in the duality gap bound of [7]. For example, the duality gap $P^{\star}_p - D^{\star}_p$ depends linearly on the richness of the parametrization $\nu$.

The second main challenge is that dual ascent methods such as Algorithm 1 (also referred to as best response) need not converge, and even it did, recovering a feasible solution from optimal dual variables may not be possible. As explained in section 2.2 and shown experimentally on Figure 1, the non-uniqueness of Lagrangian minimizers can lead to large oscillations in the feasibility of primal iterates. In the linear programming example of the general comment (which is a convex problem) the primal iterates obtained as a byproduct of the ascent method can severely violate the constraints. Indeed, in this case, the Lagrangian $L(\phi, \lambda^\star)$ is a constant (independent of $\phi$), i.e., $\Phi^\star(\lambda^\star) = \mathcal{F}$. The difficulty of recovering (near-)feasible primal solutions explains the need of randomized solutions (see e.g, ([10], Theorem 2; [11], Theorem 4.1; [7], Theorem 3). However, randomized predictors are impractical and do not solve problem $(P_p)$. Thus, it is highly relevant to determine conditions under which a near-feasible primal iterate, which is also near-optimal can be recovered. Also note that the analysis carried out in this paper involved novel proof techniques (as per reviewer z2M9), such as the use of the curvature of the perturbation function (see section 3.3.2).

(3) We respectfully disagree. The experiments in this paper clearly illustrate the fact that richer parametrizations lead to better properties of Alg. 1 in terms of the constraint violation of its iterates. This behavior, suggested by our theorems, is not straightforward. Indeed, this paper analyses the optimization error when solving constrained learning problems and not the estimation or approximation error~(see general response). Hence, while it is indeed expected that richer parametrizations will lead to lower approximation error, it is certainly not straightforward that richer models make optimization easier. While better parametrizations do provide more feasible models to choose from, they also contain more infeasible ones. Finding solutions requires handling a much larger class of hypothesis, so that we would actually expected the optimization to be harder. Our results, however, prove that richer parametrizations make it easier for the algorithm to find a feasible solution. In fact, not only a feasible solutions, but one that is also near optimal, which is not straightforward (as per our previous answer). This conclusion from Proposition 4.2 is illustrated in Figure 2(right). Note that this plot does not represent the approximation (test) error, but the constraint violation. We will work on improving the description and axis labels of these plots to avoid confusion in the future.

Thank you for your time and effort in reviewing our paper and for your positive evaluation of the soundness and presentation of our work. In what follows, we address the three weaknesses that were brought up.

(1) Yes. Consider that there exists a parameter $\theta_0$ and a strictly positive constant $C>0$ such that for all constraints $i$ we have that $\ell_i(f_{\theta_0}) \leq -C$. We then have that

$

\tag{1} \| \lambda^{*}_p \|_1 \leq \frac{\ell_0(f_{\theta_0})-D^{\star}_p }{C} .

$

This is a standard result in duality theory [8] that we have verified holds for the nonconvex optimization problems that we study in this paper. We will incorporate this result and its proof in the final manuscript.

We point out that the existence of $\theta_0$ and $C>0$ satisfying $\ell_i(f_{\theta_0}) \leq -C$ is not a new assumption. We already require strict feasibility in Assumption 3.2. We simply did not name the strict feasibility constant $C$. Further notice that the bound in (1) does not depend on the number of constraints involved in the optimization problem, but only on the properties of a strictly feasible point $\theta_0$.

(2) This is a good point. Let us point out that the algorithm we propose in this paper is a standard stochastic dual gradient ascent algorithm in which dual iterates are moving along stochastic gradients of the dual function. Since the dual function is concave (dual functions are always concave for constrained minmization problems, convex or not), convergence properties of dual iterates are therefore well understood. They follow from standard convergence results of stochastic gradient ascent for concave functions [12], [20].

In this dual gradient ascent algorithm primal iterates are a byproduct. They are computed as Lagrangian minimizers associated with dual iterates. The main goal of our paper is to study the convergence of these primal iterates, which, as we outline in the general response, is not a given. Even in the case of convex optimization problems, it is not always true that primal iterates of Alg. 1 converge to optimal primal variables.

Our paper provides a novel analysis for the convergence of primal iterates in (nonconvex) learning problems. To do so we develop novel analyses and proof techniques relying on the comparison of the problem of interest with a convex reference given by the unparameterized constrained learning problem. We think that it is best for readers to keep the paper focused on this contribution and that, consequently, finite time results are a topic of future research.

(3) This is an interesting point. The bounds that we provide in Theorem 3.5 and Corollary 3.9 are of the form:

$

\tag{2} | \ell_i(f_{\theta}(\lambda^{\star}_p)) - \ell_i(\phi^{\star}) | \leq \zeta,

$

for some specific constant $\zeta$. This equation is a comparison between the loss $\ell_i(f_{\theta}(\lambda^{\star}_p))$ obtained from the Lagrangian minimizers of the parameterized Lagrangian with the loss $\ell_i(\phi^{\star})$ of the solution of the unparameterized constrained learning problem.

We take it that the reviewer expected to see a comparison between the loss $\ell_i(f\_{\theta}(\lambda^{\star}_p))$ obtained from the Lagrangian minimizers of the parameterized Lagrangian with the loss $\ell_i(f\_{\theta}^*))$ of the solution of the parameterized constrained learning problem. They are therefore intrigued by the bounds that appear in Theorem 3.5 and Corollary 3.9.

The reason for the unexpected appearance of the difference in the left hand side of Corollary 3.9 is the core technical innovation of our proof techniques. The parametrized learning problem with variables $f_\theta$ is non-convex and difficult to analyze. The unparametrized problem with variable $\phi$ is convex and one that we can analyze using functional convex analysis techniques. Our technical approach relies on the fact that these two problems and their duals can be shown to be $O(\nu)$-close to each other if the parametrization is $\nu$-universal. This is the reason why feasibility bounds end up comparing the loss $\ell_i(f\_{\theta}(\lambda^{\star}_p))$ obtained from the Lagrangian minimizers of the parameterized Lagrangian with the loss $\ell_i(\phi^{\star})$ of the solution of the parameterized constrained learning problem -- as opposed to the loss $\ell_i(f\_{\theta}^{\star}))$ of the solution of the parameterized constrained learning problem.

Further notice that since $\phi^*$ is feasible (i.e: $\ell_i(\phi^*)\leq0$) , an upper bound on the infeasibility of $f_{\theta}(\lambda^*_p)$ can be derived directly from (2). Explicitly, $\ell_i(f\_{\theta}(\lambda^*_p)) \leq \ell_i(f\_{\theta}(\lambda^*_p)) - \ell_i(\phi^*) \leq \zeta$.

(Q7) The reviewer has a point. We will carefully review the notation of the paper and keep $D$ to refer only to the value of the dual problems $(D_u)$ and $(D_p)$. In the quote from the reviewers question, $D$ refers to the dataset (which only appears and is relevant in Section 5). The quantity $D^{\star}_p$ from Lemma 4.1 is defined in Section 2.2 as the optimal value of the parametrized dual problem $(D_p)$. Alg. 1, however, is correctly defined in terms of $\ell$. Indeed, recall that this paper does not deal with the estimation errors. Hence, we do not consider empirical approximations of the expectations in $(P_p)$ or $(D_p)$. Only when presenting the numerical experiments in Section 5 do we use these empirical approximations in order to illustrate our results in a concrete application. We refer the reviewer to our general response for a more detailed explanation on the scope and challenges of this paper.

(Q8) Yes, we mean Adam. As per Section 2.1, the constraints in this application are defined as:

$$\mathbb{E}\_{(x, y)} \left[ D_{KL}(f\_{\theta}(x) || f\_{\theta}(\rho_i (x)) \right] \leq c$$

where the $\rho_i$ denote changes in the protected features (in our case gender and race). In the current version of the manuscript the protected features are denoted by $z$, but after addressing comments from reviewer Z2M9, we find that the above presentation is less prone to misunderstanding. In other words, $\ell_i(\phi) = \mathbb{E}\_{(x, y)} \left[ D_{KL}(\phi(x) || \phi(\rho_i (x)) \right]$. As we mention in Section 5, $\ell_0$ is the cross-entropy loss.

Notice that these losses are convex and continuously differentiable. Hence, when using weight decay (which bounds the norm of $\theta$), $\ell_0$ is strongly convex and all losses are Lipschitz continuous and smooth. While constants for these properties ($M$, $\beta$, $\mu_0$) can be estimated, typical estimates are quite loose. Additionally, as we explain in our answer to rUm3, the richness of the parametrization $\nu$ in Assumption 3.3 cannot typically be computed, although for many parametrizations (e.g., NN), it is known that any $\nu > 0$ can be achieved using large enough models. Though we cannot compute the exact value of our bound, we directly observe the behaviors it predicts in our experiments. For instance, Figure 2(right) shows that, as predicted by Corollary 3.9, the constraint violation of the best iterate decreases as the model capacity increases.

Questions

(Q1) Due to the correlation between the protected features and other features, simply hiding the protected features from the model does not guarantee fairness. In fact, removing race as a predictor in our example has almost no impact on the predictions of the model (the accuracy and prediction disparity between races remain unchanged). This is a well-studied phenomenon in the fairness literature (see, e.g., [11]). This shows the need for the addition of an explicit constraint in order to guarantee fairness (in our case, counterfactual fairness as defined in [17]).

(Q2) We thank the reviewer for pointing out this typo. Indeed, when the parametrization used in a neural network, $\mathcal{F}_{\theta}$ is not a convex hypothesis set. That is why, even though the losses $\ell_i$ are convex functionals, $(P_p)$ is not a convex problem. This is in fact one of the major challenges overcome by this challenge (see general response for more details).

As we argue in the general response, this paper does not deal with the approximation (ii) and generalization (iii) errors. It deals with the algorithmic error (iii), i.e., it studies the primal iterates $f_{\theta}(\lambda_t)$ obtained as a by-product of Alg. 1 to understand whether they provide a (feasible) solution of $(P_p)$. This is not straightforward even in the convex setting and prior results in the non-convex case rely on randomization (see, e.g., guarantees in [10], Theorem 2; [11], Theorem 4.1; [7], Theorem 3). We explicitly show that, under mild conditions, randomization is not necessary. In view of the challenges and novel proof techniques deployed in this paper to characterize error (iii) alone (i.e., on whether Alg. 1 can be used to solve $(P_p)$), considerations on the generalizability, robustness, and performance on untrained data of solutions of $(P_p)$ are left for future work.

(Q3) This could indeed be done without major modifications since (strong-)convexity and the Lipschitz continuity of the gradients is preserved under expectation (the latter requires some regularity in order to exchange expectation and differentiation, e.g., this can be done using dominated convergence theorem for bounded $\mathcal{F}$). We choose to use Assumption 3.1 and 3.6 since imposing smoothness and convexity on $\tilde{\ell}$ is stricter. That being said, the reviewer has a point that this assumption is more natural and we will therefore include this comment in the revised version of the manuscript.

(Q4) As mentioned in Section 3.1, the unparametrized problem has no duality gap $(P_u^\star = D_u^{\star})$ since it is a convex problem for which Slater's condition holds (Assumptions 3.1-3.2). As the reviewer correctly notes, this is not the case for the parametrized problem. This is in fact one of the major challenges that this work has to overcome (see general responses). Under our Assumption 3.1-3.3, the duality gap of $(P_p)$ can be bounded as in [7], Proposition 3 (see again general response for details). Combining our near-feasibility results from Corollary 3.9 with this duality gap bound yields a guarantee in terms of the objective values $|\ell_0(f_{\theta}(\lambda^*_p)) - P^*|$ (further details are provided in answer 1.3 to reviewer z2M9). We will include these comments and result in the revised version of the manuscript.

(Q5) We refer the reviewer to the detailed discussion provided in a previous answer.

(Q6) No. As we mention in the beginning of section 3.3, sections 3.3.1 and 3.3.2 provide an outline of the proof of Theorem 3.5 and Corollary 3.9, the main results of this paper. Indeed, Theorem 3.5 is obtained by directly combining Propositions 3.10 and 3.11. We will further clarify this point in the beginning of section 3.3.

We thank the reviewer for the detailed feedback and for highlighting the novelty and rigour of our work. Next, we address the weaknesses they point out (i.e, interpretation of the results and strictness of assumptions) and answer the concerns they raised.

Weaknesses

(1) As we mention in our general response, the issue of neural networks vs poorly chosen kernel relates to the approximation (ii) [and perhaps generalization (iii)] error. In this manuscript, we study the algorithmic error (iii) that only considers how good a solution of $(P_p)$ can be obtained using Alg. 1. Whether $(P_p)$ yields good solutions for learning problem, i.e., errors (ii)-(iii), is tackled in, e.g., [7], [15]. In the case of a single poorly chosen kernel, there is no algorithmic error (iii): either the one kernel is feasible or the problem has no solution. This is reflected in our results ($\lambda \to \infty$ if $(P_p)$ is infeasible).

Things are more interesting in the neural network case. Indeed, while we do not analyze the approximation error (ii), the richness of the parametrization still plays a role in our results. Indeed, we show that more expressive models (Assumption 3) have a positive impact on the algorithm behavior. In other words, there are stronger guarantees for Alg. 1 to find near-feasible solutions of $(P_p)$ when using larger NNs. This point is illustrated in Figure 2(right), which shows the constraint violation as a function of the model capacity. This is not straightforward: while better parametrizations do provide more feasible models to choose from, they also contain more infeasible ones. Finding feasible solutions requires handling a much larger class of hypothesis, so we could actually expected the optimization to be harder. Combined with the duality gap bounds from [7], [15], this implies that Alg. 1 finds solutions that are not only near-feasible, but also near-optimal. This is not straightforward considering the lack of strong duality due to non-convexity and the challenges in proving convergence of primal iterates without randomization (see general response).

We will add new discussions of these interpretations and highlight these conclusions in the revised version of the manuscript.

(2) Our results effectively depend on five assumptions (since Assumption 3.4 is implied by 3.1, 3.6, and 3.7 and number 3.5 is a theorem). We summarize them below:

• Assumption 3.1: $\ell_i$ are convex and Lipschitz continuous. $\ell_0$ is strongly convex
• Assumption 3.2: there exists a strictly feasible $\phi$, i.e., $\ell_i(\phi) \leq C$ for all~$i$ and some $C > 0$
• Assumption 3.3: For all $\phi \in \mathcal{F}$, there exists $\theta \in \Theta$ such that $\| \phi - f_{\theta} \|_{L_2} \leq \nu$
• Assumption 3.6: $\ell_i$ are smooth (Lipschitz gradients)
• Assumption 3.7: The Jacobian $D_{\phi} \mathbf{\ell}( \phi^{\star})$ has full-row rank, where $D_{\phi}$ denotes the Fréchet derivative

As the reviewer notes, these assumptions are mostly regularity assumptions over which a practitioner has full control. Indeed, Assumptions 3.1 and 3.6 impose mild restrictions on the losses, namely, that they be Lipschitz continuous, convex, and smooth. These are widely used to prove convergence results for gradient descent algorithms even in the convex setting and are satisfied by typical losses used in ML when, e.g., the hypothesis class $\mathcal{F}$ is compact. Assumption 3.3 is always satisfied for some finite $\nu$ and describes the richness of the parametrization. A detailed description of this assumption was provided in section 3.1 as well as our previous answer.

Assumptions 3.2 and 3.7 are closely related to constraint qualifications widely used in the analysis of Alg. 1 in convex settings. Indeed, Assumption 3.2 is a stricter version of the well-known Slater's condition from convex optimization. It guarantees that $(P_u)$ and $(P_p)$ are well-posed. For overparametrized models, this assumption is not strict. Assumption 3.7, on the other hand, is not straightforward to satisfy at first sight. It is, however, a typical assumption used to derive duality results in convex optimization known as "linear independence constraint qualification" or LICQ [16]. In fact, it is the weakest constraint qualifications for convex optimization. This suggests that it may be possible to replace Assumption 3.7 by a stricter version of Assumption 3.2, although this is not immediate. We therefore choose to state the weakest assumptions under which our results would hold.

We will expand the description of these assumptions already present in Section 3.1 to highlight their mildness and limitations in the revised version.

[1] Nesterov, Yurii. Introductory lectures on convex optimization: A basic course. Vol. 87. Springer Science & Business Media, 2003.

[2] Bach, F., Jenatton, R., Mairal, J., Obozinski, G., Sra, S., Nowozin, S. and Wright, S.J., 2012. Optimization for Machine Learning.

[3] R. Ge, J. D. Lee, and T. Ma, “Learning one-hidden-layer neural net-works with landscape design,” in International Conference on Learning Representations, 2018.

[4] A. Brutzkus and A. Globerson, “Globally optimal gradient descent for a convnet with gaussian inputs,” in International Conference on Machine Learning, 2017, pp. 605–614.

[5] M. Soltanolkotabi, A. Javanmard, and J. D. Lee, “Theoretical insights into the optimization landscape of over-parameterized shallow neural networks,” IEEE Transactions on Information Theory, vol. 65, no. 2, pp. 742–769, 2018

[6] C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals, “Understanding deep learning requires rethinking generalization,” in International Conference on Learning Representations, 2017

[7] Chamon, Luiz FO, et al. "Constrained learning with non-convex losses." IEEE Transactions on Information Theory 69.3 (2022): 1739-1760.

[8] Nedić, A. and Ozdaglar, A., 2009. Approximate primal solutions and rate analysis for dual subgradient methods. SIAM Journal on Optimization, 19(4), pp.1757-1780.

[9] Daskalakis, C. and Panageas, I., 2018. Last-iterate convergence: Zero-sum games and constrained min-max optimization. arXiv preprint arXiv:1807.04252.

[10] Cotter, A., Jiang, H., Gupta, M.R., Wang, S.L., Narayan, T., You, S. and Sridharan, K., 2019. Optimization with Non-Differentiable Constraints with Applications to Fairness, Recall, Churn, and Other Goals. J. Mach. Learn. Res., 20(172), pp.1-59.

[11] Kearns, M., Neel, S., Roth, A. and Wu, Z.S., 2018, July. Preventing fairness gerrymandering: Auditing and learning for subgroup fairness. In International conference on machine learning (pp. 2564-2572). PMLR.

[12] Shor, N.Z., 1998. Nondifferentiable optimization and polynomial problems (Vol. 24). Springer Science & Business Media.

[13] Hornik, K., Stinchcombe, M. and White, H., 1989. Multilayer feedforward networks are universal approximators. Neural networks, 2(5), pp.359-366.

[14] Mitzenmacher, M. and Upfal, E., 2017. Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis. Cambridge university press

[15] Chamon, L. and Ribeiro, A., 2020. Probably approximately correct constrained learning. Advances in Neural Information Processing Systems, 33, pp.16722-16735.

[16] Bertsekas, D.P., 1997. Nonlinear programming. Journal of the Operational Research Society, 48(3), pp.334-334.

[17] Kusner, M.J., Loftus, J., Russell, C. and Silva, R., 2017. Counterfactual fairness. Advances in neural information processing systems, 30.

[18] Shalev-Shwartz, S. and Ben-David, S., 2014. Understanding Machine Learning: From Theory to Algorithms.

[19] Boyd, S., Xiao, L. and Mutapcic, A., 2003. Subgradient methods. lecture notes of EE392o, Stanford University, Autumn Quarter, 2004, pp.2004-2005

[20] Grimmer, B., 2019. Convergence rates for deterministic and stochastic subgradient methods without Lipschitz continuity. SIAM Journal on Optimization, 29(2), pp.1350-1365.

[21] Clerk’s Office, Broward County Sherrif’s Office, Florida Department of Corrections, COMPAS Recidivism Risk Score Data and Analysis.{ ProPublica 2020.

[22] Diana, E., Gill, W., Kearns, M., Kenthapadi, K. and Roth, A., 2021, July. Minimax group fairness: Algorithms and experiments. In Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society (pp. 66-76).

[23] Bazaraa, M.S., Sherali, H.D. and Shetty, C.M., 2013. Nonlinear programming: theory and algorithms. John wiley & sons.

[24] Larsson, T., Patriksson, M. and Strömberg, A.B., 1999. Ergodic, primal convergence in dual subgradient schemes for convex programming. Mathematical programming, 86, pp.283-312.