Robust Generalization despite Distribution Shift via Minimum Discriminating Information
Year: 2021

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.

heading: 1 Introduction
text: Developing machine 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, a standard assumption in most machine learning methods is that test and training distribution are the same [78, 59, 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 shift. Consider building a model for diagnosing a 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 to 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-policy evaluation (OPE) problems. Here, one is concerned with the task of estimating the resulting cost of an evaluation policy for a sequential decision making problem based on historical data obtained from a different policy known as behavioral policy [73]. This problem is of critical importance in various applications of reinforcement learning—particularly, when it is impossible or unethical to evaluate the resulting cost of an evaluation policy by running it on the underlying system. Solving a learning problem facing an arbitrary and unknown distribution shift based on 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
35th Conference on Neural Information Processing Systems (NeurIPS 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-known 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 versatility 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.

heading: 2 Related work
text: For supervised learning problems, there is a rich literature in the context of covariate shift adaptation [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 is 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-based ambiguity sets. Distribution shifts play a 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 a 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 a 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 regularize 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 reformulations hold for a variety of ambiguity sets such as: regions defined by moments [20, 26, 80, 11],
φ-divergences [5, 44, 39], Wasserstein ambiguity sets [43, 36], or maximum mean discrepancy ambiguity 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 a 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.

heading: 3 Problem statement and motivating examples
text: We study learning problems of the form
min θ∈Θ
R(θ,P?), (1)
where R(θ,P?) = EP? [L(θ, ξ)] denotes the risk of an uncertain real-valued loss function L(θ, ξ) that depends on a parameter θ ∈ Θ ⊂ Rn to be estimated as well as a random vector ξ ∈ Ξ ⊂ Rm governed by the probability distribution P?. In order to avoid technicalities, we assume from now on that Θ and Ξ are compact and L is continuous. In statistical learning, it is usually assumed that P? is unknown but that we have access to independent samples from P?. This paper departs from this standard scenario by assuming that there is 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 P 6= P? and that P? is only known to belong to the distribution family
Π = {Q ∈ P(Ξ) : EQ [ψ(ξ)] ∈ E} (2)
encoded by a measurable feature map ψ : Ξ→ Rd and a compact convex set E ⊂ Rd. In view of the principle of minimum discriminating information, we identify P? with the I-projection of P onto Π. Definition 3.1 (Information projection). The I-projection of P ∈ P(Ξ) onto Π is defined as
Pf = f(P) = arg min Q∈Π D(Q‖P), (3)
where D(Q‖P) denotes the relative entropy of Q with respect to P.
One can show that the I-projection exists whenever Π 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 ψ is bounded. Note that f(P) = P if P ∈ Π. In the remainder, we assume that P 6∈ Π and that P is only indirectly observable through independent training samples ξ̂1, . . . , ξ̂N drawn from P. Example 3.2 (Logistic regression). Assume that ξ = (x, y), where x ∈ Rm−1 is a feature vector of patient data (e.g., a patient’s age, sex, chest pain type, blood pressure, etc.), and y ∈ {−1, 1} a label indicating the occurrence of a heart disease. Logistic regression models the conditional distribution of y given x by a logistic function Prob(y|x) = [1 + exp(−y · θ>x)]−1 parametrized by θ ∈ Rm−1. The maximum likelihood estimator for θ is found by minimizing the empirical average of the logistic loss function L(θ, ξ) = log(1 + exp(−y · θ>x)) on the training samples. If the samples pertain to a patient cohort, where elderly males are overrepresented with respect to the general population, then they are drawn from a training distribution P that differs from the test distribution P?. Even if sampling from P? is impossible, we may know that the expected age of a random individual in the population falls between 40 and 45 years. This information can be modeled as EP? [ψ(ξ)] ∈ E, where E = [`, u], ` = 40, u = 45 and ψ(ξ) 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 Pf of the data-generating distribution P onto the set Π defined in (2). Example 3.3 (Production planning). Assume that θ ∈ R and ξ ∈ R denote the production quantity and the demand of a perishable good, respectively, and that the loss function L(θ, ξ) represents the sum of the production cost and a 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 a recession might signal that demand will decline by at least η%. The future demand distribution P? thus differs from P and belongs to a set Π of the form (2) defined through ψ(ξ) = ξ and E = [0, (1− η)µ], where µ denotes the historical average demand. By the principle of minimum discriminating information it then makes again sense to minimize the expected loss under the I-projection Pf of P onto Π.
Loosely speaking, the principle of minimum discriminating information identifies the I-projection Pf of P as the least prejudiced and thus most natural model for P? in view of the information that P? ∈ Π. 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 P ◦ ψ−1, the I-projection Pf = f(P) exists and the moment-generating function EPf [etL(θ,ξ)] is finite for all t in a neighborhood of 0, then we have
lim N→∞
EPN [L(θ, ξ1)| 1N ∑N i=1 ψ(ξi) ∈ E] = EPf [L(θ, ξ)] ∀θ ∈ Θ.
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 Π. Proposition 3.5 (Every distribution is an I-projection). If P,Q ∈ P(Ξ) are such that Q is absolutely continuous with respect to P and if Π is a set of the form (2) defined through ψ(ξ) = log dQdP (ξ) and E = {D(Q‖P)}, then Q = f(P).
The modelling of arbitrary distribution shifts via the I-projection according to Proposition 3.5 has an interesting application in the off-policy evaluation problem for Markov decision processes (MDPs). Example 3.6 (Off-policy evaluation). Consider an MDP (S,A, Q, c, s0) with finite state and action spaces S andA, respectively, transition kernel Q : S ×A → R, cost-per-stage function c : S ×A → R and initial state s0. A stationary Markov policy π is a stochastic kernel that maps states to probability distributions over A. We use π(a|s) 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π = limT→∞ 1 T ∑T−1 t=0 Eπs0 [c(st, at)].
Each policy induces an occupation measure µπ on S×A defined through the state-action frequencies
µπ(x, a) = limT→∞ 1 T ∑T−1 t=0 Pπs0 [(st, at) = (s, a)] ∀s ∈ S, a ∈ A,
see [28, Chapter 6]. One can additionally show that µπ belongs to the polytope M = { µ ∈ ∆S×A : ∑ a′∈A µ(s ′, a′)− ∑ s∈S ∑ a∈AQ(s ′|s, a)µ(s, a) = 0 ∀s′ ∈ S } ,
where ∆S×A represents the simplex of all probability mass functions over S ×A. Conversely, each occupation measure µ ∈M induces a policy πµ defined through πµ(a|s) = µ(s, a)/ ∑ a′∈A µ(s, a
′) for all s ∈ S and a ∈ A. Assuming that all parameters of the MDP except for the cost c are known, the off-policy evaluation problem asks for an estimate of the long-run average cost Vπe of an evaluation policy πe based on a trajectory of states, actions and costs generated by a behavioral policy πb. This task can be interpreted as a degenerate learning problem without a parameter θ to optimize if we define ξ = c(s, a) and set L(θ, ξ) = ξ. Here, a distribution shift emerges because we must evaluate the expectation of ξ under Q = µe ◦ c−1 given training samples from P = µb ◦ c−1, where µb and µe represent the occupation measures corresponding to πb and πe, respectively. Note that P and Q are unknown because c is unknown. Moreover, as the policy πe generates different stateaction trajectories than πb, the costs generated under πe cannot be inferred from the costs generated under πb even though πb and πe are known. Note also that Q coincides with the I-projection Pf of P onto the set Π defined in Proposition 3.5. The corresponding feature map ψ as well as the set E can be computed without knowledge of c provided that c is invertible. Indeed, in this case we have
ψ(ξi) = log dµe◦c−1 dµb◦c−1 (ξi) = log µe(si,ai) µb(si,ai) and E = { D(µe ◦ c−1‖µb ◦ c−1) } for any si ∈ S , ai ∈ A and ξi = c(si, ai). Note that as S and A are finite, c is generically invertible, that is, c can always be rendered invertible by an arbitrarily small perturbation. In summary, we may conclude that the off-policy evaluation problem reduces to an instance of (1).
Given N training samples ξ̂1, . . . , ξ̂N , we henceforth use P̂N = 1N ∑N i=1 δξ̂i and P̂ f N to denote the empirical distribution on and its I-projection onto Π, respectively. As the true data-generating distribution P and its I-projection Pf are unknown, it makes sense to replace them by their empirical counterparts. However, the resulting empirical risk minimization problem is susceptible to 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
J?N = min θ∈Θ R?(θ, P̂fN ), (4)
which minimizes the worst-case risk over all distributions close to P̂fN . Here, R? is defined through R?(θ,P′) = supQ∈Π {R(θ,Q) : D(P′‖Q) ≤ r} (5)
and thus evaluates the worst-case risk of a given parameter θ ∈ Θ in view of all distributions Q that have a relative entropy distance of at most r from a given nominal distribution P′ ∈ Π. In the remainder we use J?N and θ ? N 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 of the DRO problem (4) provides an
upper confidence bound on the risk of its optimal solution θ?N . Specifically, we prove that PN ( R(θ?N ,Pf ) > J?N ) ≤ e−rN+o(N), (6)
where Pf = f(P) is the I-projection of P. If Ξ is finite, then (6) can be strengthened to a finite sample bound that holds for every N if the right hand side is replaced with e−rN (N + 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 P̂fN can be computed via a regularized fast gradient method whenever one can efficiently project onto E. Given P̂fN , we then show that θ?N can be found by solving a tractable convex program whenever Θ is a convex and conic representable set, while L(θ, ξ) is a convex and conic representable function of θ for any fixed ξ.

heading: 4 Statistical guarantees
text: Throughout this section, we equip P(Ξ) with the topology of weak convergence. As L(θ, ξ) is continuous on Θ×Ξ and Ξ is compact, this implies that the risk R(θ,Q) is continuous on Θ×P(Ξ). The DRO problem (4) is constructed from the I-projection of the empirical distribution, which, in turn, is constructed from the given training samples. Thus, θ?N constitutes a data-driven decision. Other data-driven decisions can be obtained by solving surrogate optimization problems of the form
ĴN = min θ∈Θ
R̂(θ, P̂fN ), (7)
where R̂ : Θ×Π→ R is a continuous function that uses the empirical I-projection P̂fN to predict the true risk R(θ,Pf ) of θ under the true I-projection Pf . From now on we thus refer to R̂ as a predictor, and we use ĴN and θ̂N to denote the minimum and a minimizer of problem (7), respectively. We call a predictor R̂ admissible if ĴN provides an upper confidence bound on the risk of θ̂N in the sense that
lim sup N→∞
1
N logPN
( R(θ̂N ,Pf ) > ĴN ) ≤ −r ∀P ∈ P(Ξ) (8)
for some prescribed r > 0. The inequality (8) requires the true risk of the minimizer θ̂N to exceed the optimal value ĴN of the surrogate optimization problem (7) with a 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 (Out-of-sample guarantee). If r > 0, 0 ∈ int(E) and for every z ∈ Rd there exists an uncertainty realization ξ ∈ Ξ such that z>ψ(ξ) > 0, then the DRO predictor R? defined in (5) is continuous on Θ×Π. In addition, R̂ = R?+ε is an admissible data-driven predictor for every ε > 0.
Theorem 4.1 implies that, for any fixed ε > 0, the DRO predictor R? provides an upper confidence bound J?N + ε on the true risk R(θ ? N ,Pf ) of the data-driven decision θ?N that becomes increasingly reliable as N grows. Of course, the reliability of any upper confidence bound trivially improves if it is 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.
Theorem 4.2 (Statistical efficiency). Assume that all conditions of Theorem 4.1 hold. If J?N and R? are defined as in (4) and (5), while ĴN is defined as in (7) for any admissible data-driven predictor R̂, then we have limN→∞ J?N ≤ limN→∞ ĴN P∞-almost surely irrespective of P ∈ P(Ξ).
One readily verifies that the limits in Theorem 4.2 exist. Indeed, if R̂ is an arbitrary data-driven predictor, then the optimal value ĴN of the corresponding surrogate optimization problem converges P-almost surely to minθ∈Θ R̂(θ,Pf ) as N tends infinity provided that the training samples are drawn independently from P. This is a direct consequence of the following three observations. First, the optimal value function minθ∈Θ R̂(θ,Pf ) is continuous in Pf ∈ Π thanks to Berge’s maximum theorem [7, pp. 115–116], which applies because R̂ is continuous and Θ is compact. Second, the I-projection Pf = f(P) is continuous in P ∈ P(Ξ) thanks to [70, Theorem 9.17], which applies because the relative entropy is strictly convex in its first argument [21, Lemma 6.2.12]. Third, the strong law of large numbers implies that the empirical distribution P̂N converges weakly to the data-generating distribution P as the sample size N grows. Therefore, we have
lim N→∞ ĴN = lim N→∞ min θ∈Θ
R̂ ( θ, f(P̂N ) ) = min θ∈Θ R̂ ( θ, f ( lim N→∞ P̂N )) = min θ∈Θ R̂(θ,Pf ) P-a.s.
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 Ξ is finite, the asymptotic outof-sample guarantee (8) can be strengthened to a finite sample guarantee that holds for every N ∈ N. Corollary 4.3 (Finite sample guarantee). If R? is defined as in (5), then
1
N logPN
( R?(θ?N ,Pf ) > J?N ) ≤ log(N + 1)
N |Ξ| − r ∀N ∈ N. (9)
We now temporarily use R?r to denote the DRO predictor defined in (5), which makes its dependence on r explicit. Note that if r > 0 is kept constant, then R?r(θ, P̂ f N ) is neither an unbiased nor a consistent estimator for R(θ,Pf ). Consistency can be enforced, however, by shrinking r as N grows. Theorem 4.4 (Asymptotic consistency). Let the assumptions of Proposition 3.4 hold and {rN}N∈N be a sequence of non-negative reals with limN→∞ rN = 0. If the loss function L(θ, ξ) is Lipschitz continuous in ξ with Lipschitz constant Λ > 0 uniformly across all θ ∈ Θ, then we have
lim N→∞
R?rN (θ, P̂ f N ) = R(θ,P f ) P∞-a.s. ∀θ ∈ Θ, (10a)
lim N→∞ min θ∈Θ
R?rN (θ, P̂ f N ) = min θ∈Θ R(θ,Pf ) P∞-a.s. (10b)
Remark 4.5 (Choice of radius). Theorem 4.2 shows that the ambiguity set used in our paper displays a strong Pareto-optimality property, i.e., it leads to the least conservative predictor, uniformly across all estimator realizations, for which the out-of-sample 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 r 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-policy 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 Vπe = Ef(P)[ξ] based on the available behavioral policy and its empirical cost. As described in Example 3.6, we choose Π such that µe ◦ c−1 = f(P), where P = µb ◦ c−1 ∈ P(Ξ). Given the behavioral data (ŝi, âi) ∼ µb for i = 1, . . . N , we then construct the empirical distribution P̂N = 1N ∑N i=1 δc(ŝi,âi). Our statistical results require the samples (ŝi, âi) to be i.i.d., which can be enforced approximately by discarding a sufficient number of intermediate samples, for example. We emphasize, however, that the proposed large deviation framework readily generalizes to situations in which there is a single trajectory of correlated data [39, 72]. Details are omitted for brevity. The value function Vπe
under the evaluation policy can now be approximated by J?N = R ?(P̂fN ), where R? denotes the DRO predictor (5). As Ξ is finite, Corollary 4.3 provides the generalization bound
PN (Vπe ≤ J?N ) ≥ 1− (N + 1)|S|+|A|e−rN ∀P ∈ P(Ξ), (11)
which holds for all N ∈ N.

heading: 5 Efficient computation
text: We now outline an efficient procedure to solve the DRO problem (4). This procedure consists of two steps. First, we propose an algorithm to compute the I-projection P̂fN = f(P̂N ) of the empirical distribution P̂N corresponding to the training samples ξ̂1, . . . , ξ̂N . Given P̂fN , we then show how to compute the worst-case risk R?(θ, P̂fN ) and a corresponding optimizer θ?N over the search space Θ.
Computation of the I-projection. Computing the I-projection of the empirical distribution P̂N is a non-trivial task because it requires solving the infinite-dimensional optimization problem (3). Generally, one would expect that the difficulty of evaluating f(P̂N ) depends on the structure of the set Π, which is encoded by ψ and E; see (2). Thanks to the discrete nature of the empirical distribution P̂N , however, we can leverage recent advances in convex optimization together with an algorithm proposed in [71] to show that f(P̂N ) can be evaluated efficiently for a large class of sets Π. In the following we let η = (η1, η2) be a smoothing parameter with η1, η2 > 0, and we let Lη > 0 be a learning rate that may depend on η. In addition, we denote by z ∈ Rd the vector of dual variables of the constraint EQ[ψ(ξ)] ∈ E in problem (3), and we define Gη : Rd → Rd with
Gη(z) = −πE(η−11 z)− η2z + ∑N i=1 ψ(ξ̂i) exp(− ∑d j=1 zj ψj(ξ̂i))∑N
i=1 exp(− ∑d j=1 zj ψj(ξ̂i))
(12)
as a smoothed gradient of the dual objective, where πE denotes the projection operator onto E defined through πE (z) = arg minx∈E ‖x − z‖22. The corresponding smoothed dual of the Iprojection problem (3) can then be solved with the fast gradient method described in Algorithm 1. The complexity of evaluating Gη , and thus the per-iteration complexity of Algorithm 1, is determined by the projection operator onto E. For simple sets (e.g., 2-norm balls or hybercubes) the solution is 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 a comprehensive survey.
Algorithm 1: Fast gradient method for smooth & strongly convex optimization [47]
Choose w0 = z0 ∈ Rd and η ∈ R2++
For k ∈ N Step 1: Set zk+1 = wk + 1LηGη(wk)
Step 2: Compute wk+1 = zk+1 + √ Lη− √ η2√
Lη+ √ η2
(zk+1 − zk)
Any output zk of Algorithm 1 after k iterations can be used to construct a candidate solution
Q̂k = ∑N j=1 exp(− ∑d i=1(zk)iψi (ξ̂j))δξ̂j∑N
j=1 exp(− ∑d i=1(zk)i ψi(ξ̂j))
(13)
for problem (3) that approximates the I-projection P̂fN . The convergence guarantees for Algorithm 1 and, in particular, the approximation quality of (13) with respect to P̂fN detailed in Theorem 5.2 below require that problem (3) admits a Slater point P◦ in the sense of the following assumption. Assumption 5.1 (Slater point). Problem (3) admits a Slater point P◦ ∈ Π that satisfies
δ = miny 6∈E ‖EP◦ [ψ(ξ)]− y‖2 > 0.
Finding a Slater point P◦ may be difficult in general. However, P◦ can be constructed systematically if ψ is a polynomial [71, Remark 8], for example. Given P◦ and a tolerance ε > 0, we then define
C = D(P◦‖P̂N ), D = 12 maxy∈E ‖y‖2, η1 = ε 4D , η2 = εδ2 2C2 , α = maxξ∈Ξ ‖ψ(ξ)‖∞, Lη = 1/η1 + η2 + (maxξ∈Ξ ‖ψ(ξ)‖∞)2,
M1(ε) = 2
(√ 8DC2
ε2δ2 + 2α2C2 εδ2 + 1
) log (
10(ε+2C) ε
) , (14)
M2(ε) = 2
(√ 8DC2
ε2δ2 + 2α2C2 εδ2 + 1
) log ( C
εδ(2− √ 3) √ 4 ( 4D ε + α 2 + εδ 2 2C2 )( C + ε2 )) .
Theorem 5.2 (Almost linear convergence rate). If Assumption 5.1 holds and ε > 0, then the candidate solution (13) obtained after k = dmax{M1(ε),M2(ε)}e iterations of Algorithm 1 satisfies
Optimality: |D(Q̂k‖P̂N )− D(P̂fN‖P̂N )| ≤ 2(1 + 2 √ 3)ε, (15a)
Feasibility: d ( EQ̂k [ψ(ξ)], E ) ≤ 2εδC , (15b)
where we use the definitions (14), and the function d(·, E) denotes the Euclidean distance to the set E defined through d(x,E) = miny∈E ‖x− y‖2.
Theorem 5.2 implies that Algorithm 1 needs at most O( 1ε log 1 ε ) iterations to find an O(ε)-suboptimal and O(ε)-feasible 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 1 to efficiently approximate P̂fN via Q̂k, the DRO predictor R?(θ, P̂fN ) defined in (4) can be approximated by R?(θ, Q̂k) 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?). If r > 0, then the DRO predictor R? satisfies
R?(θ,P′) =
{ inf
α∈R,z∈Rd α+ σE(z)− e−r exp
( EP′ [log(α− L(θ, ξ) + z>ψ(ξ))] ) s.t. α ≥ maxξ∈Ξ L(θ, ξ)− z>ψ(ξ)
(16)
for ever θ ∈ Θ and P′ ∈ Π, where σE(z) = maxx∈E x>z denotes the support function of E.
Proposition 5.3 implies that if L(θ, ξ) is convex in θ for every ξ, then the DRO predictor (5) coincides with the optimal value of a finite-dimensional 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 P′ is set to an output Q̂k of Algorithm 1). In addition, the robust constraint in (16) can be expressed in terms of explicit convex constraints if L, Ξ and ψ satisfy certain regularity conditions. A trivial condition is that Ξ is finite. More general conditions are described in [6].

heading: 6 Experimental results
text: We now assess the empirical performance of the MDI-DRO method in our two running examples.1
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 a synthetic dataset where the test data is affected by a covariate shift, which constitutes a special case of 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 a lower variance; see Figures 1a and 1b. We also compare MDI-DRO against the IWERM 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 P? and training distribution P, respectively. These importance weights are assumed to be known in IWERM. In
1All simulations were implemented in MATLAB and run on a 4GHz CPU with 16Gb RAM. The Matlab code for reproducing the plots is available from https://github.com/tobsutter/PMDI_DRO.
contrast, MDI-DRO does not require any knowledge of the test distribution other than its membership in Π. Nevertheless, MDI-DRO displays a similar out-of-sample performance as IWERM even though it has less information about P?, and it achieves a lower variance than IWERM; see Figures 1c-1d. Figure 1e shows how the reliability of the upper confidence bound J?N and the out-of-sample risk R(θ?N ,P?) change with the regularization parameter r. Additional results are reported in Figure 4 in the appendix. These results confirm that small regularization parameters r lead to small out-of-sample risk and that increasing r improves the reliability of the upper confidence bound J?N .
Real data — classification under sample bias. The second experiment addresses the heart disease classification task of Example 3.2 based on a real dataset2 consisting of N? i.i.d. samples from an unknown test distribution P?. To assess the effects of a distribution shift, we construct a biased training dataset {(x̂1, ŷ1), . . . , (x̂N , ŷ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 a distribution P 6= P?. Even though the test distribution P? is unknown, we assume to know the empirical mean m = 1N? ∑N? i=1(x̂i, ŷi) of the entire dataset to within an absolute error ∆m > 0. The test distribution thus belongs to the set Π defined in (2) with E = [m−∆m1,m+ ∆m1] and with ψ(x, y) = (x, y). We compare the proposed MDI-DRO method for classification against the naive ERM method that ignores the sample bias. In 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?N and Figure 2c the misclassification rates of the different methods as the radius r of the ambiguity set is swept. Perhaps surprisingly, for some values of r the classification performance of MDI-DRO is comparable to that of the logistic regression method trained on the entire dataset.
OPE for MDPs — inventory control. We now consider the OPE problem of Examples 3.6 and 4.6. A popular estimator for the cost Vπe of the evaluation policy is the inverse propensity score (IPS) [57]
Ĵ IPSN = 1 N ∑N i=1 c(ŝi, âi) µe(ŝi,âi) µb(ŝi,âi) .
Hoeffding’s inequality then gives rise to the simple concentration bound PN ( Vπe ≤ Ĵ IPSN + ε ) ≥ 1− e −2Nε2 b2 ∀ε > 0, ∀N ∈ N, (17)
2https://www.kaggle.com/ronitf/heart-disease-uci
where b = maxs∈S,a∈A c(s, a)µe(s, a)/µb(s, a). As b is typically a large constant, the finite sample bound (11) for J?N is often more informative than (17). In addition, the variance of Ĵ IPS N grows exponentially with the sample size N [15, 13, 65]. As a simple remedy, one can cap the importance weights beyond some threshold β > 0 and construct the modified IPS estimator as
Ĵ IPSβ N = 1 N ∑N i=1 c(ŝi, âi) min { β, µe(ŝi,âi)µb(ŝi,âi) } .
Decreasing β reduces the variance of Ĵ IPSβN but increases its bias. An alternative estimator for Vπe is the doubly robust (DR) estimator ĴDRN , which uses a control variate to reduce the variance of the IPS estimator. The DR estimator was 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 πe and the behavioral policy πb from the uniform distribution on the space of stationary policies. The decision maker then has access to the evaluation policy πe and to a sequence of i.i.d. state action pairs {ŝi, âi}Ni=1 sampled from µb as well as the observed empirical costs {ĉi}Ni=1, where ĉi = c(ŝi, âi). 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 PN (Vπe > ĴN ) analyzed in Theorem 4.1, where ĴN denotes any of the tested estimators. Acknowledgments. We thank Mengmeng Li for helpful discussions. This research was supported by the Swiss National Science Foundation under the NCCR Automation, grant agreement 51NF40_180545.

Review summaries:
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.

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.  ======== After 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.

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