- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper targets constrained machine learning with stochastic constraints. First, the authors show that penalty-barrier methods over-enforce stochastic constraints in expectation. Second, they argue that existing convergence theory for constrained methods, which assumes (weak) convexity, does not cover deep learning, and give a ReLU counterexample on which all considered methods can stay infeasible. Third, they propose a method combining the classical penalty-barrier multiplier method with exponential averaging of the multipliers and proximal smoothing, plus a heuristic for updating the penalty parameters. They prove convergence for a variant of it, show that it matches or outperforms baselines, and report that all multiplier methods considered add little runtime overhead.
Critical strengths
The results appear correct. The observations (the potential over-enforcement of stochastic constraints, the low runtime overhead of multiplier methods) are relevant to the broader constrained ML community.
Critical weaknesses
The method, the theory and the experiments are only loosely connected, so it is unclear what the paper’s core claim is. The proposed method still over-enforces stochastic constraints, and the paper neither argues nor shows experimentally that it does so less than any baseline. While they argue against theory based on weak convexity, what they prove instead guarantees neither feasibility nor optimality. The claim that multiplier methods are cheap in deep learning applies to every method considered and is again disconnected from the proposed algorithm.
The case for the method itself is also weak. Its design is underexplained: why it builds on a penalty-barrier method instead of the augmented Lagrangian methods it compares with, and why the multipliers are averaged. And while it performs well, it only clearly outperforms baselines like SSL-ALM on the two CIFAR tasks, where the constraints are inactive at the solution.
Novelty is limited as well. Two of the paper’s observations already appear in work it cites: that multiplier methods are cheap [1, Section 4.1], and that weakly convex theory does not cover ReLU networks [2, Section 1]. What seems novel is the over-enforcement bound, which the experiments never test.
Less importantly, the paper’s case against weak convexity assumptions is overstated. Its counterexample seems flawed, in the sense that the reason methods do not work there is not a lack of weak convexity but their initialization in a region with an inactive ReLU and thus zero primal gradient, where the iterates cannot move. Moreover, while I agree that we need assumptions better suited to the settings met in practice, theory under stronger assumptions such as weak convexity remains a valuable sanity check that a proposed method can at least work in an easier setting than the practical one.
[1] Ramirez et al. Position: Adopt Constraints Over Penalties in Deep Learning. arXiv:2505.20628v3, 2025.
[2] Davis et al. Stochastic Subgradient Method Converges on Tame Functions. arXiv:1804.07795, 2018.
Questions for authors
- What does building on a penalty-barrier method offer over an augmented Lagrangian in this setting, and what problem does averaging the multipliers solve?
- On the CIFAR tasks, how many constraints are active over the course of training, for the proposed method and for the baselines?
- Is the over-enforcement of stochastic constraints visible in the experiments, for example as a constraint margin that shrinks as the batch size grows? Does using independent samples for the constraint and its gradient, as done for the quadratic penalty in [3, 4], remove it?
[3] Alacaoglu and Wright. Complexity of Single Loop Algorithms for Nonlinear Programming with Stochastic Objective and Constraints. AISTATS, 2024.
[4] Li et al. Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization. Computational Optimization and Applications, 2024.
4 comments
Answer to Reviewer Hm2E - Part 2
On the sampling:
This is a good remark. We added a new result, Proposition 7, in Appendix F.3 (new page 62). This proposition could be moved to Appendix E.1, which discusses the bias. The proposition states, for the special case of the quadratic branch of the penalty-barrier function (proof in the revised PDF):
Proposition (Bias of the mini-batch gradient). Assume that every , , is differentiable at , and that lies in the quadratic branch of , where , for every batch and every in a neighbourhood of . Then
where is taken over the mini-batch and over a single sample .
We now state the general case in Remark 10 on new page 62. This suggests that sampling the constraint and its gradient independently yields an unbiased mini-batch gradient estimate. We also test this empirically in Figure 16. The take-away is:
Independent sampling does not substantially reduce the over-satisfaction of the constraints. It does, however, make training less stable, as seen in the runs with very small values of . We hypothesise that this instability is caused by removing the variance term, whose weight can be as large as , from the gradient; in other words, the variance term stabilises training. Specifically, the variance term reduces the spread of . Without it, a large spread relative to produces large dual updates scaled by on violated mini-batches, so the multipliers can grow quickly. This hypothesis is supported by Figure 16.
We hope that this answers your questions.
NOTE
Please note that the updated version of the paper features an extended grid search on SSL-ALM, motivated by the method's poor performance on CIFAR tasks (E4, E5). The method now achieves performance comparable to SPBM, with the dual learning rate close to zero (). We maintain, though, that SPBM's advantage lies in its lower sensitivity to hyperparameter choices. To further substantiate this claim, we added Figure 2 to the main body. For more details, please consult our answer to Question 2 of Reviewer MjiL.
Answer to Reviewer Hm2E - Part 3
WEAKNESSES
Weakness: The proposed method still over-enforces stochastic constraints, and the paper neither argues nor shows experimentally that it does so less than any baseline.
Answer:
The over-satisfaction of the constraints can be seen for the runs with the best hyperparameters in the convergence plots (Appendix C.2, Figures 3-10). There we see that on E1-E6, SPBM stays near the boundary, and only over-satisfies the constraints on E7. In comparison, SSw over-satisfies the constraints on E3 and E4 by a significant margin, which leads to a much worse objective value.
Weakness: The method, the theory and the experiments are only loosely connected, so it is unclear what the paper’s core claim is. [...] Novelty is limited as well. Two of the paper’s observations already appear in work it cites: that multiplier methods are cheap [1, Section 4.1], and that weakly convex theory does not cover ReLU networks [2, Section 1]. What seems novel is the over-enforcement bound, which the experiments never test.
Answer: We agree with these points and we acknowledge that the claim of the paper may have been unclear. We addressed this in the revised version of the paper as follows:
-
We removed the computational benchmark from our list of main contributions (new page 2); in the numerical results section (new page 9), we now state that our findings are in line with Ramirez et al. (2025).
-
We removed the counterexample from the list of main contributions (new page 2); we removed Proposition 3 (new page 6); we now refer an interested reader to the appendix. The new page 6 now begins:
Ideally, one would like to prove convergence to KKT points. However, Appendix E.4 gives an ERM instance of Eq. (1) with a single ReLU unit under a fairness constraint which acts as a counter-example. Where the ReLU is inactive, all (sub)gradients vanish, so SPBM, SSL-ALM and SSw cannot leave this region from an infeasible initialisation, as we also show empirically in Figure 12. Hence, without further assumptions, such as a constraint qualification, feasibility cannot be guaranteed for the tested subgradient-type methods.
The counterexample now serves as a caveat: an ML task that has a KKT point which the tested methods cannot reach with an unfavourable initialization. We now acknowledge in Remark 8 (new page 57) that this observation is not novel, and cite Davis et al.
- We reframed the claim of the paper as follows (new page 1):
In this paper, we aim to partially bridge this gap. We propose a new method, called Stochastic Penalty-Barrier Method (SPBM). We show that SPBM is robust to the choice of hyperparameters, that mini-batching biases the feasible set into a stricter problem, and that SPBM keeps the bias controllable while maintaining competitive behavior in the general CML setting.
Together with the change in the list of contributions (new page 2):
Analysis: We analyse the bias that mini-batching introduces in the barrier function and show that the feasible set of the resulting transformed problem is contained within the original one. We test these results and the effect of each SPBM modification empirically. Moreover, we analyse the robustness of the method to the choice of hyperparameters. We also prove almost sure convergence of the expected values of the Lagrangian in the o-minimal setting, although we provide no complementarity or feasibility guarantees. Appendix D gives an introduction to o-minimality.
We also removed the passage that questioned whether the setting is appropriate, as it might suggest that we had found assumptions under which convergence to a KKT point can be proven.
- With the new framing, the updated conclusion now also refers to the ablation study of SPBM and to the practical impact of Proposition 2 on the PBM and SPBM penalty-updating schemes in Appendix F.1.
Weakness: While they argue against theory based on weak convexity, what they prove instead guarantees neither feasibility nor optimality.
Answer: This is true: we do not provide complementarity or feasibility guarantees, as we acknowledge on page 2 of the original document. However, as shown in Appendix E.4, in the tame setting there exist infeasible stationary points, from which no subgradient-type method can move; without a constraint qualification, stationarity is therefore the strongest guarantee of this type.
We argue only that practical problems are often not weakly convex; instead of proving guarantees in the weakly convex setting, we work in the practical setting and try to make progress there, in the hope that the community will eventually answer the questions that remain open. We removed part of the introduction (new page 1) to make this clearer.
Weakness: Its design is underexplained [...].
Answer: Please see our response to your Question 1 above.
References
Ramirez et al. Position: Adopt Constraints Over Penalties in Deep Learning. arXiv:2505.20628v3, 2025.
Thank you for the detailed response and the revision, which engage openly with my points and answer my questions with substantial new analysis. Scaling back the runtime and counterexample claims, better crediting earlier work, and better tuning the SSL-ALM baseline make the paper more precise and the comparison fairer.
There is good material here, in particular the analysis of how mini-batching makes penalty-barrier methods over-enforce the constraints and how the adaptive penalty update limits that effect, which to my knowledge is new. The robustness of SPBM to its hyperparameters could also make it attractive in practice.
That said, I do not find the paper ready yet, although with time it could become a great paper. Compared with the original submission, the revision tells a different story, led by robustness to hyperparameters, which the current experiments do not fully establish. That new story calls for a careful rework and a full evaluation.
I am keeping my score, but I encourage a resubmission that builds out the robustness evidence.
Answer to Reviewer Hm2E - Part 1
Dear reviewer, we thank you for the review. We agree with your objections and we hope our revised version improves the quality of the paper: we updated the PDF with changes highlighted in orange. For ease of navigation, we added most of the new content at the end of the document. We first answer your questions, and then address the weaknesses.
Q1. What does building on a penalty-barrier method offer over an augmented Lagrangian in this setting, and what problem does averaging the multipliers solve?
A1. We chose to build on PBM because it, like the ALM, is easily transformed into a single-loop method suitable for CML; however, unlike the ALM, it has been, to our knowledge, overlooked in the CML literature. We believe our empirical results justify this choice.
The core differences between ALM and SPBM are:
(i) SPBM admits a penalty-updating scheme that yields an SSL-ALM-like update (see Appendix E.2); in this sense, SPBM generalizes SSL-ALM rather than replacing it.
(ii) Moreover, compared to the augmented Lagrangian, SPBM has a penalty parameter for each constraint that is updated during training.
(iii) Next, SPBM uses a multiplicative dual update instead of an additive one. The multiplicative dual update rule (without smoothing), λk+1=λk⋅φ′(gˉ(xk)/pk), enables larger dual updates for small values of pk. We exploit this structure in the ADAPT penalty-updating scheme (Eq. (12) in the revision). There, the penalty parameters of unsatisfied constraints shrink, which makes the dual updates of these constraints larger, while satisfied constraints keep larger penalty parameters and hence smaller dual updates.
(iv) Averaging of the multipliers aims to mitigate the stochastic noise arising from the multiplicative update rule. The ablation study (Appendix C.1) shows that without dampening (γ=0), the results are worse on E2, E3, E4, E5 and E6, which empirically justifies dampening in the stochastic setting. For a more detailed view, we added plots of the trajectories of the individual dual variables and constraints with and without averaging in Appendix F.2 of the revised document.
To conclude, SPBM can be seen as a generalization of ALM with more degrees of freedom in its hyperparameters. Still, the Moré–Wild profiles in Figure 1 show that SPBM performs well for a fraction of configurations comparable to or larger than that of SSL-ALM.
Q2. On the CIFAR tasks, how many constraints are active over the course of training, for the proposed method and for the baselines?
A2. In the revised document, we added Appendix F.2, where we show the evolution of dual variables and constraint values per epoch for both the Augmented Lagrangian method and SPBM.
Q3. Is the over-enforcement of stochastic constraints visible in the experiments, for example as a constraint margin that shrinks as the batch size grows? Does using independent samples for the constraint and its gradient, as done for the quadratic penalty in [3, 4], remove it?
A3. We argue that SPBM does not over-satisfy the constraints in practice with our proposed penalty-updating scheme (we address this in more detail below in Weakness: The proposed method still over-enforces stochastic constraints...). To illustrate this, we added Appendix F.1 to the revised version of the document.
There, using E3 as an example, we see that the PBM updating scheme over-enforces the constraints at the cost of a higher loss value. We find Figure 13 to be an empirical illustration of Proposition 2, where the upper bound on the over-satisfaction is controlled by B and ℓc. This confirms the effect you describe: the margin shrinks as the batch size grows. Note that our proposed SPBM penalty-updating scheme is much less prone to the effect of Proposition 2 (Figure 14).
Please see next comment for the details on sampling.