Topology-aware Robust Optimization for Out-of-Distribution Generalization
Authors: Fengchun Qiao
Xi Peng
Venue: ICLR 2023 poster (2023)
Keywords: out-of-distribution generalization
distributionally robust optimization

Abstract: Out-of-distribution (OOD) generalization is a challenging machine learning problem yet highly desirable in many high-stake applications. 
Existing methods suffer from overly pessimistic modeling with low generalization confidence. As generalizing to arbitrary test distributions is impossible, we hypothesize that further structure on the topology of distributions is crucial in developing strong OOD resilience. To this end, we propose topology-aware robust optimization (TRO) that seamlessly integrates distributional topology in a principled optimization framework. More specifically, TRO solves two optimization objectives: (1) Topology Learning which explores data manifold to uncover the distributional topology; (2) Learning on Topology which exploits the topology to constrain robust optimization for tightly-bounded generalization risks. We theoretically demonstrate the effectiveness of our approach, and empirically show that it significantly outperforms the state of the arts in a wide range of tasks including classification, regression, and semantic segmentation. Moreover, we empirically find the data-driven distributional topology is consistent with domain knowledge, enhancing the explainability of our approach. 

Published as a conference paper at ICLR 2023
TOPOLOGY-AWARE ROBUST OPTIMIZATION FOR OUT-OF-DISTRIBUTION GENERALIZATION
Fengchun Qiao
Xi Peng University of Delaware x peng@udel edu
University of Delaware fengchune udel edu
ABSTRACT
Out-of-distribution (OOD) generalization a challenging machine learning prob- lem yet highly desirable in many high-stake applications. Existing methods suffer from overly pessimistic modeling with low generalization confidence. As generaliz- ing to arbitrary test distributions is impossible. we hypothesize that further structure on the topology of distributions is crucial in developing strong OOD resilience. To this end, we propose topology-awan aware robust optimization (TRO) that seamlessly integrates distributional topology in a principled optimization framework. More specifically, TRO solves two optimization objectives: (1) Topology Learning which explores data manifold to uncover the distributional topology: (2) Learning on Topology which exploits the topology to constrain robust optimization for tightly- bounded generalization risks. We theoretically demonstrate the effectiveness of our approach, and empirically show that it significantly outperforms the state of the arts in wide range of tasks including classification, regression, and semantic seg- mentation. Moreover, we empirically find the data-driven distributional topology is consistent with domain knowledge, enhancing the explainability of our approach.
INTRODUCTION
Recent years have witnessed surge of applying machine learning (MI.) in high-stake and safety- critical applications. Such applications pose an unprecedented out-of-distribution (OOD) general- ization challenge: ML models are constantly exposed to unseen distributions that lie outside their training space. Despite well-documented success for interpolation, modern ML models (e.g., deep neural networks) are notoriously weak for extrapolation; a highly accurate model on average can fail catastrophically when presented with rare or unseen distributions (Arjovsky et al. 2019). For example, a flood predictor, trained with data of 89 major flood events in the U.S. from 2000 to 2020, would erroneously predict event "Hurrccane Ida" in 2021. Without addressing this challenge, it is unclear when and where a model can be applied and how much risk is associated with its use.
A promising solution for optimization (DRO) (Namkoong & Duchi 2016 Staib & Jegelka 2019: Levy et al., 2020). DRO minimizes the worst-case expected risk over an uncertainty of potential test distributions. The un- certainty set is typically formulated as a divergence ball surrounding the training distribution endowed with certain distance metric such f-divergence (Namkoong & Duchi (0166) and Wasserstein dis- tance (Shafieezadeh Abadeh et al., 2018). Compared to empirical risk minimization (ERM) (Vapnik) 1998) that minimizes the average loss, DRO is more robust against distributional drifts from spurious correlations, adversarial attacks, subpopulations, or -occurring variation (Robey et al. 2021).
generalization is to conduct distributionally robust
However, is non-trivial to build a realistic uncertainty set that truly approximates unseen distribu- tions. On the one hand, to confer robustness against extensive distributional drifts, the uncertainty set has to be sufficiently large, which increases the risks of conferring implausible distributions, e.g., outliers, and thus yielding overly pessimistic models with low prediction confidence (Hu et al.) 2018 Frogner et al. 2021). On the other hand, the worst-case distributions are not necessarily the influential ones that are truly connected to unseen distributions; optimizing over worst-case rather than influential distributions would yield compromised OOD resilience.
The source code and pre-trained models available https:///g thub. com jombbccc///offf//////////

---

Published as a conference paper at ICLR 2023
As generalizing to arbitrary test distributions is impossible, hypothesize further structure on the topology of distributions crucial in constructing a realistic uncertainty set. More specifically, we propose topology-award robust optimization (TRO) by integrating two optimization objectives: (1) Topology learning: We model the data distributions as many discrete groups lying on a common low-dimensional manifold, where we can explore the distributional topology by either using physical priors or measuring multiscale Earth Mover's ' Distance (EMD) among distributions.
(2) Learning on topology: The acquired distributional topology then exploited construct realistic uncertainty set, where robust optimization is constrained to bound the generalization risk within a topology graph, rather than blindly generalizing to unseen distributions.
Our contributions include: 1. A new principled optimization method that seamlessly integrates topological information to develop strong OOD resilience. Theoretical analysis that proves our method enjoys fast convergence for both convex and non-convex loss functions while the generalization risk tightly bounded. 3. Empirical results in wide range of tasks including classification, regression, and semantic segmentation that demonstrate the superior performance of our method over SOTA. 4. Data-driven distributional topology that consistent with domain knowledge and facilitates the explainability of our approach.
2 PROBLEM FORMULATION AND PRELIMINARY WORKS
The problem of out-of- disttribbtiion (OOD) generalization is defined by pair of random variables (X, Y) over instances I E X C R and corresponding labels E V/ following an unknown joint probability distribution P(X, Y). The objective is to learn predictor f E F such that f(z) + for any (x. v) ~ P(X,Y), Y). Here F is a function class that is model-agnostic for a prediction task. However, unlike typical supervised learning, the OOD generalization is complicated since one cannot sample directly from P(X, Y). Instead, it is assumed that we can only measure (X, Y) under different environmental conditions
that data is drawn from set of groups &all such that (x. (X, Y). For example, in flood prediction, these environmental conditions denote the latent factors (e.g., stressors, precipitation, terrain, etc) that underlie different flood events. Let Eurain & Eall be a finite subset of training groups (distributions), given the loss function f, an OOD-resilient model can be learned by solving minimax optimization:
min JEF
R(f)==
sup (cea)--P(Xx,)1((()))..))) eEE.
(1)
Intuitively, Eq. aims to learn a model that minimizes the worst-case risk over the entire family Ean- It is nontrivial since we do not have access to data from any unseen distributions Evest Ean E
Empirical Risk Minimization (ERM). Typically, classic supervised learning employs ERM (Vapnik 1998) to find model f that minimizes the average risk under the training distribution Par:
min(R = E(,,)) ((] [(((()))))) JEF
Though proved be effective in i.i.d. settings, models trained via ERM heavily rely on spurious correlations that do not always hold under distributional drifts (Arjovsky et al. 2019).
Distributionally Robust Optimization (DRO). To develop OOD resilience, DRO (Namkoong
Duchi 2016) minimizes the worst-case risk over an uncertainty set Q by solving:
min /EF
MiinRRb
(R())=
sup QEP(P.-)
B(x.))= (()p))/@((((()))))))))))))))))))
Here the uncertainty set Q approximates potential test distributions. It usually formulated as a diver-
gence ball with a radius of p surrounding the training distribution P (Pt))= (Q. P.r < p) endowed with certain distance metric D(.,.) such as f-divergence (Namkoong & Duchi 2016
or Wasserstein distance (Shaficezadch Abadeh et al., 2018). To construct a realistic uncertainty set without being overly conservative, Group DRO is further developed formulate the uncertainty set as the mixture of training groups (Hu et al. 2018 Sagawa et al. 2019).
Despite the well-documented success, existing DRO methods suffer from critical limitations. (1) To endow robustness against a wide range of potential test distributions, the radius of the divergence ball has to be sufficiently large with high risks of containing implausible distributions; optimizing
2

---

Published as a conference paper at ICLR 2023
for implausible distributions would fundamentally damage the OOD resilience by yielding overly- pessimistic models with low prediction confidence. (2) The worst-case groups are not necessarily the infiuential ones that are truly connected to unseen distributions; optimizing over worst-case rather than influential groups would yield compromised OOD resilience.
3
TOPOLOGY-AWARE ROBUST OPTIMIZATION
We propose new principled optimization method (TRO) to develop OOD resilience, which integrates topology and optimization via a two-phase scheme: Topology Learning and Learning on Topology.
3.1 TOPOLOGY LEARNING: EXPLORE THE DISTRIBUTIONAL TOPOLOGY
We model the data groups Eall as many discrete distri- butions lying on a common low-dimensional manifold high-dimensional data measurement space. such case their structure, i.e. distributional topology, can be naturally captured by graph G = E), where the entities V De Xe symbolize the groups and the edges E represent interactions among groups. The topol- ogy graph constructed by: (1) identifying entity: assume the entities are defined by the given group iden- tities; and (2) uncovering interactions: we consider two scenarios to measure the connectivity between discrete distributions illustrated Fig
Distributed Datasets
PIENT
PUENT
Prysical
Data
(o o a)
(o Deckr
Multicale Utftusion Denuity Estimates
Physical-based Topeloay
Physical-basee distributional topology. In the sce- nario where the distributional adjacency information is available, we can instantly acquire the topology Ophysic by simply imposing the predefined neighborhood infor- mation. For example, to capture the similarity of weather events in the U.S., one can construct a graph where each state realizes an entity, and the physical adjacency be-
Pricr
Data- Bola-driven Topology
TRO
Prior
Diflusion EMD
Figure I: Overview of topology-aware dis- tributionally robust optimization (TRO).
tween two states results in an edge (see Fig. D. In this case, Ophyssc functions as a physical prior to constrain the robust optimization introduced in Sec. 3.22
3.2. We empirically find Gphysic yields an
improvement of 9.56% over the state of the art regarding OOD generalization reported in Sec. 5.1
Data-driven distributional topology. In the absence of Gphysics we propose data-driven approach to learn the topology Gdata from training data. Specifically, we embed the individual groups onto a shared data graph based (2016), such data graph can be viewed as discretization of an underlying Riemann closed manifold. By simulating a time-dependent diffusion process over the graph, we will obtain density estimates at multiple scales for each group, which will be used to calculate & distances between two groups. Such multiscale & distance has been proved to be topologically equivalent to the Earth Mover's Distance (EMD) on the manifold geodesic, but cutting down the computational complexity from O (m?n3) to Ö (mm) between m distributions over data points (Tong al. 2021
affinity matrix of the combined data. Inspired by Leeb & Coifman
We obtain the data-driven topology through three steps: (1) Data graph construction: we construct a data graph through an affinity matrix K of the combined data. K can be implemented through kernel functions (e.g., RBF kemne)) which capture the similarity of data. Instead of calculating the similarity between raw data, we calculate the similarity between features extracted from an ERM-ttained model as it captures spurious correlations which preserve group identity (Creager et al., 202T). Specifically, we define the affinity matrix as: K., = exp (-11s(z;) - (fx;))l²/o²) where o² is the kernel scale. (2) Multiscate diffusion density estimation: to simulate the diffusion process over the graph, we obtain a Markov diffusion operator P from K. Following Coifman & Lafon (2006), we normalize the affinity matrix: M = Q ''K where Q diagonal matrix and Q Σ, K.j. The diffusion operator is defined as P = D- where D is a diagonal matrix and D E,M., The operator P will be used to approximate the multiscale density estimates μa for each data group X.: 14: me
1 _P'1x. x where i is the diffusion time, P denotes the (-th power of P. and 1 x. the
3

---

Published as a conference paper at ICLR 2023
indicator function for group Intuitively, P sums the probabilities of all possible paths of length t between 24 and 2-- By taking multiple powers of P, He reveals the topological structure of X follow Tong al. (2021) to measure the geodesic distance Wa, (Xe, X between X. and Xe by aggregating the & distances between the multiscale density estimates:
at multiple scales. (3) Diffusion EMD measurement:
Wo. =
Σ IT (Xx) Ta (x
(3)
where a is used to balance long- and short-range distances, K is the maximum scale, and (2h+1)
2- 2-(K-N-1)a
pe
pee (2a))
K
Ta (Xc)=
(2*)
k h= K
Although Gdota is computationally more expensive than Gphysic. experimental results in Sec. 5.2 indicate that optimizing with Gdata can yield improved OOD resilience. Besides, the ablation study in Sec. 5 also indicates that Gaata is consistent with domain knowledge and enhances the explainability of TRO. Last but not least, the data-driven method is fully differentiable, making it amenable to jointly conducting topology learning and learning topology in end-to-end manner. We leave this as future work.
3.2 LEARNING ON TOPOLOGY: EXPLOIT TOPOLOGY FOR ROBUST OPTIMIZATION
Next, we propose principled method that in- tegrates distributional topology to develop TRO. The key challenge is how to leverage to con- struct a uncertainty set which can approximate unseen distributions with bounded generalization risk. Our main idea is to assess the group cen- trality of training distributions. Graph centrality is widely used in social network analysis (New- man 2005) to measure how much information propagated through each entity. Here we in- troduce group centrality to identify influential groups that are truly connected to unseen dis- tributions, which can be calculated using graph measurements (Tian et al. (019) such degree, betweenness, and closeness. More specifically, first calculate the centrality of each entity in g as a lopological prior p to identify influen- tial groups. Then, we construct the uncertainty set as an arbitrary mixture of training groups Q = (E Pa q E Am) where qe de- notes the weight of group e, Pe is the distribution of group e, and Am a (m -)-dimensional probability simplex. Finally, we use the prior p to constrain the uncertainty set Q by solving the minimax optimization problem as:
Algorithm 1: TRO Algorithm
Input: Data of E Step sizes 170 and 17q Output: Learned model f Topology Learning:
if 9 Gphysie exists then
9 + 9physic
else
Obtain the affinity matrix K from data
Q Diag E Kij
M < Q-'KQ-
D < Diag Σ, Miy)
P- D-D-MM
Obtain Gdtta via Eq.
g Gdata
end
Learning Topology:
Calculate topological prior p from G while not converged do
Sample (æ. 1)) ~ Pe (X, Y)
Ve E Evain
Calculate R q) via Eq
Update 0 and q via Eq.
end
min (in. == max PEF
-ee. v)), s.t. D(qllp) ST.
(4)
qE
eEEini
Intuitively, groups with high training loss and centrality will be assigned with large weights; this can tightly bound the OOD generalization risk within a topological graph. D is an arbitrary distributional distance metric. We use Eg distance to implement D due to its strong convexity and simplicity.
However, solving Eq. 4 often leads to a non-convex problem, wherein methods such as stochastic gradient descent (SGD) cannot guarantee constraint satisfaction (Robey al. 2021). To address this
4

---

Published as a conference paper at ICLR 2023
issue, leverage Karush- Tucker conditions (Boyd et al. 2004) and introduce Lagrange
multiplier to convert the constrained problem into its unconstrained counterpart:
min ( q) = max FEF
Σ ge B...))-.....))(((()))) XD(q))))
(5)
qea.
r'Emii
where À is the dual variable. Let 0 E O be the model parameters of f, we can solve the primal-dual problem effectively by alternatively updating:
0-+1= = - -
q), q't! = (q + V V R(f.g))
(6)
where ná (1%) is gradient descent (ascent) step size. Pan (q) projects onto simplex Am for regularization. The overall algorithm TRO is shown Alg. In Sec. we show TRO enjoys fast convergence for both convex and non-convex loss functions, while the generalization risk is tightly bounded with topological constraints. We empirically demonstrate TRO achieves strong OOD resilience by striking a good balance between the worst-case and influential groups (see Sec. (.2).
Calculation of group centrality. We use betweemness centrality to measure the centrality groups. Betweenness centrality measures how often entity is on the shortest path between two other entities the topology. |Freeman| (1977) reveals that entities with higher betweenness centrality would have more control over the topology as more information will pass through them. For physical-basee baased topology Ophysic we define the centrality of group e by computing the fraction of shortest paths (aadee)
that pass through it: ophysic EsEEum. a(s,8) where (s,, t) is the number of shortest paths between groups s and in the graph ((s, ()paths,,,, and (s, t. e) is the number of (8, 1)-paths that go through group Intuitively, cplgoss measures how much information is propagated through from the start (training) to the end (test). For data-driven topology Gdates the underlying assumption is that training groups with high centrality also exert strong influence unseen groups. Instead of sampling group pairs from two separate sets, we sample (s, t) from Euain. The centrality is modified as: data =
alatte) We use softmax function to normalize c. and the prior probability for - o(8,2)
group E Evran is defined as: Pe = exp(ce)/ (aae)//ees... Eese.... exp(ce).
4 THEORETICAL ANALYSIS
4.1 CONVERGENCE ANALYSIS
In this section, we show that by choosing appropriate step sizes 1/ and n/4 TRO yields fast convergence rates for both convex and non-convex loss functions. We first state the assumptions of the theorems. Next, we give the convergence rate for convex loss functions in Theorem and the convergence rate for non-convex loss functions in Theorem 2.
Definition (Lipschitz continuity) A mapping f X - R. G-Lipschitz continuous for any y X. [f) f())l s G|| yll- Definition (Smoothness) A function f : + is L-sohhth if it is differentiable on X' and the gradient V f is L-Lipschitz continuous, i.e., |/ [<x) V ( || < L - wlll for all y E X. Assumption We make the following assumptions throughout the paper: Given 8, the loss function ((fo())) y) is G-Lipschitz continuous and L-smooth with respect to
Convex Loss. The expected number of stochastic gradient computations utilized to estimate the convergence rate. To reach duality gap of (Nemirovski al. 2009), the optimal rate of convergence for solving the stochastic min-max problems is O (1/c²) if it is convex-concave. The duality gap of the pair (0, q) is defined as maxyesm R(θ,q) minsge R(0, q). In the case of strong duality, (9, q) is optimal iif the duality gap zero. We show TRO achieves the optimal (1/e2) rate. Theorem 1. Consider the dual problem in Eq. when the loss function is convex and Assumption I
holds. Let e bounded by Re, E R ②) 12
G2 and E
V R < G With step
sizes d10 = 2Re/ (GovT) and Ml 2/ (G,TT) the output of TRO satisfies:
3R + 3G,
max R (0r:9)= 9
min R (0, (T) d0e
<
/T
5

---

Published as a conference paper at ICLR 2023
Theorem shows that method requires T = 0 iterations to reach duality gap within
To derive the convergence rate for non-convex functions.. we define e-stationary points as follows: Definition 3. (e-stationary point) For a differentiable function X R. point X is said to be first-order e-stationary if V fx(x) <.
Nonconvex Loss. The loss function {(f((z)) y) be nonconvex and result, R(0,g) is nonconvex in O. Following Collins al. (2020), define (0, q) is an (e, -sstatioonyyy point of R. if: and R( 9) 2 maX45A.. R(0,g) 9) 6, where e, 8 0.
(o. 9) ||,
Theorem 2. If Assumption holds and the loss function is bounded by B and is M-smooth, the satisfies:
output of Alg. [
R (00 .q) + B
2gvTBBG
Mo
(Or, I
+
Tne
110
2
(8)
Gg
E R (Or, 9r))
max ( [R (fr, 7)]
g
nTT
Theorem 2 shows that method converges in expectation to an (e, 8) --sttioinn point of R. in (L//** stochastic gradient evaluations.
4.2 GENERALIZATION BOUNDS
In this section, we provide learning guarantees for TRO. Compared to DRO, TRO achieves lower upper bound on the generalization risks over unseen distributions with the topological constraint.
Let H denote the family of losses associated with hypothesis set F H {(x, y) + ((f()), (()),)) v)
f E F). and n (Ni,.... Rem) denote the vector of sample sizes for all training groups Follow- ing Mohri et al. (2019), define weighted Rademacher complexity for any F as:
Ru (H.,
E E sup SEF
qe
Je a (Fe,e yee.))
S.-P.o
The i=1
where e denotes group index, S. a sample of size The Pa the distribution of group e, and (sm)))ea a collection of Rademacher variables. The minimax weighted Rademacher complexity for subset C Am defined by R, (H, A) = max Rr (H, where n = Σ Tie Let PA be the distribution over the mixture of training groups and PA be its empirical counterpart. Let the distribution of some test group be P. The learning guarantee for P is shown in Theorem 3.
Theorem 3. Assume the loss function is bounded by B. For any 2 0 and 5 > 0, with probability least 1 8, the following inequality holds for all f E F:
1 [A| Rr(f) & RRp,, (U.9) + (H, + BD(P)PPA) BV log 2m 8
The upper bound of the generalization risk on P is mainly determined by its distance to PA: D Pa). With the topological prior. risks on P can tightly bounded by minimizing PA). as long as P falls into the convex hull of training groups. We empirically verify the effectiveness of the topological prior in minimizing the generalization risks over unseen distributions (see Sec. 55.
EXPERIMENTS
We evaluate TRO in wide range of tasks including classification, regression, and semantic segmen- tation. We compare TRO with SOTA baselines on OOD generalization and conduct ablation study on the key components of TRO. Following Gulrajani & Lopez Paz (2021), perform model selection based on a validation set constructed from training groups only. We provide implementation details
in Appendix 7.2 and results DomainBed (Gulrajani & Lopez- Paz 2021 in Appendix 7.3
Baselines. We compare TRO with the following methods: (1) Empirical Risk Minimization
(ERM) [Vapnik] 1998;; (2) Group distributionally robust optimization (DRO) (Sagawa al.) 2019); (3) Invariant Risk Minimization (IRM) (Arjovsky et al. 2019] (4) Risk Extrapolation (REx) Krueger
al. 202T ; (5) Spectral Decoupling (SI) (Pezeshki et al. 2021

---

Published as a conference paper at ICLR 2023
Table Accuracy (%) on DG-15 and DG-60, TRO sets the new SOTA on both DG-15 and DG-60.
ERM 58,00
IRM
REx
SD
DRO
TRO (physical)
TRO (data)
DG-15 DG-60
57.87
57.22
57.56
43.22
67.89 67.56 89.19
76.02
76.61
86.89
81.04
79.59
90.72
Group ID
Group
Cless
O Tosi
Test
Class
Class 0
(a) DG-15
(b) DG-60
Figure 2: Illustration of data groups in (a) DG-15 and (b) DG-60 datasets.
Group Importance DRO
Group Importance TRO
Imporance
ACC: 43.22%
ACC: 67. 57.56%
Figure Group importance of DRO and TRO on DG-15. DRO assigns the highest weight to the worst-case group "I" which is the furthest group to the test groups while TRO focuses on the inftuential groups "2", "5", and "6", which are truly connected to test groups.
5.1 CLASSIFICATION
Datasets. DG-15 (Xu et al. 2022) is a synthetic binary classification dataset with 15 groups. Each group contains 100 data points. In this dataset, adjacent groups have similar decision boundaries. Following Xu et al. (2022). we use six connected groups as the training groups, and use others as test groups. Note that, different from Xu et al. (2022) which focuses
domain adaptation, the data of test groups are unseen in OOD generalization. DG-60 (Xu et al.) 2022) is another synthetic dataset generated using the same procedure as DG-15, except that contains 60 groups, with 6,000 data points in total. We randomly select six groups as the training groups and use others as test groups. Visualization DG-15 and DG-60 are shown Fig. (a) and (b), respectively.
The results of DG-15 15 and DG-60 are summarized in Tab. [ In both datasets, our method yields the highest accuracy. visualize the decision boundary of DG-15 and DG-60 in Appendix 7.3
Results.
DG-15, we show the detailed results of all groups in Fig. g We
Ablations study. TRO significantly improves the generalization performance by discovering influen- tial groups. To investigate the reason why TRO outperforms DRO, we show group weights q of DRO and TRO on DG-15 in Fig. 3 DRO assigns the highest weight to group "/" which the furthest group to test groups. Instead, TRO prioritizes influential groups "2", "5", and "6" which truly connected to the test ones, yielding improved performance on unseen distributions.
5.2 REGRESSION
Datasets. TPT-48 (Vose et al. 2014) contains the monthly average temperature for the 48 contiguous states in the US from 2008 to 2019. We focus on the regression task to predict the next 6 months' temperature based on the previous first months' temperature. We consider two generalization tasks: (1) E(24) + W(24): we use the 24 eastern states as training groups and the 24 western states test groups; (2) N(24) + S(24): we use the 24 northern states as training groups and the 24 southern states test groups. Test groups
hop away from the closest training group defined Hop- 1 test groups, those two hops away are Hop-2 test groups, and the remaining groups are Hop-3 test groups. The visualization of N(24) S(24) TPT-48 shown in Fig. 4 (left).
7

---

Published as a conference paper at ICLR 2023
Table 2: Mean Squared Error (MSE) for both tasks (24) + W (24) and N (24) + S (24) on TPT-48.
TRO (data-driven topology) consistently outperforms TRO (physical-banl based topology) in both tasks, indicating the data-driven topology captures the distributional relation more accurately.
Task
Group
ERM
IKM
REs
SD
DRO
TRO (physical)
TRO (ditta)
Avenge of Hop-1 groups
1.693
1,699)
1.577
1.701
1,678
1.445
1.435
Avenaee Hop-2 groupe
1.800
1,811
1.702
1.806
1,762
1.576
1,569
(24)) (24)
Average of Hop-3 groups
1.672
1,679
1.584
1.674
1,628
1,400
1.392
Average of All test groups
1,716
1,724
1.616
1.722
1,684
1.466
14588
Avenge Hop-1 groups
0.487
0.855
N (24)-S (24)
Average of 2op groups
1.265
1,312
0.944
1.354
1.170
0.991
0.950
Average Hop-3 groups
2.266
Average All test groups
1,426
1.474
1.194
1,523
1.356
1.177
1.129
Generaliationn Task of North South
Physical- based Disiibttionl Topoiogy
Data-driven D Diniibttonaly Topology
Tonn
MSE: 1.177
MSE
Figure 4: Left: Generalization task of North - South TPT-48. Middle: Group centrality of physical-based topology. Right: Group centrality of data-driven topology. "PA" is identified by TRO the influential group in physical-basee topology; "NY", "PA", and "MA" are identified by TRO as inftuential groups in data-driven topology. Data topology yields lower MSE than physical topology.
Group importance of DRO
Group Importancs ahar Topaiogy Learning
importance after Leoming Topology
MSE: 1,368
1,828
Figure 5: Group importance of DRO and TRO the North - South task. TRO significantly reduces the generalization risks by not only prioritizing the worst-case groups but also the influential ones.
Results. We show the results of 7P7-48 in Tab. 2 TRO yields the lowest average MSE on both tasks. We also report the average MSE of H, 2 and Hop-3 3 test groups for both tasks. Although REx yields the lowest error on Hop-1 and Hop-2 groups in N (24) - (24), yields the highest prediction еигог Hop-3 groups. The results indicate that REx may yield compromised performance under large distributional drifts. TRO yields the best performance on Hop-3 groups, indicating its strong generalization capability under large distributional drifts.
Ablations study. (1) Data-driver topology yields better performance than physical- topology.
We show group centrality of both physical and data topology the task of North - South in Fig, 4 topology; "NY", "PA", and
"PA" is identified by TRO as the inftuential group in physical- "MA" are identified by TRO influential groups in data-driven topology. The results prove that the influential groups in data topology are more effective in minimizing the generalization error.
(2) Strong OOD resilience of TRO comes from the synergy of the worst-ease and inftuential groups To investigate which components contribute to the superior performance of TRO. We build simple baseline based on ERM: we directly use the group importance acquired from the topology to weight training groups and the weights are fixed during the training. We name this baseline as importance weighted ERM (IW-ERM). We show the results of "N(24)-+S(24) on TPT-48 in Tab. The results of IW-ERM are inferior to ERM and DRO, possibly because IW-ERM merely considers influential
Table 3: MSE on TPT-48. Ignoring either the worst-case (IW-ERM) or influential (DRO) groups would yield compromised performance.
Hop-I Avg.
Hop-2 Avg.
Hop-3 Avg.
Avg.
ERM
1,084
1.265
1.975
1.426
IW-ERM
1.320
1.604
2.635
1.829
DRO
0.931
1.170
2.027
1.356
TRO
0.855
0.950
1.604
1.129
8

---

Published as a conference paper at ICLR 2023
FLOCO
2012 DOL FLOCO
Figure 6: Left: Location of the 11 flood events on Sen 1. We use the event "BOL" for testing and other events for training. Right: Data-driven distributional topology on Sen Fen/Floods]1 I. (1) "IND" and "NGA" are identified by TRO as the most influential groups. A possible explanation is that both "IND" and "NGA" are aroused by heavy rainfall, most prevalent disaster that causes floods. (2) "GHA" and "KHM" are identified by TRO as the least influential groups. A possible explanation is that both "GHA" and "KHM" are aroused edge cases such as dam collapse. The data-driven distributional topology is consistent with domain knowledge and facilitates the explainability of TRO.
groups. We further show the group importance of DRO and TRO in Fig. 5 the generalization risks by not only prioritizing the worst-case groups but also the influential ones.
TRO significantly reduces
5.3 SEMANTIC SEGMENTATION
Datasets.
Floodloods! / (Bonafilia al. 2020 is public dataset for flood mapping at the global scale. The dataset provides global coverage of 4,831 chips of 512 x 512 10m satellite images across 11 distinct flood events, covering 120,406 km Each image associated with its pixel-wise label. Locations of the 11 flood events are shown in Fig. 6 (left). Flood events vary in boundary conditions, terrain, and other latent factors, posing significant OOD challenges to existing models in terms of reliability and explainability. Following Bonafilia et al. (2020), event "BOL" is held out for testing, and data of other events are split into training and validation sets with a random 80-20 split.
ERM
IRM
REx
SD
DRO
TRO (data)
Val
.489
.387
.484
.449
.480
.485
Test
.430
.338
.357
.400
.433
.450
Table 4: Segmentation results (IoU) Sen / Floods I. TRO yields better performance than other baselines on unseen flood events.
320 C1 Lagrange
300
Figure 7: Ablation study on X. IoU remains stable for wide range of X.
Results. We show the results of Sen/Floods in Tab. 4 ERM achieves the highest IoU the validation set while TRO achieves the highest IoU on the test set. The results prove that TRO yields better performance than other baselines on unseen flood events.
Ablations study. (1) Data-driven distributional lopology is consistent with domain knowledge.
We visualize the distributional topology well group centrality in Fig. 6 (right). The learned distributional topology is consistent with domain knowledge, enhancing the explainability of TRO. (2) Ablation study on We report IoU under different À on Senl Floods]1 in Fig. IoU remains stable for a wide range of X, and X = 0.01 yields the best performance.
6 CONCLUSION
In this paper, we proposed new principled optimization method that seamlessly integrates topological information to develop strong OOD resilience. Empirical results in wide range of tasks including classification, regression, and semantic segmentation demonstrate the superior performance of our method over SOTA. Moreover, the data-driven distributional topology consistent with domain knowledge and facilitates the explainability of our approach.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENTS
This work is partially supported by National Science Foundation (NSF) CMM1-2039857, General University Research (GUR), and University Delaware Research Foundation (UDRF). The authors would like to thank Kien X. Nguyen for helping with the experiments on DomainBed.
REFERENCES
Martin Arjovsky, Léon Bottou, Ishaan Gulrajani, and David Lopez-Paz, Invariant risk minimization. arXiv preprint arXiv:1907.0289) 2019.
Sara Beery, Grant Van Horn, and Pietro Perona. Recognition in terra incognita. In Proceedings of the European conference computer vision (ECCV), pp. 456-473, 2018.
Derrick Bonafilia, Beth Tellman, Tyler Anderson, and Erica Issenberg. Sen floodsl 1: A georefer- enced dataset train and test deep learning flood algorithms for sentinel-1. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops, pp. 210-211, 2020.
Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
Ronald R Coifman and Stéphane Lafon. Diffusion maps. Applied and computational harmonic analysis, 21(1):5-30, 2006.
Liam Collins, Aryan Mokhtari, and Sanjay Shakkottai. Task-robust model-agnostic meta-learning. Advances in Neural Information Processing Systems, 33: 33:10080-1887, 2020.
Elliot Creager, Jörn-Henrik Jacobsen, and Richard Zemel. Enviromment inference for invariant learning. International Conference on Machine Learning, pp. 2189-2200. PMLR, 2021.
Erick Delage and Yinyu Ye. Distributionally robust optimization under moment uncertainty with application to data-driven problems. Operations research, 58(3):595 612, 2010.
John C Duchi and Hongscok Namkoong. Learning models with uniform performance via distribu- tionally robust optimization. The Annals of Statistics, 1378)11378-1466 2021.
Chen Fang, Ye Xu, and Daniel N Rockmore. Unbiased metric learning: On the utilization of multiple datasets and web images for softening bias. In Proceedings of the IEEE International Conference Computer Vision, pp. 1657-1664, 2013.
Linton C Freeman. A set of measures of centrality based on betweenness. Sociometry, pp. 35-41, 1977.
Charlie Frogner, Sebastian Claici, Edward Chien, and Justin Solomon. Incorporating unlabeled data into distributionally robust learning. Journal of Machine Learning Research, 22(56):1-46, 2021.
Ishaan Gulrajani and David Lopez-Paz. In search of lost domain generalization. In International Conference on Learning Representations, 2021.
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.
Pang Wei Koh, Shiori Sagawa, Henrik Marklund, Sang Michael Xie, Marvin Zhang, Akshay Bal- subramani, Weihua Hu, Michihiro Yasunaga, Richard Lanas Phillips, Irena Gao, et al. Wilds: A benchmark of in-the-will wild distribution shifts. In International Conference on Machine Learning. pp. 5637-5664. PMLR, 2021.
Masanori Koyama and Shoichiro Yamaguchi. Out-of-distribution generalization with maximal invariant predictor. 2020.
10

---

Published as a conference paper at ICLR 2023
David Krueger, Ethan Caballero, Joemn Henrik Jacobsen, Amy Zhang, Jonathan Binas, Dinghuai Zhang, Remi Le Priol, and Aaron Courville. Outto--distribution generalization via risk extrapola- tion (rex). In International Conference on Machine Learning, pp. 5815-5826.. PMLR, 2021.
Joern-Henri
William Leeb and Ronald Coifman. Hölder-lipschitz norms and their duals on spaces with semigroups, with applications to earth mover's distance. Journal of Fourier Analysis and Applications, 22(4): 910-953, 2016.
Daniel Levy, Yair Carmon, John C Duchi, and Aaron Sidford. Large-scale methods for distributionally robust optimization. Advances in Neural Information Processing Systems, 33:8847-886/ 2020.
Da Li et al. Deeper, Broader and Artier Domain Generalization. In ICCV, 2017.
Jiashuo Liu, Zheyuan Hu, Peng Cui, Bo Li, and Zheyan Shen. Heterogeneous risk minimization. In International Conference on Machine Learning, pp. 6804-6814 14. PMLR, 2021.
Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic federated learning. In Interna- tional Conference on Machine Learning, pp. 4615-4625, PMLR, 2019.
Hongseok Namkoong and John C Duchi. Stochastic gradient methods for distributionally robust optimization with f-divergences. Advances in neural information processing systems, 29, 2016.
Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach stochastic programming. SIAM Journal on optimization, 19(4):5574- 1609, 2009.
Mark EJ Newman. A measure of betweenness centrality based random walks. Social networks, 27(1):39-544 54, 2005.
Mohammad Pezeshki, Oumar Kaba, Yoshua Bengio, Aaron C Courville, Doina Precup, and Guil- laume Lajoie. Gradient starvation: A learning proclivity in neural networks. Advances in Neural Information Processing Systems, 34, 2021.
Qi Qian, Shenghuo Zhu, Jiasheng Tang, Rong Jin, Baigui Sun, and Hao Li. Robust optimization over multiple domains. In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pp. 4739-4746, 2019.
Alexander Robey, George J Pappas, and Hamed Hassani. Model-hased domain generalization. Advances in Neural Information Processing Systems, 34:20210-2000 202299, 2021.
Elan Rosenfeld, Pradeep Ravikumar, and Andrej Risteski. The risks of invariant risk minimization. In International Conference on Learning Representations, volume 9, 2021.
Shiori Sagawa, Pang Wei Koh, Tatsunori Hashimoto, and Percy Liang. Distributionally robust neural networks for group shifts: On the importance of regularization for worst-case generalization. In International Conference on Learning Representations, 2019.
Soroosh Shafieezadeh Abadeh, Viet Anh Nguyen, Daniel Kuhn, and Peyman M Mohajerin Esfahani. Wasserstein distributionally robust kalman filtering. Advances in Neural Information Processing Systems, 31, 2018
Shai Shalev-Shwartz. and Yonatan Wexler. Minimizing the maximal loss: How and why. In International Conference Machine Learning, pp. 793-801. PMLR, 2016.
Yuge Shi, Jeffrey Seely, Philip Torr, Siddharth, Awni Hannun, Nicolas Usunier, and Gabriel Synnaeve. Gradient matching for domain generalization. In International Conference Learning Representations, 2022.
Matthew Staib and Stefanie Jegelka. Distributionally robust optimization and generalization in kernel methods. Advances in Neural Information Processing Systems, 32, 2019.
Yu Tian, Long Zhao, Xi Peng, and Dimitris Metaxas. Rethinking kernel methods for node representa- tion learning graphs. Advances in neural information processing systems, 32, 2019.

---

Published as a conference paper at ICLR 2023
Alexander Y Tong, Guillaume Huguet, Amine Natik, Kincaid MacDonald, Manik Kuchroo, Ronald Coifman, Guy Wolf, and Smita Krishnaswamy. Diffusion earth mover's s distance and distribution embeddings. In International Conference Machine Learning, pp. 10336-10346. PMLR, 2021.
Vladimir Vapnik. Statistical learning theory, 1998.
Vose, S Applequist, M Squires, I Durre, MJ Menne, CN Williams Jr, C Fenimore, K Gleason, and D Arddt. Gridded 5km ghen-daily temperature and precipitation dataset (nclimgrid) version 1. Information, NNCJE, editor. Maximum Temperature, Minimum Temperature, Average Temperature, and Precipitation, 2014.
Zihao Xu, Guang-He Lee, Yuyang Wang. Hao Wang, et al. Graph-relational domain adaptation. In International Conference Learning Representations, 2022.
7 APPENDIX
7.1 RELATED WORK
Distributionally Robust Optimization, In the context of distributionally robust optimization (DRO), Duchi & Namkoong 2021) and Shalev-Shwartz & Wexler (016)) argued that minimizing the maximal loss over a set of possible distributions can provide better generalization performance than minimizing the average loss. The robustness guarantee of DRO heavily relies on the quality of the uncertainty set which is typically constructed by moment constraints (Delage & Yel 20 f f-divergence (Namkoong Duchi 2016) or Wasserstein distance (Shatieezadeh Abadeh et al. 2018). To avoid yielding overly pessimistic models, group DRO (Hu et al.) 2018 [Saawaa et al. 2019) is proposed to leverage pre-defined data groups formulate the uncertainty set as the mixture of these groups Although the uncertainty set of Group DRO is of a wider radius while not being too conservative, our preliminary results show that Group DRO recklessly prioritizes worst-case groups that ineur higher losses than others. Such worst-case groups not necessarily the influential ones that truly connected to unseen distributions; optimizing over the worst-case rather than influential groups would yield mediocre OOD generalization performance.
Out-of-Distribution Generalization. The goal of OOD generalization is to generalize the model from source distributions to unseen target distributions. There mainly two branches of methods to tackle OOD generalization: group-invarianl learning (Arjovsky et al., 2019; Koyama & Yamaguchi 2020 Liu al. 2021) and distributionally robust optimization. The goal of group-invariant learning is to exploit the causally invariant correlations across multiple distributions. Invariant Risk Minimization (IRM) one of the most representative methods which learns the optimal classifier across source distributions. However, recent work (Rosenfeld et al. (02I)) shows that IRM methods can fail catastrophically unless the test data are sufficiently similar the training distribution.
7.2 IMPLEMENTATION DETAILS
In Sec. 3.1 for all hyperparameters such the kernel scale a² and the maximum scale K, the default values from the official implementation[]on Tong et al. 2. In Sec. 3.2 for learning rate of model parameters 1J8, use default values from Xu al. (022)) (DG-15/-60 and TPT-48) and Bonafilia et al. 2020) (Sen/ Floods l). Therefore, we only tune the learning rate of the mixture distribution 74 and the dual variable X. All results are reported over 3 random seed runs, which is consistent with Koh et al. (2021) ) and Shi et al. (2022). We select À from [le-3, 1e-2, le-1, 1, 10, 100) and select 7/q from (1e-4, Te-3, 1e-2, le-1, 1).
7.3 ADDITIONAL RESULTS
DG-15 and DG-60. We provide detailed classification results for each group. The results shown in We can see that, compared to other baselines, TRO significantly improves the generalization performance on groups that are far from the training groups, such as group "13". r We further visualize the decision boundary of DG-15 and DG-60 in Fig. 9 and Fig. T0 respectively.
Fig. [
https::/githha wwwo/o/mmoooo kri htgp
12

---

Published as a conference paper at ICLR 2023
Trean Test
ERM: 58.00%
IRM: 57.87%
Accuray
100%
DRO: 43.22%
TRO: 67.56%
Figure 8: Detailed results on DG-15. Our method outperforms ERM by 9.56% while other baselines inferior to ERM.
Ground Truth
ERM: 58.00%
JRM: 57.87%
Class
REX: 57 22%
DRO: 43.22%
TRO: 67.56%
Figure 9: Visualization of decision boundary on DG-15.
Ground Truth
ERM: 78.02%
IRM: 7861%
REx: 86. 89%
DRO: 78.58%
TRO: 89 19%
Figure 10: Visualization of decision boundary DG-60. TRO correctly classify the data of most groups even if training groups are only one-tenth all groups
13

---

Published as a conference paper at ICLR 2023
Art
Cartoon
Photo
Sketch
PACS
Data-driven topology on PACS
Centrality
L100
L38
L43
L46
Terra Incognita
10
LabelMe
SUN09
VOC2007
VLCS
Photo
Art
Sketch
Image samples of DomainBed. Right: the data-driven topology of PACS when "Cartoon" is the test group while the other three training groups. We assume the reason why "Art" the most influential group is that "Art" may contain more information than "Photo" and "Sketch" as "Art" is the combination of photos and various kinds of styles.
Figure 11: Left:
Table 5: Accuracy (%) on PACS. "Art": "Arr" is the test group while the other three groups are training groups. In average accuracy, TRO outperforms the SOTA by 0.5% and outperforms ERM and DRO by 0.8% and 2.4%.
Art 88. 88.1(0.1)
Cartoon
Photo
Sketch
Average
ERM
77.9(1.3)
97.8(0)
79.1(0.9)
85.7(0.5)
Group DRO
86.4(0.3)
79.9(0.8)
98.0(0.3)
72.1(0.7)
84.1(0.4)
CORAL (SOTA)
87.7(0.6)
79.2(1.1)
97.6(0)
79.4(0.7)
86.0(0.2)
TRO (ours)
87.7(0.5)
82.1(0.5)
98.0(0.2)
78.2(1.9)
86.5(0.4)
Table Accuracy (%) on Terra. TRO achieves comparable results with the SOTA and outperforms ERM and DRO by 1.8% and 2.0%.
L100
L38
L43
L46
Average
ERM
50.8(1.8)
42.5(0.7)
57.9(0.6)
37.6(1.2)
47.2(0.4)
Group DRO
47.2(1.6)
40.1(1.6
57.6(0.9)
43.0(0.7)
47.0(0.3)
MMD (SOTA)
52.2(5.8)
47.0(0.6)
57.8(1.3)
40.3(0.5)
49.3(1.4)
TRO (ours)
53.3(2.4)
42.2(1.3)
59.0(0.8)
41.3(0.5)
49.0(0.6)
DomainBed. Following the instructions of the official implementation of DomainBed Gulrajani
Lopez-Paz (202T) have conducted experiments PACS ([i al. 2017). Terra (Beery al. 2018), and VLCS Fang et al. 2013). Image samples of the three datasets are shown in Fig. (left).
(1) PACS is one of the most popular dataset for images from four groups: "Art", "Cartoon", "Photo" and "Sketch". Results on PACS are shown in Tab. Results of other baselines are from Appendix B.4 of Gulrajani & Lopez-Paz (2021) In average accuracy, TRO outperforms the SOTA by 0.5%. To further investigate the results, we visualize the learned topology Fig. [T] (right). As observed, when "Cartoon" is the test group, the topology is a chain graph consisting of three nodes where "Arr" is the most influential group. possible explanation that "Arr" may contain more information than "Photo" and "Sketch" as "Art" can be viewed as the combination of photos and various kinds of styles. Even though the topology is so simple, it enables our method significantly outperforms ERM and DRO by 0.8% and 2.4% on average. The results empirically demonsirate the strong explainability of our method when the number training groups is quite limited, i.e., 3. We would like to point out that when the distributional shift across different groups is small (see explanation influential group may not exist and all groups share the same centrality. In this special case, TRO aims strike good balance between the average (ERM) risk and the worst-case (DRO) risk.
generalization. It consists of
the results of VLCS), the
14

---

Published as a conference paper at ICLR 2023
Table 7: Accuracy (%) on VLCS. The average accuracy of DRO and TRO is the same. We assume the reason is that the distributional shift across different groups is small (Li et al. 2017 and therefore the influential group may not exist and all groups share the same centrality.
Caltech101
LabelMe
SUN09
VOC2007
Average
ERM
97.6(1.0)
63.3(0.9)
72.2(0.5)
76.4(1.55
77.4(0.3)
Group DRO
97.7(0.4)
62.5(1.1)
70.1(0.7)
78.4(0.9)
77.2(0.6)
DANN (SOTA)
98.5(0.2)
64.9(1.1)
73.1(0.7)
78.3(0.3)
78.7(0.3)
TRO (ours)
96.9(0.2)
65.0(0.8)
71.3(0.9)
75.5(0.9)
77.2(0.5)
(2) Terra consists of images of wild animals captured by camera traps under four locations. Results on Terra are shown in Tab. 6 Results of other baselines are from Appendix B.6 of Gulrajani & Lopez-Pat (202T). As observed, in average accuracy. TRO achieves comparable results with the SOTA and outperforms ERM and DRO by 1.8% and 2.0%.
(3) Results on VLCS are shown in Tab. Results of other baselines are from Appendix B.3 of Gulrajani & Lopez- Lopez-Pazz Paz (2021). The average accuracy of DRO and TRO is the same. We assume the
reason is that the distributional shift across different groups small (Li et al., 2017), and therefore the influential group may not exist and all groups share the same centrality. In this special case, TRO aims to strike good balance between the average (ERM) risk and the worst-case (DRO) risk. The images of VLCCS are all photos and the distributional shift is not as significant as PACS (e.g., Photo vs. Sketch). As stated in Sec. 2.1 of Li et al. (2017). "despite the famous analysis of dataset bias that motivated the creation of the VLCS benchmark, smaller with recent deep features", and PACS (Li et al. 2017 was proposed to address this limitation.
later shown that the domain shift is much
7.4 PROOF OF THEOREM
Proof. By using the property convex loss functions, we can obtain:
T (0' -0:00))-R(00))
1
max R (0.,.)) 9) min R (0, (r) S geam
max GEO
0E
T
where Vt 2 1:
R - -0 (0.0))) -R (0', R (0' ,4) + (0',0") R (0,9')
< <(4 - (() V,R (0', .q')) ((0' - 6), VoR (0' (.)))))
By rearranging the terms in the above equation, we obtain:
Σ R (0 .q) -R (0,9"))
< E
max DEB
(00' 0) .66
gEA,
1=1
T
E
max
Σ
((q g') .b)
+E
max 7Eam
{q. R (0' (0',09) -9h)
VoR (8' .011
E max
(8,
BEB
Following Collins et al. (2020). we will derive the combined bound by bounding the expectation of each term in the above equation. For the first term, by utilizing the telescoping sum, we can obtain:
T
E
max 8EB
Σ (00 0) .06)
100
0112
||1b11?
1 110e
nogh - 011
2
110
70
2R2
1]8
Σ
T
|
<
2R2
n
T/0
2
7/0
2
t=1
15

---

Published as a conference paper at ICLR 2023
Similarly, for the second term:
E
max ge
Σ
(4-
<
2
+
119
TG²
114
2
The third term and the last term are bounded by vTōg and Re Tãa, respectively. To this end, we can derive the overall bound as:
212 noT
Go
2
ng
Roō
og VT
E max R (0T. min R (0, (T) m m
+
+
+
AEB
2
n
2
VT
The above bound can be minimized by setting the step sizes no 2Ra/ (GoVT) and fl
2/ (G,VT)
7.5 PROOF OF THEOREM 2
Proof. Inspired by Qian et al. 2019 and Collins et al. 2020), we utilize the property of M-smooth to start the proof:
EE
Σ dee (0t+1)
le (0t)
118
m M
||,b|| +
Mo
2
2
We rearrange these terms by:
( 110
nhMM M
n Σ lie. (0ct1)
+ Mog
) ||,و||
S
dels (0))
a
=I'
di4s (0))
Σ di le (0+1)
n
nhe Mož 2
+E
q
4+16 e (0l+1)-
Σ gils (BL+2)
The second term of the above equation can be bounded by:
++1 l, (0)+1)
- Σ
= EE
(of - df) & (0-t1)
1=1
1=1
|| - r'1l2 Σ (ee 10++1)) 1/12
< E
Bg VBBB
By using the Law of Iterated Expectations, we can obtain:
M 2
T
|1
E
1=1
+ 2TT @TTnVVnBB + TMn
< E
a l, (00)
- E
T+1 e, (0T+1)
(9)
2
< R (0' g²) + B + 2T VnBG, + Moa Next, we investigate the convergence of q:
E RR (0", 9) R .e)]g)] = =
211g (11g - 9 0'112 + (nr)) 110611 11g (g' + na 11:)
(1l9 - of 2l1 + (n.) 110:11 /|a g (13)
$
2714
274 (114 " + (nr)) 6% |/q (1))
<
16

---

Published as a conference paper at ICLR 2023
By aggregating the difference at all time steps, we obtain:
Σ E [R (0', .0) R (0,, .q))]
1
E
119
['112]
1
EF
||
al
112
[12]
6
27y
277
2
[||g
2/11
144
T
+
27g
2
1
na
To
17
2
Since the above equation holds for all E Am. we maximize the right hand side over y E Am:
G
+ Bg
E R (0', o¹)]
max gE
[R (fr, 9)] -
2
(10)
T
170
2
Eqs. and 10 show that TRO converges in expectation to an (c, (estatiiy point of R in O(1/et)
stochastic gradient evaluations.
17


Reviews:
[{"review_id": "qg41dIner1", "reviewer": "Reviewer_zKvZ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 1, "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": "--", "summary_of_the_review": "--", "strength_and_weaknesses": "--", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "Exns8KcqN4", "reviewer": "Reviewer_BJCq", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "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": "Compared to the standard distributionally robust optimization (DRO, Namkoong & Duchi 2016), this paper constructs a new uncertainty set. The uncertainty set of DRO is an f-divergence ball whose center is the uniform distribution of all training samples. The new uncertainty set is a distributional metric ball whose center is the group centrality of the graph constructed by training data. This graph-based uncertainty set captures the correlation of samples. Then solving the corresponding problem can utilize the off-the-shelf method. The theoretical analyses are similar to the existing results in the DRO and ML communities. When the graph captures the underlying relation of training data, the proposed method shows promising results. ", "summary_of_the_review": "This paper introduces the group centrality to construct the uncertainty set. This method is applicable to distributionally robust optimization for graph data. However, the novelty is limited to combining the existing methods (graph construction, group centrality, optimization method & convergence rate, generalization bound). Consequently, it does not reach the requirement of ICLR. ", "strength_and_weaknesses": "* **Strength**\n\n  - Learning the group centrality to construct the uncertainty set explores the relationship of the training data.\n\n\n* **Weakness**\n\n  - The novelty is limited to combining the existing methods (graph construction, group centrality, optimization method & convergence rate, generalization bound).\n\n  - The definition of uncertainty set is incorrect.  ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "Euid9tFIKif", "reviewer": "Reviewer_vFEm", "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 studies the distributionally robust optimization problem by leveraging topological knowledge. Specifically, two types of topologies are considered, namely physical-based topology and data-driven topology. The physical-based topology is based on neighborhood information, and the data-driven topology is based on the affinity matrix of the data. By constructing the uncertainty set based on one of the considered topologies, the proposed TRO method is shown to be superior to many popular methods.", "summary_of_the_review": "I have carefully read the methodology and experiments. This paper managed to make some contributions to DRO, however, there are still some concerns (see weaknesses). If the authors can address my concerns, I will consider raising my score.", "strength_and_weaknesses": "Strength:\n* As traditional DRO methods are only based on the loss values, utilization of the topological knowledge can further improve the uncertainty set selection, thus can improve the learning performance.\n* The experiments are pretty sufficient, both quantitative and qualitative evidence is provided to support the proposed TRO. Moreover, three tasks including classification, regression, and semantic segmentation are investigated to show the effectiveness of TRO.\n* The proposed TRO is theoretically guaranteed.\n\nWeakness:\n* The writing of this paper can be further polished. There are many unclear sentences and unprofessional writing styles. For example, what is the “$L^1$ distance between two groups”? Since $\\ell_2$ is used in this paper, is it supposed to be “$\\ell_1$ distance”? Moreover, it is suggested to explain the notations $q_e$ and $P_e$ to avoid misunderstanding.\n* The three steps of data-driven topology are not clearly presented and it is quite difficult to understand for unfamiliar readers. These three steps seem to be isolated from each other, I cannot see any relevance between them and how they are conducted to produce the topology. Could you please give a more detailed explanation?\n* The constraint in Eq. (3) seems to be erroneously motivated. The distance constraint between $\\mathbf{p}$ and $\\mathbf{q}$ can only make sure that they are numerically close to each other, instead of having a similar topology structure. Intuitively, as $\\mathbf{p}$ tries to find the most influential groups, and $\\mathbf{q}$ focus on finding the groups with large losses, so the optimal $\\mathbf{q}$ is the groups that have both large loss and influence. Is this a correct interpretation?\n* More importantly, the proposed method is a two-stage learning process. The computational cost of learning the topology is not provided.\n", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "BHQJ_5UTvu", "reviewer": "Reviewer_uihf", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes an algorithm for improving out-of-distribution generalization performance by modeling the topology structures of distributions. Specifically, the algorithm first constructs a graph based on either manually defined priors, e.g., spacial relationships, or learning it from the data. This topology graph serves as a topological prior. Then, it remains to solve a minimax problem under the constraint induced by the topological prior. In contrast to the conventional DRO approach, the proposed algorithm utilizes the topological structure and hence reduces the search space. This can exclude those implausible distributions, reduce the pessimism and hence improve the OOD generalization. The authors provide theoretical guarantees for the convergence rate of the algorithm under both convex and nonconvex loss functions. In addition, the experimental results demonstrate the effectiveness of the algorithm.\n", "summary_of_the_review": "This paper propose a novel algorithm for utilizing the topological structure to improve the OOD generalization performance. I don't have critical concerns about this paper, except for some minor questions/weakness. Hence, I would recommend for an acceptance. ", "strength_and_weaknesses": "Strength:\n- I think the idea of incorporating the topological prior in this paper is novel and very interesting. Especially, most of the prior work in dealing with distribution shift will cast the problem as a minimax problem, which is overly pessimistic. Though TRO also adopts such a method, it constrains the search space of maximization with the topological prior. This can (hopefully) exclude those implausible distributions, and further improves the OOD generation performance. \n\n- The experiments conducted in this paper are related to very important real-world problems, e.g., flood prediction. So, I believe the algorithm in this paper can potentially have some real-world impact on improving the well-being of humans.\n\n- TRO also has theoretical guarantees on the convergence rate under both convex and non-convex losses, though the derivations are straightforward from the existing results and the technical contributions are limited. \n\n\nWeakness/Questions:\n- The proposed framework, TRO, seems to only work for data distributions where they can be categorized into a bunch of discrete groups. It's unclear to me whether many problems satisfy this assumption. It would be great if the authors can provide more discussions. \n\n- For those groups that we don't have any data, how can we infer the topological relationship between them with the groups with data? Also, how do we know the number of groups, if it's not given?\n\n- How do you choose $\\lambda$ in your experiments? If you use a validation set, how do you construct this validation set; and shouldn't it also suffer from distribution shift? ", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "B4u6bCTAh0M", "reviewer": "Reviewer_bQwH", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The main idea in this paper is to incorporate structural priors on the domains/distributions in an out-of-distribution (OOD) generalization setting.  Given a graphical prior over the set of domains, the authors propose a group-DRO-like optimization problem which incorporates this prior by enforcing that the mixture distribution $q$ over groups must be \"close\" (in some sense) to the prior distribution.  The authors argue that the algorithm they propose for solving this problem enjoys a favorable convergence rate to a saddle point of the minimax formulation.  They also provide experiments concerning classification, regression, and semantic segmentation, showing strong empirical performance vis-a-vis several standard domain generalization baselines. \n\nThe meat of the algorithmic contribution involves inferring the structure amongst the domains and imposing that structure on the groupDRO objective.  To this end, the authors consider settings where the structure comprises a graph (G,E), which describes the relationships within the set of domains G by means of the edge weights E.  If the graph structure is known a priori, the authors compute a particular statistic (namely, a distribution over domains/nodes) on the graph, which is used in the robust optimization framework.  Otherwise, if the graph structure is unknown, the authors argue that the relevant statistics can be inferred from data, although a detailed description of *how* this graph is inferred is lacking.  The remaining algorithmic portions of the paper, including the primal-dual-style optimization scheme and the convergence analysis, use standard tools and do not constitute a novel technical innovation.\n\n", "summary_of_the_review": "I thought the main idea here was novel.  I also note that the paper reports strong empirical results, and that the formulation is principled and follows from several well-known results in domain generalization.\n\nOn the negative side, the paper is somewhat hard to understand, especially around Section 3.  There are not enough details given to understand or reproduce the topology learning procedure.  The convergence analysis seems to make assumptions that are violated by the formulation, and the analysis does not seem to have any bearing on the practice of domain generalization.  The contributions listed by the authors do not seem to be satisfied.  The experiments also seem to be not reproducible as far as I can tell.\n\nSo to summarize, while this paper starts from a novel idea, the execution is lacking.  Reproducibility is a major concern.  This paper could be significantly improved by adding more details about how the relevant structure is learned, and why the authors' method in particular is the right way of doing it.  All of this being said, I feel that in its current form, the paper is not yet ready for publication.  However, I welcome a discussion with the authors.", "strength_and_weaknesses": "### Strengths\n\n**Main idea.**  If this paper is to be accepted, it will be due to the motivation idea, which is that domain generalization is impossible unless some sort of structure is placed on the space of domains.  The argument laid out in the paper -- which is that one must construct a reasonable uncertainty set for the minimax formulation -- is convincing.  Until now, it has been unclear how to define this uncertainty set to engender meaningful notions of OOD generalization.  To this end, imposing structural priors over these domains seems worthwhile, especially when this structure is available a priori.  Momentarily playing devil's advocate, I would suggest that the assumption that the uncertainty set should contain any mixture of training distributions is somewhat strong.  However, on the toy datasets considered at the beginning of the experiments, I would tend to agree that the assumption is more or less realistic.\n\n**Natural optimization-based formulation.**  Grounding this formulation in the minimax formulation of groupDRO also seems natural, as this setting naturally lends itself to restricting the distributions that can be obtained over the training groups.  Furthermore, the analysis from steps (3)-(5) seems natural, as the primal-dual style scheme has been shown to be effective in other domain generalization problems (as noted by the authors).\n\n**Strong empirical results.**  On the datasets that the authors choose, the proposed algorithm yields strong results.  This indicates that structure can help to improve OOD performance.  However, I am concerned that there is insufficient detail regarding reproducibility, which -- if experiments are to be a motivating reason for acceptance -- must be added to the paper (see my comments below).\n\n### Weaknesses\n\n**Failing to satisfy the stated contributions.**  One of the aspects I look for when reviewing is whether or not a paper accomplishes the contributions it lists.  In this regard, I believe that this paper is not successful.  In the last section of the intro, the authors say that one of their contributions is the following:\n\n> \"Topology learning methods that are orders of magnitude faster than previous methods to uncover distributional structure from massively collected datasets.\"\n\nHowever, the authors do not show -- in the main text or appendix -- any comparison regarding the speed/efficiency of their method.  They allude to the fact that complexity results exist for a particular distance metric (c.f. (Tong et al., 2021) in the paper), but they never (a) explain how these results relate to the method that they propose and (b) they never demonstrate that this holds empirically.  In fact, there is no comparison to any \"previous methods\" in terms of learning the distribution structure the authors mention, and so the claim quoted above seems to be incorrect as written.\n\nWRT the other contributions, some of them hold, while others are arguable.  The theoretical analysis seems to make a unilateral assumption that the objective R is convex-concave, which as I argue elsewhere in this review, may not hold.  The claims to \"explainability\" do not seem to be discussed in the experiments, and so it's hard to validate that this claim holds as well.\n\n**Insufficient details for learning the topology.**  Simply put, there are nowhere near enough details given to be able to reproduce the topology learning procedure outlined in Section 3.1.  To begin, the authors do not define what an \"affinity matrix\" is, or how it is constructed.  As we are presumably computing K on the space of distributions, it's somewhat unclear (at least to me) how it should be computed.  And while some readers will know what an affinity matrix is, others will not.  It's worth explaining in detail here so as to not lose readers.\n\nIt's unclear why the notion that \"[ERM] captures spurious correlations which preserve group identities\" is important in this context.  What do spurious correlations have to do with the problem described thus far?  Does this setting not work for arbitrary distribution shifts?  And moreover, if ERM pretraining is to be performed, how is model selection performed?  Is the pretraining implemented in the same style as the implementation of e.g. IRM in DomainBed?  This should be discussed in the appendix, as the reason for using ERM pretraining is not fundamentally clear.  Moreover, to provide a fair comparison, one would expect the authors to have allowed groupDRO to also use ERM pretraining.  However, this does not seem to be the case.\n\nThere are almost no details given on how the Markov diffusion operator P is inferred from K.  At the very least, the authors should devote an appendix to discuss this.  Otherwise, there is no way to reproduce the method.  There simply aren't enough details for anyone to reasonably reproduce this work. And what is $P^t$?  Is t an exponent, or a time index?  The same questions could be asked of $\\mu^t$.  And how do these quantities factor into the algorithm? -- Algorithm 1 does not include them.  \n\nThere should also be further discussion of how one moves from $\\mathcal{G}$ -- the graph -- to $p$ -- the structural prior.  There are a few lines on this in the appendix, but as the authors list this as a main contribution, it should be discussed in much more detail in the main text.\n\nFurther questions/comments regarding learning the topology:  What does it mean to yield \"OOD resilience?\"  In what way are these graphical priors consistent with \"human knowledge\" or \"scientific plausibility?\"  The authors offer no evidence to back up either of these claims, meaning that these claims of contribution are not verifiable.  And why is the Earth Mover's distance the relevant metric here?\n\n**Convergence analysis.**  The authors seem to assume (unless I've misread their proofs) that $R(f,q)$ is convex-concave.  This seems to not hold, especially as this depends on the distance metric $\\mathcal{D}$.  What if $\\mathcal{D}$ is not convex?  Then the inner problem seems to have no hope of being concave.  The fact that the analysis relies on this choice of distance metric is not discussed in the paper, and moreover I do not see where the authors mention which distance metric they actually use in the experiments.\n\nAnother comment on the convergence analysis is that it does not inform the practical aspects of the algorithm in any way.  The analysis follows from standard tools which are well-known in the literature, and it's not clear what insight this theory brings to the paper. \n\n**Notation.**  I would also argue that the notation in this section -- and more generally, in several parts of the paper -- is unnecessarily confusing.  The authors seem to use the terms \"entities,\" \"groups,\" \"domains,\" and \"nodes\" to refer to the same thing -- the domains in the domain generalization problem.  The authors do not define $\\mathcal{D}^{n_k}$ here.  What is $k$ indexing? The domains?  And what is $\\sigma_{k,i}$ vis-a-vis $\\sigma$?  Is $\\sigma$ a matrix?  And note that $\\mathcal{D}$ is overloaded here.  First it is used as a distance metric in (3), and then it is used as a distribution/dataset in Section 4.2.  $d$ is used for the distance in the remainder of the paper, which is confusing. \n\n**Experiments.**  Though the paper reports strong empirical results, there are no details about how the algorithms were tuned.  How many hyperparameter seeds were used?  Was this experiment repeated across multiple trials?  These details are crucial for the paper.\n\nFurthermore, one fundamental drawback is that the authors used somewhat non-standard datasets, in the sense that these datasets are not commonly used in domain generalization papers.  This is fine in general, but the fact that no datasets from e.g. WILDS or DomainBed are used means that as a reader, we have no basis for comparing these results to past work.  The reason that benchmarks like these exist is to provide a metric for measuring progress.  And so by choosing not to use these datasets, it's more difficult for the reader to understand the contribution of this work.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "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": {}}]

Author rebuttal:

Decision: Accept: poster