A Modified Proximal-Perturbed Lagrangian for Non-Convex Non-Smooth Representatives of Fairness Constraints

• The authors claim that the assumptions are standard in the optimization literature; however, after reviewing some of the cited papers, I could not find the exact same assumptions. Could the authors provide more precise references to the relevant literature? In particular for Assumption 5.

• Why is the problem in Eq. (3) tractable? As stated some lines above the constraint is non-convex and non-smooth. What do the authors mean by tractable?

• Could the authors explain the different terms in the Proximal-Perturbed Lagrangian in Eq. (6) ? In particular, why are the penalty and proximal terms added to the regular Lagrangian?

• Could the authors explain the different choices for the update rules (and the chosen order)? For instance, why is the parameter $\theta_k$ updated as in Eq. (9)?

• The authors state that they "show that the generated primal-dual iterates converge to a KKT point of problem (3)". The KKT conditions for problem (3) are given in (4) but I don't see the link with the obtained results in Theorem 1 and 2. Could the authors clarify this point?

• Unlike claimed by the authors, there is no rate of convergence in the statement of Theorem 1 (though one can be obtained from the proof). The authors should be more rigorous when describing (or stating) Theorem 1. Same comment applies to Remark 1.

• How does Theorem 2 guarantee the feasability guarantees for Algorithm 1?

• I cannot make the link between Lemma 4, Theorem 1 and Remark 1. Could the authors explain how they go form a bound on the norm of the sub-gradients to a bound on the iterates using Lemma 4?

• There is a running typo in the paper: the iteration number of the algorithm is sometimes denoted by $k$ and other times by $t$ (e.g., when the authors define $\delta_k = \kappa \cdot (t+1)^{-1}$.

1. The proposed algorithm can only handle two protected groups, what about multi-group problems?
2. In Eq. (2), the sum is over $s$ but no $s$ is found inside the sum.

1. Can the result in Theorem 1 be presented in a non-asymptotic way as commented below the theorem (and as claimed in the concluding remarks as well)?

2. How to verify Assumption 1 (or strong duality) for the considered non-convex and non-smooth proximal-perturbed Lagrangian formulation?

i) According to line 165-167 on page 4, $G=(G_1,\dots,G_m):\mathbb{R}^d\rightarrow\mathbb{R}^m$ is a non-convex non-smooth mapping. In Line 3 in Algorithm 3 from line 225-226 on page 5, the objective function of the subproblem on $\theta_{k+1}$ directly involves $\langle\lambda_k,G(\theta)\rangle$, which makes the subproblem itself a possible non-convex non-smooth problem. How to obtain $\theta_{k+1}$ in every iteration of Algorithm 1?

ii) $\theta_{k+1}$ in (9) on page 5 is used in (22) and (24) on page 15 in the convergence analysis. If we replace $\langle\lambda_k,G(\theta)\rangle$ by $\langle\nabla G(\theta_k)^\top\lambda_k,\theta\rangle$ in the subproblem, then (9) changes to $\theta_{k+1}=\text{arg}\min_{\theta\in\Theta}\Big(\langle\nabla_{\theta}\mathcal{L}_{\alpha\beta}(\theta_k,u_k,z_k,\lambda_k,\mu_k),\theta\rangle+\frac{1}{2\eta}||\theta-\theta_k||^2\Big)$

$\quad\quad=\Pi_\Theta\Big(\theta_k-\eta\nabla_{\theta}\mathcal{L}_{\alpha\beta}(\theta_k,u_k,z_k,\lambda_k,\mu_k)\Big).$

We then need a trivial bound on the sequence of $\lambda_k$ to obtain the Lipschitz constant of $\nabla_{\theta}\mathcal{L}_{\alpha\beta}(\theta_k,\cdots)$ for all $k$ and adopt the constant step-size $\eta$ on $\theta$. The authors directly assume the boundedness of the sequence of $\lambda_k$ in Assumption 5 and say that this is standard in the optimization literature (line 271-274 on page 6). However, the boundedness of the dual sequence is proved as a result by assuming certain constraint qualifications, e.g., Theorem 5 (b) in Boob et al. (2023). How to justify Assumption 5?

See weakness.