Calibrated Data-Dependent Constraints with Exact Satisfaction Guarantees
Authors: Songkai Xue
Yuekai Sun
Mikhail Yurochkin
Venue: NeurIPS 2022 Accept (2022)

Abstract: We consider the task of training machine learning models with data-dependent constraints. Such constraints often arise as empirical versions of expected value constraints that enforce fairness or stability goals. We reformulate data-dependent constraints so that they are calibrated: enforcing the reformulated constraints guarantees that their expected value counterparts are satisfied with a user-prescribed probability. The resulting optimization problem is amendable to standard stochastic optimization algorithms, and we demonstrate the efficacy of our method on a fairness-sensitive classification task where we wish to guarantee the classifier's fairness (at test time).

Calibrated Data-Dependent Constraints with Exact Satisfaction Guarantees
Songkai Xue Department of Statistics University of Michigan sxue@umi ch. edu
Yuekai Sun Department of Statistics University Michigan yuekai @umi momichhedu edu
Mikhail Yurochkin IBM Research
MIT-IBM Watson Al Lab mikhail, www..ckkkoiiiiii...... com
Abstract
We consider the task of training machine learning models with data-dependent constraints. Such constraints often arise empirical versions of expected value constraints that enforce fairness or stability goals. We reformulate data-dependent constraints that they calibrated: enforcing the reformulated constraints guarantees that their expected value counterparts are satisfied with a user-prestt uiser-preccrbed probability. The resulting optimization problem is amendable to standard stochastic optimization algorithms. and we demonstrate the efficacy of our method on a fairness-sensitive classification task where wish to guarantee the classifier's fairness (at test time).
Motivation
In machine learning (ML) practice, accuracy is often only one of many training objectives. For exam- ple, algorithmic fairness considerations may require a credit scoring system to perform comparably on men and women. Here are a few other examples.
Churn rate and stability The churn rate of an ML model compared another model is the fraction of samples which the predictions of the two models differ k0) In MI. practice, one may wish to control the churn rate between a new model and its predecessor because a high churn rate can disorient users and downstream system components. One way of training models with small churn is to enforce a churn rate constraint during training.
Precision, recall, Classification and information retrieval models must often balance precision and recall. To train such models, practitioners carefully trade off one metric for the other by optimizing for one metric subject to constraints on the other.
Resource constraints Practitioners sometimes wish to control how often classifier predicts certain class due to budget or resource constraints. For example, company that uses ML to select customers for targeted offer may wish to constrain the fraction of customers selected for the offer. Another prominent example of stochastic optimization problem with resource constraints the newsvendor problem, which we come back to in section
Unlike constraints the structure of model parameters (e.g., sparsity), the constraints encoding the preceding training objectives are data-dependent. This leads to the issue of constraint generalization: whether the constraints generalize out-of-sample. For example, if classifier is trained to have comparable accuracy on two subpopulations in the training data, will it also have comparable accuracy on samples from the two subpopulations test time?
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

In this paper, we consider the out- out-of-sample generalization of expected-value constraints. To keep things simple, consider a stochastic optimization problem with a single expected-value constraint:
0* arg mingge subject to Ep, [g( z)] = = _0
Er [S(0; 2)] = ((0:2)(P(z)
(1.1)
where O is linite-dimensional) parameter space, f.g 0 2 + R are (known) cost and constraint functions, and Z E is a random variable that represents a sample. The distribution of Z is unknown, so cannot solve (I.I) directly. Instead, we obtain IID training samples { {Zi) 1 from the true underlying distribution Po and solve the empirical version of (LI)
1 - Z.) arg mingee subject to
On
R.
(1.2)
1 -x=19 90; 2
The estimator On (r) is guaranteed satisfy the empirical constraint (i.e., 1, E g(0ns Z:) S 0), but it is unclear whether On satisfies the actual (population) constraint En [0(: 2)] S 0. As we shall see, under standard assumptions on (T.), On only satisfies the actual constraint with probability approaching 1 (see corollary 2.2 This is especially problematic for constraints that encode algorithmic fairness goals. For example, the 80% rule published by the US Equal Employment Opportunity Commission, interpreted in the machine learning context, requires the rate at which classifier predicts the advantaged label in minority groups to be at least 80% of the rate at which the classifier predicts the advantaged label in the majority group [
In this paper, we propose a distributionally robust version of that guarantees the actual constraint Ep, [9(0; 2)] < 0 will be satisfied with probability 1 a:
arg mingge subject to
1 E f(0; Z.)
0n
(1.3)
SUP (P))) Er [r(g(0 2)] S sof
where Dip is a sp-divergence (see section samples, and VPa is the a quantile standard normal random variable. More concretely, we show that on achieves asymptotically exact constraint satisfaction
for details), Pn, is the empirical distribution of the training
lim P [o(.:: 5 = -1-a. a.
(1.4)
Here the inner expectation is with respect to Z: the outer probability is with respect to the training samples ( Three desirable properties of (13) are
1. exact constraint satisfaction: If the actual probability of constraint satisfaction exceeds 1 - a. then the method is too conservative. This may (unnecessarilyy increase the cost of the model. By picking P., in (.3) carefully, constraints are satisfied with asymptotically exact probability - O.
2. computationally efficient: As we shall see, the computational cost of solving (1.3) is comparable to the cost of solving distributionally robust sample average approximation (SAA) problems.
pivotal: There are no nuisance parameters to estimate (e.g., asymptotic variances) (L.) The
user merely needs to look up the correct quantile of the standard normal distribution for their desired level of constraint generalization.
The rest of this paper is organized as follows. In Section 2 we develop method, theory, and algorithm for stochastic optimization problems with single constraint. In Section D we extend our method, theory, and algorithm to stochastic optimization problems with multiple constraints. In Section 4 we validate our theory by simulating resource-constrained newsvendor problem. In Section 5 we demonstrate the efficacy of our method by using it to train an algorithmically fair income classifier. In addition, show how to apply our method to a faimess constrained learning problem and discuss two practical considerations for fair ML application scenarios. Finally, we summarize our work in Section and point out interesting avenue of future work.
1.1 Related work
The closest work to our work is 2 They seek to pick (data-dependent) uncertainty set U such that
lim P (supo {E [g( Z)] supreu Ep [g(0: 2)]} s 0} a-a. (1.5) n-+

---

This condition is stronger than necessary: we only require
lim IP Er. [9(On: 2)] - supreu Ep [9(0n; 2)] = =0] =
(1.6)
where 0n is (data- )eeeedene)) estimator (not necessarily or
1.3) 133 2 study (asymptotic)
constraint satisfaction (1.4) for all deterministic objective functions (see $1.1 for details). They advocate picking KI. divergence ball with radius that depends on the excursion probability of certain x" process.
Another closely related line of work is on data-splitting approaches for ensuring constraint gener- alization B77 7l. At high level, they split the training data into training and validation subsets and use the validation subset to tune models trained on the training subset so that they satisfy the constraints. Although (computationally) simple and intuitive, their approach does not allow users to precisely control the constraint violation probability.
2 is the latest in line of work distributionally robust optimization (DRO) that show the optimal value of DRO problems
mingge suppeu E. (g(0; Z)],
(1.7)
where U is a (data-dependent) uncertainty set of probability distributions, are upper confidence bounds for the optimal values of stochastic optimization problems. Common choices of uncertainty sets in DRO include uncertainty sets defined by moment support constraints [6] 12 221, (p-
divergences 4 22 BIJ and Wasserstein distances 334 5 28
35). This line work is motivated by Owen's s seminal work empirical likelihood 3 In recent work, 126 [5] show that the optimal
value of DRO problems with empirical likelihood uncertainty sets leads to asymptotically exact upper confidence bounds for the optimal value of stochastic optimization problems (I15) consider more general d-divergence uncertainty sets). [ establish similar coverage results for Wasserstein uncertainty sets.
Our work is also closely related to the work on the variance regularization properties of DRO 31 which uses DRO to approximate the variance regularization cost function (see (2.4). 20
establish similar results for Wasserstein DRO. Lastly, we relate our work to the literature on chance constrained optimization (see [4 and the references therein). The general goal of chance constrained optimization is to minimize a loss function subject to the probability of satisfying uncertain constraints is above prescribed level. While our methods reformulate expected value constraints and we show that the solution of the reformulated problem enjoys an asymptotically exact probabilistic guarantees of constraint satisfaction. In addition, the data data-dependent constraints in our work are also unknown in practice, which differs from the common setup in the chance constrained optimization literature.
2 Single expected value constraint
We motivate L.3 by considering a few alternatives. First, we note that the results later in this section show that (1.2 violates the actual constraint in (I.I) approximately half the time (see corollary
2.2
The most straightforward modification of to ensure O, satisfies the (actual) constraint Er g(0; Z < 0 is to add a "margin" " in i.e. enforce the constraint
E 9(0; Z.) + En 00
(2.1)
in
If we pick the slack term en such that
IP {supoce [Er,[g(0: 2 - - g(0; > 6x Sa.
then it is not hard to check that the resulting 6n satisfies the (actual) constraint with probability greater than 1 36 29 However, this approach is most likely conservative because the constraint is unnecessarily stringent for 0's such that A ΣT g0; Z.) is less variable. also not pivotal: én is often set using bounds from (uniform) concentration inequalities, which typically depend on unknown problem parameters.
To relax the empirical constraint in way that adapts to the variability of the empirical constraints, we replace the uniform margin in 22. with deremeter-dependen margin:
1 Em Z,) + Za Vn
s 0,
(2.2)
3

---

where is the - a quantile of a standard normal random variable and (²) is an estimate of the asymptotic variance of g(:; Z). We recognize the (parameter-deeeeddent) margin (a multiple of) the standard enror of the empirical constraint. It is possible to show that enforcing (.2 achieves
asymptotically exact constraint generalization
22
The main issue with this method is it is not amenable to standard stochastic optimization algorithms. In particular, even if the original constraint in (.2) is convex, (.2) is generally non-convex. Another
issue is that it is not pivotal: the user must estimate the asymptotic variance of g(0; 2).
To overcome these two issues, we consider distributionally robust version of 1.2 i.e. enforcing
(f Ep [g(; [p[[((: 2)] - 0,
(2.3)
where (PllQ) & | aq dQ is u-divergence. Common choices of yp include (p()) (t 1)²
(which leads to the x² --dvvergence) and (tt) = logt t + - 1 (which leads to the Kullback-eeibe divergence). Although there many other choices for the uncertainty set in (2.3) pick an
<-divergeecc ball because (i) 22.3 with an e-divergence ball is asymptotically equivalent to (2.2)
sup (PI. Ep Z)] ~ Ei= 9(0; Zi)
Za
@ vn
(2.4)
and (ii) it leads to pivotal uncertainty sets. For theoretical analysis, we always use up(t) (t 1)²
and -dveeeegee in the remainder this paper.
Before we state the asymptotically exact constraint satisfaction property of (1.3) rigorously, we describe our assumptions on the problem.
1. smoothness and concentration: f and g are twice continuously differentiable with respect to 0, and l(0"; Z). VO(0 Z), g(0"; g0(0"; Z) are sub-Gaussian random variables.
2. uniqueness: the stochastic optimization problem with single expected value constraint has a unique optimal primal-dual pair (0",>*), and 8 belongs to the interior of the compact set O.
3. strict complementarity: X O.
4. positive definiteness: The Hessian of the Lagrangian evaluated at (0*,** is positive definite.
The preceding assumptions not the most general, but they are easy to interpret. The smoothness conditions on I and with respect to 8, the concentration conditions of f(0"; Z) and g(0"; Z), and the uniqueness condition facilitate the use of standard tools from asymptotic statistics study the large sample properties of the constraint value. The strict complementarity condition rules out problems which the constraint is extraneous; i.e. problems in which the unconstrained minimum coincides with the constrained minimum.
We are ready to state the asymptotically exact constraint satisfaction property of 1.3) rigorously. The main technical result characterizes the limiting distribution of the constraint value.
Theorem 2.1. Let On be optimal solution of Under the standing assumptions, we have
1.3 converging in probability
0o to 0*.
vn Ep [9(On: Z)] (E210000211] $ N Pa Varp. (((:: 2)], Varp, 2)1
We translate this result on the constraint value to result constraint generalization.
Corollary 2.2. Let PPa be the 1- 1-a a quantile of a standard normal random variable. Under the conditions of theorem 2.1 we have
lim P 11+00
[En 2)] S -P = /pa) = aa,
where U N(O0,) 1) is standard Gaussian random variable.
From theorem 2.1 and corollary 2.2 (see proofs in Appendix A we find that
1. picking Pr. O (i.e., equivalently solving 1.2) leads to a constraint violation probability that
approaches 7 in the large sample limit.
the relation between the mean and variance of the limiting distribution of the constraint value in
Theorem 2.T allows us to pick Pa in pivotal way (i.e. does not depend nuisance parameters).

---

2.1 Stochastic approximation for 1.3
In the rest of this section, we derive stochastic optimization algorithm to solve efficiently. As we shall see, the computational cost of this algorithm is comparable to the cost of solving a DRO problem. The key insight is that the robust constraint function has dual form (see Appendix Dr:
sup suPr:D.(P1)..ss Ep [0;;; 2)] infu20.vER
El= Hup" ((0:2.)-") + pp + v)
(2.5)
where (0(s) _ sut - p(t)} is the convex conjugate of s. As we use x² -quurrd divergence and (P() (t 1)2, the corresponding (0) & + s. The Lagrangian of (1. is
L(O, 2) - /4 Σー 2.) + p.u Ep 2)]
Σ f0; + Xinf WERR E up" (0l0:2))-u #
1 Pe + +
We see that evaluating the dual function inf, I( A) (at a fixed X) entails solving stochastic optimization problem that is suitable for stochastic approximation. This suggests dual ascent algorithm for solving
1. evaluate the dual function at A by solving stochastic optimization problem. update X with a dual ascent step.
We summarize this algorithm in Algorithm The main cost of Algorithm Tis incurred in the third line: evaluating the dual function. Fortunately, this step is suitable for stochastic approximation, so we can leverage recent advances in the literature to reduce the (computational) cost of this step. The total cost of this algorithm is comparable to that of distributionally robust optimization.
Algorithm Dual ascent algorithm for
1: Input: starting dual iterate λo 2 0
2: repeat
3: Evaluate dual function:
(e. arg min 1 E
{
nm Ei=1 Hip (0(((()2))-))) + pl t
4: Dual ascent update: det1 +- [Ax + +1 1 En /4pp (000((():22)))1) + M Pu + u1 }}
5: until converged
3 Multiple expected value constraints
In this section, we extend the results from the preceding section to stochastic optimization problems with multiple data-dependent constraints. Consider a stochastic optimization problem with K expected value constraints
arg mingee
Er, [[(0; 2)]
0*
(3.1)
[Ep, [9x (0; 2)] < 0) K
subject to
k=
Following the development in Section versions of the sample average constraints:
we enforee the expected value constraints with robust
arg mingee
1 1(00
0n subject
< 0 K
(3.2)
Ep [gx( (upPp.
k=1
where p (P1,... (Pi..... PK) T are uncertainty set radii for the constraints. There other approaches to enforcing multiple constraints that result in constraint generalization; we focus on (3.2) here because it allows the user adjust the constraint generalization probability for different constraints.
First, we extend theorem and corollary to problems with multiple (expected value) constraints. We assume
5

---

The Lagrangian of 1. smoothness and concentration: for & E [K], f. Ih are twice continuously differentiable with respect and f( Z). f 2). (x Z), Vg Z) are sub-Gaussian random variables.
2. uniqueness: the stochastic optimization problem with K expected value constraints (3.1) has unique optimal primal-dual pair (0' X*), and 0* belongs to the interior the compact set O
3. strict complementarity: X ( + i.e., each component of X is strictly positive.
positive definiteness: The Hessian of the Lagrangian evaluated at (0*, X*) is positive definite.
The strict complementarity constraint seems especially strong here because it requires all the con- straints to be active. It is possible (with extra notational overhead) state the result in terms of just the active constraints. We refer to Section 5. for more information about the unknown active set. Further, as long as the sample size is large enough, the active constraints in (32) coincide with the active constraints in I. To keep things simple, we assume all the constraints are active.
Theorem 3.1. Let 0n be optimal solution of 3.2 converging in probability + 0o to 0*.
Under the standing assumptions, we have
E. [on (Ons ]]]
Pn Varn, 91 (0*; 2)
90 Z) : 9k (8"; 2)
4 AN
vn
Varp,
Ep, 99 (On; 2))
LV PK Var gK (0: 2)
Corollary 3.2. Under the conditions of theorem
3.7
we have
En (O,; 2)]
lim TP n-700
RRR
P(U S vp).
Pr 9 On. 2)
where vD- (VPI,... .... PK)
and U is Gaussian random vector with mean zero and covariance
91(0": z)
91 (6 2)
Corr
& D- Cov DCCCO
D-
(3.3)
9K (0( 2)
9K (0: 2)
D diag ((Var (9 (0", Z) K (k=1)
From theorem 3.1 and corollary 3.2 (see proofs in Appendix B and C. we find that the probability of constraint satisfaction decreases exponentially as the number constraints increases. We also see that our method is no longer pivotal for multiple expected value constraints: the uncertainty set radii depends on the (unknown) correlation structure among the constraint values. Fortunately, is not hard to estimate this correlation structure. The most straightforward way is with the empirical correlation matrix. Let E, be the empirical covariance matrix of the constraint values. The empirical correlation matrix then given by R, A diag(E..) & (
Finally, it is straightforward to extend the algorithm for solving to 3.2
13.2
L(0, A)
1 Σ [(0; + Ek d (PS.PP....PPRR..55 Ep [x Z)] -.
=K A inf
El Hesp"( ge (0:7, (0. H4
PE + 1/
where we recalled the dual form of the robust constraint function 2.5 in the second step. We that evaluating the dual function inf, L(0. A) (at a fixed X) entails solving a stochastic optimization problem that is suitable for stochastic approximation. This suggests similar dual ascent algorithm we skip the details here (see Algorithm in Appendix D
for solving 1.3
Simulations
We simulate the frequency of constraint satisfaction for the following multi-ite newsvendor problem:
maxage subject to
Ep. [p min Z, 8]
c
Ey, [1] (1) [0(1]
S 61
(4.1)
[ (2)
[0(2]
< 52

---

where e E R. is the manufacturing cost, p E R4 is the sell price, 0 E θ [0, 100 is the number of items in stock, Z E Rd is random variable with probability distribution Po representing the demand, and there are d items in total. The distribution Po is unknown but we observe IID samples Z1, 2....., Zn from Po. All of the items have been partitioned into two groups so that the corresponding demand and stock can be written as Z = (Z(), 2) and 0 (oC), o The constraints in the problem exclude stock levels that underestimate the demand too much for each group of items, where 62 > 0 indicate tolerance level of such underestimation. The target of the problem is to maximize the profit while satisfying the constraints. minimization problem with expected value constraints in the form of (3.1) that we can apply our method B.2p. We pick Po as multivariate Gaussian with independent components so that the two constraints are generally uncorrelated with each other (see Appendix E for details).
easy to rewrite the maximization problem (4.)) as a
Throughout the simulations, we solve 3.2 with p = (Za: za) T for a E f0.4, 0.25, 0.1, 0.05, 0.005).
As suggested by our asymptotic theory in Section 3 the nominal probability of constraint satisfaction 1 a for each constraint and (1 )²² for both constraints due to the independence setup.
In Figure D we plot frequencies of constraint satisfaction for each constraint and both constraints, all of which averaged over 1000 replicates. As the sample size grows, the frequency versus probability curve converges to the theoretical dashed line of limiting probability of constraint satisfaction, validating our theory in the large sample regime. For more simulations (e.g., single constraint, two dependent constraints) we refer to Appendix
n- 30
n- 30
n=:30
200
0.-
0.3
INaaarng ai 22th 2andlee
Seqpanoo wattrgrr
0.7
0.6
0.5
0.4
03-
2.0
0.5
3.0
02
07
cwobabiityo
probubiliy Satidyynng condtraket
satieting both
Figure 1: Frequency versus limiting probability of constraint satisfaction of the first constraint (left), the second constraint (middle), and both of the constraints (right).
5 Application to fair machine learning
As ML models are deployed in high-stakes decision making and decision support roles, the fairness of the models has come under increased scrutiny, In response. there is a flurry of recent work on and algorithms to enforee the definitions
mathematical definitions of algorithmic fairness 16 2 25
10 38
A prominent class of fairness definitions is group fairness; such definitions require equality of certain metrics (e.g. false/true positive rates) among demographic groups. For example, consider a fair binary classification problem. Let X' C Rd be the input space, (0, 1) be the of possible labels, and A be the set of possible values of the prosected/sensstivee attribute. In this setup, training and test examples X A x V, and a classifier is a map f
are tuples of the form A, definition of algorithmic fairness for binary classification is equality of opportumity (23.
(0. 13. A popular
Definition 5.1 (equality of opportunity). Let Y a positive outcome and Y & f(X be the output of the classifier. Equality of opportunity entails P( = A a, Y = 1] = P(
be the advantaged label that is associated with
A = a', Y = 1} for all a, E A.
Equality of opportunity, or true positive rate parity, means that the prediction P = h((X) conditioned on the advantaged label Y = 1 is statistically independent of the protected attribute A. Furthermore, an approximate version of equality of opportunity can be readily defined. We say that Y h(X)
satisfies E-equality of opportunity if PYY A a, Y = =) - -P = 1 A a', Y = =13 Se for for all a, a' e A. In this case, represents practitioner's 's tolerance for fairness violations.
7

---

Given a parametric model space H. = (ff(-)) : ) and loss function f: e: x x x an in in-processing fair ML routine minimize the (empirical) risk E [e[e: Y) while satisfying some fairness constraints. Most commonly, definitions of group fairness (including equality of opportunity, demographic parity, and more) can be written as a special example a general set of linear constraints 2 of the form Mf²(0) I where matrix M IR K and vector E IRK encode the constraints; ( θ RT is a vector of (conditional) moments (e( = E (X, A, 0) & for [T]; I; event & is defined with respect to A,Y)
Fr X' A x V O
This framework fits to our methodology if we note that each (conditional) moment can be written as
Fe (0) E E(x,AY)>>p (X, A, 0) (E,(XYY
(5.1)
P(x,A.))-Po (X, A)}
Here the indicator 1 } takes value 1 if the event & happens, and O otherwise. Moreover, we use (x A, Y) emphasize that & only depends on (X, Y, but not on 0 in any way.
Note that (5.1) is a ratio of expected values, which is a non-linear statistical functional of Po. To use method, we first replace the denominator of (0) with estimator, such the unbiased estimator P(E.) = _ Σx= 1 (X; A,; Y.)]. The resulting plug-in estimation of μu then becomes linear in Po. allowing us to apply our method (see similar tricks in [8). We describe the application of our method to e-equality of opportunity Appendix
5.1 A two-stage method for unknown active set
In practice, it is probable that only a subset of the constraints are active. Furthermore, we do not know beforehand whether or not constraint is active in the true population problem. To handle this scenario, we propose a two-stage method:
1. At the first stage, we solve the sample average approximation (SAA) problem 3.2 with 0x- By doing so, identify the active set of the SAA problem.
2. At the second stage, we solve (.2) with such that Ps is a positive number only if the k-th constraint, & [K]. was identified as active the first stage.
In Appendix we show that the two-stage method also enjoys the calibration property (similar to Theorem and Corollary 3.2) under standard assumptions (i.e., strict complementarity). At high level, the limiting probability of satisfying the true constraints depends solely on the correlation structure between active constraints and the uncertainty set radii for active constraints, long as the SAA problem identifies active constraints with probability tending to
5.2 Proxy dual function for non-differentiable constraints
Constraint functions in fair ML are often non-differentiable. For instance, fairness metrics are typically linear combinations of indicators that result in non-differentiable rate constraints [8 This prevents the use of any gradient-base based optimization algorithms. Fortunately, only the dual function evaluation step in Algorithm T requires access to gradients. Therefore, we can modify the algorithm by: (1) introducing proxy dual function, which uses a differentiable surrogate ğ instead of the non-differentiable g in the dual function evaluation step; (2) keeping g in the dual ascent step. For an indicator function h(t)= = 1 0}, one can replace it by sigmoidal function fy (t) = (1+e-at)
or hinge upper bound l2(() max(0, & 1} to produce smooth surrogates for non-differentiable
rate constraints [I]
We summarize the proxy dual ascent algorithm in Appendix H
5.3 Adult experiments
We compare the frequency of constraint satisfaction (at test time) of the sample average approximation and our methods with nominal probability 0. 0.60, 0.75, 0.90, 0.95 using the Adult dataset from UCI
[K
The classification task is to predict whether an individual's 's income per year is higher than $50K.
The fairness goal is E-demographic parity (s-DP): P( 1 A A= 1) P(
A = 0) <
where A for male the advantaged group and A = 0 for female is the disadvantaged group. We use logistic regression model for classification and techniques in this section for implementation.
In Figure we have line plots for frequency of constraint satisfaction and box plots for classification error rate, all of which summarized over 100 replicates. The left panel shows that solving B.1

---

directly leads to one half chance of constraint violation, while our method's constraint satisfaction frequency matches its nominal value. The price higher chance of test-time faimess satisfaction is
an increase in classification error rate shown in the right panel. From the baseline to 95% chance of fairness satisfaction, we basically trade off 2% increase error rate. We refer to Appendix D and for details and more experiments.
nitfie
Frogetna Congman SananSaarrom Salrtstooo
Ener Raee
0.30
melleed yro 0.50
reshedd pod 030
040
Job 6.2
332
0.-
OP Teleaace
TIP Thlerance
Figure 2: Frequency of constraint satisfaction (left) and classification error (right) for different demographic parity tolerance & E {0.01, 0.02, 0.03, 0.04, 0.05). Baseline (sample average approxi- mation, SAA) and our methods (with nominal probability 0.60, 0.75, 0.90, 0.95) compared.
Summary and discussion
We explore the problem of exact constraint satisfaction probability in stochastic optimization with expected-value constraints. We propose distributionally robust reformulation of data-dependent constraints and provide theoretical guarantee constraint satisfaction with an asymptotically exact probability specified by the For solving the reformulated problem, scalable dual ascent algorithm and its variants are proposed. The computational cost of our algorithm is comparable that of a standard distributionally robust optimization problem. Our theory on exact constraint satisfaction probability is validated via simulations on the resource-constrained newsvendor problem. The efficacy of methods empirically demonstrated fair machine learning applications.
Some data-dependent constraints are by nature non-linear the underlying probability measure. For example, (5.1) is ratio of expected values. An intriguing direction for future research is to generalize the methods and theory developed in this work to constraints on non-linear functions of expected values. Such forms of constraints are known statistical functionals in statistics literature [9). The non-linear dependence of the constraint function on the probability measure precludes the stochastic approximation general way of evaluating the dual function, the constraint function no longer admits dual form 2.5). calling for the development of new algorithm.
Acknowledgments and Disclosure of Funding
This paper is based upon work supported by the National Science Foundation (NSF) under grants no. 1916271, 2027737, and 21333
References
[1] Alekh Agarwal, Alina Beygelzimer, Miroslav Dudík, John Langford, and Hanna Wallach. Reductions Approach to Fair Classification. arXiv:1803.0245: [cs], July 2018.
[2] Alekh Agarwal, Miroslav Dudík, and Zhiwei Steven Wu. Fair Regression: Quantitative Definitions and Reduction-based Algorithms. arXiv:1905. 12843 [cs, stat), May 2019.
[3] Solon Barocas, Moritz Hardt, and Arvind Narayanan. Fairness and Machine Learning. fairml- book.org, 2019.

---

[4] Aharon Ben-Tal, Dick den Hertog, Anja De Waegenaere, Bertrand Melenberg, and Gijs Rennen. Robust Solutions of Optimization Problems Affected by Uncertain Probabilities. Management Science, 59(2):341-35) November 2012. ISSN 0025-1909.
doi: 18.1287/mnsc. 1 120. 1641.
[5] Jose Blanchet, Yang Kang, and Karthyek Murthy. Robust Wasserstein Profile Inference and Applications to Machine Learning. arXiv:1610.05627 [math, stat], October 2016.
[6] Xin Chen, Melvyn Sim, and Peng Sun. A Robust Optimization Perspective on Stochastic Programming. Operations Research, 15:1105--171. 2007. doi: 10. 1287//ppre.070.0044
[7] Andrew Cotter, Maya Gupta, Heinrich Jiang. Nathan Srebro, Karthik Sridharan, Serena Wang. Blake Woodworth, and Seungil You. Training Well-Generalizing Classifiers for Fairness Metrics and Other Data-Dependent Constraints. arXiv:/807.00028 [cs, stat], September 2018.
[8] Andrew Cotter, Maya Gupta, Heinrich Jiang, Nathan Srebro, Karthik Sridharan, Serena Wang, Blake Woodworth, and Scungil You. Training well well-generalizing classifiers for fairness metrics and other data-dependent constraints. In International Conference on Machine Learning, pages 1397-1405. PMLR, 2019.
[9] Andrew Cotter, Heinrich Jiang, Maya Gupta, Serena Wang, Taman Narayan, Seungil You, and Karthik Sridharan. Optimization with Non-Differentiable Constraints with Applications to Fairness, Recall, Churn, and Other Goals, Journal of Machine Learning Research, 20(172):
1-59, 2019. ISSN 1533-7928.
[10] Andrew Cotter, Heinrich Jiang, and Karthik Sridharan. Two-Player Games for Efficient Non- Convex Constrained Optimization. In Algorithmic Learning Theory, pages 300-332. PMLR, March 2019.
[11] Mark A Davenport, Richard G Baraniuk, and Clayton D Scott. Tuning support vector machines for minimax and neyman- pearson classification. IEEE transactions on pattern analysis and machine intelligence, 32( 18) 2010.
[12] Erick Delage and Yinyu Ye. Distributionally Robust Optimization Under Moment Uncertainty with Application to Data-Driven Problems. Operations Research, 58:595-612, 2010. doi: 10. 10.1287/0pre.0000.07744
[13] Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL http://rrcchev
i ics uci. edd/mll
[14] John Duchi and Hongseok Namkoong. Variance-based regularization with convex objectives. October 2016.
[15] John Duchi, Peter Glynn, and Hongseok Namkoong. Statistics of Robust Optimization: A Generalized Empirical Likelihood Approach. arXiv:6610.03425 [stat], October 2016.
[16] Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Rich Zemel. Fairness Through Awareness. arXiv:1104.39) [cs], April 2011.
[17] Elad Eban, Mariano Schain, Alan Mackey, Ariel Gordon, Ryan Rifkin, and Gal Elidan. Scalable learning of non -ecompoooes objectives. In Artificial intelligence and statistics, pages 332-840.
PMLR, 2017.
[18] Peyman Mohajerin Esfahani and Daniel Kuhn. Data-driven Distributionally Robust Optimiza- tion Using the Wasserstein Metric: Performance Guarantees and Tractable Reformulations. May 2015.
[19] Luisa Turrin Fernholz. Von Mises calculus for statistical functionals, volume 19. Springer Science & Business Media, 2012.
[20] Chao Gao. Robust Regression via Mutivariate Regression Depth. arXiv:1702.04653 [math, stat], February 2017.
[21] Gabriel Goh, Andrew Cotter, Maya Gupta, and Michael Friedlander. Satisfying Real-world Goals with Dataset Constraints. Advances in Neural Information Processing Systems, 29, 2016.
10

---

[22] Joel Goh and Melvyn Sim. Distributionally Robust Optimization and Its Tractable Approxima- tions. Operations Research, (114-part-11:002999999 August 2010. ISSN 0030-364X, 1526-5463. doi: 10.1287/opre. 1090.0795.
[23] Moritz Hardt, Eric Price, and Nathan Srebro. Equality of Opportunity in Supervised Learning. arXiv:1610.02444 011.1111...00111.. [cs]. October 2016.
[24] Ruiwei Jiang and Yongpei Guan. Data-driven chance constrained stochastic program. Mathe- matical Programmingg 158(1):291-322 2016.
[25] Matt Kusner, Joshua Loftus, Chris Russell, and Ricardo Silva. Counterfactual Fairness. 1rXiv:1703.06855 [cs, stat], March 2018.
[26] H. Lam and Enlu Zhou. Quantifying uncertainty in sample average approximation. In 2015 Winter Simulation Conference (WSC), pages 3846-3857, December 2015. doi: 109//09 2015.7408541.
[27] Henry Lam. Recovering Best Statistical Guarantees via the Empirical Divergence-Bart Based Distributionally Robust Optimization. Operations Research, 67(4):1000-1105, July 2019. ISSN
0030-364X. doi: 10. 21128///prr.2118.1778
[28] Jaeho Lee and Maxim Raginsky. Minimax Statistical Learning with Wasserstein Distances. 1705:01705.0885 [cs), May 2017.
[29] James Luedtke and Shabbir Ahmed. A Sample Approximation Approach for Optimization with Probabilistic Constraints. SIAM Journal on Optimization, 19(2):674-69) January 2008. ISSN 1052-6234. doi: 10.1137/070702988.
[30] Mahdi Milani Fard, Quentin Cormier, Kevin Canini, and Maya Gupta. Launch and Iterate: Reducing Prediction Churn. In Advances in Neural Information Processing Systems, volume 29,
Curran Associates, Inc., 2016.
[31] Hongseok Namkoong and John C. Duchi. Stochastic Gradient Methods for Distributionally Robust Optimization with F-divergences. In Proceedings of the 30th International Conference on Neural Information Processing Systems, NIPS' 16, pages 2216-2211 USA, 2016. Curran Associates Inc. ISBN 978-1-5108-3881-9
[32] Art Owen. Empirical Likelihood Ratio Confidence Regions. The Annals of Statistics, 18(1): 90-120, March 1990. ISSN 0090-5364, 2168-8966. doi:
[33] Reuven Y Rubinstein and Alexander Shapiro. Discrete event systems: Sensitivity analysis and stochastic optimization by the score function method, volume 13. Wiley, 1993.
[34] Soroosh Shafieezadeh-Abaaeel Peyman Mohajerin Esfahani, and Daniel Kuhn. Distributionally Robust Logistic Regression. September 2015.
[35] Aman Sinha, Hongseok Namkoong, and John Duchi. Certifying Some Distributional Robustness with Principled Adversarial Training. arXiv: 1710.1077 [cs, stat], October 2017.
[36] Wei Wang and Shabbir Ahmed. Sample average approximation of expected value constrained stochastic programs. Operations Research Letters, 36(5):515-519, September 2008 ISSN 0167-6377. doi: orl.1//..rrl.000.. 05,0030........
[37] Blake Woodworth, Suriya Gunasekar, Mesrob Ohannessian, and Nathan Srebro. Learning Non-Diseriminatory Predictors. In Conference on Learning Theory, pages 1920-1953. PMLR,
June 2017.
[38] Mikhail Yurochkin and Yuckai Sun. SenSel: Sensitive Set Invariance for Enforcing Individual Fairness. In International Conference Learning Representations, September 2020.

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them?
[Yes]
you are including theoretical results...
(a) Did you state the full set assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No]
you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you'l 're
using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applica-
ble? [N/]]
(b) Did you describe any potential participant risks, with links Institutional Review Board
(IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent participant compensation? [N/A]
12


Reviews:
[{"review_id": "lNNDIYpRkXU", "reviewer": "Reviewer_EQuq", "summary": "This paper addresses the problem of constraints satisfaction in Machine Learning. More precisely, the goal is to guarantee that, with high probability, a model learned to satisfy an empirical estimate of a given constraint will also satisfy the constraint with respect to the original distribution. Based on recent advances in Distributionally Robust Optimization, the paper proposes a new approach to learn models that are theoretically guaranteed to exhibit such behaviour. Empirically, the interest of the proposed algorithm is demonstrated in an application to Fair Machine Learning. ", "questions": "My main concerns with this paper are detailed in comments 4., 5., and 6. in the Strengths and Weaknesses section and would need to be addressed.", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\n - The paper is well written and relatively easy to follow.\n - The problem of exact constraints satisfaction is important.\n - The proposed approach is theoretically well founded.\n\nCons:\n - The proposed algorithm does not come with guarantees on the quality of its solutions.\n - Group fairness constraints do not satisfy the main assumptions in the theoretical analysis.\n - There is a lack of datasets diversity and baselines in the experiments.\n\nOn the one hand, this paper addresses the important problem of exact constraint satisfaction in machine learning in a theoretically sound way. On the other hand, there is a gap between the developed theory and the main motivating example, that is fairness. Overall, the merits of this paper outweight its flaws and it could be accepted.\n\nDetailed comments:\n1. This paper is well written and relatively easy to follow. The assumptions on the problem are necessary for the theoretical derivations are explicitly stated and intuition is provided on the meaning of the various results.\n\n2. The problem addressed in the paper is significant. Indeed, models learned on a limited training set encounter new examples when they are deployed in the wild and ensuring that the desired constraints are respected on these new examples (as long as they follow the distribution that generated the training samples) is important. This is particularly true for fairness constraints which is one of the motivating problems of this paper.\n\n3. To ensure that the learned model satisfies a constraint exactly, that is even on the overall unknown distribution, the paper proposes to ensure that the empirical estimate is satisfied with a sufficiently large margin. It is then shown that it is similar to solving a distributionally robust optimization problem where the constraint has to be satisfied for any distribution that lies in a ball around the empirical distribution of the training sample. It is then theoretically shown that, in the large sample limit, the solution to this optimization problem satisfies the exact constraint provided that the radius of the ball considered is sufficient large and that the constraint under consideration respect some constraints. Similar results are provided in the case where several constraints should be satisfied.\n\n4. To solve the distributionally robust optimization problem, the paper proposes to use a stochastic scheme based on Lagrange multipliers. Due to its nature, this approach is likely to lead to approximate solutions and it is not clear as to how good these solutions will be compared to the optimal one. Similarly, in Section 5, several heuristic are proposed to deal with the problems of unknown active sets and non-differentiable constraints but their impact on the quality of the solutions is not discussed.\n\n5. One of the motivating problems for the proposed approach is group fairness constraints in machine learning as detailed in the experimental Section 5. Unfortunately, there seems to be a gap between the theory and algorithm developed in the paper and this setting:\n    - Fairness constraints do not satisfy the assumptions necessary for the theory to hold. Indeed, group fairness constraints are usually non-differentiable.\n    - In the case of exact fairness, the proposed approach might lead to unfeasible problems. Indeed, in this setting, the goal is, for example, to ensure that the probability of correctly predicting the desirable outcome given that it should be predicted is independent of the sensitive attribute (equality of opportunity, Definition 5.1). It corresponds to an equality constraint (where a difference should be equal to $0$) that is often broken down in two inequality constraints which can only be simultaneously satisfied with a margin of $0$. The interpretation given in Equation (2.4) shows that this is not compatible with the proposed approach.\n    - The previous issue is less likely to happen with approximate fairness where the constraints have to be satisfied up to a factor $\\epsilon$. However, in this case, it could be that when $\\epsilon$ is smaller than the margin necessary to ensure a given probability of satisfying the exact constraints, the problem becomes infeasible again. Consequently, an interesting extension of this work would be to provide guarantees on the probability that the exact constraints will be satisfied given that the empirical constraints are satisfied up to a given margin.\n\n6. The experiments investigate the interest of the proposed approach in two different settings.\n    - In a simulated environment, it is shown that the, as the number of training examples increases, the proposed approach will indeed learn models that satisfy the exact constraints with the desired probability.\n    - On a fair machine learning problem, it is shown that using the proposed approach indeed increases the probability of constraints satisfaction. Unfortunately, this result is only shown on a single dataset (Adult) and a single baseline is considered (directly solving the problem with the empirical constraints). It would have been interesting to provide more extensive experiments by, for example, considering [1], [10], and [23] as baselines and considering other datasets (the ones used in the aforementioned papers for example).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "_k01LEHn5T", "reviewer": "Reviewer_tHYG", "summary": "This paper considers the problem of stochastic optimization subject to data-dependent constraints in the form of E g(\\theta;Z) <= 0. Solving these problems using finite samples raises the issue of ensuring that the constraints will be satisfied on the population distribution, and not just on the samples. This paper proposes to address this issue by solving a distributionally robust variant of the problem, where the empirical loss is minimized subject to the constraint that E_P g(\\theta;Z) <= 0 for all probability distributions P that are sufficiently close to the empirical distribution in the sense that the phi-divergence between them is less than a certain size. The paper shows that this allows for calibrated satisfaction of the constraints asymptotically, i.e. in the large sample limit, the constraints will be satisfied with probability exactly 1-alpha for alpha chosen by the user. Several examples are also discussed, as are a few tricks for solving the associated optimization problem.", "questions": "I noticed in almost all of the experiments that the frequency of satisfying the constraints seems to nearly always approach the asymptotic limit from below. This suggests to me that the distributionally robust modification of the constraint is generally over-permissive, and only becomes correctly calibrated in the limit (or at least once the CLT kicks in). Is it clear that this would be the case? If you are concerned about what happens with relatively few finite samples, do you have any suggestions about how to adjust the method to improve calibration here?", "limitations": "See \"weaknesses\" above.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThis paper is very clearly written. Each idea is introduced nicely and each step in the discussion follows very nicely from the previous one, to the extent that everything seems almost obvious in hindsight. Having the constraints' satisfaction rate be calibrated in this way seems very useful in practice and this paper presents a very straightforward recipe for achieving this asymptotically. Finally, the experiments indicate that although the theoretical results in the paper are only asymptotic, they appear to hold already at practical sample sizes.\nWeaknesses:\nI think it would be helpful to discuss also the computational issues that arise in trying to solve the optimization problem associated with the method. E.g., the optimization problem in line 3 of Algorithm 1 is generally non-convex (unless the constraint g(\\theta;Z_i) is linear in \\theta). Of course, given the current practice of machine learning, we may not actually be so concerned about this, and we might just use SGD and hope that it works. But in this case, I wonder if anything can be said about what happens when (1.3) is solved only approximately? If you solve it to some epsilon error, is it clear what happens to the satisfaction rate? This is perhaps too big of a question to fully address in this paper, which focuses on the statistical issues at play, but I think that computational issues deserve at least some discussion in a machine learning venue such as Neurips.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "KBRTSU_xTnn", "reviewer": "Reviewer_oKKe", "summary": "This paper proposes a distributionally robust optimization algorithm to machine learning problems with constraints in the form of expected values. Performing the proposed DRO with the empirical version of the constraints acts as a variance-estimation-free way of introducing margins so that the data dependent solution can achieve exact constraint satisfaction in terms of the expectations. The proposed method is compatible with standard stochastic optimization in its dual form, and empirical studies show that the method is indeed calibrated and is effective for multiple fairness sensitive classification tasks. ", "questions": "The reviewer does not have major questions regarding the manuscript. Here are a few minor questions:\n- Since the dual form of the DRO is key to running the computation, it is worth a bit more attention and explanation in Section 2.1. \n- If the reviewer understands correctly, the \"pivotalness\" is a direct result of the chi-square divergence. It would be nice to have more discussions here. ", "limitations": "See weaknesses.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThe paper presents a complete study on the exact constraint satisfaction perspective of ML fairness, which is a widely-recognized and important topic. The authors introduces DRO with chi-square divergence bounding the empirical and the population distributions, which can be viewed as a replacement for parameter-dependent constraint margins in other literature, resulting in an optimization problem that is both more convex and does not require the estimate the variability of constraint violation. This is a theoretically sound conclusion. The authors also have covered most alternatives or fixes for practical nuisances when applying the algorithm, which makes the method easily feasible for lots of real world questions. The presentation in the paper is clear and easy to follow. \n\nWeaknesses:\nThe proposed method only guarantees \"exactness\" for a single constraint expressed as an expectation. Despite that the authors have introduced adaptations for multiple constraints in other forms (e.g. ratio of expectations), the \"exactness\" might be subtly impacted by the plug-in estimates used there. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept