PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning Samples Importance: Parameterizing Dual Variables in Everywhere Learning

Ignacio Boero, Jonathan Nixon, Alejandro Ribeiro

arXiv:2609.36310v1cs.LGeess.SP

TL;DR

Everywhere learning uses pointwise constraints, but standard empirical duals assign separate multipliers to training samples, limiting evaluation on unseen samples. This paper learns sample-dependent parametric multipliers, characterizes the resulting primal error, and reports preserved primal performance alongside retained sensitivity interpretation.

  • Problem

    Standard empirical dual formulations assign independent multipliers to training samples, while restricting functional duals to a parametric family may affect recovery of a suitable primal solution.

    Source: §1 · p. 1

  • Method

    The paper parameterizes dual multipliers as functions of samples and optimizes over that family so learned multipliers can be evaluated on unseen samples.

    Source: §1 · p. 1

  • Results

    The induced primal solution remains approximately feasible and optimal, with added error controlled by the parametric family's approximation of an optimal multiplier; empirically, parametric duals preserve primal performance.

    Source: §1 · pp. 1–2

  • Takeaways & Limitations

    Learned multipliers retain the sensitivity role of optimal dual variables, supporting transferable sample-level sensitivity beyond training samples.

    Source: §1 · p. 2

    Primal recovery guarantees require additional structure, including convex losses and a strongly convex objective loss, while dual approximation error remains a quantified cost of restricting the multiplier family.

    Source: §3 · p. 4

Abstract

from arXiv · show

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.

1 INTRODUCTION

The introduction proposes learning sample-dependent dual multipliers that can be evaluated on unseen samples, then studies whether this restriction preserves primal guarantees and multiplier sensitivity. It reports theoretical guarantees and empirical evidence across diverse tasks.

1 INTRODUCTION

  • Pointwise constraints prevent improvements in one criterion or data region from compensating for violations in another, motivating the study of their functional dual multipliers.Classical optimal dual multipliers quantify how changes to individual constraints affect the optimal value.Source: §1 · p. 1
  • The proposed approach parameterizes the multiplier as a function of samples, unlike empirical duals that assign independent multipliers to training samples.This shared function can be evaluated on unseen samples.Source: §1 · p. 1
  • The recovered primal solution remains approximately feasible and optimal, with added error controlled by how well the parametric class approximates an optimal multiplier.The introduction also states that the learned multiplier retains information carried by the optimal multipliers.Source: §1 · p. 1
  • The learned multiplier approximately quantifies how perturbing individual constraints affects the optimal value, but unseen-sample sensitivity also requires generalization.Richer parameterizations can improve multiplier approximation while incurring greater statistical error.Source: §1 · p. 2
  • Across tasks, expressive dual parameterizations approach sample-wise multiplier performance, remain effective as constraints grow, and generalize multiplier information to unseen samples.The evaluation spans image classification, agentic workflows, language-model unlearning, and optimal power flow.Source: §1 · p. 2

2 EVERYWHERE LEARNING

Everywhere learning expresses multiple requirements as constraints that must hold pointwise over their data distributions. Its dual formulation uses nonnegative functions to weight those constraints and connects optimal multipliers to sample-level sensitivity.

2 EVERYWHERE LEARNING

  • Pointwise requirements prevent good performance in some data regions from compensating for constraint violations in others.The formulation makes prescribed tolerances explicit rather than combining requirements as weighted losses.Source: §2 · p. 2
  • For the analysis, the paper henceforth considers one constraint with tolerance zero and represents each input-output pair as z.It writes the sample loss as ℓ(fθ, z).Source: §2 · p. 2

2.1 EVERYWHERE DUAL PROBLEM

  • Because constraints are imposed pointwise, the dual variable is a nonnegative function of the sample that weights its constraint when optimizing the predictor.The dual problem searches over admissible multipliers to maximize the dual function.Source: §2.1 · pp. 2–3
  • The dual formulation is principled, although for nonconvex predictor parameterizations primal and dual optimal values need not coincide exactly.The passage states that the duality gap can be controlled by the richness of the predictor class.Source: §2.1 · p. 3
  • An optimal multiplier provides a sample-level measure of how strongly each constraint shapes the predictor; unlike independent training-sample multipliers, a learned function can give values for new samples.The standard empirical formulation assigns an independent multiplier to each training sample.Source: §2.1 · p. 3

3 PARAMETRIC EMPIRICAL DUAL PROBLEM

The section replaces independent empirical multipliers with a bounded parametric multiplier function, making multiplier values available on unseen samples. It establishes conditions for primal recovery and approximate sensitivity, with sensitivity generalization requiring the dual class itself to generalize.

3 PARAMETRIC EMPIRICAL DUAL PROBLEM

  • Restricting the dual to a bounded parametric class yields a finite-dimensional empirical problem whose multiplier function can be evaluated on unseen samples.Unlike independent per-training-sample multipliers, the parametric function is defined over the domain; the formulation also replaces population expectations with sample averages.Source: §3 · p. 3
  • The additional primal-recovery error from restricting the dual class is controlled by how well that class approximates an optimal statistical multiplier.The approximation error need not be small a priori; it quantifies the cost of restricting the functional dual domain.Source: §3 · p. 4
  • Under the stated assumptions, the learned parametric dual recovers a primal solution that is approximately feasible and optimal for the statistical problem.The bounds depend on statistical estimation, dual-parameterization, and model-approximation errors; the parameterization penalty is controlled by approximation of the optimal multiplier.Source: §3 · p. 5

3.2 SENSITIVITY OF THE LEARNED PARAMETRIC MULTIPLIER

  • The learned multiplier approximately quantifies how perturbing constraints affects the optimal value, retaining the sensitivity interpretation of the optimal statistical multiplier.The optimal multiplier characterizes the cost of tightening a sample's constraint, and learned values can be evaluated on unseen samples.Source: §3.2 · pp. 5–6
  • Sensitivity generalization trades off approximation and statistical complexity: richer dual classes can better approximate the optimal multiplier but may generalize less well.The dual-class complexity term affects sensitivity guarantees, whereas primal recovery depends on the dual class through its approximation error.Source: §3.2 · p. 6

4 NUMERICAL EXPERIMENTS

Across four learning problems, the experiments evaluate primal recovery and whether learned multipliers retain useful information on unseen samples. The reported results show competitive primal performance and sensitivity-related generalization, alongside a capacity tradeoff between approximation and generalization.

4.1 PRIMAL RECOVERY FOR THE PARAMETRIC DUAL

  • On TOFU, the parameterized dual satisfies forgetting constraints across essentially the entire forget set and achieves retain-set KL divergence 0.084 versus 0.106 for the pointwise formulation.The two formulations also achieve nearly identical memorization, privacy, and utility scores.Source: §4.1 · pp. 7–8
  • The parametric dual achieves a −3.63% mean optimality gap on IEEE 30-bus while maintaining constraint violations on the same overall scale as pointwise-dual baselines.The benchmark contains hundreds of heterogeneous constraints per sample.Source: Table 1 · p. 8, §4.1 · p. 8

4.2 LEARNABILITY OF THE DUAL MULTIPLIERS

  • Across MNIST, OPF, and FLORA-Bench, learned multipliers achieve tight-set AUCs of 0.877–0.935 and NDCG of 0.836–0.914 against pointwise references.TOFU has about 80% active constraints, and active-set identification remains nontrivial there, with AUC 0.713.Source: §4.2 · pp. 8–9, Table 2 · p. 8
  • On FLORA-Bench, increasing dual-network capacity improves ranking recovery, with gains saturating beyond roughly 10^7 parameters as approximation error falls and generalization error rises then levels off.The capacity trend reflects the tradeoff between expressivity and statistical complexity.Source: Figure 3 · p. 9, §4.2 · p. 9
  • On MNIST, objective increase grows monotonically with the mean predicted multiplier for held-out constraints, while random sets produce a nearly constant baseline.Examples assign small multipliers to an unambiguous zero and a large classwise multiplier to an ambiguous seven resembling a one.Source: §4.2 · p. 9, Figure 2 · p. 9

APPENDIX

  • The appendix provides theoretical proofs and convergence-rate derivations, task and implementation details, and additional figures and tables.Source: APPENDIX · p. 13

A.1 DERIVATION OF UNIFORM CONVERGENCE RATES FROM RADEMACHER COMPLEXITY

This appendix derives the uniform-convergence rates used in the proofs from Rademacher complexity. It extends the bounds to positive-part, weighted, and jointly learned multiplier–loss classes, then uses them in the empirical-to-statistical dual comparison.

A.1 DERIVATION OF UNIFORM CONVERGENCE RATES FROM RADEMACHER COMPLEXITY

  • When the relevant Rademacher complexities vanish, the uniform-convergence rates ζ0(N0, δ) and ζ(N, δ) also vanish, as for standard neural networks.The appendix obtains these rates from symmetrization and concentration for bounded function classes.Source: §A.1 · p. 13
  • Lipschitz transformations and bounded reweightings transfer Rademacher-complexity bounds to positive-part and weighted losses, with factors determined by their Lipschitz constants or magnitude bounds.The jointly learned product class has complexity bounded by 2[ΓRN(L) + BRN(ΛΦ)].Source: §A.1 · pp. 13–14
  • The learned-class bound applies to products of a multiplier from ΛΦ and a loss from L when multipliers are bounded by Γ.This yields a uniform-convergence rate for the jointly learned multiplier and predictor class.Source: §A.1 · p. 14

A.2 PROOF OF LEMMA 1

  • The empirical-to-statistical dual comparison uses a fixed approximating multiplier, uniform convergence for its weighted loss, and regularity of the constraint sample space.The stated regularity suffices when losses vary uniformly continuously with samples and the distribution assigns positive mass to neighborhoods of support points.Source: §A.2 · pp. 15–16

A.3 PROOF OF THEOREM 1

The proof of Theorem 1 combines empirical dual optimization, convexification, and approximation of the original hypothesis class to establish primal recovery. Theorem 2’s sensitivity argument treats pointwise constraint perturbations through the corresponding perturbed dual.

A.3 PROOF OF THEOREM 1

  • The primal recovery argument controls feasibility and optimality by comparing the returned predictor with a convexified solution and transferring guarantees back to the original hypothesis class.The transfer uses the hypothesis-class approximation bound and Lipschitz continuity; the optimality proof also uses a strictly feasible predictor and sensitivity to constraint tightening.Source: §A.3 · pp. 17, 19
  • Strong convexity makes the convexified empirical dual smooth, allowing dual suboptimality to control the constraint residual of its Lagrangian minimizer.The proof then combines this residual control with uniform convergence and convexification bounds.Source: §A.3 · pp. 16, 17, 20

A.4 PROOF OF THEOREM 2

  • For a pointwise perturbation u, the perturbed dual subtracts E_D[λ(z)u(z)] from the original dual, linking the multiplier to value sensitivity.The proof applies weak duality and the primal–dual approximation result to bound the resulting sensitivity error.Source: §A.4 · p. 20

A.5 EXTENSION TO THE AUGMENTED LAGRANGIAN

The appendix extends primal recovery and sensitivity guarantees to the Powell–Hestenes–Bertsekas augmented Lagrangian. Augmentation changes the smoothness controlling feasibility, but increasing its parameter trades improved recovery conditioning against potentially larger approximation and statistical errors.

A.5 EXTENSION TO THE AUGMENTED LAGRANGIAN

  • The augmented Lagrangian supplies dual smoothness directly, so primal recovery depends on augmentation parameter α rather than only on primal-objective curvature.The extension also assumes an optimal augmented multiplier is a multiplier of the original constrained problem for the sensitivity result.Source: §A.5 · pp. 21–22
  • The augmented and standard guarantees share statistical, multiplier-approximation, and predictor-approximation error sources, but differ in converting dual suboptimality into primal feasibility.The augmented dual is 1/α-smooth, replacing dependence on objective curvature; with νH = 0, the feasibility argument no longer depends on µ.Source: §A.5 · p. 22
  • Increasing α improves conversion of dual suboptimality into constraint satisfaction but can increase approximation and statistical errors through the augmented loss’s Lipschitz constant.Thus the augmentation parameter entails a recovery-versus-estimation tradeoff.Source: §A.5 · p. 22

A.5.1 PROOFS

  • The augmented sensitivity proof retains the original sensitivity interpretation when an optimal PHB multiplier is also a multiplier of the original problem.Its approximation and uniform-convergence terms replace BνΦ + Γζ with BανΦ + ζα; the dual-class generalization term BζΛ remains unchanged.Source: §A.5 · p. 22, §A.5.1 · p. 23

B TASKS DETAILS

The task details instantiate pointwise constraints and learned multipliers across classification, workflow prediction, unlearning, and optimal power flow. Their dual networks share information across samples rather than storing only independent training-sample multipliers.

B.1 MNIST IMAGE CLASSIFICATION

  • For MNIST, the classifier faces pointwise margins against each incorrect class, while a second convolutional network predicts bounded multipliers from each image.The primal network has two convolutional layers, max pooling, a width-32 hidden layer, and a linear output classifier.Source: §B.1 · pp. 23–24

B.2 FLORA-BENCH WORKFLOW PREDICTION

  • For FLORA-Bench, task-wise ranking is the objective and per-workflow–task binary-cross-entropy constraints require accurate individual classifications.The dual network uses the primal GNN’s penultimate representation and predicts a scalar multiplier for each observed pair.Source: §B.2 · pp. 24–25

B.3 TOFU LANGUAGE-MODEL UNLEARNING

  • For TOFU unlearning, the retain-set objective is paired with four pointwise constraints per forget example, and a shared dual network predicts their multipliers.The learned dual can predict multipliers for forget examples not used to fit the dual network.Source: §B.3 · pp. 25–26

B.4 IEEE30 OPTIMAL POWER FLOW DISPATCH

  • For IEEE 30-bus OPF, a shared dual network predicts bus, generator, and branch multipliers from the primal GNN’s latent representations.The parametric representation omits one two-dimensional branch-constraint group, so tabular-versus-parametric comparisons use their common inequality subset; the learned function also evaluates unseen demand realizations.Source: §B.4 · p. 28

C IMPLEMENTATION DETAILS

Training alternates primal updates with dual ascent whose pointwise targets are approximately projected back into a shared parametric multiplier family. The additional experiments assess primal recovery and sensitivity across several tasks, with capacity and sensitivity studies focused on MNIST and FLORA-Bench.

C IMPLEMENTATION DETAILS

  • Dual ascent targets from observed constraints are approximately projected onto the shared function class, so the method maintains no persistent sample-wise multipliers.The projection uses a neural network and finite stochastic-gradient steps, making the implementation an approximate realization of the parametric empirical dual.Source: C IMPLEMENTATION DETAILS · p. 29
  • Primal parameters are updated by stochastic gradient descent, and primal and dual updates are alternated during training.The primal step approximately minimizes the empirical augmented Lagrangian.Source: C IMPLEMENTATION DETAILS · p. 29
  • The theoretical guarantees describe an exact optimizer of the parametric empirical dual, while implementation uses an approximate projection with finite stochastic-gradient steps.The projection is approximate because the multiplier is represented by a neural network and equation 180 uses finitely many stochastic-gradient steps.Source: C IMPLEMENTATION DETAILS · p. 29

D ADDITIONAL RESULTS

  • Additional experiments examine primal recovery on MNIST, FLORA-Bench, and IEEE 30-bus, plus dual capacity and unseen-sample sensitivity on MNIST and FLORA-Bench.The capacity and sensitivity ablations focus on the latter two tasks because repeated training and evaluation are less computationally costly there.Source: D ADDITIONAL RESULTS · p. 30

D.1 ADDITIONAL PRIMAL RECOVERY RESULTS

The parameterized dual formulation preserves primal-solution quality across MNIST, FLORA-Bench, and IEEE 30-bus. On FLORA-Bench, it also outperforms ERM and feasibility-only training in constraint satisfaction and objective value.

D.1 ADDITIONAL PRIMAL RECOVERY RESULTS

  • On MNIST, parameterized and pointwise duals produce nearly identical constraint profiles and comparable primal objectives, with essentially identical classification performance.Figure 4 compares these formulations with unconstrained or partially constrained baselines.Source: §D.1 · p. 30, Figure 4 · p. 31
  • On FLORA-Bench, parameterized and pointwise duals achieve near-zero violations, the same primal objective, and essentially identical test accuracy, outperforming ERM and feasibility-only training on objective and feasibility.Figure 5 compares these methods and baselines.Source: §D.1 · p. 30, Figure 5 · p. 31
  • On IEEE 30-bus, violations remain small across heterogeneous constraint types, with the largest deviations for reactive generation and branch flow and small violations for active generation and voltage magnitude.The disaggregated analysis covers hundreds of constraints; voltage-angle constraints have no observed violations.Source: §D.1 · p. 31

D.2 ADDITIONAL DUAL CAPACITY RESULTS

On MNIST, increasing dual-network capacity improves multiplier-ranking recovery mainly by reducing approximation error, while generalization error stays comparatively stable. The capacity–statistical complexity tradeoff depends jointly on model capacity and available data.

D.2 ADDITIONAL DUAL CAPACITY RESULTS

  • Increasing dual-network capacity improves pointwise-multiplier ranking recovery, primarily by reducing approximation error, while generalization error remains comparatively stable on MNIST.Gains diminish and eventually saturate as capacity increases; Figure 7 reports ranking recovery and the approximation–generalization decomposition.Source: §D.2 · p. 31, Figure 7 · p. 32
  • The tradeoff between dual expressivity and statistical complexity depends jointly on the capacity of ΛΦ and the amount of data available to estimate the multiplier function.The authors suggest MNIST's large sample count may facilitate learning increasingly expressive dual functions.Source: §D.2 · pp. 31–32

D.3 ADDITIONAL SENSITIVITY RESULTS

On FLORA-Bench, unseen samples with larger predicted multipliers tend to produce larger increases in the optimized objective when their constraints are imposed. The relationship is less sharp than in MNIST, but the trend supports the multiplier’s sensitivity information on unseen samples.

D.3 ADDITIONAL SENSITIVITY RESULTS

  • On FLORA-Bench, imposing constraints on unseen samples with larger predicted multipliers tends to produce larger increases in the optimized objective.Figure 8 groups samples by predicted multiplier magnitude and compares the resulting objective changes.Source: §D.3 · p. 32, Figure 8 · p. 33
  • The multiplier–objective-change separation is less sharp than in MNIST, consistent with sensitivity depending jointly on workflow, task, and interactions with other constrained samples.The overall trend remains similar to the MNIST experiment.Source: §D.3 · p. 32
  • The observed trend provides evidence that predicted multipliers retain information about the cost of enforcing previously unseen constraints.Together with Table 2 ranking results, the authors report that the learned dual captures which unseen constraints matter and, to a meaningful extent, how strongly they influence the optimized objective.Source: §D.3 · p. 32
Loading 2609.36310v1…