- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper proposes learning a multiplier function for sample-wise constraints in Everywhere Learning. Since maintaining a separate multiplier for each training sample does not directly provide values for unseen samples, the authors introduce a parametric dual that predicts multipliers from sample information and is trained alternately with the primal model. Accounting for function approximation error and finite-sample effects, they analyze the constraint satisfaction and objective suboptimality of the resulting primal solution under certain assumptions. They also present conditions under which the learned multipliers admit a sensitivity interpretation with respect to changes in the constraints. The goal is to estimate how strongly constraints associated with new samples affect the learning problem. Experiments showed that the method achieved primal performance comparable to that of the sample-wise multiplier approach in some settings, and that the learned multipliers could help assess constraint importance and sensitivity for unseen samples.
Critical strengths
- The paper extended the sample-wise multiplier implementation of Everywhere Learning to a function-based approach and showed that it could be used to estimate constraint importance for new samples. This highlighted the potential of multipliers to serve both as training weights and as indicators of how constraints on unseen samples may affect the optimal objective value.
- Under certain assumptions, the paper analyzed the effects of function approximation for multipliers on the primal solution’s constraint satisfaction and objective value, and characterized the error in the sensitivity interpretation of the learned multipliers. By distinguishing approximation error from statistical error, the analysis helped explain the trade-off between greater expressiveness of the multiplier function and the associated generalization cost.
Critical weaknesses
The limited discussion of and comparison with existing multiplier learning approaches made it difficult to assess the proposed method’s additional contribution. Prior studies have learned constraint-specific multiplier functions or used multiplier predictions to estimate the importance of unseen samples [1, 2], and recent work continues to explore the learning and use of dual variables [4, 5]. PDL [3], in particular, trains a neural network to approximate targets generated by augmented Lagrangian dual updates and alternates between updating the primal and dual models, warranting a concrete comparison with this paper’s training procedure. However, the submission cited PDL only in the context of storage costs, without adequately explaining its relationship to or differences from the proposed method.
Although the analyses of function approximation error and sensitivity can be regarded as contributions, the paper did not sufficiently explain how they differ from the guarantees provided by existing approaches. The experiments demonstrated the effects of replacing sample-wise multipliers with a function, but the added value over closely related function-based approaches remained difficult to assess. A more explicit methodological and theoretical comparison, together with experiments involving applicable existing methods, would make it easier to evaluate how the paper advances beyond prior work.
[1] Narasimhan, H., Cotter, A., Zhou, Y., Wang, S., & Guo, W. (2020). Approximate heavily-constrained learning with lagrange multiplier models. Advances in neural information processing systems, 33, 8693-8703.
[2] Elenter, J., NaderiAlizadeh, N., & Ribeiro, A. (2022). A lagrangian duality approach to active learning. Advances in Neural Information Processing Systems, 35, 37575-37589.
[3] Park, S., & Van Hentenryck, P. (2023, June). Self-supervised primal-dual learning for constrained optimization. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 37, No. 4, pp. 4052-4060).
[4] Tanneau, M., & Van Hentenryck, P. (2024). Dual lagrangian learning for conic optimization. Advances in Neural Information Processing Systems, 37, 55538-55561.
[5] Bessa, S., Dabert, D., Bourgeat, M., Rousseau, L. M., & Cappart, Q. (2025, April). Learning valid dual bounds in constraint programming: Boosted lagrangian decomposition with self-supervised learning. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 39, No. 11, pp. 11113-11121).
Questions for authors
I may be misinterpreting the experimental results or metrics and would appreciate clarification on the following points. For FLORA, Fig. 5 reports objective values of 0.131 for pointwise and 0.213 for parameterized, whereas Appendix D.1 states that both methods achieved the same primal objective value. For OPF, Table 1 reports mean constraint violations of 0.49% for Dual-P and 2.70% for Param. Considering both the objective value and constraint violations, how should these results be interpreted in relation to the paper’s discussion of preserving primal performance?
Could the authors also clarify whether “rise in mean BCE” in Fig. 8 for FLORA refers to a change in the pairwise ranking loss in Eq. (133), expressed as BCE, or in the per-sample BCE used in Eq. (134)?
2 comments
Similar to Elenter et al., their work is primarily empirical. They demonstrate empirically that learning primal and dual networks jointly can produce nearly feasible and optimal solutions to constrained optimization problems. However, they do not provide theoretical guarantees explaining how parameterizing the dual affects primal feasibility and optimality. This is precisely the gap addressed by our Theorem 1 (C2).
Moreover, they do not evaluate the accuracy or sensitivity interpretation of the predicted multipliers. In fact, they explicitly identify applications of the learned dual variables, such as estimating prices and identifying binding constraints, as directions for future work in their conclusions. Our Theorem 2 (C3) provides theoretical guarantees for precisely this additional use of the learned dual function, while our experiments (C4) directly evaluate its ability to identify constraint importance and predict sensitivity on unseen samples.
1.3. Relation to Narasimhan et al. (2020)
We thank the reviewer for bringing this relevant work to our attention. Narasimhan et al. study ranking with one constraint per query. This can be viewed as an instance of Everywhere Learning and provides further motivation for our theoretical analysis.
Similar to Park et al., they use parametric dual multipliers as a means to solve the constrained learning problem, without studying the sensitivity information encoded in the learned multipliers. Thus, our main motivation and contributions C3–C4, concerning the theoretical and empirical sensitivity properties of learned multipliers, remain unaddressed by their work.
Unlike Park et al., they do provide theoretical guarantees for primal recovery, although with important limitations. Their Theorem 1 establishes approximate optimality and feasibility for an approximate mixed Nash equilibrium of the empirical problem. However, this guarantee holds for distributions over network parameters, rather than a single deterministic model, and measures feasibility through a multiplier-class-dependent violation function, rather than directly bounding the constraint violations.
Their Theorem 2 extends the feasibility analysis to unseen samples, but not the objective guarantee. Moreover, its generalization bound depends on the complexity of both the primal and dual networks.
Our Theorem 1 (C2) addresses three important limitations of these results:
-
Deterministic primal recovery. We establish guarantees for a single deterministic primal model. Narasimhan et al. explicitly acknowledge that their analysis requires randomized predictors, although deterministic models are what they use in practice, and they work (Section 5.1).
-
Direct statistical feasibility and optimality. We bound the expected positive-part constraint violation rather than a multiplier-class-dependent feasibility measure. Narasimhan et al. explicitly identify this limitation as their greatest weakness (Broader Impact, p. 10), noting that their guarantees cannot ensure satisfaction of every constraint.
-
Dependence on dual expressivity. Our primal recovery bound depends on how well the dual network approximates the optimal statistical multiplier, rather than on the complexity of the dual class as in Narasimhan et al. This explains why richer dual networks improve primal generalization, as observed in their experiments (Table 2) and in our experiments.
1.4. Relation to Tanneau and Van Hentenryck (2024) and Bessa et al. (2025)
Both Tanneau et al. and Bessa et al. have a substantially different scope from our work. They belong to the learning-to-optimize literature, using neural networks to predict tight dual bounds for instances of classical (non-AI) constrained optimization problems.
In contrast, our network represents the Lagrange multiplier function of the Everywhere Learning problem itself, which is a single constrained statistical learning (AI) problem.
This distinction is fundamental. Their guarantees concern the validity of predicted optimization bounds, whereas ours establish guarantees for solving the statistical learning problem in both the primal and dual domains (C2–C3).
2. Addressing the Questions
-
Primal performance (FLORA and OPF). We agree that parameterization introduces some degradation relative to pointwise multipliers. In FLORA, the objective increases from 0.131 to 0.213, but remains better than the ERM baselines (0.305 and 0.316). In OPF, mean constraint violation increases from 0.49% to 2.70%. Our intended claim is that parameterization preserves competitive primal performance, not identical performance to pointwise multipliers. We have corrected Appendix D.1 and clarified this distinction in the manuscript.
-
FLORA sensitivity metric (Fig. 8). The metric is the mean pairwise ranking loss (Eq. 133), not the per-sample BCE (Eq. 134). We have corrected the figure label accordingly.
We sincerely thank the reviewer for their recognition of the importance of learning multipliers. We agree that the relationship to prior multiplier-learning approaches should be explained more thoroughly, which we do below.
We have also revised the Introduction and added a Related Work section to the manuscript. We invite the reviewer to read these revisions and hope they address the reviewer's concerns.
1. Novelty and relation to prior work
We first summarize the scope of our contributions and their relationship to prior work, and then provide a detailed comparison with each work.
C1 — Parametric dual formulation for Everywhere Learning. Although we propose parameterizing dual variables in the general framework of Everywhere Learning, prior works have introduced similar parameterizations in specific problems that can be viewed as instances of this framework. We therefore agree that C1 could suggest a broader novelty claim than intended, and we have rephrased it accordingly.
C2 — Primal recovery. We establish near-feasibility and near-optimality guarantees for a deterministic predictor on the statistical problem, directly controlling constraint violations and characterizing the effect of dual approximation. These results address limitations explicitly identified by Narasimhan et al. and provide a theoretical explanation for the empirical behavior observed by both Narasimhan et al. and Park et al.
C3 — Approximate sensitivity. We establish that the learned parametric multiplier retains an approximate subgradient interpretation on unseen samples, explicitly characterizing the approximation–generalization tradeoff. This provides the missing theoretical justification for the empirical use of learned multipliers in Elenter et al.
C4 — Empirical validation. We directly validate the theoretical properties established in C2–C3, evaluating both primal recovery and the sensitivity of learned multipliers on unseen samples, rather than focusing solely on performance in a specific application.
Table 1. Comparison with prior work.
Th. = theoretical guarantees; Emp. = empirical validation; ✓ = addressed; ✗ = not addressed.
1.1. Relation to Elenter et al. (2022)
Elenter et al. study active learning through an Everywhere Learning formulation. This is another relevant application of our framework. Their work demonstrates that dual multipliers can provide useful information about sample importance, directly supporting our motivation for learning them.
Theoretical distinction (C3). Their results are primarily empirical regarding the usefulness of learned multipliers. Their Theorem 3.2 establishes that the statistical dual multiplier is a subgradient of the statistical optimal value function. However, they provide no guarantees that this interpretation generalizes to their learned multiplier function. Thus, their theorem motivates the proposed method but does not explain why it works. Our Theorem 2 (C3) addresses precisely this gap, establishing that the learned parametric multiplier remains an approximate subgradient.
Methodological distinction (C1–C2). The works also differ methodologically. Elenter et al. first train the primal model using pointwise multipliers and only afterward fit a regression head to predict them. Since their parametric predictor is learned a posteriori, it does not participate in primal optimization. Consequently, they neither study how dual parameterization affects primal recovery nor experimentally evaluate this question.
We instead parameterize the dual domain during primal training. Our Theorem 1 (C2) establishes guarantees for the resulting primal solution, which we directly validate in our experiments (C4).
1.2. Relation to Park and Van Hentenryck (2023)
Park and Van Hentenryck propose parameterizing dual multipliers, in their case for learning to solve parametric constrained optimization problems (like OPF). This can be viewed as a particular instance of Everywhere Learning, and thus their work provides further motivation for studying parametric dual functions in this broader framework.
(cont.)