acceptodds
Under review as a conference paper at ICLR 2027

Learning Samples Importance: Parameterizing Dual Variables in Everywhere Learning

Abstract

Everywhere learning provides a principled framework for training AI models under constraints that must hold throughout the data distribution. In the dual domain, these pointwise constraints give rise to functional dual variables. In this work, we propose to learn these dual variables, motivated by the fact that their values encode useful information about the underlying constrained problem. By representing the dual variable as a parametric function of each sample, we enable the learned multiplier to be evaluated on new, unseen samples. This contrasts with standard empirical dual formulations, which assign an independent multiplier to each training sample. We characterize the error in the recovered primal solution induced by restricting the dual variable to a parametric function class and show that it is controlled by how well this class approximates the optimal statistical multiplier. Moreover, we show that the learned parametric multiplier retains the sensitivity interpretation of the optimal statistical multiplier, yielding approximate sensitivity guarantees that extend beyond the samples used for training. We empirically validate our theory across a variety of everywhere learning tasks, showing that the resulting constrained problems can be solved efficiently and that the learned dual variables provide meaningful representations of sample-level sensitivity.

Primary area:
learning theory
Keywords:
Constrained Learning, Everywhere Learning, Duality, Optimization, Sensitivity Analysis

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_o4z7OpenReview ↗
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
  1. 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.
  2. 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

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.

WorkPrimal Th.Dual Th.Primal Emp.Dual Emp.
Elenter et al. (2022)✗✗✗✓
Park et al. (2023)✗✗✓✗
Narasimhan et al. (2020)Partial✗✓✗
Tanneau et al. (2024)✗✗✗✗
Bessa et al. (2025)✗✗✗✗
Ours✓✓✓✓

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

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:

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

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

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

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

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

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

This paper considers constrained learning problems, and investigates the direct parametrization of dual variables using a dual predictor model. Theoretical existential results are given under strong convexity and regularity assumptions, and numerical experiments are conducted on several small learning problems.

The paper's contribution is low given its lack of originality and restrictive assumptions (see Critical Weaknesses section below). The numerical experiments are conducted on small learning tasks not representative of state-of-the-art constrained learning (especially the OPF experiments), and do not demonstrate that the proposed approach actually achieves feasibility.

Critical strengths

The paper considers the direct parametrization of dual multipliers in constrained learning, as opposed to storing one multiplier per constraint per data point, and moves away from constraint satisfaction in expectation only.

Critical weaknesses

Lack of originality: The paper closely mimics the primal-dual learning methodology set forth in [Park and Van Hentenryck, Self-supervised primal-dual learning for constrained optimization], whereby a primal network predicts primal solutions, and a dual network predicts dual solutions.

Restrictive assumptions:

  • Assumption 3 effectively restricts the setting to strongly convex problems (convex loss and convex constraints); this excludes linear constraints and any non-convex constraints. The paper states: "Assumptions 3 and 4 are standard regularity conditions and are satisfied by common losses on bounded prediction domains"; I would not call Assumption 3 "standard" because of how restrictive it is.
  • Assumption 6 assumes that the learning problem is strictly feasible, i.e., that there exists a predictor within the hypothesis class that strictly satisfies all constraints. This is not realistic because 1) it does not hold when the problem contains equality constraints (which are very common), 2) it does not allow for infeasible instances.
Questions for authors
  • Both terms "Constrained learning" and "everywhere learning" appear in the paper and it is not clear whether they are used interchangeably or not.
  • In Assumption 2, λ⋆\lambda^{\star} appears to be a vector, whereas λϕ\lambda_{\phi} is a function. Thus, I am not sure that Eq. (8) is well-defined.
  • Please define the subscript notation L_1(D)} in Eq. (8)
  • Assumption 2 appears to be a definition, not an assumption?
3 comments

We sincerely thank the reviewer for taking the time to evaluate our paper. We appreciate the opportunity to clarify our contributions and acknowledge that the scope and relationship to prior work need to be communicated more clearly.

We believe that most concerns arise from a confusion between learning to solve constrained optimization problems and Everywhere Learning. This distinction is central to understanding both the novelty of our contributions and the scope of our assumptions.


0. Terminology and notation

  • Constrained learning refers to training a machine-learning predictor under constraints, which may be imposed in expectation. Everywhere Learning specifically requires constraints to hold almost everywhere over the data distribution.

  • In Eq. (8), both λϕ\lambda_\phi and λ⋆\lambda^\star are functions, not vectors. The function λ⋆\lambda^\star is defined in the equation that poses the statistical dual problem (D). It belongs to the functional space L1(D)L^1(\mathcal D), which is the space of integrable functions (defined right before Eq. (1)).

  • We agree that Assumption 2 defines the dual approximation error rather than imposing a restrictive hypothesis, and will relabel it as a definition.


1. Novelty, contributions, and relation to Park and Van Hentenryck (2023)

We acknowledge that the methodology of representing dual variables with neural networks is similar to that of Park and Van Hentenryck (2023). However, their work focuses on learning to solve parametric optimization problems, where they consider training a neural network to approximate the solution mapping of a family of constrained optimization problems.

Our work considers the broader framework of Everywhere Learning, where an AI model is trained under multiple requirements imposed as pointwise constraints across the data distribution. Learning to optimize can be viewed as a particular instance of this framework, but Everywhere Learning also encompasses problems that do not involve predicting optimization solutions. This is the case in three of our applications:

  • MNIST: Training a classifier subject to per-sample classification-margin constraints.

  • TOFU: Training a language model to forget specified information while preserving its behavior on retained data.

  • FLORA-Bench: Training a predictor to rank agentic workflows while satisfying individual classification requirements.

Our OPF experiment does share the learning-to-optimize structure of the cited work.

Thus, C1 refers to extending the use of parametric dual multipliers to the broader class of Everywhere Learning problems. We acknowledge that, although we cite Park and Van Hentenryck, we do not explicitly discuss this methodological similarity in the Introduction, and this distinction should be addressed. We include this in the revised manuscript and clarify the wording of C1 to better reflect its scope.

Regardless of whether extending parametric duals to Everywhere Learning is considered a standalone contribution (which we are willing to remove), our main contributions (C2–C4) focus on understanding the properties of the parametric dual network itself, rather than merely using it to recover a primal solution. This is fundamentally different from Park and Van Hentenryck's work. Specifically:

  • C2 — Primal recovery (Theorem 1). We establish how the approximation capacity of the dual network affects the feasibility and optimality of the recovered primal model. In particular, the recovery guarantees improve as the dual class better approximates the optimal statistical multiplier. This relationship is not obvious and is not analyzed by Park and Van Hentenryck.

  • C3 — Sensitivity recovery (Theorem 2). We establish that the learned dual network preserves an approximate sensitivity interpretation of the statistical multiplier on unseen samples. Crucially, we characterize an approximation–generalization tradeoff: more expressive dual networks can better approximate the optimal multiplier but may generalize worse due to their greater statistical complexity.

  • C4 — Empirical validation. Beyond evaluating primal performance, we demonstrate that learned multipliers predict constraint importance and sensitivity on unseen samples, including their effect on the optimal learning objective. This is also absent from the cited work.

We respectfully disagree that using neural networks to represent dual multipliers is sufficient to characterize our work as closely mimicking the cited paper. Beyond considering the more general setting of Everywhere Learning, our work addresses different theoretical questions, focusing on the approximation, generalization, and sensitivity properties of the learned dual variables themselves, which are not studied by Park and Van Hentenryck.

2. Clarification of assumptions

We believe that some concerns regarding the restrictiveness of our assumptions may also arise from interpreting them in the context of learning to optimize, rather than Everywhere Learning. We clarify their scope below.

2.1. Strong convexity (Assumption 3)

"Assumption 3 effectively restricts […] I would not call Assumption 3 'standard' because of how restrictive it is."

If we were learning to solve constrained optimization problems, then considering only strongly convex problems would indeed be restrictive. However, in Everywhere Learning problems, convex losses are very common. Examples include:

  • Binary cross-entropy in classification, as in the FLORA-Bench experiment.

  • Negative log-likelihood in language model training, as in the TOFU experiment.

  • Affine margin constraints, as in the MNIST experiment.

We remark that we require strong convexity only for the objective loss. The constraints may be convex, including linear constraints.

2.2. Strict feasibility (Assumption 6)

"Assumption 6 assumes that the learning problem is strictly feasible [...]"

In the context of Everywhere Learning, strict feasibility of the statistical problem amounts to the existence of one predictor in the hypothesis class that can strictly satisfy the multiple requirements of the problem. If we consider very rich and expressive classes (i.e., large neural networks), it is reasonable to expect that a strictly feasible point exists.

2.3. Equality constraints

"1) it does not hold when the problem contains equality constraints (which are very common)"

Our theory does not consider equality constraints. We agree that they are common in learning to optimize, where physical or mathematical equations must be satisfied exactly. However, in Everywhere Learning, requirements on model performance are naturally expressed as inequalities, such as classification margins, loss thresholds, or forgetting requirements.

This is the case in all three of our applications except OPF. Our OPF experiment does include equality constraints, but the evaluation of dual generalization is restricted to inequality multipliers, consistent with the theoretical framework (Appendix B.4).

2.4. Infeasible instances

"2) it does not allow for infeasible instances."

Yes, we only consider feasible problems, where the hypothesis class is chosen sensibly.


3. Experimental validation

3.1. Scale and representativeness of the experiments

"The numerical experiments are conducted on small learning tasks not representative of state-of-the-art constrained learning (especially the OPF experiments)"

We respectfully disagree that the experiments are limited to small learning problems. Beyond MNIST, we evaluate agentic workflow prediction on FLORA-Bench and language-model unlearning on TOFU, both representing relevant applications of constrained learning. We acknowledge that the IEEE 30-bus system is a relatively small OPF benchmark and that larger-scale settings exist across all these applications.

However, as emphasized in the first section of this rebuttal, our primary objective is not to demonstrate state-of-the-art primal performance, but to study the learnability and generalization of dual multipliers.

Our experiments are designed accordingly: we evaluate whether parametric duals preserve primal performance, predict constraint importance on unseen samples, and capture sample-level sensitivity. These properties are the central focus of our contributions.

3.2. Constraint feasibility

"and do not demonstrate that the proposed approach actually achieves feasibility."

Figures 1, 4, and 5 show near-zero pointwise constraint violations on TOFU, MNIST, and FLORA-Bench, respectively. The OPF results exhibit residual violations, which we explicitly report.

Consistently, our theoretical results establish near-feasibility guarantees rather than exact feasibility.

I thank the authors for their feedback. While I believe that learning functional dual approximations is a relevant avenue of work, I do not consider this paper ready for publication.

My point was not that the approach considered in the paper is equivalent to learning optimization problems, it was that learning a functional approximator of dual multipliers has already been studied in the literature (as was also pointed out by the other 2 reviewers). More generally, there is a rich literature on learning with constraints, from safe RL to physics-informed learning, parametric optimization. Just because other approaches have relaxed the underlying problem via penalization or aggregation does not mean that this setting has not been studied before. See, for instance, Feasible Learning that casts a learning problem as a constrained learning problem with hard constraints, then uses a Lagrangian approach to train the model.

After reading the authors' response and the revised manuscript, I still see several mathematical and notational inconsistencies:

  • The loss function ℓ0\ell_{0} is assumed to be strongly convex and bounded; this automatically restricts the setting to the case where the output domain Y\mathcal{Y} is bounded (a strongly convex function cannot be upper-bounded on an unbounded domain).
  • The example loss functions provided by the authors (cross-entropy and negative log-likelihood) are not bounded nor L-Lipschitz
  • The revised manuscript does not use consistent notations, e.g. ℓ(fθ,z)\ell(f_{\theta}, z) vs ℓ(z,fθ)\ell(z, f_{\theta})
  • Table 1 and 2 are almost identical to one another
  • The loss functions are assume to take value in the domain [0,B][0, B], but some experiments report negative constraint values.
  • In Figure 3, the right-hand side plot appears to display a negative recovery error? (left-most point on the blue curve).
Reviewer_bgxcOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies "everywhere learning," i.e., constrained learning with pointwise (almost-everywhere) constraints, whose dual variable is a nonnegative function λ:Z→R+\lambda: \mathcal{Z} \to R_+. Instead of the standard empirical dual that assigns an independent multiplier to each training constraint, the authors parameterize the multiplier as a bounded function class ΛΦ={λϕ:∥λϕ∥∞≤Γ}\Lambda_\Phi = \lbrace \lambda_\phi : \lVert \lambda_\phi \rVert_\infty \le \Gamma \rbrace (a neural network), so that it can be evaluated on unseen samples.

The theoretical contributions are:

  • Lemma 1: the parametric empirical dual value approximates the statistical dual value up to BνΦ+ζ0+ΓζB \nu_\Phi + \zeta_0 + \Gamma \zeta, where νΦ\nu_\Phi is the L1(D)L_1(D) distance from ΛΦ\Lambda_\Phi to an optimal multiplier λ⋆\lambda^\star.
  • Theorem 1: a primal recovery result (near-feasibility and near-optimality) under strong convexity of the objective, approximate convexity of the hypothesis class, and a strict Slater condition.
  • Theorem 2: the learned multiplier is an approximate subgradient of the perturbation function, with an additional term BζΛB \zeta_\Lambda reflecting the statistical complexity of the dual class.

An augmented-Lagrangian extension is given in the appendix. Algorithmically, the dual network is trained by regressing onto projected augmented-Lagrangian ascent targets, alternating with primal SGD.

Experiments on MNIST (margin constraints), FLORA-Bench (workflow prediction), TOFU (LLM unlearning), and IEEE 30-bus AC-OPF compare against pointwise (tabular) multipliers and evaluate (i) primal recovery and (ii) whether the learned multiplier identifies active or important constraints on held-out samples (tight-set AUC, NDCG, Spearman) and predicts the objective increase when held-out constraints are imposed.

Critical strengths
  1. Well-motivated question. Asking whether pointwise dual variables can be amortized into a function, both for scalability and to obtain sensitivity information on unseen samples, is natural and practically relevant (e.g., data selection, unlearning, power systems).
  2. Clean error decomposition. The bounds separate statistical error (ζ0,ζ\zeta_0, \zeta), dual-class approximation error (νΦ\nu_\Phi), and primal-class approximation error (νH\nu_{\mathcal H}). Theorem 2 also makes explicit an approximation/estimation tradeoff in the choice of dual class (νΦ\nu_\Phi vs. ζΛ\zeta_\Lambda), which is a sensible way to frame the problem.
  3. Diverse experimental testbeds. The tasks span vision, graph-based prediction, LLM unlearning, and AC-OPF with hundreds of heterogeneous constraints per sample. The held-out evaluation protocol for the dual (fitting the dual on one split and evaluating on another) is a reasonable design.
  4. Detailed appendix and code. Task formulations, architectures, and the algorithm are described in detail, and per-task repositories are provided.
Critical weaknesses

1. Novelty compared to prior work on multiplier models is not clear. The central idea of replacing per-constraint multipliers with a learned function of constraint features, together with optimality, approximate feasibility, and generalization guarantees that depend on the flexibility of the multiplier class, appears in Narasimhan et al., "Approximate Heavily-Constrained Learning with Lagrange Multiplier Models" (NeurIPS 2020), which is not cited. The use of learned dual variables as a sample-level sensitivity or informativeness score, including predicting duals on unseen samples by training a dual regression head on learned embeddings, appears in Elenter et al., "A Lagrangian Duality Approach to Active Learning" (NeurIPS 2022), which is also not cited. In addition, primal-dual learning with a dual network trained to track augmented-Lagrangian multiplier updates has been studied in the learning-to-optimize literature (e.g., Park & Van Hentenryck, AAAI 2023, which the paper cites only in passing in the appendix). The paper should position its contributions (C1)-(C4) precisely against these works. As written, the main new elements appear to be the specialization to the everywhere-learning setting and the ζΛ\zeta_\Lambda term in Theorem 2.

2. The theory does not cover the experimental settings.

  • Dual class depends on the primal. In FLORA-Bench and OPF (and apparently TOFU), the dual network takes the primal network's penultimate representation hθ(z)h_\theta(z) as input. Then ΛΦ\Lambda_\Phi is not a fixed function class: it changes with θ\theta, and Assumption 7 (uniform convergence over a fixed ΛΦ\Lambda_\Phi) and the Lagrangian-minimization arguments no longer apply.
  • Exact dual optimization. All results are stated for an exact maximizer λ^Φ\hat\lambda_\Phi of g^\hat g over ΛΦ\Lambda_\Phi. Since ϕ↦g^(λϕ)\phi \mapsto \hat g(\lambda_\phi) is nonconcave, this maximizer is not computable. The implemented method (regression onto projected ascent targets, Eqs. 178-180) comes with no convergence or optimality analysis. Appendix C acknowledges this, but it substantially weakens the link between the theorems and the experiments.

3. Theorem 2 does not support the sample-level sensitivity claims. Theorem 2 is essentially the observation that any multiplier whose dual value is within ϵ\epsilon of D⋆D^\star is an ϵ\epsilon-subgradient of the perturbation function, combined with Lemma 1 and uniform convergence. Two issues follow.

  • The statement holds for perturbations u∈L1(D)u \in L_1(D), so a perturbation supported on a single unseen point has measure zero and the theorem says nothing about it. Moreover, in the everywhere-learning problem (P), unseen z∼Dz \sim D are already constrained. The experimental notion of "imposing the constraint of an unseen sample" is therefore a statement about the empirical problem, not about P(u)P(u).
  • Approximate-subgradient guarantees do not identify the multiplier. Many near-optimal multipliers can differ substantially pointwise, so the theorem does not imply that λ^Φ\hat\lambda_\Phi ranks constraints like λ⋆\lambda^\star, which is what Table 2 and Figures 2-3 evaluate.

The paper should state precisely which sensitivity claims are supported by theory and which are empirical.

4. Experimental evidence is weaker than presented.

  • Missing comparison to multiplier-model methods (Narasimhan et al., 2020) for primal recovery.
  • OPF (Table 1, Figure 6). Param has a mean violation of 2.70% versus 0.49% (Dual-P), 1.05% (Dual-H), and 1.34% (Dual-S), and a higher P95 maximum violation than Dual-P and Dual-H. Disaggregated by type, reactive-generation violations are 5.68% versus 0.69% for Dual-P, and branch-flow violations are 4.90% / 2.49% versus 0.68% / 0.15%. The negative optimality gap (−3.63%-3.63\%) is therefore most plausibly explained by infeasibility rather than better optimization, yet the text presents it as a positive result. In addition, the parametric dual omits the voltage-angle constraint group (338 vs. 420 multipliers), and the baseline numbers are copied from a figure in Owerko et al. (2025) rather than re-run under the same protocol.
  • FLORA-Bench sensitivity (Figure 8). The random-draw baseline (about 0.0189) is at or above every group ranked by λϕ\lambda_\phi (about 0.0177 to 0.0188). This does not support the claim that larger predicted multipliers identify more impactful constraints.
  • Dual recovery (Table 2). Spearman correlations are low (0.21-0.32), and on TOFU the method essentially fails (NDCG 0.386, Spearman −0.048-0.048). It is also unclear how reliable the "independently computed pointwise reference" is: pointwise multipliers from nonconvex training are not unique, and no noise ceiling (agreement between pointwise runs with different seeds) is reported.
  • Missing baselines for sensitivity. There is no comparison against simple predictors of constraint activity and importance, such as the current constraint value or margin, the per-sample loss, or influence-function and data-valuation scores. The most natural baseline is a post-hoc dual regression head fitted to pointwise multipliers (as in Elenter et al., 2022). Without these comparisons, the tight-set AUC and NDCG numbers are hard to interpret; for MNIST, for instance, margin alone may identify active constraints well.
  • No cost analysis. The abstract claims the problems "can be solved efficiently," but no wall-clock, memory, or iteration counts are reported. In FLORA-Bench the dual network goes up to about 10810^8 parameters, larger than the 27M-parameter primal network.
Questions for authors
  1. Relation to prior work. How do your formulation and guarantees differ from the Lagrange multiplier models of Narasimhan et al. (NeurIPS 2020) and from the dual regression head of Elenter et al. (NeurIPS 2022)? Is Algorithm 1 (regression onto projected augmented-Lagrangian targets) different from the dual-network training in Park & Van Hentenryck (AAAI 2023)? Please state precisely which of (C1)-(C4) are new.
  2. Dual class conditioned on primal features. When λϕ(z)=qϕ(hθ(z))\lambda_\phi(z) = q_\phi(h_\theta(z)) depends on the primal representation, the dual class changes with θ\theta. Do Lemma 1 and Theorems 1-2 still apply? I suspect it does not. A more careful concentration needs to be applied.
  3. Existence and boundedness of λ⋆\lambda^\star. Under what conditions does an optimal multiplier exist in L1(D)L_1(D) for almost-everywhere constraints? If λ⋆\lambda^\star is unbounded, is νΦ\nu_\Phi bounded away from zero for every Γ\Gamma-capped class?
  4. Sample-level sensitivity. Theorem 2 concerns perturbations u∈L1(D)u \in L_1(D), which cannot single out an individual sample. What formal statement, if any, supports interpreting λ^Φ(z)\hat\lambda_\Phi(z) at a single unseen zz as its sensitivity? Can you bound ∥λ^Φ−λ⋆∥\lVert \hat\lambda_\Phi - \lambda^\star \rVert under additional conditions (e.g., uniqueness of λ⋆\lambda^\star or strong concavity of the dual)?
  5. OPF feasibility. Given that Param's mean violation is 2-5 times larger than the baselines' (and much larger for reactive generation and branch flows), is the negative optimality gap explained by infeasibility? Can you report results with all 420 multipliers, including voltage-angle constraints, and re-run the baselines under an identical protocol?
2 comments

1. Relation to prior work (C1–C4)

We thank the reviewer for highlighting these works. We provide a detailed comparison in our response to Reviewer o4z7, whose main concern was novelty, and summarize the main distinctions here. We have also revised the Introduction and added a Related Work section, which we invite the reviewer to read.

Narasimhan et al. (2020). Narasimhan et al. propose parametric multipliers for heavily constrained learning, including instances of Everywhere Learning, and provide partial primal recovery guarantees. However, their Theorem 1 applies to randomized predictors and multiplier-class-dependent violation measures, while Theorem 2 provides a feasibility generalization bound depending on both primal and dual network complexity. Our Theorem 1 (C2) addresses these limitations, establishing statistical feasibility and optimality guarantees for a deterministic predictor, with errors controlled by dual approximation. Moreover, they do not study multiplier sensitivity (C3).

Elenter et al. (2022). Elenter et al. demonstrate the usefulness of predicted multipliers for active learning. Their Theorem 3.2 establishes the sensitivity interpretation of the optimal statistical multiplier, but provides no guarantees for its learned approximation. Our Theorem 2 (C3) addresses this gap, establishing an approximate subgradient interpretation with explicit approximation and statistical errors. Their multiplier predictor is also trained a posteriori, rather than during primal optimization, so they do not study the effect of dual parameterization on primal recovery (C2).

Park and Van Hentenryck (2023). Park and Van Hentenryck propose a closely related procedure for learning to solve parametric optimization problems. We acknowledge the methodological similarity, particularly regression onto augmented-Lagrangian updates. However, they do not establish statistical primal recovery guarantees (C2) or study multiplier sensitivity and generalization (C3).

In summary, we agree that C1 required more precise wording, which we have revised. Our main contributions C2–C3 remain distinct, establishing statistical primal recovery and approximate sensitivity guarantees. Our experiments (C4) evaluate both properties, beyond primal performance or a specific downstream application.


2. Theoretical assumptions and experimental settings

We agree that our theory does not fully characterize the experimental implementations. Our analysis focuses on statistical recovery and generalization guarantees given an optimal empirical parametric dual solution, rather than a complete characterization of neural network training.

2.1. Exact dual optimization

We acknowledge that our theorems assume the empirical parametric dual optimum is attained. However, we disagree that this maximizer is necessarily "not computable." Nonconcavity prevents general guarantees of finding a global optimum, but does not imply that good solutions cannot be obtained in practice. Indeed, neural networks routinely achieve nearly zero training loss despite nonconvexity.

Our theory characterizes the optimal empirical multiplier, without claiming that our algorithm is guaranteed to find it. Understanding neural network optimization despite nonconvexity remains an active research area, whose extension to parametric dual optimization is beyond our statistical analysis.

2.2. Dual class conditioned on primal features

The generalization analysis can be extended through uniform convergence over the entire dual network, including the primal backbone extracting features. This defines a fixed function class over all backbone and dual-head parameters, with the complexity term accounting for both.

Moreover, the features passed to the dual network are detached from the computational graph, so primal updates treat multipliers as fixed, consistent with the Lagrangian inner minimization. The shared backbone introduces optimization complexity, but does not invalidate the uniform convergence argument.

3. Existence and boundedness of the optimal multiplier

This question is addressed in Appendix H of Everywhere Learning (Boero et al., 2026). Under strict feasibility, compactness, and continuity conditions, Proposition 5 establishes the existence of an optimal finite measure-valued multiplier. Its representation in L1(D)L^1(\mathcal D) additionally requires absolute continuity with respect to D\mathcal D.

Boundedness, however, is not guaranteed. Proposition 1 shows that restricting multipliers to ∥λ∥∞≤Γ\|\lambda\|_\infty \leq \Gamma is equivalent to introducing an L1L^1-penalized relaxation of the primal constraints.

If λ⋆\lambda^\star is unbounded, a finite cap introduces approximation error νΦ\nu_\Phi, accounted for in our guarantees. Increasing Γ\Gamma can reduce this error, provided λ⋆∈L1(D)\lambda^\star \in L^1(\mathcal D) and the parametric class is sufficiently expressive.


4. Sample-level sensitivity

We thank the reviewer for highlighting the distinction between statistical sensitivity and the empirical effect of individual constraints. Our Theorem 2 establishes approximate functional sensitivity, not pointwise multiplier recovery.

The sample-level interpretation follows from viewing the multiplier as a sensitivity density, analogous to a probability density function (PDF). Although individual points have zero probability under a continuous distribution, we interpret p(z)p(z) as the probability density at that point.

Similarly, λ(z)\lambda(z) represents the local sensitivity density of the optimal objective to constraint perturbations around zz. Tightening constraints by tt over a measurable region AA increases the optimal value by at least tE[λ^Φ(z)1A(z)]−ηt\mathbb{E}[\hat{\lambda}_\Phi(z)\mathbf{1}_A(z)]-\eta. As the region shrinks, its average multiplier converges to the local value almost everywhere, under standard regularity conditions.

We agree that Theorem 2 does not directly guarantee optimal multiplier ranking or quantify the finite effect of adding held-out constraints. We investigate these questions empirically in Table 2 and Figures 2–3.

For the empirical problem, under standard regularity conditions, −λi⋆/N-\lambda_i^\star/N is the derivative of the optimal objective with respect to the corresponding constraint threshold. Our experiments test whether learned multipliers transfer this sensitivity information to unseen samples and predict the realized effect of adding their constraints.

We have clarified the distinction between theoretical guarantees and empirical validation in the manuscript.


5. Experimental evaluation

  1. OPF implementation and baselines. The 82 omitted voltage-angle constraints were inherited from Owerko et al.'s public repository, where they are commented out. We have now trained with all 420 constraints, reducing mean violation from 3.20% to 2.08%. Our reproduction of Dual-P yielded worse results than published (1.13% vs. 0.49% mean violation). We reported the stronger published results to avoid favoring our method, and now clarify their provenance.

  2. Comparison with prior methods. We implemented Narasimhan-style direct Lagrangian ascent and Elenter-style post-hoc dual regression baselines. Direct ascent failed to reach feasibility on MNIST in tested configurations. Post-hoc regression achieved better multiplier recovery (Spearman 0.191 vs. 0.108 on MNIST; 0.338 vs. 0.203 on FLORA). These clarify methodological differences, while our contributions (C2–C3) establish guarantees absent from these methods.

  3. Primal performance (FLORA and OPF). We agree that parameterization degrades performance relative to pointwise multipliers. In FLORA, the objective increases from 0.131 to 0.213, but remains better than ERM baselines (0.305 and 0.316). In OPF, mean violation increases from 0.49% to 2.70%. The negative optimality gap is also likely partly explained by reduced feasibility. Our claim is competitive primal performance, not identical performance to pointwise multipliers. We have clarified this distinction.

  4. Dual recovery (Table 2). We agree that Spearman correlations indicate limited global ranking recovery, which our theory does not guarantee. However, AUC and NDCG complement this with active-set identification and ranking quality. We acknowledge weak TOFU results: many constraints are active, and multipliers are highly concentrated near zero, making ranking difficult.

  5. Computational cost. We agree that the abstract's efficiency claim was insufficiently supported. Parameterized training is 1.20× and 1.34× slower per epoch on MNIST and FLORA, without reducing peak GPU memory. FLORA networks approaching 10810^8 parameters were used only in the capacity ablation; the main dual network has 4.46M parameters. We have clarified this in Appendix D.

Comments on the paper

1 comment

Dear Area Chair,

In the absence of further discussion following our rebuttal, we would like to provide a brief summary of the main concerns raised by the reviewers and how we have addressed them.

  • Novelty and relation to prior work. This was the main concern shared by the three reviewers. We substantially revised the Introduction and added a Related Work section, explicitly positioning our contributions against existing multiplier-learning approaches. While we acknowledge methodological similarities, we identify two distinct theoretical contributions: (i) statistical primal recovery guarantees for deterministic predictors under dual parameterization, and (ii) approximate sensitivity guarantees for learned multipliers, characterizing their approximation–generalization trade-off. Neither of these results is established in the cited works.

  • Theoretical assumptions and scope. We clarified the distinction between Everywhere Learning and learning to solve parametric optimization problems, the scope and motivation of our assumptions, and the relationship between our theoretical framework and experimental implementations.

  • Sensitivity interpretation. We clarified the distinction between the theoretical guarantees on statistical sensitivity and the empirical investigation of constraint importance and sample-level sensitivity on unseen data.

  • Additional experiments and limitations. We implemented two additional baselines based on the suggested prior works, extended the OPF experiments to include all 420 constraints, and conducted a computational cost analysis. We also revised the manuscript to more accurately communicate the limitations and trade-offs of dual parameterization.

Importantly, the main objective of our work is not to introduce a new primal-dual learning algorithm, but to establish a theoretical and empirical understanding of the approximation, generalization, and sensitivity properties of learned dual multipliers.

We hope that our responses, additional experiments, and manuscript revisions will be taken into consideration in the final assessment of our submission.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.