Bitrate-Constrained DRO: Beyond Worst Case Robustness To Unknown Group Shifts
Authors: Amrith Setlur
Don Dennis
Benjamin Eysenbach
Aditi Raghunathan
Chelsea Finn
Virginia Smith
Sergey Levine
Venue: ICLR 2023 poster (2023)
Keywords: Robustness
Distribution shift
Group Shift

Abstract: Training machine learning models robust to distribution shifts is critical for real-world applications. Some robust training algorithms (e.g., Group DRO) specialize to group shifts and require group information on all training points. Other methods (e.g., CVaR DRO) that do not need group annotations can be overly conservative, since they naively upweight high loss points which may form a contrived set that does not correspond to any meaningful group in the real world (e.g., when the high loss points are randomly mislabeled training points). In this work, we address limitations in prior approaches by assuming a more nuanced form of group shift: conditioned on the label, we assume that the true group function (indicator over group) is simple. For example, we may expect that group shifts occur along low bitrate features (e.g.,  image background, lighting). Thus, we aim to learn a model that maintains high accuracy on simple group functions realized by these low bitrate features, that need not spend valuable model capacity achieving high accuracy on contrived groups of examples. Based on this, we consider the two-player game formulation of DRO where the adversary's capacity is bitrate-constrained. Our resulting practical algorithm, Bitrate-Constrained DRO (\bdro), does not require group information on training samples yet matches the performance of Group DRO on datasets that have training group annotations and that of CVaR DRO on long-tailed distributions. Our theoretical analysis reveals that in some settings \bdro objective can provably yield statistically efficient and less conservative solutions than unconstrained CVaR DRO.

Published as a conference paper at ICLR 2023
BITRATE-CONSTRAINED DRO: BEYOND WORST CASE ROBUSTNESS To UNKNOWN GROUP SHIFTS
Amrith Setlur'
Don Dennis'
Benjamin Eysenbach'
Aditi Raghunathan
Chelsea Finn²
Virginia Smith'
Sergey Levine"
1 Carnegie Mellon University
Stanford University
UC Berkeley
ABSTRACT
Training machine learning models robust to distribution shifts is critical for real-world applications. Some robust training algorithms (egg, Group DRO) specialize to group shifts and require group information all training points. Other methods (e.g, CVaR DRO) that do not need group annotations can be overly conservative. since they naively upweight high loss points which may form a contrived set that does not correspond to any meaningful group in the real world (e.g., when the high loss points are randomly mislabeled training points). In this work, we address limitations in prior approaches by assuming a more nuanced form of group shift: conditioned on the label, we assume that the true group function (indicator over group) is simple. For example, we may expect that group shifts occur along low bitrate features (e.g. image background, lighting). Thus, we aim learn a model that maintains high accuracy on simple group functions realized by these low bitrate features, that need not spend valuable model capacity achieving high ac- curacy on contrived groups of examples. Based on this, we consider the two-player game formulation of DRO where the adversary's s capacity is cttrate-constraineed Our resulting practical algorithm, mation training samples yet matches the performance of Group DRO on datasets that have training group annotations and that of CV&R DRO on long-tailed distributions. Our theoretical analysis reveals that in some settings BR-DRO objective can provably yield statistically efficient and less conservative solutions than unconstrained CVaR DRO.
Crrrte-Coonttraneed DRO BDR), does not require group infor-
INTRODUCTION
Machine learning models may perform poorly when tested on distributions that differ from the training distribution. A common form of distribution shift is group shift, where the source and target differ only in the marginal distribution over finite groups or sub-populations, with no change in group conditionals (Oren)
al. 2019: Duchi et al. 2019) (e.g., when the groups are defined by spurious correlations and the target distribution upsamples the group where the correlation is absent Sagawa et al. (219)).
Prior works consider various approaches to address group shift. One solution is to ensure robustness to worst case shifts using distributionally robust optimization (DRO) (Bagnell 2005 Ben- Tal et al. 2013 Duchi et al. 2016), which considers a two-player game where a learner minimizes risk on distributions chosen by an adversary from a predefined uncertainty set. As the adversary is only constrained to propose distributions that lie within an f-divergence based uncertainty set, DRO often yields overly conservative (pessimistic) solutions (Hu et al., 2018) and can suffer from statistical challenges (Duchi et al. 2019). This is mainly because DRO upweights high loss points that may not form a meaningful group in the real world, and may even be contrived if the high loss points simply correspond to randomly mislabeled examples in the training set. Methods like Group DRO (Sagaaa et al. 2019) avoid overly pessimistic solutions by assuming knowledge of group membership for each training example. However, these group- based methods provide no guarantees on shifts that deviate from the predefined groups (e.g., when there is a new group), and are not applicable to problems that lack group knowledge. In this work, we therefore ask: Can we train non-pessimistic robust models without access to group information on training samples?
We address this question by considering a more nuanced assumption on the structure of the underlying groups. We assume that, conditioned on the label, group boundaries are realized by high-level features that depend on small set of underlying factors (e.g., background color, brightness). This leads to simpler group
"Correspondence can be sent to cuetlu@@cs.cmu.com

---

Published as a conference paper at ICLR 2023
Tue gina dasrte
Look
Preto Prndeer 016, o' It
JIT ai DRO Jany st
Bixta Gendanad DPD
Indprity
44
C2:
-02-
-02
ado
16-6777-6-5--225030 0.0 minority by
manotiy
Fecorccty y Maaied
Figure 1: Bitrate-Constrained DRO: A method that assumes group shifts along low- features, and restricts the adversary appropriately so that the solution found is less pessimistic and more robust to unknown group shifts. Our method also robust to training noise. (Lefi) In Waterbirds (Wah al. 201I the spurious feature background is large margin simple feature that separates the majority and minority points in each class. (Right) Prior works (evv al. 2020 Liu et al. 202T) that upweight arbitrary points with high losses force the model to memorize noisy mislabeled points while our method is robust to noise and only upweights the true minority group without any knowledge of its identity (see Section 6.2).
functions with large margin and simple decision boundaries between groups (Figure | (left).. Invoking the principle of minimum description length (Günnalld 2007), restricting our adversary functions that satisfy this assumption corresponds to bitrate constraint. In DRO, the adversary upweights points with higher losses under the current learner, which in practice often correspond to examples that belong to rare group, contain complex patterns, or are mislabeled (Carlini et al. 2019 Toneva et al. 2018). Restricting the adversary's 's capacity prevents it from upweighting individual hard or mislabeled examples (as they cannot be identified with simple features), and biases it towards identifying erroneous data points misclassified by simple features. This also complements the failure mode of neural networks trained with stochastic gradient descent (SGD) that rely simple spurious features which correctly classify points in the majority group but may fail on minority groups (Blodgett et al. 2016).
The main contribution of this paper is that provides robustness to distribution shifts along groups realized by simple functions. Despite not using group information on training examples, we demonstrate that BR-DRO can match the performance of methods requiring them. We also find that BR-DRO is more successful in identifying true minority training points, compared to unconstrained DRO. This indicates that not optimizing for performance on contrived worst-case shifts can reduce the pessimism inherent in DRO. It further validates: (i) our assumption on the simple nature of group shift; and (ii) that our bitrate constraint meaningfully structures the uncertainty set to be robust to such shifts. As consequence of the constraint, we also find that BR-DRO is robust to random noise in the training data (Song et al.) 2022). since it cannot form "groups" entirely based on randomly mislabeled points with low bitrate features. This is in contrast with existing methods that use the leamer's 's training emor to up-weight arbitrary sets of difficult training points (e.g.. [iu et al., [202]] Levy et al., 2020), which we show are highly susceptible to label noise (see Figure [ (right)). Finally, we theoretically analyze our approach characterizing how the degree of constraint on the adversary can effect worst risk estimation and excess risk (pessimism) bounds, as well convergence rates for specific online solvers.
DRO (BR-DRO), supervised learning procedure
2 RELATED WORK
Prior works in robust ML (e.g., Li et al. 2018 Lipton al. 2018 Goodiellow et al. 2014) address various forms of adversarial or structured shifts. We specifically review prior work on robustness to group shifts. While those based DRO optimize for worst-case shifts in an explicit uncertainty set, the robust set is implicit for some others, with most using some form of importance weighting.
Distributionally robust optimization (DRO). DRO methods generally optimize for worst-case performance on joint (x.y)
distributions that lie in an f-divergence ball (uncertainty set) around the training
2013 Rahimian & Mehrotra 2019 Bertsimas et al., 2018 Blanchet & Murthy 2019, Miyato et al. 2018 Duchi et al. 2016 Duchi & Namkoong] 2021). Hu et al. (2018) highlights that
distribution (Ben-Tal Tal et al.
the conservative nature of DRO may lead to degenerate solutions when the unrestricted adversary uniformly upweights all misclassified points. (Sagawa et al. (211)) proposes to address this by limiting the adversary to shifts that only differ in marginals over predefined groups. However, in addition to it being difficult to obtain this information, Kearns et al. (018)) raise "genyymnndrrnn" concerns with notions of robustness that fix a small number of groups aprioni While they propose a solution that looks at exponentially many subgroups defined over protected attributes, our method does not assume access to such attributes and
2

---

Published as a conference paper at ICLR 2023
aims to be fair them as long they realized by simple functions. Finally, Zhai et al. (2021) avoid conservative solutions by solving the DRO objective over randomized predictors learned through boosting. We consider deterministic and over- wer-pparmeteriieed learners and instead constrain the adversary's class.
Constraining the DRO uncertainty set. In the marginal DRO setting, Duchi et al. (2019) limit the adver- sary via
reproducing kernel hilbert spaces (RKHS) or bounded Hölder continuous functions (Liu & Ziebart 2014 Wen et al.] 2014). While this reduces the statistical eroor in worst risk estimation, the size of the uncertainty set (scales with the data) remains too large avoid cases where an adversary can re- weight mislabeled and hard examples from the majority set (Carlini et al. 2019). In contrast, we restrict the adversary even for large datasets where the estimation enror would be low, as this would reduce excess risk when we only care about robustness to rare sub poppulatiisns defined by simple functions. Additionally, while their analysis and method prefers the adversary's 's objective to have a strong dual, we show empirical results on real-world datasets and generalization bounds where the adversary's objective is not necessarily convex.
Robustness to group shifts without demographics. Recent works (Sohoni et al. 2020 Creager et al. 2021
Bao & Barzilay 2022) that aim to achieve group robustness without access group labels employ various heuristics where the robust set is implicit while others require data from multiple domains (Arjovsky et al.
2019 Yao et al. 2022) ability to query test samples (Lee et al. 2022). Liu et al. (202T) use training losses for a heavily regularized model trained with empirical risk minimization (ERM) to directly identify minority data points with higher losses and re-train on the dataset that up up-weights the identified set. Nam al. 2020)
take a similar approach. Other methods (Idrissi et al. 2022) propose simple baselines that subsample the majority class in the absence of group demographics and the majority group in its presence. Hashimoto al. (2018) find DRO over a x² ddvveeegee ball can reduce the otherwise increasing disparity of per-group risks dynamical system. Since it does not use features upweight points (like
BR-DRO) it vulnerable Nam et al. (2020)). ))
to label noise. Same can be said about some other works (e.g.. Liu et al. (201
Importance weighting in deep learning. Finally, numerous works Ducchi al. 2016 Levy al. 2020,
Lipton et al. 2018 Oren et al. (219)) enforce robustness by re- re-weighting losses on individual data points. Recent investigations (Soudry et al. 2018 Byrd & Lipton 2019 Lt all. (022) reveal that such objectives have little impact on the learned solution in interpolation regimes. One way to avoid this pitfall is to train with heavily regularized models (Sagawa et al. 2019, 2020) and employ early stopping. Another way is to subsample certain points, as opposed to up-weighting (Idrissi et al. 2022). In this work, we use both techniques while training our objective and the baselines, ensuring that the regularized class is robust to shifts under misspecificationn (Wen al. 2014).
3 PRELIMINARIES
We introduce the notation we use in the rest of the paper and describe the DRO problem. In the following section, we will formalize our assumptions on the nature of the shift before introducing our optimization objective and algorithm.
Notation. With covariates X' C _dd and labels V. the given source P and unknown true target Qo are measures over the measurable space (X' x Y) and have densities p and go respectively (w.r.. base measure μ1). The learner's 's choice is a hypothesis h: h'''>>> in class H C (P)... and the adversary's 's action in standard DRO a target distribution Q in set @r... := [Q:Q < P. (Q]) P) <x). Here, D, is the f-divergence between Q and P for a convex function 1 with f(1) 0 An equivalent action space for the adversary is the set of re- weighting functions:
WP. - (w:
I:; wis measurable under P, P,[[w 1, [x}
(I)
For convex loss function 1: x''' x y' + R,, we denote I(h) as the function over (x.y) that evaluates 1(h ()).)))). and use 1o_ to denote the loss function 11 (h(x) y). Given either distribution Q E Q or a re- weighting function w E Wp,.. the risk of leamne h is:
R(h,Q)=Eq [(h)]] R(haw) - =x [(((x)))) (xx((xxx)))))xxxx))))(()())))))) ((h)))))))
(2)
Note the overload of notation for ). If the adversary is stochastic it picks mixed action O' A(Wpx). which the set of all distributions over Wp,.. Whenever it is clear, we drop P.s.
Unconstrained DRO (Ben- Tal et al. 2013). This is a min-max optimization problem understood as a two-player game, where the leamner chooses a hypothesis, to minimize risk on the worst distribution that
For egg, KL.(QI) can he derived with f(x = zlogz and for Total Variation f(x)= = Jz 11/2.
3

---

Published as a conference paper at ICLR 2023
the adversary can choose from its set. Formally, this is given by Equation S The first equivalence is clear from the definitions and for the second since R(h,Q) Q) is linear in Q, the supremum over A(Wpx)) is a Dirac delta over the best weighting in Wpx. In the next section, we will see how bitrate-constrainee adversary can only pick certain actions from A(Wr,))
inf sup R(h,Q)= = inf sup R(h,w) = inf sup Eu (R(h,ww) RERQEEP..
WEWP.
BEAWW.))
Group Shift. While the DRO framework in Section 3 is broad and addresses any unstructured shift, we focus on the specific case of group shift. First, for a given pair of measures P.Q we define what we mean by the group structure GPo (Definition B.I.. Intuitively, it a set of sub-populations along which the distribution shifts, defined in way that makes them uniquely identifiable. For e.g. in the Waterbirds dataset (Figure D.. there are four groups given by combinations of (label, background). Corollary 3.2 follows immediately from the definition of Gr.Q- Using this definition, the standard group shift assumption (Saaaaa et al. 2019) can be formally re-stated as Assumption 3.3
Definition 3.1 (group structure Gr For Q < P the group structure GP.Q= (Gx) is the smallest finite set of disjoint groups {Gx R== s.t. Q(UK_
and wk (i) Gk E E, Q(Gx) > 0 and (ii)
p(x.y (Gx)=q(xx)) G&) > Da.e. in p. such a structure exists then Gr&q is well defined.
Corollary 3.2 (uniqueness of GP,q). VPQQ. the structure ((P.Q) is unique it is well defined.
Assumption 3.3 (standard group shift). There exists well-defined group structure GP.20 s.t. larget Qo disfers P only in terms of marginal probabilities over all GE &p..0.
4 BITRATE-CONSTRAII
DRO
We begin with note on the expressivity of the adversary in Unconstrained DRO and formally introduce the ussumption we make on the nature of shift. Then, we build intuition for why unconstrained adversaries fail but restricted ones do better under our assumption. Finally, we state our main objective and discuss a specific instance of it.
How expressive unconstrained adversary? Note that the set Wp., includes all measurable functions (under P) such that the re-weighted distribution is bounded in f-divergence (by K). While prior works (Shafieezadeh Abadeh et al. 2015. Duchi et al. 2016) shrink x: to construct confidence intervals, this only controls the total mass that can be moved between measurable sets G1,G2 E Σ, but does not restrict the choice of G1 and G2 itself. As noted by Hu et al. (2018), such an adversary is highly expressive, and optimizing for the worst case only leads to the solution of empirical risk minimization (ERM) under 1o-1 loss. Thus, we can conclude that DRO recovers degenerate solutions because the worst target in Wr,, lies far from the subspace of naturally occurring targets. Since it is hard precisely characterize natural targets we make a nuanced assumption: the target Qo only upsamples those rare subpopulations that are misclassified by simple features. We state this formally in Assumption after we define the bitrate-constrained function class W(7) in Definition
4.1
Definition 4.1. A function class W(y) is bitrate-constrainet if there exists a data independent prior n. s.f. W(7) = [E[]]] ó A(W), ( ST).
Assumption 4.2 (simple group shift). Target Qo satisfies Assumption 3.3 (group shift) w.r.t. source P. Additionally, For some prior and a small >", the re-weighting function qu/P lies in a bitrate-constrainee class W('*). In other words, for every group G GGG(, 2wa E W(r") We refer such G simple group that realized in W(-").
(((""sss s.t. 1((x.y) E = WG a.e..
Under the principle of minimum description length Grünnalld 2007 any deviation from the prior (i.e., KL x)) increases the description length of the encoding ò E A(W). ) thus we refer to W(r) as being birrate-construineed in the sense that it contains functions (means of distributions) that can be described with a limited number of bits given the prior æ. See Appendix for an example of bitrate-constrained class of functions. Next we present arguments for why identifiability of simple (satisfy Assumption minority groups can be critical for robustness.
Neural networks can perform poorly simple minorities. For fixed target Qo. let's say there exists two groups: Gmin and Gmazj E EG(P.Qo) such that P(Gmin) < P(Gmg)) By Assumption 4.2 both Gmin and Gmag are simple (realized in W(+")), )), and are thus separated by some simple feature. The learner's s class H is usually a class of overparameterized neural networks. When trained with stochastic gradient descent (SGD), these are biased towards learning simple features that classify majority of the
4

---

Published as a conference paper at ICLR 2023
data (Shah al. 2020 Soudry et al. 2018 Thus, if the simple feature separating Guin and Gmuj itself correlates with the label y on Gmaj. then neural networks would fit on this feature. This is precisely the case in the Waterbirds example, where the groups are defined by whether the simple feature background correlates with the label (Figure M]. Thus our assumption on the nature of shift complements the nature of neural networks perform poorly on simple minorities.
The bitrate constraint helps identify simple unfair minorities in ((P.Qo). Any method that aims be robust on Qo must up-weight data points from Gmin but without knowing its identity. Since the unconstrained adversary upsamples any group of data points with high loss and low probability, it cannot distinguish between rare group that is realized by simple functions in W(r") and rare group of examples that share no feature in common or may even be mislabeled. On the other hand, the group of mislabeled examples cannot be separated from the rest by functions in W(+"). Thus, a bitrate constraint adversary can only identify simple groups and upsamples those that incur high losses possibly due to the simplicity bias of neural networks.
BR-DRO objective. According to Assumption 4.2 there cannot exist a target Qo such that minority Gmin E ((...))) is not realized in bitrate constrained class W(y"). Thus, by constraining our adversary to class W(:) (for some 7 that is user defined), we can possibly evade issues emerging from optimizing for performance on mislabeled or hard examples, even they were rare. This gives us the objective in Equation 4 where the equalities hold from the linearity of (:+) and Definition 4.1
inf sup E RR(,,) = inf sup (1(h).Rs(wl)) inf sup R(h,w) hEHWEW(()
(4)
NEH BEA(W) Kl.(1|]>)S>
REH 6EA(W) kI((8||))S
BR-DRO in practice. We parameterize the leamer 0₁ E EO, and adversary Ou e as neural networks In practice, we implement the adversary either one hidden layer variational information bottleneck
(VIB) (Alemi et al. (016)) where the Kullback-Leibler (KL) constraint on the latent variable z (output of VIB's hidden layer) directly constrains the bitrate; or as an l2 norm constrained linear layer. The objective for the VIB (l2) version is obtained by setting 3,b * (3,a #0) in Equation S below. See Appendix [A.2] for details. Note that the objective in Equation no longer convex-concand and can have multiple local equilibria or stationary points (Mangoubi & Vishnoi 2021). The adversary's 's objective also does not have a strong dual that can be solved through conic programs- standard practice in DRO literature Namkoong & Duchi 2016). Thus, we provide an algorithm where both learner and adversary optimize BR-DRO iteratively through stochastic gradient ascent/descent (Algorithm I in Appendix A.I.
min (1(O.).0t)) P s.t. 0% argmax Ludv (O O, O..
(5)
O,
Ladv (0u Svb. =
BBb EpKLLppKK x (I O
Training, For each example, the adversary takes as input: (i) the last layer output of the current leamer's feature network; and (ii) the input label. The adversary then outputs a weight (in [0, 1)). The idea of applying the adversary directly on the learner's features (instead of the original input) is based on recent literature (Rosenteld et al. 2022 Kinchenko al. 2022) that suggests re-training the prediction head is sufficient for robustness to shifts. The adversary tries to maximize weights on examples with value n (hyperparameter) and minimize on others. For the learner, in addition to the example takes as input the adversary assigned weight for that example from the previous round and uses it to reweigh its loss in minibatch. Both players are updated in round (Algorithm MT.
THEORETICAL ANALYSIS
The main objective of our analysis of BR-DRO is to show how adding a bitrate constraint on the adversary can: (i) give us tighter statistical estimates of the worst risk; and (ii) control the pessimism (excess risk) of the learned solution. First, we provide worst risk generalization guarantees using the PAC-Bayes framework (Catoni 2007), along with a result for kernel adversary. Then, we provide convergence rates and pessimism guarantees for the solution found by our online solver for specifie instance of W(n) For both these, we analyze the constrained form of the conditional value at risk (CVaR) DRO objective (Levy al. 2020 below.
Bitrate-Constrainee CVaR DRO. When the uncertainty set Q is defined by the set of all distri- butions Q that have bounded likelihood i.e. lla/plloe I 1/00. we recover the original CVaR DRO
We use Bu. and 1(0%) to denote un(0 (x.))(( and ((((0x:))))) respectively.
5

---

Published as a conference paper at ICLR 2023
objective Duchh & Namkoong 2021). The bitrate-constrained version of CVaR DRO is given in
Equation 6 (see Appendix X for derivation). Note that, slightly different from Section 3 we define W as
the set of all measurable functions w: X' "x - [0.1], since the other convex restrictions in Equation | arr
handled by dual variable 1/. As in Section 4 W(y) is derived from W using Definition 4.1 In Equation S
if we replace the bitrate-oostrainedd class W(2) with the unrestricted W then recover the variational
form of unconstrained CVaR DRO in Duchi et al. (2016).
Lovar (7)
inf sup R(h,n.w) where, ((lx)_)))((/oo)(((00-aaa--a)) hew.nERPeW(())
(6)
Worst risk estimation bounds for BR-DRO. Since we are only given a finite sampled dataset D P we solve the objective in Equation 2
using the empirical distribution P.. We denote the plug-in estimates as 66.. .i-- This incurs an estimation error for the true worst risk. But when we restrict our adversary to A(W y),, )), for fixed learner h reduce the worst-case risk estimation error which scales with the bitrate KL(-1 || 1T) of the solution (deviation from prior т). Expanding this argument to every learner in H. with high probability we also reduce the estimation error for the worst risk of hh. Theorem 5.1 states this generalization guarantee more precisely.
Theorem 5.1 (worst-case risk generalization), With probability 2 1 8 over 'D ~ pa, the worst bitrate-constrained Org- CVoC risk for hi can be upper bounded by the following oracle inequality:
sup m) & foultt) au (1+tog (:) +dd+++++ogg (
M.
L'n +logn) /(2n-1),
wEW())
when 1(--) is -bouded, L-Lipschitz and H. is parameterized by convex set OCR"
Informally, Theorem 5. tells us that bitrate-constraint gracefully controls the estimation error O((b+C(H))/ (where C(H) is a complexity measure) if we know that Assumption 4.2 is satisfied. While this only tells us that our estimator is consistent with (1)v)) the estimate may itself be con- verging a degenerate predictor, ie.. (+) may be very high. For example, if the adversary can cleanly separate mislabeled points even after the bitrate constraint, then presumably these noisy points with high losses would be the ones mainly contributing to the worst risk, and up-weighting these points would result in a learner that has memorized noise. Thus, it becomes equally important for us to analyze the excess risk (or the pessimism) for the learned solution. Since this is hard to study for any arbitrary bitrate- conttreecn class W(7), we shall do so for the specific class of reproducing kernel Hilbert space (RKHS) functions.
Special case of bounded RKHS. Let assume there exists prior IT such that W(7) in Definition 4. given by RKHS induced by Mercer kernel h: X' X IR s.t. the eigenvalues of the kernel operator decay polynomially, i.e., P2 S /2/x (1 < 2). Then, if we solve for hb by doing kernel ridge regression over norm bounded (I) [[lf" 1) smooth functions f then we can control: (i) the pessimism of the leamned solution; and (ii) the generalization error (Theorem 5. Formally, we refer to pessimism for estimates f f7, as excess risk defined as:
excess risk: sup inn R(h.maw) R(h..Ab.00) wEW(s) hon
Theorem 5.2 (bounded RKHS). For 1.H. in Theorem 5.7 and for W(r) described above 3% s.t. for all sufficienaly bitrate-construined W(n) ie., 7ST0. w.h.p. 1- 8 worst risk generalization error is (d+ 1)0g)(BB-)1/2))) (o
and the excess risk is O(B) for hb. above.
Thus, in the setting described above we have shown how birrate-constraitts given indirectly by R. can control both the pessimism and statistical estimation errors. Here, we directly analyzed the estimates ib.00 but did not describe the specific algorithm used to solve the objective in Equation 6 with Pr.. Now, we look at an iterative online algorithm solve the same objective and see how bitrate-onntrriints can also influence convergence rates in this setting.
Convergence and excess risk analysis for an online solver. In the following, we provide an algorithm to solve the objective in Equation and analyze how bitrate-constrain impacts the solver and the solution. For convex losses, the min-max objective in Equation 6 has a unique solution and this matches the unique Nash equilibrium for the generic online algorithm (game) we describe (Lemma 5.3). The algorithm is as follows: Consider a two awo-player zero-sum game where the learner uses a no-regret strategy to first play he H. e IR to minmmize & Wh),,,w) Then, the adversary plays follow the regularized leader (FTRL) strategy
6

---

Published as a conference paper at ICLR 2023
Waterbirks
CelebA
CivilComments
Method
Avg
WG
Avg
WG
Avg
WG
FRM
(0.1)
71.0 (0.4)
95.4 (0.2)
46.9 (1.0)
92.3 (0.2)
57.2 (0.9)
Li:
Nam al
2120
90.7 (0.2)
77.6 (0.5)
85.3 (0.2)
77.4 (0.7)
924 (0.1)
58.9 (1.1)
RWY
Idmssa al.
2122
93.7 (0.3)
85.8 (0.5)
84.9 (0.2)
804 (0.3)
91.7 (0.2)
67.7 (0.7)
JTT
Liu et al.
2011
93.2 (0.2)
86.6 (0.4)
87.6 (0.2)
81.3 (0.5)
908 (0.3)
69.4 (0.8)
DRO
Lay
2120
(0.2)
75.5 (0.4)
82.2 (0.3)
64.7 (0.6)
92.3 (0.2)
60.2 (0.8)
BR DBD (VIB) (ours)
94.1 (0.2)
86.3 (0.3)
86.7 (0.2)
80.9 (0.4)
90.5 (0.2)
68.7 (0.9)
BR-NRO (12) (ouns)
(0.2)
86.4 (0.3)
87.7 (0.3)
80.4 (0.6)
91.0 (0.3)
68.9 (0.7)
Group DRO Sugawa al
2019
93.2 (0.3)
91.1 (0.3)
92.3 (0.3)
88.4 (0.6)
88.5 (0.3)
70.0 (0.5)
Table 1: BR-DRO recovers worst group performance gap between CVaR DRO and Group DRO: On Water- birds, CelebA and CivilComments we report test average (Avg) and test worst group (WG) accuracies for BR-DRO and baselines. In (.) we report the standard error of the mean accuracy across five runs.
to pick distribution 8 ((W()) to maximize the same. Our goal is to analyze the consstainnn y effect on the above algorithm's 's convergence rate and the pessimistic nature of the solution found. For this, we need to first characterize the bitrate-constraint class W(y). If we assume there exists prior IT such that (() Vapnik-Chervenokii (VC) class of dimension O(7), then in Theorem 5.4 we see that the iterates of our algorithm converge to the equilibrium (solution) in O( D(V/logge /ologg// (T) steps. Clearly, the degree of bitrate constraint can significantly impact the convergence rate for generic solver that solves the constrained DRO objective. Theorem 5.4 bounds the excess risk (Fquation 7 on P,,
Lemma 5.3 (Nash equilibrium). For strictly convex U(h), I(h) [0.M], the objective in Equation P has a unique solution which is also the Nash equilibrium of the game above when played over compact sets Hx MO A(W,)) We denote this equilibrium as hi (1))))
Theorem 5.4. At time step t, if the learner plays (h,, me) with no-regret and the adversary plays 5e with FTRL strategy that uses a negative entropy regularizer on 5 then average iterates (hr, Ti, 5r) = (1/T) (i=i nu 61) converge to the equilibrium (17,(7), nf(()), (7)) at rate O( Plolo///T) Further the excess risk defined above is ((M//a)) -)))))
EXPERIMENTS
Our experiments aim to evaluate the performance of BR-DRO and compare it with ERM and group shift robustness methods that do not require group annotations for training examples. We conduct empirical analyses along the following axes: (i) worst group performance on datasets that exhibit known spurious correlations; (fi) robustness to random label noise in the training data; (iii) average performance on hybrid covariate shift datasets with unspecified groups; and (iv) accuracy in identifying minority groups. See Appendix B for additional experiments and details B
Baselines. Since our objective is to be robust to group shifts without group annotations on training examples, we explore baselines that either optimize for the worst minority group (CVaR DRO (Lev
Ct al.
2020 or use training losses to identify specific minority points (LfF (Nam et al.] 2020). JTT (Lu
et re-weighting baseline (RWY) proposed by Idrissi al. (022)..
2021 Group DRO (aaaaaa et al. (019) is treated as an oracle. We also compare with the simple
Implementation details. We train using Resnet-50 (He et al. 2016 for all methods and datasets except CivilComments, where we use BERT (Wolf et al. 2019). For our VIB adversary, we use 1-hidden layer neural network encoder and decoder (one for each label). As mentioned in Section E the adversary takes as input the learner model's features and the true label to generate weights. All implementation and design choices for baselines were adopted directly from Liu et al. (22T drissi et al. 2022). We provide model selection methodology and other details in Appendix
Datasets. For experiments in the known groups and label noise settings we use: (i) Waterbirds (Wah et al. 2011) (background is spurious), CelebA (Liu et al.] 2015) (binary gender is spuriously correlated with label "blond");; and CivilComments (WILDS) (Borkan et al. 2019) where the task is predict "toxic" texts and there are 16 predefined groups Koh et al. (021). We use FMoW and Camelyon17 17 (Koh el al. T02T) to test methods on datasets that do not have explicit group shifts. In FMoW the task is to predict
land use from satellite images where the training/test set comprises of data before/after 2013. Test involves both subpopulation shifts over regions (e.g.. Africa, Asia) and domain generalization over time (year). Camelyon17 7 presents a domain generalization problem where the task is to detect tumor in tissue slides from different sets of hospitals train and test sets.
'The code used in our experiments be found ht httph///ttt//////oooooo/////////
7

---

Published as a conference paper at ICLR 2023
Wasterblice
Celebd
Synthet
85-
08-CR0
18-090
Werr grup acCU000
-0
00-
422
6.05 6.07 Random rass fraction
Random notse traction
Random Fraction
(a)
(b)
Figure 2: (Left) Visualization (2d) of noisy synthetic data and learned predictons: We plot the decision boundaries (projected onto core and spurious features) leamned by JTT and BR-DRO when the adversary restricted to sparse predictor. While our method recovers the core feature the baselines memorize the minority points. (Right) BR-DRO is robust to random label noise in training data: Across varying levels of noise fraction in training data we compare performance of BR-DRO with FRM and methods (JTT, CVaR DRO) that naively up weight high loss points.
6.1 IS BR-DRO ROBUST TO GROUP SHIFTS WITHOUT TRAINING DATA GROUP ANNOTATIONS?
Table I compares the average and worst group accuracy for BR- DR- with ERM and four group shift robustness baselines: JTT, LtF, SUBY, and CVaR DRO. First,
that unconstrained CVaR DRO
underperforms other heuristic algorithms. This matches the observation made by Liu et al. (02T). Next, we see that adding bitrate constraints the adversary via KL term l2 penalty significantly improves the performance of BR-DRO (VIB) or BR-DRO (12). which now matches the best performing baseline (JTT). Thus, we the less conservative nature of BR-DRO allows to recover large portion of the performance gap between Group DRO and CVaR DRO. Indirectly, this partially validates our Assumption 2 which states that the minority group is identified by a low bitrate adversary class. In
Section 6.3 we discuss exactly what fraction of the minority group is identified, and the role played by the strength of bitrate-constrintt
6.2 DR- IS MORE ROBUST TO RANDOM LABEL NOISE
Several methods for group robustness (e.g., CVaR DRO, JTT) are based on the idea of up weighting points with high training losses. The goal is obtain a leamer with matching performance on every (small) fraction of points in the dataset. However, when training data has mislabeled examples, such an approach will likely yield degenerate solutions. This is because the adversary directly upweights any example where the learner has high loss, including datapoints with incorrect labels. Hence, even if the leamne's 's prediction matches the (unknown) true label, this formulation would force the learner to memorize incorrect labelings at the expense of learning the true underlying function. On the other hand, if the adversary is sufficiently bitrate constrained, it cannot upweight the arbitrary set of randomly mislabeled points, as this would require it to memorize those points. Our Assumption noisy examples. Thus, our constraint on the adversary ensures BR BR-DRO is robust to label noise in the training data and our assumption on the target distribution retains its robustness to test time distribution shifts.
2 also dictates that the distribution shift would not upsample such high bitrate
In Figure 2 we highlight this failure mode of unconstrained up-weighting methods in contrast to BR-DRO. We first induce random label noise (Carlini et al. 2019) of varying degrees into the Waterbirds and CelebA training sets. Then we run each method and compare worst group performance. In the absence of noise we see that the performance of JTT is comparable with BR-DRO, if not slightly better (Table D. Thus, both BR-DRO and JTT perform reasonably well in identifying and upsampling the simple minority group in the absence of noise. In its presence, BR-DRO significantly outperforms JTT and other approaches on both Waterbirds and CelebA, as it only upsamples the minority examples misclassified by simple features, ignoring the noisy examples for the reasons above. To further verify our claims, we set up a noisily labeled synthetic dataset (see Appendix B for details). In Figure 2a we plot training samples as well as the solutions learned by BR-DRO and and JTT on synthetic data. In Figure rightt) we also plot exactly which points are upweighted by figures, we note that JTT mainly upweights the noisy points (in red) and memorizes them using Xnoise Without any weights minority, it memorizes them as well and leams component along spurious feature. On the contrary. when we restrict the adversary with BR-DRO to be sparse (41 penalty), it only upweights minority samples, since sparse predictor separate noisy points in the data. Thus, the learner can no longer memorize the upweighted minority and we recover the robust predictor along core feature.
and JTT. Using both
6.3 WHAT FRACTION OF MINORITY IS RECOVERED BY BR-DRO?
We claim that our less pessimistic objective can more accurately recover (upsample) the true minority group if indeed the minority group is simple (see Assumption 4.2 for our definition of simple). In this section, we aim to verify this claim. If we treat examples in the top 10% (chosen for post hoc analysis)
8

---

Published as a conference paper at ICLR 2023
OVaR DRO
JTT
BA-DRO (8.6 - 0.01)
Random baseline
BR-DRO 18 0.11
BR-DRO (8.e 0.000)
Waterbirds
Waterbirds
Ce eDA
CelebA
0.5
Rocall 0.
9.15
0.0
0.20
0.7
Prectsion
0.15
Prectsion
0:10
0.6
0.5
0.4
0.05
0.05
0.3
0.2
0.00
0.00
0 50 100 150 200 250 300
50 100 150 200 250 300 10 20
30
50
10
20
30 50
Training epochs
Training epochs
Training epochs
Training epochs
Figure 3: By considering the fraction of points upweighted by our adversary (top 10%) as the positive class we analyze the precision and recall of this class with respect to the minority group. and do the same for JTT, random baseline and CVaR DRO. BR-DRO achieves highest precision and matches recall with JTT asymplotically. We also find that increasing bitrate constraint Ban. helps improving precision/recall.
fraction of examples as our predicted minorities, we can check precision and recall of this decision on the Waterbirds and CelebA datasets. Figure E] plots these metrics at each training epoch for BR-DRO (with varying Buis), JTT and CVaR DRO. Precision of the random baseline tells us the true fraction of minority examples in the data. First we note that BR-DRO consistently performs much better on this metric than unconstrained CVaR DRO. In fact, as we reduce strength of Bub we recover precision/recall close to the latter. This controlled experiment shows that the bitrate constraint is helpful (and very much needed) in practice to identify rare simple groups. In Figure 3 we observe that asymptotically, the precision of BR-DRO is better than JTT on both datasets, while the recall is similar. Since importance weighting has little impact in later stages with exponential tail losses (Soudry et al., 2018 [Byrd & Lipton 2019). other losses (e.g., polytail [Wang el al. (20TT) may further improve the performance of BR-DRO as it gets better at identifying the minority classes when trained longer.
6.4 How DOES BR-DRO PERFORM ON MORE GENERAL COVARIATE SHIFTS?
In Table 2 we report the average test accuracies for BR-DRO and baselines on the hybrid dataset FMoW and domain generalization dataset Camelyon17. Given its hybrid nature, on FMoW we also report worst region accuracy. First, we note that on these datasets group shift robustness baselines do not do better than ERM. Some are either too pessimistic (e.g.. CVaR DRO), or require heavy assumptions (egg, Group DRO) to be robust to domain generalization. This is also noted by Gulrajani & Papez-Paz (2020). Next, we see that BR-DRO (12 version) does better than other group shift baselines on both both worst region and average datasets and matches ERM performance on Camelyon17, 17. One explanation could be that even though these datasets test models on new domains, there maybe some latent groups defining these domains that are simple and form a part of latent subpopulation shift. Investigating this claim further is a promising line of future work.
Method
FMoW
Camelyon17 Avg
Avg
W-Rog
ERM
53.3 (0.1) 32.4 (0.3)
70.6 (1.6)
JTT
Liu al
2021
52.1 (0.1) 31.8 (0.2)
66.3 (1.3)
L.F
Nam
49.6 (0.2)
31.0 (0.3)
65.8 (1.2)
RWY
Knsai
50.8 (0.1) 30.9 (0.2)
69.9 (1.3)
Group DRO
Sagawa al
2019
51.9 (0.2)
30.4 (0.3)
68.5 (0.9)
CVaR DRO
Levy cl al
2020
51.5 (0.1)
31.0 (0.3)
66.8 (1.3)
BR-DRO (VIB) (ouns
$2.0 (0.2)
31.8 (0.2)
704 (1.5)
BR DRO (122 (ours
53.1 (0.1)
32,3 (0.2)
71.2 (1.0)
Table 2: Average (Avg) and worst region (W-Reg for FMoW) test accuracies on Camelyon17 and FMoW.
7 CONCLUSION
In this paper, we proposed a method for making machine learning models more robust. While prior methods optimize robustness on a per-example per-group basis, our work focuses on features. In doing so, we avoid requiring group annotations on training samples, but also avoid the excessively conservative solutions that might arise from CVaR DRO with fully unconstrained adversarics. Our results show that our method avoids learning spurious features, is robust to noise in the training labels, and does better on other forms of covariate shifts compared to prior approaches. Our theoretical analysis also highlights other provable benefits in some settings like reduced estimation error, lower excess risk and faster convergence rates for certain solvers.
While our method lifts the main limitation of Group DRO (access to training group annota- tions), it does so at the cost of increased complexity. Further, to tune hyperparameters, like prior work we assume access to some group annotations validation set but also get decent performance (on some datasets) with only a balanced validation set (see Appendix B Adapting group shift methods to more generic settings remains an important and open problem.
Limitations.

---

Published as a conference paper at ICLR 2023
Acknowledgement. The authors would like to thank Tian Li, Saurabh Garg at Carnegie Mellon University, and Yoonho Lee at Stanford University for helpful feedback and discussion.
REFERENCES
Jacob Abemethy, Kevin A Lai, Kfir Y Levy. and Jun-Kun Wang. Faster rates for convex-concut games. In Conference On Learning Theory, pp. 1595-1625. PMLR, 2018.
Alexander Alemi, lan Fischer, Joshua Dillon, and Kevin Murphy. Deep variational information bottleneck. arXiv preprint arXiv:/612.004100 2016.
Martin Arjovsky, Léon Botton, Ishaan Gulrajani, and David Lopez-Paz. Invariant risk minimization. arXiv preprint arXiv: 1907.02893 2019.
J Andrew Bagnell. Robust supervised leaming. In AAAL, pp. 714-719, 2005.
Yujia Bao and Regina Barzilay. Learning to split for automatic bias detection. arXiv preprint arXiv:2204.15 13749, 2022.
Peter L Bartlett, Sanjeev R Kulkami, and S Eli Posner. Covering numbers for real-valued function classes. IEEE transactions on information theory, 431511122111224, 1997.
Aharon Ben-Tal, Dick Den Hertog, Anja De Waegenaere, Bertrand Melenberg, and Gijs Rennen. Robust solutions of optimization problems affected by uncertain probabilities. Management Science, 59(2): 341-357, 2013.
Dimitris Bertsimas, Vishal Gupta, and Nathan Kallus. Data-driven robust optimization. Mathematical Programmingg 167(())235-29)) 292, 2018.
Jose Blanchet and Karthyek Murthy. Quantifying distributional model risk via optimal transport. Mathe- matics of Operations Research, 44(2):665-600, 2019.
Su Lin Blodgett, Lisa Green, and Brendan O'Connor. Demographic dialectal variation in social media: A case study of african-american english. arXiv preprint urXiv:/60..008 1608.0886, 2016.
Daniel Borkan, Lucas Dixon, Jeffrey Sorensen, Nithum Thain, and Lucy Vasserman. Nuanced metrics for measuring unintended bias with real data for text classification. Companion proceedings of the 2019 world wide web conference, pp. 491-500, 2019.
Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
Jonathon Byrd and Zachary Lipton. What is the effect of importance weighting in deep learning? In International Conference on Machine Learning, pp. 872-881, PMLR, 2019.
Nicholas Carlini, Ulfar Erlingsson, and Nicolas Papemnt. Distribution density, tails, and outliers in machine learning: Metrics and applications. arXiv preprint arXiv:1910.13422 2019.
Olivier Catoni. Pac-bayesian supervised classification: the thermodynamics of statistical learning, arXiv preprint arXiv:0712.02248. 2007.
Elliot Creager, Jörn-Henrik Jacobsen, and Richard Zemel. Environment inference for invariant learning. In International Conference Machine Learning, pp. 2189-2200. PMLR, 2021.
John Duchi, Peter Glynn, and Hongseok Namkoong. Statistics of robust optimization: A generalized empirical likelihood approach. arXiv preprint drXf::1610.03325, 2016.
John C. Duchi and Hongseok Namkoong, Leamiing models with uniform performance via distributionally robust optimization. The Annals of Statistics, 49(3):1378 1406, 2021. doi: 00.1214/20AAS2200 URL https:://oi.......oo
www/logg....... 1214/20-A0S2002
John Duchi, Tatsunori Hashimoto, and Hongseok Namkoong. Distributionally robust losses against mixture covariate shifts. Under review, 2019.
10

---

Published as a conference paper at ICLR 2023
Ian Goodfellow, Jonathon Shiens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint arXiv:1412.6572, 2014.
Peter D Grünnald. The minimum description length principle. MIT press, 2007.
Ishaan Guirajani and David Lopez-Paz. In search of lost domain generalization. arXiv preprint arXiv:2007.01434, 2020.
Tatsunori Hashimoto, Megha Srivastava, Hongscok Namkoong, and Percy Liang. Faimess without demographics in repeated loss minimization. In International Conference on Machine Learning, pp. 1929-1938. PMLR, 2018.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Devon Hjelm, Alex Fedorov, Samuel Lavoie- Marchilnn,, Karan Grewal, Phil Bachman, Adam Trischler, and Yoshua Bengio. Learning deep representations by mutual information estimation and maximization. arXiv preprint 1 2018.
Weihua Hu, Gang Niu, Issei Sato, and Masashi Sugiyama. Does distributionally robust supervised learning give robust classifiers? In International Conference on Machine Learning, pp. 2029-2037, PMLR, 2018.
Badr Youbi Idrissi, Martin Arjovsky, Mohammad Pezeshki, and David Lopez-Paz. Simple data balancing achieves competitive suun--rouup-ccurracy. In Conference on Causal Learning and Reasoning, pp. 336-351. PMLR, 2022.
Michael Kearn,, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. Preventing faimess gerrymandering: Auditing and learning for subgroup faimess. In International Conference on Machine Learning, pp- 2564-2572. PMLR, 2018
Polina Kirichenko, Pavel Izmailov, and Andrew Gordon Wilson, Last layer re-training sufficient for robustness to spurious correlations. arXiv preprint arXiv:2204.029.77 2022.
Pang Wei Koh, Shiori Sagawa, Henrik Marklund, Sang Michael Xie, Marvin Zhang, Akshay Balsubramani. Weihua Hu, Michihiro Yasunaga, Richard Lanas Phillips, Irena Gao, et al. Wilds: A benchmark of in-the-wild distribution shifts. In International Conference Machine Learning, pp. 5637-5664. PMLR, 2021.
Yoonho Lee, Huaxiu Yao, and Chelsea Finn. Diversify and disambiguate: Learning from underspecified data. arXiv preprint arXhv:2002.03418. 2022.
Daniel Levy, Yair Carmon, John Duchi, and Aaron Sidford. Large-scale methods for distributionally robust optimization. Advances in Neural Information Processing Systems, 33:8847-8860, 2020.
Da Li, Yongxin Yang, Yi-Zhe Song, and Timothy Hospedales. Learning generalize: Meta-leamiig for domain generalization. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018.
Zachary Lipton, Yu-Xiang Wang, and Alexander Smola. Detecting and correcting for label shift with black box predictors. In International conference machine learning, pp.
PMLR, 2018.
Anqi Liu and Brian Ziebart. Robust classification under sample selection bias. Advances in neural information processing systems, 27, 2014.
Evan Z Liu, Behzad Haghgoo, Annie S Chen, Aditi Raghunathan, Pang Wei Koh, Shiori Sagawa, Percy Liang, and Chelsea Finn. Just train twice: Improving group robustness without training group information. In International Conference on Machine Learning, pp. 6781-6792. PMLR, 2021.
Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes in the wild. In Proceedings of the IEEE international conference on computer vision, pp. 3730-3738, 2015.
Yiping Lu, Wenlong Ji, Zachary Izzo, and Lexing Ying. Importance tempering: Group robustness for overparameterized models. arXiv preprint 25940:2209.08745 2022.

---

Published as a conference paper at ICLR 2023
Oren Mangoubi and Nisheeth K Vishnoi. Greedy adversarial equilibrium: efficient altemative to nonconvex-nonconeee min-max optimization. In Proceedings of the 53rd Annual ACM SIGACT Symposhum Theory of Computing, pp. 396-909, 2021.
David A McAllester. Some pac-bayesian theorems. Proceedings of the eleventh annual conference on Computational learning theory, pp. 230-234, 1998.
Takeru Miyato, Shin-ichi Maeda, Masanori Koyama, and Shin Ishii. Virtual adversarial training: regularization method for supervised and eemi-supervieed learning. analysis and machine intelligence, 41(8):1979 1993. 2018.
IEEE transactions on pattem
Junhyun Nam, Hyuntak Cha, Sungsoo Ahn, Jaeho Lee, and Jinwoo Shin. Learning from failure: Di-binsing classifier from biased classifier. Advances Neural Information Processing Systems, 33:20673-20684, 2020.
Hongseok Namkoong and John C Duchi. Stochastic gradient methods for distributionally robust optimiza- tion with f-divergences. Advances in neural information processing systems, 29, 2016.
Yonatan Oren, Shiori Sagawa, Tatsunori B Hashimoto, and Percy Liang. Distributionally robust language 2019.
modeling. arXiv preprint
Nicholas Polson and Vadim Sokolov. Bayesian regularization: From tikhonov to horseshoe. Wiley Interdisciplinary Reviews: Computational Statistics, 11(4):e1463, 2019.
Hamed Rahimian and Sanjay Mchrotra. Distributionally robust optimization: review. arXiv preprint arXiv:1908.0566 2019.
Tyrrell Rockafellar Convex analysis, volume 18. Princeton university press, 1970.
Elan Rosenfeld, Pradeep Ravikumar, and Andrej Risteski. Domain-adjusted regression or: Erm may already learn features sufficient for out-of-distribution generalization. arXiv preprint arXiv:2202.06855 2022.
Shiori Sagawa, Pang Wei Koh, Tatsunori B Hashimoto, and Percy Liang. Distributionally robust neural networks for group shifts: On the importance of regularization for worst-case generalization. arXiv preprint arXiv:1911.0873., 2019.
Shiori Sagawa, Aditi Raghunathan, Pang Wei Koh, and Percy Liang. An investigation of why overparam- eterization exacerbates spurious correlations. In International Conference on Machine Learning, pp. 8346-8356. PMLR, 2020.
Seonguk Seo, Joon- Young Lee, and Bohyung Han. Unsupervised learning of debiased representations with pseudo-attributes. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 16742-16751, 2022.
Soroosh Shafieezadeh Abadeh, Peyman M Mohajerin Esfahani, and Daniel Kuhn. Distributionally robust logistic regression. Advances in Neural Information Processing Systems, 28, 2015.
Harshay Shah, Kaustav Tamuly, Aditi Raghunathan, Prateek Jain, and Praneeth Netrapalli. The pitfalls of simplicity bias in neural networks. Advunces in Neural Information Processing Systems, 33:9573-9585, 2020.
Nimit Sohoni, Jared Dunnmon, Geoffrey Angus, Albert Gu, and Christopher Ré. No subclass left behind: Fine- Fine-grained robustness in grained classification problems. Advances in Neural Information Processing Systems, 33:19339-19331 2020.
Hwanjun Song, Minseok Kim, Dongmin Park, Yooju Shin, and Jae-Gil Lee. Learning from noisy labels with deep neural networks: A survey. IEEE Transactions on Neural Networks and Learning Systems, 2022.
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent on separable data. The Journal of Machine Learning Research, 19(1)2822-299 2018.
12

---

Published as a conference paper at ICLR 2023
Naftali Tishby and Noga Zaslavsky. Deep learning and the information bottleneck principle. In 2015 ieee information theory workshop (itw), pp. 1-5. IEEE, 2015.
Mariya Toneva, Alessandro Sordoni, Remi Tachet des Combes, Adam Trischler, Yoshua Bengio, and Geoffrey Gordon. An empirical study of example forgetting during deep neural network learning. arXiv preprint arXiv:18/2.05159, 2018.
Catherine Wah, Steve Branson, Peter Welinder, Pietro Perona, and Serge Belongie. The caltech-uesd birds-200-2011 dataset. None, 2011.
Martin J Wainwright. High-dimensional statistics: A non-asymptotic viewpoint, volume 48, Cambridge University Press, 2019.
Ke Alexander Wang, Niladri S Chatterji, Saminul Haque, and Tatsunori Hashimoto. Is importance weighting incompatible with interpolating classifiers? arXiv preprint arXiv:2112.12986, 2021.
Junfeng Wen, Chun-Nam Yu, and Russell Greiner. Robust learning under uncertain test distributions: Relating covariate shift to model misspecification. International Conference on Machine Learning, pp. 631-639. PMLR, 2014.
Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, et al. Huggingface's 's transformers: State-of-the-ar natural language processing. arXiv preprint 11X1::1910.03771, 2019.
Huaxiu Yao, Yu Wang. Sai Li, Linjun Zhang, Weixin Liang, James Zou, and Chelsea Finn. Improving out-of-distributioo robustness via selective augmentation. arXiv preprint arXiv:220.000999 2022.
Runtian Zhai, Chen Dan, Arun Suggala, Zico Kolter, and Pradeep Ravikumar. Boosted evar classification.
Advances in Neural Information Processing Systems, 34:2 1860-28871, 2021.
Yuchen Zhang, John Duchi, and Martin Wainwright. Divide and conquer kernel ridge regression. In Conference learning theory, pp. 592-617. PMLR, 2013.
13


Reviews:
[{"review_id": "gKd2YnY7La", "reviewer": "Reviewer_WsDK", "summary": "", "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": "", "summary_of_the_paper": "This paper proposes bitrate-constrained DRO and makes a connection with the \"simple group shift\" conception. Specifically, they argue that this constrained DRO can distinguish between a rare group that is realized by simple functions and a rare group of examples that share no feature in common or may even be mislabeled, without knowing the group information in advance, and can thus improve the performance of neural networks by avoiding being too pessimistic. To support their result, they both give a theoretical generalization guarantee as well as many empirical experiments. In addition, they proposed a modified online game-based strategy to solve this optimization problem.", "summary_of_the_review": "This paper to me is slightly above the acceptance borderline because it provides a clean and well-defined framework, a good intuitive explanation, and convincing experimental results. But like I said above, its theoretical results are still relatively incremental and their justification on the connection between  \"simple group shift\" and \"bitrate-constrained distribution\" is a bit weak.", "strength_and_weaknesses": "Strength: This \"simple group shifted\" phenomenon is well-motivated and using this well-defined, easy-to-solve DRO to capture such phenomena without knowing group information is a clean framework and has been well-supported by experiments. (But I am not an empirical person so my evaluation of empirical results has low confidence). \n\nWeakness: \n1\\ All the theorem seem a bit incremental. Theorem 5.1 is a classical generalization bound analysis and 5.2 is s RKHS-specialized version. Theorem 5.4 highly relies on the assumption that $W(\\gamma)$ is Vapnik-Chervenokis (VC) class of dimension $O(\\gamma)$ and other standard techniques from  Abernethy et al. (2018) . But I think it is ok given it is not a purely theoretical paper.\n2\\ To me, the connection between \"simple group shift\" and \"bitrate-constrained distribution\" is a bit weak. Seems to me the group shift can violate the bitrate-constrained distribution and the bitrate-constrained distribution can also imply a non-group shift. Of course, I think the explanation from the paper is a good intuition... \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "RvvJHzEhA9f", "reviewer": "Reviewer_EndR", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "This paper proposes a new method for the problem of distributionally robust optimization. The learning procedure ‘Bitrate-Constrained DRO’ (BR-DRO) provides robustness to distribution shifts along groups realised by simple functions. This procedure is able to match the performance of methods that use group information on training samples, despite not actually using this information. \n\nIn comparison to prior works such as DRO, which generally optimizes for worst-case performance on distributions that lie in an f-divergence ball around the training distribution, BR-DRO further constrains the adversary’s class, while not requiring more information about the underlying group structure. Other approaches to constrain the adversary, the resulting set seems to still contain some mislabelled and hard instances from the majority set. Other works which seem to obtain group-robustness without group information either implicitly assume the group structure, or are vulnerable to label noise. \n\nTheir main theoretical result is an upper bound on the estimation error of the BR-DRO estimator in terms of the KL divergence from the prior. \n\nThey provide experiments comparing BR-DRO to ERM and other group shift robustness methods that do not require annotations for training samples. ", "summary_of_the_review": "I think this paper is good and vote to accept it. It introduces a novel constrained version of DRO which is performs as well as GROUP-DRO without the group information. The paper is well-written and provides experiments supporting this choice of modelling assumptions. \n\nOne interesting modelling assumption on the adversary they introduce, is that the adversary can only separate datapoints into potential groups using simple features. \n\n", "strength_and_weaknesses": "Strengths: \n1. BR-DRO has a well-motivated constraint and is amenable to clean theoretical analysis.\n2. BR-DRO performs well on the benchmark datasets and recovers the kind of guarantees GROUP-DRO achieves without using the group information. \n3. I think the paper is well-written and clear.\n\nWeaknesses: \n1. As expected, BR-DRO has higher complexity when compared to GROUP-DRO. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "JTWOQvhwpK0", "reviewer": "Reviewer_Pjrc", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "This paper proposes bit-rate constrained group DRO, where the assumption is that group identities can be modeled by a simple function class. This allows the framework to improve the overall utility of the learned model by relying less on arbitrarily chosen mis-labeled points (in a DRO framework), but ensure that only once that are also well modeled by the bit-rate constrained function are upweighted. Using the motivation, an objective is proposed to come up with a local minima where both the adversary and the hypothesis model is a neural network. Theoretical analysis provides risk bounds as well as analysis on convergence for online solver is provided. Experimental results demonstrate some benefit of the approach on real world data, including domain shift benchmarks.", "summary_of_the_review": "Overall, I am a little unsure about some modeling choices and practical utility of the paper. But I will look forward to the response and update my review accordingly.", "strength_and_weaknesses": "Strengths:\n1. The paper is largely well written and motivated. \n2. The problem setup is well motivated and being robust to unknown but well modeled group shift is an interesting approach to address lack of robustness of ML models to spurious correlations (if modeled as potential groups).\n\nWeaknesses:\nAlthough the paper is well written, there are many clarifications necessary that could improve the paper:\n1. I am guessing $z$ in Equation 5 corresponds to latent group identities? It seems to be introduced in a rush without explaining the objective function at all, leaving it to the reader to decipher details.\n\n2. Unclear motivation of why adversary needs to be a deep neural network and then add l-2 regularization to the parametrization. I would've liked to see a simpler set up where an exact solution is available, and then a heuristic proposed when adversary is also a complex model. It is also not clear how this ties to the assumption that the group identity function is actually a simple function.\n\n3. The latent group identification via KL regularization is interesting, but then I am a little confused what happens if the group identities somehow overlap with class labels themselves, guessing no real robust learning can happen then?\n\n4. Comparison of Theorem 5.1 to vanilla group DRO would be more informative.\n\n5. Same overall concern: What is the applicability of theorem 5.4 to the heuristic assumption of adversary being neural network with regularization added in the objective function.\n\n6. Empirical evaluation could also use more insights:\n   6.1 Are celebA results worse compared to other datasets for domain-specific reasons? If yes, why is the worst-group test accuracy lower for Bit-rate DRO always?\n   6.2 If the benefit of BR-DRO is more visible only with label noise, how practically useful is BR-DRO?\n   6.3 What are the groups used by group DRO vs BR-DRO and how is that affected by the choice of regularization, beyond the fact that higher regularization will constrain the function to be less complex.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "BMy4Q_LPSJ", "reviewer": "Reviewer_BZ25", "summary": "", "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": "", "summary_of_the_paper": "Distributionally robust optimization methods are often overly convservative, while group DRO approaches requires group annotations, which limits its practicality. To address this challenge, they introduce a practical assumption that group shift is captured by high-level features with a simple function. Based on this assumption, the authors propose a BR-DRO, which makes the model to be robust against distribution shifts along group which is realized by simple functions. This helps model not to be overly conservative while being robust to plausible worst cases, resulting in meaningful performance improvement compared to unconstrained DRO.", "summary_of_the_review": "The authors constrains the distributionally robust optimization method under the assumption of group shift, which prevents the model from being overly conservative and pessimistic. The practical relaxation of BR-DRO is novel and well supported by experimental results, though those are not that strong compared to recent debiasing approaches. Additional discussions with other robust optimization approaches can help for better understanding.", "strength_and_weaknesses": "Strength\n- The paper address why restricted adversary for DRO do better than unconstrained one, which is supported by theoretical justification under the assumption of simple group shift.\n- The proposed BR-DRO framework is empirically validated by extensive experiments.\n\nWeakness\n- Several important unsupervised comparisons are missing. Especially, [George] and [BPA] extend Group DRO in an unsupervised way, where they conduct clustering on the feature space and identify latent subclass (minority group). In other words, they also aim to identify potential groups for worst-case robustness without group annotations.\n- The formulation of BR-DRO starts from Assumption 4.2, but what is the motivation of the assumption? Also, I think it may be applied well because most of group robustness datasets has binary (bias) attributes, Does this simple group shift assumption still work well in datasets where the bias attribute has multiple values?\n\n[George] No Subclass Left Behind: Fine-Grained Robustness in Coarse-Grained Classification Problems, NeurIPS 2020\n\n[BPA] Unsupervised Learning of Debiased Representations with Pseudo-Attributes, CVPR 2022", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster