acceptodds
Under review as a conference paper at ICLR 2027

Stochastic Penalty-Barrier Method for Constrained Machine Learning

Abstract

Constrained Machine Learning (CML) enables fairness-aware training, physics-informed neural networks, and integration of symbolic domain knowledge into statistical models. In this work, we introduce the Stochastic Penalty-Barrier Method (SPBM) for CML problems. SPBM extends classical penalty and barrier methods by incorporating an exponential averaging of the dual variables, a stabilized penalty schedule, and the Moreau envelope to handle non-smoothness. We analyze 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 compare SPBM with CML baselines across multiple fairness and physics informed neural networks experiments. We find that SPBM is competitive with state-of-the-art methods. We also observe, on our fairness-based computational benchmark, that the per-epoch runtime of CML methods is largely independent of the number of constraints, and within of the per-epoch runtime of regularized Adam, for a number of constraints ranging from to .

Primary area:
optimization
Keywords:
constrained optimization, constrained machine learning, penalty-barrier method, stochastic optimization, non-convex optimization, non-smooth optimization, primal-dual methods, fairness, physics-informed neural networks

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_Hm2EOpenReview ↗
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
  1. What does building on a penalty-barrier method offer over an augmented Lagrangian in this setting, and what problem does averaging the multipliers solve?
  2. On the CIFAR tasks, how many constraints are active over the course of training, for the proposed method and for the baselines?
  3. 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
AuthorsOpenReview ↗

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)\lambda^{k+1} = \lambda^k \cdot \varphi'(\bar g(x^k) / p^k), enables larger dual updates for small values of pkp^k. 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\gamma=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 BB and ℓc\ell_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.

AuthorsOpenReview ↗

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 gi(⋅,ξ(l))g_i(\cdot,\xi^{(l)}), l=1,…,Ml = 1,\dots,M, is differentiable at xx, and that gˉi(x′;j)/pi\bar g_i(x';\mathbf{j})/p_i lies in the quadratic branch of φ\varphi, where φ(t)=t+12t2\varphi(t) = t + \tfrac{1}{2}t^2, for every batch j\mathbf{j} and every x′x' in a neighbourhood of xx. Then

∇xE[piφ(gˉi(x)/pi)]=φ′(gi(x)/pi)∇gi(x)+1BpiCov(gi(x,ξ),∇xgi(x,ξ)),\nabla_x \mathbb{E}\big[p_i\varphi(\bar g_i(x)/p_i)\big] = \varphi'\big(g_i(x)/p_i\big)\nabla g_i(x) + \frac{1}{Bp_i}\mathrm{Cov}\big(g_i(x,\xi), \nabla_x g_i(x,\xi)\big),

where E\mathbb{E} is taken over the mini-batch ξ1,…,ξB\xi_1,\dots,\xi_B and Cov\mathrm{Cov} over a single sample ξ∼Ξ\xi \sim \Xi.

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 ℓc\ell_c. We hypothesise that this instability is caused by removing the variance term, whose weight 1/pi1/p_i can be as large as 1/ℓc1/\ell_c, from the gradient; in other words, the variance term stabilises training. Specifically, the variance term reduces the spread of gˉi\bar g_i. Without it, a large spread relative to pip_i produces large dual updates scaled by φ′(gˉi/pi)\varphi'(\bar g_i/p_i) 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 (5⋅10−55 \cdot 10^{-5}). 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.

AuthorsOpenReview ↗

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:

  1. 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).

  2. 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.

  1. 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.

  1. 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.

Reviewer_MjiLOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This work analyze constrained machine learning under stochastic, nonconvex, and potentially nonsmooth setting and proposes a stochastic penalty-barrier method (SPBM). The method adapts the penalty-barrier framework to minibatch training by combining stochastic primal updates, exponential moving average of dual updates, adaptive penalty parameters, and proximal regularization around a moving center. The framework accommodates practical primal optimizers such as SGD and Adam and includes both an adaptive penalty update and an alternative update related to augmented Lagrangian methods.

The theoretical analysis addresses two aspects of the method. First, it characterizes the bias introduced by applying nonlinear penalty-barrier transformations to minibatch constraint estimates. Through a Jensen-gap analysis, the paper shows that the resulting transformed constraints are more conservative and bounds the discrepancy in terms of constraint variance, batch size, and penalty scale. Second, it establishes an asymptotic convergence result for an SGD-based variant under additional assumptions, including bounded primal iterates and specific schedules for the primal, dual, and penalty updates. The result guarantees that accumulation points are D-critical points of a limiting transformed Lagrangian; it does not establish primal feasibility or KKT conditions.

The empirical evaluation covers eight tasks involving classification with weight-norm and class/group loss-disparity constraints, and physics-informed neural networks with boundary and initial condition constraints. SPBM is compared with Adam, a stochastic switching method, and a smoothed augmented Lagrangian method. The evaluation includes objective values, constraint violations, hyperparameter sensitivity, component ablations, and computational overhead. The reported results show substantial improvements over the constrained baselines on the multiclass classification tasks, while the benefits of individual components vary across tasks, particularly in the PINN experiments.

Critical strengths

Clear analysis and transparent presentation of limitations.

The paper clearly explains how nonlinear penalty-barrier transformations interact with minibatch constraint estimates, quantifying the resulting bias through constraint variance, batch size, and penalty scale. It carefully distinguishes the theoretical guarantees from the practical implementation and explicitly acknowledges the absence of feasibility and complementarity guarantees. The inclusion of failure examples further clarifies the method’s scope.

Promising empirical results supported by a substantial evaluation.

SPBM improves over the compared constrained baselines on both CIFAR tasks; on CIFAR-10, it also improves both training loss and reported constraint violation over Adam. The evaluation includes multiple seeds, hyperparameter sweeps, component ablations, and runtime measurements, providing useful evidence of the method’s practical benefits with modest computational overhead.

Critical weaknesses

The methodological and theoretical advances are relatively incremental.

The method combines established penalty-barrier, smoothing, and proximal point method. Although the stochastic analysis is informative, its main ingredients draw on standard Jensen-gap bounds and existing stochastic approximation frameworks. The convergence guarantee establishes D-criticality under specifically designed schedules, providing limited insight into the behavior of the practical Adam optimizer implementation. These limitations are acknowledged, but they constrain the significance of the theoretical contribution.

The benefits of the proposed components are strongly task-dependent.

The experiments demonstrate clear gains on CIFAR-10, but on CIFAR-100 ordinary Adam already achieves comparable objective and feasibility values. More importantly, the adaptive penalty update that benefits classification performs substantially worse than the ALM alternative on some PINN tasks, particularly E8. The paper reports this reversal transparently, but offers limited explanation or guidance on when the adaptive mechanism should be preferred, leaving its practical scope insufficiently characterized.

Questions for authors

1. What explains the different behavior of the adaptive penalty update across tasks?

It substantially improves the CIFAR results but performs much worse than the ALM alternative on PINN related tasks. Do the existing training trajectories provide insight into this reversal, and is there practical guidance for choosing between the two updates?

2. Why do SSL-ALM and SSw struggle on CIFAR-100 when ordinary Adam already achieves nearly zero loss and reported violation?

Could the authors explain what the observed optimization trajectories suggest about this failure and which aspect of SPBM helps avoid it?

1 comment
AuthorsOpenReview ↗

Answer to Reviewer MjiL

We thank the reviewer for their response. Below, we hope to address their questions. We have updated the document; new content is marked in orange.

Q1. What explains the different behavior of the adaptive penalty update across tasks? It substantially improves the CIFAR results but performs much worse than the ALM alternative on PINN related tasks. Do the existing training trajectories provide insight into this reversal, and is there practical guidance for choosing between the two updates?

A1. Note that for E6, SSL-ALM, SPBM with πALM\pi_{ALM}, and even SSw display a lower mean, but a much larger variance in the loss (with πALM\pi_{ALM} achieving very similar results to SSL-ALM, as expected); the loss of SPBM with πADAPT\pi_{ADAPT} sits within one standard deviation of that of both SSL-ALM and SPBM (πALM\pi_{ALM}) and is much more consistent across initialization seeds. On E9, we were unable to identify the reason for the anomalous behaviour of πADAPT\pi_{ADAPT}. We keep this experiment for transparency.

Overall, as the reviewer mentioned, πADAPT\pi_{ADAPT} matches or improves on πALM\pi_{ALM} on the fairness experiments and on E7, and shows less noisy behaviour across seeds on E6; hence, we suggest using it as the default choice.

Q2. Why do SSL-ALM and SSw struggle on CIFAR-100 when ordinary Adam already achieves nearly zero loss and reported violation? Could the authors explain what the observed optimization trajectories suggest about this failure and which aspect of SPBM helps avoid it?

A2. Our ablation study (Appendix C.1, Table 4) suggests that both the adaptive penalty update scheme πADAPT\pi_{ADAPT} and the exponential smoothing of the dual variables via the parameter γ\gamma contribute to the performance of SPBM on CIFAR-100. Recall from the multiplicative dual update rule (without smoothing): λk+1=λk⋅φ′(gˉ(xk)/pk)\lambda^{k+1} = \lambda^k \cdot \varphi'(\bar g(x^k) / p^k) that the penalty parameter corresponding to each constraint might enable a wider spectrum of behaviours: such as slower/faster change of the dual variables based on the difficulty of satisfying the constraint. πADAPT\pi_{ADAPT} depends only on φ′(gˉ)\varphi'(\bar g), and its effect follows from the property of φ′\varphi' in lines 155–158: for satisfied constraints jj, φ′(gˉj)<1\varphi'(\bar g_j) < 1, so pjk+1p^{k+1}_j grows; for unsatisfied constraints, φ′(gˉj)>1\varphi'(\bar g_j) > 1, so pjk+1p^{k+1}_j decreases. We believe that this is what enables SPBM to solve CIFAR tasks more easily. This is supported by Appendix F.2 (new page 59), which shows the smooth change of duals in SPBM vs SSL-ALM.

As for the performance of SSL-ALM on the CIFAR tasks, the original paper includes convergence plots in Appendix C.2, which show the method over-satisfying the constraints. During the rebuttal period, to find an explanation for this behaviour, we extended the grid search to include substantially smaller dual learning rates. Specifically, we tried the dual learning rates of 0.000050.00005 and 0.00010.0001. This indeed allowed SSL-ALM to achieve performance close to that of SPBM, with the constraints satisfied and loss values of 0.0640.064 vs. SPBM's 0.0160.016 on E4 and 0.0040.004 vs. SPBM's 0.0010.001 on E5, both with a dual learning rate of 0.000050.00005. We have updated Table 2 in the main body of the paper, and added the corresponding convergence plots in Appendix F.6.

We note, however, that the hyperparameter values that enable SSL-ALM's good performance on E4 and E5 differ by orders of magnitude from the ones that work well on E1-E3 and E6-E8.

We have updated our claims in the paper: we no longer state that SPBM outperforms SSL-ALM on the CIFAR experiments. We maintain, though, that SPBM is more resilient to the choice of hyperparameters. To substantiate this claim, we have added Figure 2 to the main body of the paper, showing a comparative hyperparameter sensitivity study of SPBM vs. SSL-ALM on all fairness experiments (E2-E5). We do this by fixing the primal learning rate to 0.01 and varying each method's other hyperparameters -- γ\gamma and κ\kappa for SPBM and dual learning rate for SSL-ALM. We observe that on all experiments, SPBM generally achieves a close-to-best loss value with γ=0.99\gamma=0.99 and κ∈{0.5,0.9}\kappa \in \{0.5, 0.9\}, whereas SSL-ALM’s performance depends visibly more on the hyperparameter choice.

Reviewer_645GOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

This paper proposes a stochastic penalty barrier method (SPBM), extending penalty-barrier methods (PBM) for general constrained machine learning (CML) problems which feature stochastic (integral) and potentially non-convex and non-differentiable objective and constraints. SPBM applies PBM to a mini-batch setting, where the expectations/integrals in the CML problem are approximated by mini-batches of finite samples. It further extends PBM by adding (a) a proximal update for the primal variable, (b) new penalty updating functions, and (c) exponential averaging for the dual variables and proximal parameters. This work supports the method proposal with various theoretical results. (1) They show that the empirical mini-batch constraints are tighter than the original constraints, and prove an upper bound for this gap. (2) They show that the CML formulation admits pathological instances where various CML methods, based on mini-batch gradients (including SPBM) drastically fail. (3) They provide a convergence result that characterises the convergence and limit points of SPBM's iterates. Their algorithm is validated on fairness and PINN benchmarks, and compared to two CML baselines, along with regularised Adam.

Critical strengths
  • This work features an extensive literature review covering a variety of methods and theoretical works in CML and related areas in constrained optimization.
  • The method is supported by theoretical analysis. The analysis of the mini-batch setting is especially interesting and closer to practice than previous works.
Critical weaknesses

Since this method extends penalty barrier methods (in the sense of Tal et al 1997), the novelty of this method hinges upon the modifications that have been introduced. However, the major weakness of this work is that the motivation for these modifications are either absent or suffer from flaws. Specifically,

  • The approximate proximal update step for the primal iterate is motivated as a solution to the non-smoothness of the constraints/Lagrangian (see line 202 "Challenge 1 : Non-smoothness"). However, as the authors note, it is only known that the Moreau envelope is a smooth approximation of a weakly convex function, which is not generally true in this setting. Moreover, the optimisation defining the Moreau envelope is only approximately solved, i.e. the proximal update is approximate. In particular, the primal update requires availability of the subgradients of the Lagrangian. Therefore, it is not clear why the proximal update is necessary, and if it can be replaced by a simple gradient descent step with respect to the Lagrangian.
  • The motivation for the penalty updating functions is spread over two sections, leaving the reader to stitch it together. Moreover, it contains several flaws, enumerated below :
    • Line 216 states that "In the stochastic setting, however, such a procedure might tighten the original feasible set at a cost of a worse objective value". It is not clear why this is the case and no justification is provided.
    • Line 217 states "on the other hand, it introduces a controllable bias for constraints that are difficult to satisfy (details in Section 3.1)", and Line 273 states "when SPBM struggles to reach feasibility, decreasing lcl_c tightens the transformed constraints (introduces a controllable bias) and enlarges the dual updates of violated constraints,". The controllable bias in question is ambiguous and not formally defined. Moreover, why should decreasing lcl_c tighten the transformed constraints (which don't depend on lcl_c at all), or increase the dual updates (which also don't directly depend on lcl_c)?
    • Line 270-273 uses Proposition 2 to justify the choice of an adaptive penalty updating function. However, the interpretation of the bound is incorrect. Since it is an upper bound on the gap between the mini-batch and non-mini batch transformed constraints, while pk→0p_k \to 0 drives the upper bound to ∞\infty, this does not imply that the gap itself will grow (contradicting Line 270 : "As pi→0p_i \to 0, the gap grows without bound"). Thus the comment about the "direct tension with the penalty schedule" (line 270) is also not justified.
    • Overall the provided justifications are insufficient to show that an adaptive πk\pi_k is needed. Moreover, since the default choice for πk\pi_k is not presented, it is difficult to reason about any potential improvement provided by the modified functions.
    • Besides the flaws in the general motivation for an adaptive πk\pi_k, the two particular choices of πk\pi_k that are presented are entirely unmotivated. The only element of the construction that is motivated, is the lower bound on pkp_k , i.e. lcl_c, since this lower bound implies an upper bound to the gap in Proposition 2 that can be controlled by the batch size BB. Note that Proposition 2 only motivates clipping pkp_k from below, while the method proposes clipping to an interval (i.e. includes an upper bound to pkp_k that is also not well motivated).
    • There is also no comparison between the two choices presented, leaving open questions about their relative advantages or disadvantages, similarities and differences etc.
  • The exposition of the main contribution, Algorithm 1, in Section 3 does not include the dual update (line 6 of Algorithm 1), despite it being mentioned in the abstract and introduction (in the methodological contributions). It is not clear why exponential averaging is necessary, or what benefit it provides.
  • Similarly, the use of exponential averaging for the proximal iterates sks_k is only weakly motivated with a reference, and there is no clarification why it is beneficial in the stochastic setting.

The main concern that I have regarding the empirical validation is that there is no ablation study comparing vanilla PBM (with mini batch estimates), and SPBM. Thus, there is no empirical evidence that the extensions introduced in SPBM are necessary or useful.

The second weakness of this work is the clarity, which can be improved on the following points :

  • The empirical penalised problem appears in Equation 13, after the presentation of its Lagrangian, and the SPBM method. This makes it hard to properly understand the difference between SPBM and PBM until Section 3.1.
  • The motivating example for Theorem 1, i.e. the "two parameter stochastic fitting problem" (which is also listed in the main contributions in the introduction) is postponed to Appendix E.4, making it difficult to evaluate the significance of Proposition 3.
  • Line 63 states "However, whether the o-minimal assumption is an answer to our question remains unresolved". This statement is hard to evaluate without significant background.
  • Algorithm 2 is referred to in Section 3.1 (Line 294, 330) without any introduction, making the containing comments hard to follow.
  • Line 154 : "Since φ′\varphi' is increasing with φ′(0)=1\varphi'(0)=1". This is indeed one of the assumptions inherited from Tal et al 1997. Consider adding a reference to the same here, or explicitly stating this assumption at line 130 when the reference to the assumptions is first given.
  • Mini batch estimates fˉ,gˉ\bar{f}, \bar{g} are referred to much before their formal definition in Section 3, making it difficult to understand the statement that "we assume ... fˉ,gˉ\bar{f}, \bar{g} to be integrable in ξ\xi" (Line 59).

Finally, the following are minor issues and typos in the work :

  1. Line 137 : Inconsistent use of "penalty-barrier" vs "penalty/barrier".
  2. Line 137 : L\mathcal{L} only takes 2 inputs, but the function signature implies 3 inputs.
Questions for authors
  1. Line 145 : Can you give an example of πk\pi_k? Does it depend on the iteration count kk? By what mechanism does it ensure that p→0p \to 0?
  2. Has the penalty-barrier method been generalised, or applied, to general CML problems, or problems with stochastic constraints?
  3. Line 129 : What do you mean by "uniform space"?
1 comment

While I appreciate the response given by the authors, I am not convinced that the weaknesses stated in my original review have been suitably addressed, and retain my overall decision. Here are some points that might help improve the manuscript further.

  • The example in the authors' response to W2.2-2.4, along with their response to 2.5, gives some intuition as to how ADAPT works. It also sheds some light into why reducing lcl_c leads to larger dual updates. This informal example can be made rigorous and incorporated into the presentation of the ADAPT penalty updating function, so that the reader understands the effect of using the ADAPT function (and why should they use it), and why it has that particular form. This will help with the motivation for the same. Moreover, the example of the classical PBM function should also be included to give further context - if nothing else, to give context to the statement "the original penalty updating function" (l.215).
  • While it is interesting that the ALM penalty function leads to an ALM like update after eliminating the penalties, it should still be motivated why this penalty update function is appropriate for the CML problem, and an improvement over the classical examples.
  • While the empirical comparison of the two penalty update functions in C.1 is informative, Sec 3.1 should provide some theoretical/principled comparison of the same.
  • App F.1 gives some empirical evidence that reducing lcl_c leads to worse objectives. However, the reasons are still not clearly stated, though apparently related to Prop 2. The statements regarding Prop 2 still seem non-rigorous. Prop 2 gives an upper bound and, in particular, does not state that "the gap might grow without bound". However, one can argue that for lcl_c large enough, the gap is small, and perhaps use this to justify the ADAPT function. Overall, the parts of the text introducing the penalty updating functions (l.213-233), and following Prop 2 (l.268- 277), still lack rigour (see my original review for unaddressed points). In particular, I disagree that W2.1 is "evident from Prop 2". I also fail to see the reasoning why "Nevertheless, the gap... grows without bound as lc→0l_c \to 0".
  • "the proximal smoothing might give interesting improvements in practice" is a weak argument, and contradicts the positioning that the proximal smoothing is motivated by non-smoothness of the CML problem. Moreover, C.1 gives mixed results, with SPBM (μ=0\mu=0) performing comparably to the two SPBM variants in most problems (e.g. E1-E3, E6, E7). It is also not clear if the "SPBM (μ=0\mu=0)" rows used the ADAPT or ALM variant, or this was also selected as a hyperparameter (in which case, it makes it harder to understand the effect of the proximal update).
  • Principled arguments for exponential averaging of duals and proximal updates (especially in the stochastic setting) are still not provided. The authors only provide empirical evidence in C.1, but again the results are mixed, and moreover, do not directly answer the question why these modifications are important.

Overall, the authors should focus on rewriting Sec 3.0, 3.1, and improving App C.1 and App F.1 to resolve these problems, and clearly and rigorously justify each component of SPBM's method.

Besides this,

  • Equation 13 : "Introducing (13) without introducing SPBM feels wrong," - Typically, problem definition precedes the proposed method. Since the target of SPBM is the batched penalised optimization problem, I would assume it could precede SPBM. Indeed the whole "Mini-batching notation" segment arguably belongs with the content in 3.1 (which should be introduced before 3.2). However, I leave this decision to the authors.
  • Regarding the page limit, ICLR allows 10 pages during the rebuttal period. If the authors believe they can improve the readability of Sec 3.2 by introducing the ReLU example in a meaningful way, they should do so.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.