Robust Generalization despite Distribution Shift via Minimum Discriminating Information
Authors: Tobias Sutter
Andreas Krause
Daniel Kuhn
Venue: NeurIPS 2021 Poster (2021)
Keywords: Distributionally robust optimization
distribution shift
stochastic programming
large deviations

Abstract: Training models that perform well under distribution shifts is a central challenge in machine learning. In this paper, we introduce a modeling framework where, in addition to training data, we have partial structural knowledge of the shifted test distribution. We employ the principle of minimum discriminating information to embed the available prior knowledge, and use distributionally robust optimization to account for uncertainty due to the limited samples. By leveraging large deviation results, we obtain explicit generalization bounds with respect to the unknown shifted distribution. Lastly, we demonstrate the versatility of our framework by demonstrating it on two rather distinct applications: (1) training classifiers on systematically biased data and (2) off-policy evaluation in Markov Decision Processes.

Robust Generalization despite Distribution Shift via Minimum Discriminating Information
Tobias Sutter
Andreas Krause ETH Zurich, Switzerland krausea@ethz.cht
University of Konstanz, Germany tobias. sutteronii -twterrrrni-oooota...... konstanz.da.
Daniel Kuhn EPFL, Switzerland daniel. kuhn@epf1.ch
Abstract
Training models that perform well under distribution shifts a central challenge in machine learning. In this paper, we introduce modeling framework where, in addition to training data, we have partial structural knowledge of the shifted test distribution. We employ the principle of minimum discriminating information embed the available prior knowledge, and use distributionally robust optimization account for uncertainty due the limited samples. By leveraging large deviation results, we obtain explicit generalization bounds with respect to the unknown shifted distribution. Lastly, we demonstrate the versatility of our framework by demonstrating it on two rather distinct applications: (1) training classifiers on sys- tematically biased data and (2) off-policy evaluation Markov Decision Processes.
Introduction
Developing machine learning- learning-based systems for real world applications is challenging, particularly because the conditions under which the system was trained are rarely the same as when using the system. Unfortunately, standard assumption in most machine learning methods is that test and training distribution are the same [78, 57, 12]. This assumption, however, rarely holds in practice, and the performance of many models suffers in light of this issue, often called dataset shift [52] or equivalently distribution shifi. Consider building a model for diagnosing Specific heart disease, and suppose that most participants of the study are middle to high-aged men. Further suppose these participants have a higher risk for the specific disease, and as such do not reflect the general population with respect age and gender. Consequently, the training data suffers from the so-called sample selection bias inducing a covariate shift [62. 52]. Many other reasons lead to distribution shifts, such as non-stationary environments [67], imbalanced data [52], domain shifts [3], label shifts [83] or observed contextual information [8, 9]. A specific type of distribution shift takes center stage in off- off-policy evaluation (OPE) problems. Here, one concerned with the task of estimating the resulting cost of an evaluation policy for sequential decision making problem based on historical data obtained from a different policy known as behavioral policy [73]. This problem of critical when it is impossible or
importance in various applications of reinforcement unethical to evaluate the resulting cost of an evaluation policy by running it on the underlying system. Solving learning problem facing arbitrary and unknown distribution shift based training data in general is hopeless. Oftentimes, fortunately, partial knowledge about the distribution shift is available. In the medical example above, we might have prior information how the demographic attributes in our sample differ from the general population. Given a training distribution and partial knowledge about the shifted test distribution, one might ask what is the "most natural" distribution
carning-paaticulle
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

shift mapping the training distribution into a test distribution consistent with the available structural information. Here, we address this question, interpreting "most natural" as maximizing the underlying Shannon entropy. This concept has attracted significant interest in the past in its general form, called principle of minimum discriminating information dating back to Kullback [37], which can be seen as a generalization of Jaynes' maximum entropy principle [31]. While these principles are widely used in tasks ranging from economics [27] to systems biology [63] and regularized Markov decision processes [48, 25, 2]. they have not been investigated to model general distribution shifts as we
consider in this paper. Irrespective of the underlying distribution shift, the training distribution of any learning problem is rarely known, and one typically just has access to finitely many training samples. It is well-know that models can display a poor out-of- sample performance if training data is sparse. These overfitting effects are commonly avoided via regularization [12]. A regularization technique that has become popular in machine learning during the last decade and provably avoids overfitting is distributionally robust optimization (DRO) [36].
Contributions. We highlight the following main contributions of this paper:
We introduce a new modelling framework for distribution shifts via the principle of minimum discriminating information, which encodes prior structural information on the resulting test distribution.
Using our framework and the available training samples, we provide generalization bounds via a DRO program and prove that the introduced DRO model is optimal in a precise statistical sense.
We show that the optimization problems characterizing the distribution shift and the DRO program can be efficiently solved by exploiting convex duality and recent accelerated first order methods.
We demonstrate the versafility of the proposed Minimum Discriminating based DRO (MDI-DRO) method on two distinct problem classes: Training classifiers on systematically biased data and the OPE for Markov decision processes. In both problems MDI-DRO outperforms existing approaches.
2 Related work
For supervised learning problems. there rich literature in the context of covariate shift adap- tation [62, 68]. A common approach is to address this distribution shift via importance sampling, more precisely by weighting the training loss with the ratio of the test and training densities and then minimize the so-called importance weighted risk (IWERM), see [62, 82, 68, 69]. While this importance weighted empirical risk an unbiased estimator of the test risk, the method has two major limitations: It tends to produce an estimator with high variance, making the resulting test risk large. Further, the ratio of the training and test densities must be estimated which in general is difficult as the test distribution is unknown. There are modifications of IWERM reducing the resulting variance [15, 13, 65), for example by exponentially flattening the importance ratios [62]. For the estimation of the importance weights several methods have been presented, see for example [81]. These methods, however crucially rely on having data from both training and test distribution. Liu and Ziebart [40] and Chen et al. [14] propose a minimax approach for regression problems under covariate shift. Similar to our approach taken in this paper, they consider a DRO framework, which however, optimizes over so-called moment-base based ambiguity sets. Distribution shifts play key role in causal inference. In particular, the connection between causal predictors and distributional robustness under shifts arising from interventions has been widely studied [58, 42, 56, 66). Oftentimes, a causal graph is used to represent knowledge about the underlying distribution shift induced by an intervention [49, 50]. Distribution shifts have been addressed in variety of different settings [35], we refer the reader to the comprehensive textbook [52] and references therein.
There is a vast literature on OPE methods which we will not attempt to summarize. In a nutshell, OPE methods can be grouped into three classes: a first class of approaches that aims to fit model from the available data and uses this model then to estimate the performance of the given evaluation policy [41, 1, 38). A second class of methods are based on invoking the idea of importance sampling to model the underlying distribution shift from behavioral to evaluation policy [51, 29, 74]. The third, more recent, class of methods combines the first two classes [24, 32, 76, 33].
Key reasons for the popularity of DRO in machine learning are the ability of DRO models to regular- ize learning problems [36, 60, 61] and the fact that the underlying optimization problems can often be exactly reformulated as finite convex programs solvable in polynomial time [4, 10]. Such refor- mulations hold for variety of ambiguity sets such as: regions defined by moments [20, 26, 80, 11].
2

---

o-divergences [5, 44, 391, Wasserstein ambiguity sets [43, 36], or maximum mean discrepancy ambi- guity sets [64, 34]. DRO naturally seems a convenient tool when analyzing "small" distribution shifts as it seeks models that perform well "sufficiently close" to the training sample. However, modelling general distribution shift via DRO seems difficult, and recent interest has focused on special cases such as adversarial example shifts [23] or label shifts [83]. To the best of our knowledge, the idea of combining DRO with the principle of minimum discriminating information is new.
Problem statement and motivating examples
We study learning problems of the form
min R(O, 6E
(I)
where R(O,P*) = Ep. [L(0,)] E)] denotes the risk of an uncertain real-valued loss function L(0, E) that depends on a parameter 0 E O C R to be estimated as well as a random vector & e E C R.. m governed by the probability distribution IP*, In order to avoid technicalities, we assume from now on that and E are compact and is continuous. In statistical learning, it is usually assumed that P* is unknown but that we have access to independent samples from IP* This paper departs from this standard scenario by assuming that there a distribution shift. We first state our formal assumption about the shift and provide concrete examples below. Specifically, we assume to have access to samples from a distribution F + IP and that IP' is only known to belong to the distribution family
II = [Q P(E) (x) E E}
(2)
encoded by measurable feature map 3/ - d and compact convex set E C Rd. In view of the principle of minimum discriminating information, we identify I with the I-projection of P onto II. Definition 3.1 (Information projection). The I-projection of P(E) onto 11 is defined as
p (TP) arg min D
QEl
where D(QIIP) denotes the relative entropy of Q with respect to P.
One can show that the I-projection exists whenever II is closed with respect to the topology induced by the total variation distance [17, Theorem 2.1]. As E is closed, this is the case whenever t is bounded. Note that ((P) = IP if F II. In the remainder, we assume that IP Il and that P is only indirectly observable through independent training samples EI....,,x drawn from P.
Example 3.2 (Logistic regression). Assume that { (z, y). where x E 1= is a feature vector of patient data (e.g.. patient's 's age, sex, chest pain type, blood pressure, etc.), and y E {-1,1} label indicating the occurrence of a heart disease. Logistic regression models the conditional distribution of given x by a logistic function Prob(ylæ:) = [1 + exp(-y- 0 [Tx)]= parametrized by 0 E m= The maximum likelihood estimator for A is found by minimizing the empirical average of the logistic loss function L(),E)= = log(1 + cxp(-y B x)) on the training samples. If the samples pertain to patient cohort, where elderly males are overrepresented with respect to the general population. then they are drawn from training distribution PP that differs from the test distribution IP. Even if sampling from Pa is impossible, we may know that the expected age of a random individual in the population falls beiween 40 and 45 years. This information can be modeled as Ep. [g(E) E F, where E = Lt, u), E = 40, u = 45 and vv(E) projects & to its 'age" component. Other available prior information can be encoded similarly. Inspired by the principle of minimum discriminating information, we then minimize the expected log-loss under the I-projection pS of the data- generrgengg distribution P onto the set II defined in (2).
Example 3.3 (Production planning). Assume that 0 E R and 5 E RR denote the production quantity and the demand of a perishable good, respectively, and that the loss function L(0,E) represents the sum of the production cost and penalty for unsatisfied demand. To find the optimal production quantity, one could minimize the average loss in view of training samples drawn from the historical demand distribution P. However, a disruptive event such as the beginning of recession might signal that demand will decline by at least 1/%. The future demand distribution Tp* thus differs from IP and belongs to a set II of the form (2) defined through vi(E) = E and E. = [0, (1 10-n) n]), where y denotes the historical average demand. By the principle of minimum discriminating information it then makes again sense minimize the expected loss under the I-projection pd of P onto II.
3

---

Loosely speaking, the principle of minimum discriminating information identifies the 1-projection 1p/ of as the least prejudiced and thus most natural model for IP in view of the information that IP E II. The principle of minimum discriminating information is formally justified by the conditional limit theorem [18], which we paraphrase below using our notation.
Proposition 3.4 (Conditional limit theorem). If the interior of the compact convex set E overlaps with the support of the pushforward measure IP ub- the I-projection TP/ = [(P) exists and the moment- gennentngnnertiingg. function Eps [etL((..1] is finite for all t in a neighborhood of 0, then we have
lim Epp (I(0,E)) E.= (b())) E E} Epp [T(9,C) E
N N-000
In the context of Examples 3.2 and 3.3, the conditional limit theorem provides an intuitive justification for modeling distribution shifts via I-projections. More generally, the following proposition suggests that any distribution shift can be explained as an I-projection onto a suitably chosen set II.
Proposition 3.5 (Every distribution an I-projection). If Q E P(E) are such that Q absolutely continuous with respect to IP and if II a set of the form (2) defined through (E( = log E = [D()) then Q = (PP).
dQ ae (E) and
The modelling of arbitrary distribution shifts via the I-projection according to Proposition 3.5 has an interesting application in the off- aff-policy evaluation problem for Markov decision processes (MDPs).
Example 3.6 (Off-policy evaluation). Consider an MDP (S, A, Q, so) with finite state and action spaces S and A, respectively, transition kernel Q : S x A - R. cost-per-stage function c S x A R and initial state so- A stationary Markov policy π is stochastic kernel that maps states to probability distributions over A. We use T(aas) to denote the probability of selecting action a in state s under policy и. The long-run average cost generated by can be expressed as
V₂ = limm- T Et= R% [c(st,aa) at)]-
Each policy induces an occupation measure Ha on defined through the state-action frequutecctiiooneeeeeeeeei
Mx, a) = lim + ET-Ipp Pr. [s a+) = (s, a)] Vs E S, a E A.
see 128, Chapter 6]. One can additionally show that μt belongs to the polytope
M {u ASXA: En' ((s', - EnEA Q(''ls, (s, a)p(s, a) = 0 E S),
where ASxA represents the simplex of all probability mass functions over S A. Conversely, each occupation measure E M induces a policy T defined through T (als) = ()s, /(s,a)/E EdeAm(s a') for all s E S and a E A. Assuming that all parameters of the MDP except for the cost are known, the off-policy evaluation problem asks for an estimate of the long-run average cost Va, of an evaluation policy Te based on trajectory of states, actions and costs generated by a behavioral policy Tb- This task can be interpreted as a degenerate learning problem without parameter @ to optimize if we define { = c(s, a) and set L(0, {) E. Here, distribution shift emerges because we must evaluate the expectation of & under Q = Pe o c given training samples from IP = Pb o c-!, where μ& and we represent the occupation measures corresponding to To and Ta, respectively, Note that P and Q are unknown because is unknown. Moreover, the policy generates different state- action trajectories than Th, the costs generated under me cannot be inferred from the costs generated under To even though Th and ne are known. Note also that Q coincides with the I-projection Pl of P onto the set I1 defined in Proposition 3.5. The corresponding feature map tb as well as the set E can be computed without knowledge of provided that e is invertible. Indeed, in this case have
du (E.)) = llog dptaoc
(Es) = .log Pelsi.ad) pa(acaa))
and E = (D(He o "111b00 )c
for any E S, 04 E A and & = c(ss, 0.). Note that as S and A are finite, e is generically invertible, that can always be rendered invertible by an arbitrarily small perturbation. In summary, we may conclude that the off pollco evaluation problem reduces to an instance of (1).
Given N training samples E....,, ,,,,, we henceforth use PN = N SNN og. and P to denote the empirical distribution on and its I-projection onto II, respectively. As the true data-generating distribution IP and its I-projection pl are unknown, it makes sense to replace them by their empirical counterparts. However, the resulting empirical risk minimization problem is susceptible overfitting

---

if the number of training samples is small relative to the feature dimension. In order to combat overfitting, we propose to solve the DRO problem
JN
min R (0,P)) B
(4)
which minimizes the worst-case risk over all distributions close to P Here, R is defined through Rd (0, P)) = supgen (R(0, Q) D(P))))) sr}
(5)
and thus evaluates the worst-case risk of a given parameter A E in view of all distributions Q that have relative entropy distance of at most from given nominal distribution P' II. In the remainder we use Jj and f to denote the minimum and a minimizer of problem (4), respectively.
Main results. The main theoretical results of this paper can be summarized as follows.
(i) Out-of-sample guarantee. We show that the optimal value the DRO problem (4) provides an upper confidence bound on the risk of its optimal solution 0% Specifically, we prove that
PNN (R(ON. P') JR) e N
where Tp/ = (P) is the I-projection of TP. If E is finite, then (6) can be strengthened to finite sample bound that holds for every N if the right hand side is replaced with e (N + 1)|=1 (ii) Statistical efficiency. In a sense to be made precise below, the DRO problem (4) provides the least conservative approximation for (1) whose solution satisfies the out-of-sample guarantee (6). (iii) Computational tractability. We prove that the I-projection T can be computed via regularized fast gradient method whenever one can efficiently project onto E. Given To/ we then show that Ol can be found by solving tractable convex program whenever θ is convex and conic representable set, while [(0, {) is a convex and conic representable function of for any fixed g.
Statistical guarantees
Throughout this section, we equip P(E) with the topology of weak convergence. As L(0,E) g is continuous on θ x E and is compact, this implies that the risk R(0, Q) continuous on θ x P(E). The DRO problem (4) is constructed from the I-projection of the empirical distribution, which, in turn, constructed from the given training samples. Thus, 0y constitutes a data-driven decision. Other data-driven decisions be obtained by solving surrogate optimization problems of the form
JN min ((0, #Ee
where R. ④ x II + R is continuous function that uses the empirical I-projection T to predict the true risk R[0, P() of 0 under the true I-projection IPf, From now on we thus refer to R a predictor, and we use J.v and 0y to denote the minimum and a minimizer problem (7), respectively. We call a predictor A admissible if JN provides an upper confidence bound on the risk of 0 in the sense that
lim sup log wad (R(ON, JN - VP E P(E) N N
1
(8)
for some prescribed >> 0. The inequality (8) requires the true risk of the minimizer Øy to exceed the optimal value JN of the surrogate optimization problem (7) with probability that decays exponentially at rate r as the number N of training samples tends to infinity. The following theorem asserts that the DRO predictor R* defined in (5), which evaluates the worst-case risk of any given across a relative entropy ball of radius r. almost satisfies (8) and is thus essentially admissible.
Theorem 4.1 (fut-of-sample guarantee). !fr > 0, int( and for every E RRd there exists an uncertainty realization & E E such that (E) > O, then the DRO predictor R defined in (5) is continuous on θ x II. In addition, R R + 8 is an admissible data-driven predictor for every >
Theorem 4.1 implies that, for any fixed O. the DRO predictor R" provides an upper confidence
bound J & on the true risk R(0 pl) of the data-driven decision 0% that becomes increasingly reliable as N grows. Of course, the reliability of any upper confidence bound trivially improves if it increased. Finding some upper confidence bound is thus easy. The next theorem shows that the DRO predictor actually provides the best possible (asymptotically smallest) upper confidence bound.
5

---

Theorem 4.2 (Statistical efficiency). Assume that all conditions of Theorem 4.1 hold. If J and R are defined as in (4) and (5), while JN is defined as in (7) for any admissible data-driven predictor R. then we have lem JN I limm-xx JN P aalmost surely irrespective P P(E).
One readily verifies that the limits in Theorem 4.2 exist. Indeed, if R is an arbitrary data-driven predictor, then the optimal value IN of the corresponding surrogate optimization problem converges P-almost surely to mingee R(6, P/) as N tends infinity provided that the training samples are drawn independently from P. This is direct consequence of the following three observations. First, the optimal value function mingge R(e, P() is continuous in P E II thanks to Berge's maximum theorem 17, pp. 115-116], which applies because R is continuous and θ is compact. Second, the I-projection pf = (TP is continuous in IP E P(E) thanks to [70, Theorem 9.17], which applies because the relative entropy is strictly convex in its first argument [21, Lemma 6.2. Third, the
strong law of large numbers implies that the empirical distribution PN converges weakly to the data-generating distribution TP as the sample size N grows. Therefore, we have
lim JN lim min R (QP(()))) min R (0. ( Jim Pw)) min R(0,11) P-a.s. DEG
(N
700 N DE
In summary, Theorems 4.1 and 4.2 assert that the DRO predictor R is (essentially) admissible and that it is the least conservative of all admissible data-driven predictors, respectively. Put differently, the DRO predictor makes the most efficient use of the available data among all data-driven predictors that offer the same out-of-sample guarantee (8). In the special case when E is finite, the asymptotic out- of-sample guarantee (8) can be strengthened to finite sample guarantee that holds for every N E N.
Corollary 4.3 (Finite sample guarantee). If R is defined as in (5), then
P)) > J&) log(N N 1) E - N
log Ta
N
We now temporarily use Rt to denote the DRO predictor defined in (5), which makes its dependence on explicit. Note that if >> is kept constant, then R2 (0, 1%() is neither an unbiased nor consistent estimator for R(0, Pf). Consistency can be enforced, however, by shrinking
N grows. Theorem 4,4 (Asymptotic consistency). Let the assumptions of Proposition 3.4 hold and (rx hNeN be a sequence of non-negative reals with Nim IN = O. If the loss function ( {) is Lipschitz continuous in with Lipschitz constant A >> O uniformly across all 0 E O then we have
lim Ri (0,Pf/) R(0,PPf) po--as. VO E N+00
(10a)
lim min Rey (0, (0.1%) N-500 REB
min R(O,P)) Pm-a.s
(10b)
DEO
Remark 4.5 (Choice of radius). Theorem 4.2 shows that the ambiguity set used in our paper displays a strong Pareto-optimalin property, i.e., it leads to the least conservative predictor, uniformly across all estimator realizations, for which the out-oofsampll disappointment probability is guaranteed to decay exponentially at rate r. Therefore, the radius r has a direct operational interpretation that captures the risk tolerance of the decision maker-it is chosen subjectively. Since the statistical guarantees of Theorem 4.1 are asymptotic, selecting the radius T when we only have access to finitely many samples is challenging, and in practice r is usually selected via cross validation.
We now exemplify our DRO approach and its statistical guarantees in the context of the off-policy evaluation problem introduced in Section 3.
Example 4.6 (Off- -off-p evaluation). Consider again the OPE problem introduced in Example 3.6. We now aim to construct an estimator for the performance of the evaluation policy Vz, = EE [S] based on the available behavioral policy and its empirical cost. As described in Example 3.6, we choose II such that Hl o c1 = [(P), where F 1bb c1 P(E). Given the behavioral data (B,, ā.) ~ ub f we then construct the empirical distribution FN= = E. dect,a. Our statistical results require the samples (3i, āx) to be i.i.d., which can be enforced upproximately by discarding a sufficient number of intermediate sumples, for example. We emphusize, however, that the proposed large deviation frumework readily generalizes to situations in which there is single trajectory of correlated data [39, 72]. Details are omitted for brevity. The value function Va..

---

under the evaluation policy can now be approximated by JN = RR RP'P's), where R denotes the DRO predictor (5). As E is finite, Corollary 4.3 provides the generalization bound
P.N (Vz. J.) (N 11)+ VP E
(11)
which holds for all N E.N.
5 Efficient computation
We now outline efficient procedure to solve the DRO problem (4). This procedure consists of two steps. First, propose algorithm compute the I-projection P/ f(Px) of the empirical distribution Pyy corresponding to the training samples fi..... .n. Given PP we then show how to compute the worst-case risk 1t (0, F N) and a corresponding optimizer 0z over the search space O.
Computation of the I-projection. Computing the I-projection of the empirical distribution i' is non-trivial task because it requires solving the infinit-ddimensiinal optimization problem (3). Generally, one would expect that the difficulty of evaluating / [(PN) depends on the structure of the set IT, which encoded by tp and E; see (2). Thanks the discrete nature of the empirical distribution Pv. however, we can leverage recent advances in convex optimization together with an algorithm proposed in [71] to show that fIPx) can be evaluated efficiently for large class of sets II.
In the following let 17 (71 772) be smoothing parameter with 771 7/2 > 0, and we let Ly > 0 be a learning rate that may depend r). In addition, we denote by E IRd the vector of dual variables of the constraint Eg(e/ (E)) E in problem (3), and we define G R + Rd with
EN M(E) exp( & EN exp( Σ (E.))
G,(()) - - 2) 1722 +
(12)
a smoothed gradient of the dual objective, where TE denotes the projection operator onto E defined through Te (z) arg minzer || 2113. The corresponding smoothed dual of the I- projection problem (3) can then be solved with the fast gradient method described in Algorithm
The complexity of evaluating G,, and thus the per-iteration complexity of Algorithm 1, is determined by the projection operator onto F., For simple sets (e.g.. 2-norm balls or hybercubes) the solution available in closed form, and for many other sets (e.g., simplices or 1-norm balls) it can be computed cheaply, see [53, Section 5.4] for comprehensive survey.
Algorithm 1: Fast gradient method for smooth & strongly convex optimization [47]
Choose wo = 20 Rd and E I
For 1: E N
Step 1:
Set 7k+1 = Wk + 1 G,G,(
Top L (2k+1
Step 2:
Compute Wk+1 = 2k-1 +
24)
Any output zạ of Algorithm I after l: iterations can be used to construct candidate solution
Egan exp( - Ei (aulave (5,))
(13)
Σn exp( Ed (ma)s (E()))
for problem (3) that approximates the I-projection Pa-- The convergence guarantces for Algorithm and, in particular, the approximation quality of (13) with respect to s detailed in Theorem 5.2 below require that problem (3) admits a Slater point 5 in the sense of the following assumption.
Assumption 5.1 (Slater point). Problem (3) admits Slater point Po that satisfies
8 minggE
Ep [b){ 2112 0.
7

---

Finding a Slater point P may be difficult in general. However, IP can be constructed systematically & is a polynomial 171, Remark 8). for example. Given IP and tolerance E > we then define
C' = D(P [ (PN))
D = 7 maxyER 11ul22,
DD:
1/2 20
a - max [E)
L 1/m + 1/2 + (maxce= (l)())
Mi(e) =
8DC2
2naC3 zd²
+1
log
10()+20))
(14)
228
Ma(e) =
1DDC2 gage
2o 202
+1) log 2012- v3)
C
V
(
(1D
a²
562 20
CC
Theorem 5.2 (Almost linear convergence rate). If Assumption 5.1 holds and e > then the candidate
solution (13) obtained after k = Imx [M (E), M= iterations of Algorithm 1 satisfies
Optimality:
D Q PP D(P
[1 2V/3E.
(15a)
Feasibility:
(E [F F.
2cB C
(15b)
where we use the definitions (14), and the function d(,, E)) denotes the Euclidean distance to the set E defined through (zz E) = mingeg
2/12-
Theorem 5.2 implies that Algorithm needs at most O log !) iterations to find an -subbsuuall and O(e) ffessbble solution for the I-projection problem (3). These results are derived via convex programming and duality by using the double smoothing techniques introduced in [22] and [71].
Computation of the DRO predictor. Equipped with Algorithm I to efficiently approximate f via Qt, the DRO predictor R' (0, PP)) defined in (4) can be approximated by R (0, @s) because the function R is continuous. We now show that the worst-case risk evaluation problem (5) admits a dual representation, which generalizes [77, Proposition 5].
Proposition 5.3 (Dual representation of R*). Ifr > 0, then the DRO predictor R satisfies
inf aER s.t.
a a O= - e exp (E>r [log(a L(0, + +
R' RO')P'') {
(16)
2 maxtc L0, z =TE(E)
for ever 8 E O and IP& E II. where (2(2) max F T denotes the support of E.
Proposition 5.3 implies that if L(B.E) {) is convex in 0 for every &. then the DRO predictor (5) coincides with the optimal value of a finiteddimensional convex program. Note that the objective function of (16) can be evaluated cheaply whenever the support function of E is easy to compute and P' has finite support (e.g., if TP' is set to output Q& of Algorithm 1). In addition, the robust constraint in (16) can be expressed in terms of explicit convex constraints L, E and v satisfy certain regularity conditions. A trivial condition is that E is finite. More general conditions described in [6].
6 Experimental results
We now assess the empirical performance of the MDI-DRO method in our two running examples.
Synthetic dataset covariate shift adaptation. The first two experiments revolve around the logistic regression problem with a distribution shift described in Example 3.2. Specifically, we consider synthetic dataset where the test data is affected by covariate shift, which constitutes special case a distribution shift. Detailed information about the data generation process is provided in Appendix 7.4. Our numerical experiments reveal that the proposed MDI-DRO method significantly outperforms the naive ERM method in the sense that its out-of-sample risk has both a lower mean as well as lower variance; method, which accounts for the distribution shift by assigning importance weights p (-))p(()) to the training samples, where p (-) and p(-) denote the densities of the test distribution IP* and training distribution P. respectively. These importance weights are assumed to be known in IWERM. In
Figures la and 1b. We also compare MDI-DRO against the IWERM
All simulations were implemented in MATLAB and run 4GHz CPU with 16Gb RAM. The Matlab code for reproducing the plots is available from https :/tp::////iii /ttpt/gtttttttteg///////gtg comm/tobsutteer//po__o00
8

---

contrast, MDI-DRO does not require any knowledge of the test distribution other than its membership II. Nevertheless, MDI-DRO displays a similar out-o--sample performance as IWERM even though it has less information about IP* and it achieves a lower variance than IWERM; see Figures 1c- dd. Figure shows how the reliability of the upper confidence bound J and the out-of-sample risk R( IP*) change with the regularization parameter r. Additional results are reported in Figure 4 in the appendix. These results confirm that small regularization parameters lead to small out-of-sample risk and that increasing improves the reliability of the upper confidence bound J
0.8
0.8
0.5
0.0
0.6
0.0
0.0
0.2
0.2
10P
10P
10
10a
10P
10a
10a
N
NV
Oatiof-aamppe mak R10% Poy
thi Chaootl-omppi R1 Pr)
Ic: Oksi-of-sample rick R105,
Oue-el--mpii mok R19, Relisbiity 2- (R)--.)
MDI-DRO
Naive ERM IWERM [69] mingge RPO)
Figure I: Results for synthetic dataset with 6. Shaded areas and lines represent ranges and mean values across 1000 independent experiments, respectively.
Real data classification under sample bias. The second experiment addresses the heart disease classification task of Example 3.2 based on real dataset consisting of N i.i.d. samples from an unknown test distribution IP* To assess the effects of a distribution shift, we construct biased training dataset { (1) D............ (#N. (N)}. N < N in which male patients older than 60 years are
substantially over-represented. Specifically, the N training samples are drawn randomly from the set of the 20% oldest male patients. Thus, the training data follows distribution IP ş IP Even though
the distribution P* is unknown, we assume know the empirical mean m + Σ ED110a (Ga, Di) of the entire dataset to within an absolute error Am > 0. The test distribution thus belongs to the
N.
II defined in (2) with = [m Am1, + Am1] and with (z, y) = (z. y). We compare the proposed MDI-DRO method for classification against the naive ERM method that ignores the sample bias. addition, we use a logistic regression model trained on the entire dataset as an (unachievable) ideal benchmark. Figure 2a shows the out-of-sample cost, Figure 2b the upper confidence bound Jī and Figure the misclassification rates of the different methods as the radius of the ambiguity set is swept. Perhaps surprisingly, for some values of the classification performance of MDI-DRO is comparable that of the logistic regression method trained on the entire dataset.
6 -1-
0.5
0.4
0.5
0.3
0.2
10-5
10a
10-5
10-3
10-1
10a
10-3
10-3
10a
(a) oamell R()%.Q)
Upper confidence Jq
Misclasification rate
MDI-DRO -.- Full information logistic regression ..... Naive logistic regression
Figure 2:
Heart disease classification example with m 6, N 20, n 303 and Am 10-3.
OPE for MDPs - inventory control. We now consider the OPE problem of Examples 3.6 and 4.6. A popular estimator for the cost Vn, of the evaluation policy is the inverse propensity score (IPS) [57]
Jap N ΣN c(S,, k.) (.)
Hoeffding's 's inequality then gives rise to the simple concentration bound
Np
V==
J Pir + 2 1 - -2N
WE 200 O, AN E E,,
(17)
htttpe:/www.kgglle.comm wwg.lw www.a/ggl.....oooo..oaoooooooaao disease-uct

---

where 6 = max,eS c(s, ()/ss. a). As is typically a large constant, the finite sample bound (11) for JN is often more informative than (17). In addition, the variance of N grows exponentially with the sample size N [15, 13, 65J. As a simple remedy, one can cap the importance weights beyond some threshold 3 > 0 and construct the modified IPS estimator as
JIPSo N
= 1 N
E c(3 a.) min { (o(
(.G......
Decreasing 3 reduces the variance of T but increases its bias. An alternative estimator for V=, is the doubly robust (DR) estimator JRR, which uses a control variate to reduce the variance of the IPS estimator. The DR estimator
first developed for contextual bandits [24] and then generalized to MDPs [32, 75]. We evaluate the performance of the proposed MDI-DRO estimator on a classical inventory control problem. A detailed problem description is relegated to Appendix 7.4. We sample both the evaluation policy Te and the behavioral policy Th from the uniform distribution on the space of stationary policies. The decision maker then has access to the evaluation policy me and to sequence of i.i.d. state action pairs {3,, @ sampled from as well as the observed empirical where C; = c($; a.). Figure 3 compares the proposed MDI-DRO estimator against the original and modified IPS estimators, the DR estimator and the ground truth expected cost of the evaluation policy. Figures 3a and 3b show that for small radii r. the MDI-DRO estimator outperforms the IPS estimators both in terms of accuracy and precision. Figure 3c displays the disappointment probabilities P. (V=, > JN) analyzed in Theorem 4.1, where JN denotes any of the tested estimators.
costs {cr //1
Acknowledgments. We thank Mengmeng Li for helpful discussions. This research was sup- ported by the Swiss National Science Foundation under the NCCR Automation, grant agreement 5INF40_180545
10
10-2
10
0.22
0.22
0.2
0.2
0.5
0.18
0.18
0.16
100
100
200
300
N
N
10
=
10
10-2
0.1
0.1
100
200
300
100
100
200
300
100
0
100
200
300
100
(a) Off-policy performance
(b) CiT--policy performance
(c) Disuppaintment probubilities
DRO J .... IPS JIPS
IPS; J
DR JRR ..- ground truth Vs,
Figure 3: Shaded areas and lines represent 90% confidence intervals and mean values across 1000 independent experiments, respectively.
References
[1] A. Antos, C. Szepesvári, and R. Munos. Learning near-optimal policies with Bellman-residual minimization based fitted policy iteration and a single sample path. In I Learning Theory, pages 574-588, Springer, 2006.
10

---

[2] B. Belousov and J. Peters. Entropic regularization of Markov decision processes. Entropy, 21
(7), 2019.
[3] Ben-Davvd, Blitzer, K. Crammer, and Pereira. Analysis of representations for domain adaptation. In Advances in Neural Information Processing Systems, 2007.
[4] A. Ben-Tal, L. El Ghaoui, and A. Nemirovski. Robust Optimization. Princeton University Press, 2009.
[5] A. Ben-Tal Tal, D. den Hertog, A. De Waegenaere, B. Melenberg, and G. Rennen. Robust solutions of optimization problems affected by uncertain probabilities. Management Science, 59(2):
341-357, 2013.
[6] A. Ben-Tal, D. den Hertog, and J.-P. Vial. Deriving robust counterparts of nonlinear uncertain inequalities. Mathematical Programming, 149(1):265-299 2015.
[7] C. Berge. Topological Spaces: Including a Treatment of Multi-valued Functions, Vector Spaces, and Convexity. Courier Corporation, 1997.
[8] D. Bertsimas and N. Kallus. From predictive prescriptive analytics. Management Science,
104)::02551044, 2020.
[9] D. Bertsimas and B. V. Parys. Bootstrap robust prescriptive analytics. arXiv preprint arXiv:1711.09974,, Accepted in Mathematical Programming. 2017.
[10] D. Bertsimas and M. Sim. The price of robustness. Operations Research, 52(1):35-53, 2004.
[11] D. Bertsimas, V. Gupta, and N. Kallus. Data-driven robust optimization. Mathematical Programming, 167(2)2255-292, 2018. 2018.
[12] C. M. Bishop. Pattern Recognition and Machine Learning. Springer, 2006.
[13] L. Bottou, J. Peters, J. Quinonero-Candela,
Charles, D. M. Chickering, E. Portugaly, D. Ray, P. Simard, and E. Snelson. Counterfactual reasoning and learning systems: The example of computational advertising. Journal Machine Learning Research, 14(65):3207-3260, 2013.
[14] X. Chen, M. Monfort, A. Liu, and B. D. Ziehart. Robust covariate shift regression. In International Conference on Artificial Intelligence and Statistics, 2016.
[15] C. Cortes, Y. Mansour, and M. Mohri. Learning bounds for importance weighting. In Advances in Neural Information Processing Systems, 2010.
[16] Cover and Thomas. Elements of Information Theory. Wiley, 2006.
[17] I. Csiszár. I-divergence geometry of probability distributions and minimization problems. Annals of Probability, 3(1):146-155: 02 1975.
[18) I. Csiszár. Sanov property, generalized T-projection and conditional limit theorem. The Annals of Probability, 12(3):768-793, 1984.
[19] I. Csiszár and J. Korner. Information Theory: Coding Theorems for Discrete Memoryless Systems. Academic Press, 1982.
[20] E. Delage and Y. Ye. Distributionally robust optimization under moment uncertainty with application to data-driven problems. Operations Research. 58(3):595-615 2010.
[21] A. Dembo and O. Zeitouni. Large Deviations Techniques and Applications. Springer, 2009.
[22] O. Devolder, F. Glineur, and Y. Nesterov. Double smoothing technique for large-scale linearly constrained convex optimization. SIAM Journal on Optimization, 22(2):702-727, 2012.
[23] J. Duchi and H. Namkoong. Learning models with uniform performance via distributionally robust optimization. arXiv preprint, arXiv.1810.0875 1810.0880,, Accepted in Annals Statisties, 2020.

---

[24] M. Dudik, D. Erhan, J. Langford. and L. Li. Doubly Robust Policy Evaluation and Optimization. Statistical Science. 29(4):85--51, 2014.
[25] M. Geist, B. Scherrer, and O. Pietquin. theory of regularized Markov decision processes. In International Conference Machine Learning. 2019.
[26] Goh and M. Sim. Distributionally robust optimization and its tractable approximations. Operations Research, 58(4):902-917, 2010.
[27] A. Golan. Information and Entropy Econometries: Review and Synthesis. Foundations and Trends in Econometrics, 2(1-2):1-145, 2008
[28] O. Hernández-LLerma and J. Lasserre. Discrete- Time Markov Control Processes: Basic Optimality Criteria. Springer, 1996.
[29] K. Hirano, G. W. Imbens, and G. Ridder. Efficient estimation of average treatment effects using the estimated propensity score. Econometrica, 1111)116111118, 2003.
[30] J. Horowitz and R. L. Karandikar, Mean rates of convergence of empirical measures in the Wasserstein metric. Journal of Computational and Applied Mathematics, 55(3):261-273, 1994.
[31] E. T. Jaynes. Information theory and statistical mechanics. Physical Review, 108:171-190, 1957.
[32] N. Jiang and L. Li. Doubly robust off-policy value evaluation for reinforcement learning. In International Conference Machine Learning, 2016.
[33] N. Kallus and M. Uehara. Double reinforcement learning for efficient off- off-policy evaluation in Markov decision processes. Journal of Machine Learning Research, 21(167):1-63, 2020.
[34] J. Kirschner, I. Bogunovic, S. Jegelka, and A. Krause. Distributionally robust Bayesian optimization. In Artificial Intelligence and Statistics, 2020.
[35] K. Kuang, P. Cui, S. Athey, R. Xiong, and B. Li. Stable prediction across unknown environments.
In International Conference on Knowledge Discovery Data Mining, 2018.
[36] D. Kuhn, P. Mohajerin Esfahani, V. A. Nguyen, and S. Shafieezadeh Abadeh. Wasserstein distributionally robust optimization: Theory and applications in machine learning. INFORMS TutORials in Operations Research, pages 130-166, 2019.
[37] S. Kullback. Information Theory and Statistics. Wiley, 1959.
[38] M. G. Lagoudakis and R. Parr. Least-squares policy iteration. Journal Machine Learning Research, 4: 1:1107-1149, 2003.
[39] M. Li, T. Sutter, and D. Kuhn. Distributionally robust optimization with Markovian data. In International Conference on Machine Learning, 2021.
[40] A. Liu and B. Ziebart. Robust classification under sample selection bias. In Advances in Neural Information Processing Systems, 2014.
[41] S. Mannor, D. Simester, P. Sun, and J. N. Tsitsiklis. Bias and variance approximation in value function estimates. Management Science, 53(2):308-32) 2007.
[42] N. Meinshausen. Causality from distributional robustness point of view. IEEE Data Science Workshop (DSW), 2018.
[43] P. Mohajerin Esfahani and D. Kuhn. Data-driven distributionally robust optimization using the Wasserstein metric: Performance guarantees and tractable reformulations. Mathematical Programming. 171(1-2):115-11 2018.
[44] H. Namkoong and Duchi. Stochastic gradient methods for distributionally robust optimiza- tion with f-divergences. In Advances in Neural Information Processing Systems, 2016.
12

---

[45] A. Nedić and A. Ozdaglar. Approximate primal solutions and rate analysis for dual subgradient methods. SIAM Journal on Optimization, 19(4):1757-1780, 2008.
[46] Y. Nesterov. Smooth minimization of non-smooth functions. Mathematical Programming, 103(1):127-152, 2005.
[47] Y. Nesterov. Introductory Lectures Convex Optimization: A Basic Course. Springer, 2014.
[48] G. Neu, A. Jonsson, and V. Gómez. A unified view of cntropy-reeullrizzd Markov decision processes, arXiv preprint arXiv:1705.07798, 2017.
[49] Pearl and E. Bareinboim. Transportability of causal and statistical relations: formal approach. In IEEE International Conference on Data Mining Workshops, 2011.
[50] J. Peters, D. Janzing, and B. Schölkopf. Elements of Causal Inference: Foundations and Learning Algorithms. MIT Press, 2017.
[51] D. Precup, R. S. Sutton, and S. P. Singh. Eligibility traces for off-policy policy evaluation. In International Conference on Machine Learning, 2000.
[52] Quionero-Candela, M. Sugiyama, A. Schwaighofer, and N. D. Lawrence. Dataset Shift in Machine Learning. MIT Press, 2009.
[53] S. Richter. Computational Complexity Certification of Gradient Methods for Real-Time Model Predictive Control. PhD thesis, ETH Zurich, 2012.
[54] R. T. Rockafellar. Convex Analysis. Princeton University Press, 1997.
[55] R. T. Rockafellar and R. J.-B. Wets. Variational Analysis. Springer, 1998.
[56] M. Rojas-Carulla, B. Schölkopf, R. Turner, and J. Peters. Invariant models for causal transfer learning. Journal of Machine Learning Research, 19(36):1 2018.
[57] R. Rosenbaum and D. B. Rubin. The central role of the propensity score in observational studies for causal effects. Biometrika, 70(1):41-55, 1983.
[58] D. Rothenhäusler, Bühhmann, N. Meinshausen, and Peters. Anchor regression: Heteroge- neous data meet causality. Journal of the Royal Statistical Society: Series B, 83(2):215-246, 2021.
[59] B. Schölkopf and A. J. Smola. Learning with Kernels: Support Vector Machines, Regular- ization, Optimization, and Beyond. MIT Press, 2001.
[60] S. Shaficezadeh Abadeh, P. Mohajerin Esfahani, and D. Kuhn. Distributionally robust logistic regression. In Advances in Neural Information Processing Systems, 2015.
[61] S. Shafieezadeh-Ahadeeh D. Kuhn, and P. Mohajerin Esfahani. Regularization via mass trans- portation. Journal of Machine Learning Research, 20(103):1-68, 2019.
[62] H. Shimodaira. Improving predictive inference under covariate shift by weighting the log- likelihood function. Journal of Statistical Planning and Inference, 90(2):227-244,, 2000.
[63] P. Smadbeck and Y. N. Kaznessis. On a theory of stability for nonlinear stochastic chemical reaction networks. The Journal of Chemical Physics, 142(18):1 2015.
[64] M. Staib and S. Jegelka. Distributionally robust optimization and generalization in kernel methods. In Advances in Neural Information Processing Systems, 2019.
[65] A. L. Strehl, J. Langford, L. Li, and M. Kakade. Learning from logged implicit exploration data. In Advances in Neural Information Processing Systems, pages 2217-2225, 2010.
[66] A. Subbaswamy, P. Schulam, and S. Saria. Preventing failures due to dataset shift: Learning predictive models that transport. International Conference on Artificial Intelligence and Statistics, 2019.
13

---

[67] M. Sugiyama and M. Kawanabe. Machine Learning in Non-Stationary Environments: Introduction to Covariate Shift Adaptation. MIT Press, 2012.
[68] M. Sugiyama and K.-R. Müller. Input-dependent estimation of generalization error under covariate shift. Statistics & Decisions, 23:249-279, 2005.
[69] M. Sugiyama, M. Krauledat, and K.-R. Müller. Covariate shift adaptation by importance weighted cross validation. Journal of Machine Learning Research, 8(35):985-1055, 2007.
[70] R. K. Sundaram. First Course in Optimization Theory. Cambridge University Press, 1996.
[71] T. Sutter, D. Sutter, P. Mohajerin Esfahani, and J. Lygeros. Generalized maximum entropy estimation. Journal of Machine Learning Research, 20(138):1 2019.
[72] Sutter, B. G. Parys, and D. Kuhn. general framework for optimal data-driven optimization. arXiv preprint, 2010.06606, 2020.
[73] R. S. Sutton and A. G. Barto. Reinforcement Learning: An Introduction. MIT Press, 2018.
[74] A. Swaminathan and T. Joachims. The self-normalized estimator for counterfactual learning. In Advances Neural Information Processing Systems, 2015.
[75] Z. Tang, Y. Feng, L. Li, D. Zhou, and Q. Liu. Doubly robust bias reduction in infinite horizon off- off-policy estimation. International Conference on Learning Representations, 2020.
[76] Thomas and E. Brunskill. Data-efficient off- off-policy policy evaluation for reinforcement learning. In International Conference Machine Learning, 2016.
[77] B. Van Parys, P. Mohajerin Esfahani, and D. Kuhn. From data to decisions: Distributionally robust optimization is optimal. Management Science, 67(6):3377-3402, 2021.
[78] V. Vapnik. Statistical Learning Theory. Wiley, 1998.
[79] C. Villani. Optimal Transport: Old and New. Springer, 2008.
[80] W. Wiesemann, D. Kuhn, and M. Sim. Distributionally robust convex optimization. Operations Research, 62(6):1358-133) 1376, 2014.
[81] M. Yamada, Suzuki, T. Kanamori, H. Hachiya, and M. Sugiyama. Relative density-ratio estimation for robust distribution comparison. In Advances in Neural Information Processing Systems, 2011.
[82] B. Zadrozny. Learning and evaluating classifiers under sample selection bias. In International Conference Machine Learning. 2004.
[83] Zhang. A. Menon, A. Veit, S. Bhojanapalli. S. Kumar, and S. Sra. Coping with label shift via distributionally robust optimisation. arXiy preprint, arXiv.2010.12230, 2020.
14


Reviews:
[{"review_id": "sWu8VqD16w_", "reviewer": "Reviewer_fqJW", "summary": "In this paper, they aim at test and training distribution shift problem where partial knowledge of shifted test distribution is known. With the principle of minimum discriminating information, they introduce a new modeling framework catching prior structural information, and a specific MDI-DRO with theoretical generalization bound, satisfying the statistical guarantee of out-of-sample.  For computational tractability, they leverage convex duality and accelerated first-order methods to efficiently solve the DRO program. Experiments on two distinct problem classes prove the availability of the proposed approach.\n\n========\nAfter reading the authors' response and other reviews, I would like to raise my score to 5, but still think the paper in its current form is not self-contained due to the lack of ablation study and important baselines.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "1. This work assumes and takes advantage of prior structure knowledge of tests in their modeling framework. So in their experiments, approaches that do not employ such information should be compared to verify the validity of leveraging partial test information. For example, there are a series of works facing an arbitrary and unknown distribution shift based on training data (Stable Prediction across Unknown Environments. KDD, 2018). \n2. The baselines and experimental settings are inadequate. Other DRO algorithms and other types of methods that use or do not use the test information should be discussed and compared, for example, self-normalized IPS (reweighing approach) and double robust methods for inventory control example. And the OOD generalization problem has developed to cover complicated data structures. More real data should be applied. \n3. The presentation of theory and method is confusing. Some propositions and examples can be moved to the appendix and they can highlight the theorem and related conclusion in writing.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I wonder if their approach can be applied to large-scale complex data structures, for example, image data that has been fully studied for the OOD problems.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8 hours"}, "extra_text": {}}, {"review_id": "qdFRah6InpQ", "reviewer": "Reviewer_h1zT", "summary": "The authors propose a new MDI-DRO approach that is the combination of an I-projection (to adjust for distribution shift) and DRO over both a KL-divergence constraint and a moment constraint. The major contribution is the generalization / efficiency theory results, and a convex optimization procedure for solving the DRO problem reasonably efficiently.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The introduction was mostly clear, but the discussion of P^f around line 97 stuck out, because there's is an abrupt (and very important) statement 'we identify P^f with an I-projection of P onto Pi' . But this is actually a really tricky and somewhat subtle point. You can either view this as an assumption on P^f, where you get to pick an arbitrary phi, or a statement that phi is fixed (as in prop 3.5) and P^f is arbitrary. In either case, this seems like in many ways the key assumption and structure, so I'd be alot more careful about the writing here. \n\nAs a related work note, I believe 'Robust Classification Under Sample Selection Bias' and the line of work by Brian Ziebart may be relevant. There's some similarity to this work in that they consider minimax games with moment constraints on the distribution. Their setup is similar to the DRO problem in eq (5), but they don't have a I-projection step as in eq (4). I think it would add to the paper to carefully discuss the differences between these approaches and MDI-DRO.\n\nThe writing in section 5 can also be made much clearer. I wasn't sure exactly what 'z' was until Thm 5.2, where it became clear that it was going to be used to construct \\mu_{k,\\eta} which was the solution. I'd suggest a slight rewrite that brings the high level plan before the details in the 'computation of i projection' section. \n\nI also think the slater point discussion could be improved a bit - my understanding is that this is a fairly mild assumption, equivalent to the existence of an interior point, but the writing doesnt make it clear if this is something that's a regularity condition that can safely be treated as a detail, or something that has substantial implications for the applicability of this optimization approach. \n\nExperiment wise, the second, 'real world data' experiment has several points that could use further discussion. The left panel shows out of sample cost that increases substantially as r goes to zero. This seems fairly counterintuitive, esp given the discussion in the earlier experiment that there is a 'known tradeoff stating that small regularization parameter r leads to small out of sample risk'. It's also pretty surprising to me that the model doesn't degenerate as r grows large. at r=10.0, I'm guessing that the KL constraint is sufficiently loose that the KL constraint does very little, and almost all of the gains come from the moment constraint. Is this true?\n\nAs a framing thing, I think it may also be helpful to mention that the goal of the paper is in many ways the upper bound on the risk, rather than the out of distribution risk itself. This is because it seems likely that if your goal is only out of distribution performance, then you might as well take r=0, which would just be the I-projection.\n\nMinor notes — I think the arguments in line 127 about the conditional limit theorem don't necessarily justify min. discriminating information (which is an argument made in line 129). My understanding was that the this is a type of consistency result (as n→infty, I-projections converge to the population) and I fail to see how this alone provides an intuitive justification for modeling distribution shifts via I-projections. \n\nAs a style note- the large red boxes around the legends make it harder to read the figures and the legend.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No issues expected.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "kx4LrAHk5Uw", "reviewer": "Reviewer_chLA", "summary": "This paper proposes a distributionally robust optimization (DRO) framework for learning models that can generalize well under distribution shifts, when partial knowledge about the nature of the shift is available. As opposed to classical domain adaptation methods, the proposed method does not require data from the target distribution. For an uncertainty set of distributions defined to satisfy a set of moment conditions (the partial knowledge about the shift), the authors propose to train a model to minimize risk with respect to the distribution in the uncertainty set which minimizes the relative entropy from the training distribution. Using the empirical distribution of the training data as the source distribution, the authors show that the solution to this minimax problem upper bounds the optimal risk and provide finite sample guarantees. The authors then develop a two step learning procedure: First, they estimate the I-projection (using a fast gradient-like method, Algorithm 1). Then, they can efficiently compute the model parameters. They also consider simple extensions to the case of off policy evaluation in reinforcement learning. Synthetic and real data experiments demonstrate the effectiveness of the proposed method given a good choice of the relative entropy radius hyperparameter.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The distribution shift problem addressed in this paper is very relevant in the community, and a distinct advantage of DRO methods (like the proposed method) is that they do not require samples from the test distribution. The structure for expressing knowledge about the distribution shift seems useful and interpretable. I thought the paper was well-written and I really appreciated the examples---they helped me understand how the proposed framework would work on practical examples. The experiments were presented in a way in which it was easy to draw conclusions about how the method performs as sample size and hyperparameters vary.\n\nI had a couple questions/concerns that I hope the authors can address:\n- Can the authors provide any guidance on how to choose the $r$ hyperparameter (defining the radius of the relative entropy ball)? From a practical perspective, this seems like one of the primary challenges that would make the method hard to use. As the experiments demonstrate, the proposed method can achieve very good performance, but this is highly sensitive to the choice of $r$.\n- The authors claim that, e.g., the principle of maximum entropy has not been used to model general distribution shifts. I would like to point the authors to Chen et al. (2018), which considers learning a regression model under covariate shift with moment constraints. Their setting is a little different from the current paper (the current paper considers a more general problem), but I think it deserves to be mentioned.\n\nChen, X., Monfort, M., Liu, A., & Ziebart, B. D. (2016, May). Robust covariate shift regression. In Artificial Intelligence and Statistics (pp. 1270-1279). PMLR.\n\nAs a suggestion, I think that the discussion of related work could be broadened to include work at the intersection of distribution shift, causality, and distributional robustness. Tools from causality have been used to represent structural knowledge about distribution shifts, and recent works have established connections between causal predictors and distributional robustness under shifts arising from interventions.\n\nCausal inference & distributional robustness:\n- Rothenhäusler, D., Meinshausen, N., Bühlmann, P., & Peters, J. (2021). Anchor regression: Heterogeneous data meet causality. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 83(2), 215-246.\n- Meinshausen, N. (2018, June). Causality from a distributional robustness point of view. In 2018 IEEE Data Science Workshop (DSW) (pp. 6-10). IEEE.\n- Rojas-Carulla, M., Schölkopf, B., Turner, R., & Peters, J. (2018). Invariant models for causal transfer learning. The Journal of Machine Learning Research, 19(1), 1309-1342.\n- Subbaswamy, A., Schulam, P., & Saria, S. (2019, April). Preventing failures due to dataset shift: Learning predictive models that transport. In The 22nd International Conference on Artificial Intelligence and Statistics (pp. 3118-3127). PMLR.\n\nUsing causal graphs to represent knowledge about shifts.\n- Subbaswamy, A., Schulam, P., & Saria, S. (2019, April). Preventing failures due to dataset shift: Learning predictive models that transport. In The 22nd International Conference on Artificial Intelligence and Statistics (pp. 3118-3127). PMLR.\n- Pearl, J., & Bareinboim, E. (2011, August). Transportability of causal and statistical relations: A formal approach. In Twenty-fifth AAAI conference on artificial intelligence.\n\nAs a very minor note: On line 16, reference [47] actually coins the term \"dataset shift\" for the \"distribution shift\" problem the authors refer to.\n\n### UPDATES:\nThanks to the authors for their response. I think the practical discussion of the radius (i.e., its interpretation and general guidance on how to select it) should be included in the main paper. Even better would be to include or modify an experiment to demonstrate the (subjective) process by which a user would select a radius. Contingent on the inclusion of this practical discussion (as well as the expansion of the related work), I am raising my score 1 point.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, though I wonder if there might be any implications for performance on subgroups created by the choice of shift constraints.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "TUgN_dO-rq4", "reviewer": "Reviewer_qvWC", "summary": "The paper proposes to solve a distribution shift problem by minimizing risk over an uncertainty ball around the empirical training distribution, subject to a shift with a known structure. This structure is encoded as knowing the expectation of some function of the random observation falls within a compact convex set E. The paper uses the principle of minimum discriminating to justify encoding *only* these structural requirements, being the least prejudiced approximation to the original distribution given only the structural knowledge.\n\nThe authors gives statistical guarantees and a tractable algorithm for finding the I-projection (the closest distribution in relative entropy which satisfies the structural requirement) of the empirical training distribution and then finding an approximate DRO solution around this projection.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "I think this is a nice paper with a well-defined focus and useful results. My background is not in this area so I did not check the math in detail but I am in favor of acceptance. A couple notes:\n\n* The paper is quite dense, particularly the examples. At a minimum, it would be helpful to indicate earlier on which of the examples will be persistent, so that the reader can focus on understanding these and perhaps not so much on the ones which will not appear again. This would also help justify the lengthy descriptions and encourage the reader not to skip them. I'd recommend even dropping all but the OPE example, or at least drastically shortening them.\n* I'm struggling to understand the equation between lines 133 and 134. We're assuming N samples (an empirical expectation) but then also evaluating the true expectation? I've considered interpreting the LHS as $\\mathbb{E}_{\\mathbb{P}}[L(\\theta, \\xi) \\mid \\psi(\\xi) \\in E]$ but I think this is not correct. What is this meant to say?\n* Line 137, $\\ll$ is typically \"absolutely continuous w.r.t.\" but I don't think it's defined anywhere. I think this term is probably worth explicitly defining.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Sure", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4.5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Authors propose a DRO formulation that incorporates prior information in the form of moments of functionals, using minimum discriminating information. I agree with the reviewers that the new formulation is a meaningful contribution.

One remaining concern is that prior information studied in the experiments is somewhat contrived. The narrative of the paper will be substantially stronger if authors can demonstrate their method on a realistic example where the prior information presents naturally.
Decision: Accept (Poster)