Learning Distributionally Robust Models at Scale via Composite Optimization
Authors: Farzin Haddadpour
Mohammad Mahdi Kamani
Mehrdad Mahdavi
amin karbasi
Venue: ICLR 2022 Poster (2022)
Keywords: Composite Optimization
Distributionally Robust Optimization

Abstract: To train machine learning models that are robust to distribution shifts in the data, distributionally robust optimization (DRO) has been proven very effective. However, the existing approaches to learning a distributionally robust model either require solving complex optimization problems such as semidefinite programming or a first-order method whose convergence scales linearly with the number of data samples-- which hinders their scalability to large datasets.  In this paper, we show how different variants of DRO are simply instances of a finite-sum composite optimization for which we provide scalable methods.  We also provide empirical results that demonstrate the effectiveness of our proposed algorithm with respect to the prior art in order to learn robust models from very large datasets. 

Published as a conference paper at ICLR 2022
LEARNING DISTRIBUTIONALLY ROBUST MODELS AT SCALE VIA COMPOSITE OPTIMIZATION
Farzin Haddadpour
Mohammad Mahdi Kamani
Yale Institute for Network Science
Wyze Labs Inc.
Yale University farzin, www.hhdddoorrr@aleeeeeee.
mmkamant @alumni psu edu
Mehrdad Mahdavi
Amin Karbasi
Department of Computer Science Engineering The Pennsylvania State University
Yale Institute for Network Science
Yale University
mzm61 1 60psu. edu
ami n. ka raabb @ya le edu
ABSTRACT
To train machine learning models that are robust to distribution shifts in the data, distributionally robust optimization (DRO) has been proven very effective. How- ever, the existing approaches to learning a distributionally robust model either require solving complex optimization problems such as semidefinite programming or a first-order method whose convergence scales linearly with the number of data samples- which hinders their scalability to large datasets. In this paper, show how different variants of DRO are simply instances of a finite-sum composite optimization for which provide scalable methods. We also provide empirical results that demonstrate the effectiveness of our proposed algorithm with respect to the prior art in order to learn robust models from very large datasets.
INTRODUCTION
Conventional machine learning problem aims learning model based on the assumption that training data and test data come from same data distribution. However, this assumption may not hold various practical learning problems where there is label shift (Zhang et al., 2020a), distribution shift (Sagawa et al., 2019), fairness constraints (Hashimoto et al., 2018), 8), and adversarial examples (Sinha et al., 2017), to name a few. Distributionally robust optimization (DRO), which has recently attracted remarkable attention from the machine learning community, is common approach to deal with the aforementioned uncertainties (Chen et al., 2017; Duchi & Namkoong, 2016; Rahimian & Mehrotra, 2019). Defining the empirical distribution of the training data of size m by IP... A 1 Σmh 6g. where 8 is the Dirac delta function, the goal of DRO is to solve the following optimization problem
inf
(x)
A supgeq Eg [e(x;
(I)
where & is a data sample randomly drawn from distribution Q, E(x; {) is the corresponding loss function and Eq [f(x, {)] is the expected loss over distribution Q which belongs to uncertainty set um. The uncertainty set thm is defined as U.. & (Q Pm)) S { indicates the ball of distribution with center P.,. and also d(P.Q) Q) distance measure between probability distribution P and Q- We note this uncertainty set captures the distribution shift hence Eq. (1) minimizes the worse data distribution. Prior studies (Ben-Tal Tal al., 2013; Bertsimas et al., 2018; Blanchet et al., 2019; Esfahani & Kuhn, 2018; Pourbabace, 2020) considered different uncertainty sets (see Definition 3.1 in Esfahani Kuhn (2018)) for which they proposed equivalent reformulations of Eq. (1) based on the specific choice of Um.
To solve the above min max optimization problems, majority of prior studies heavily rely on either semidefinite programming (Esfahani & Kuhn, 2018) or stochastic primal-dual methods both for convex (Deng et al., 2021: Nemirovski et al., 2009; Juditsky et al., 2011; Yan et al., 2019; 2020; Namkoong & Duchi, 2016) and non-convex (deep learning) objectives (Yan al., 2020). While

---

Published as a conference paper at ICLR 2022
primal-dual methods can be used as approach to solve min-max optimization problems, it suffers from a few downsides. First and foremost, they need to store a probability distribution of constrained violation of dimension
corresponding to dual variables. Additionally, available primal-dual methods often demand data sampling that corresponds to the probability distribution over m data samples which introduces additional cost over uniform sampling. Finally, while majority of prior studies are limited to DRO problems with convex objectives, establishing tight convergence rate for DRO problems with penalty with non-convex objectives is still lacking.
To overcome these issues, we consider three different reformulations of Eq. (I), corresponding to three different choices of uncertainty sets Um namely, (1) DRO with Wasserstein metrics, (2) DRO with x2 divergence metrics, and (3) DRO with regularized entropy metrics (also known as KL) and show in Section 2 that all aforementioned DRO notions are indeed different instances of a deterministic composite optimization and can be solved by reducing to an instances of the following problem:
1 > m
h2(2)) + (2
i-1 ( (
min (x)) a r(z)+
+
(2)
where we suppose r(x:) is convex and a relatively simple function, f(a:) : Rp - R and h,(x)) Rd + IR for 1 < i S m are scalar-valued functions, and gx(x) R - Rd for S i < m are vector-valued functions. On the road to solve problem (2) at scale, we also develop a novel algorithm for heavily constrained optimization problems (Narasimhan et al., 2020b; Wang & Bertsekas, 2015; 2016) that rather surprisingly invokes a single projection through the course of optimization. This algorithm is of independent interest and addresses the scalability issues raised in applications such as fairness (Donini et al., 2018; Zafar et al., 2019).
We summarize the main contributions of our paper below:
We provide a large-scale analysis of DRO with Wasserstein distance and heavily constrained reformulation when the objective function is strongly-conwe Our result relies novel mini- buni-batchue constraint sampling for handling
optimization problems. As summarized in Table our convergence analysis improves the state-of-the-art both in terms of the dependence on the convergence error as well as the number of constraints m.
We represent a large-scale analysis of DRO with non-convex objectives and x² KL diver- gences and propose a distributed varaint to further improve scalability of DRO problems. We verify our theoretical results through various extensive experiments on different datasets. In particular, we show that our proposed method outperforms recent methods in DRO for heavily constrained problems with a great reduction in time complexity over them.
The proofs of all the theorems are provided in the appendix.
1.1 RELATED WORK
DRO and connections to heavily constrained optimization. As mentioned earlier, DRO has many different formulations, depending the divergence metrics used (e.g., Wasserstein, x² KL). While Duchi & Namkoong (2021); Namkoong & Duchi (2016); Shapiro (2017) consider constrained or penalized DRO formulation, Levy et al. (2020); Sinha et al. (2017) formulate the underlying optimization problem as unconstrained. One of the contributions of our paper is to provide a unifying framework through the language of composite optimization and treat all these variants similarly.
In particular, when the objective function is convex, Levy et al. (2020) recently proposed scalable algorithms for different variants of the DRO problems with. e.g., x² KL divergence metrics. Our unifying approach readily extends those results to the more challenging non-convex setting for which we are unaware of any prior work with convergence guarantees (for instance, Hashimoto al. (2018) studied DRO with X -dvvergeee but did not provide any convergence guarantee). Similarly, Esfahani & Kuhn (2018); Kuhn et al. (2019) formulated DRO with Wasserstein distance as an instance of constrained optimization. Notably, they require ti impose one constraint per training data point and to solve such a constrained problem they proposed a semi-definite program. Even though the formulation is very novel, it cannot scale. We, in contrast, consider such a heavily constrained optimization as an instance of a composite optimization for which we provide a scalable solution. What is rather surprising about our method is that it only checks batch of constraints per iteration, inspired by Cotter et al. (2016), and performs a single projection at the final stage of the algorithm in order to provide an e-optimal solution in the case of strongly convex objectives. Moreover, in
2

---

Published as a conference paper at ICLR 2022
contrast to Cotter et al. (2016), do not keep a probability distribution over the set of constraints. We should also remark that our convergence guarantees achieve the known lower bounds in terms Finally, should highlight the difference of our
of accuracy and the number of constraints algorithm and Frank- Wolfe (FW) (Frank et al., 1956; Jaggi, 2013; Zhang et al., 2020b). While FW does not require a projection oracle, it performs linear program over the set of constraints each iteration. In contrast, our heavily- constrained optimization solution performs a single projection without the overhead of running linear program at each iteration.
Stochastic composite optimization. The general stochastic composite optimization min, [Vx
r(x) + (Eg [g (x))] has recently received lot of attentions (Qi al., 2020b;a; Wang et al., 2017; Kalogerias & Powell, 2019). Our reformulation of DRO variants is a finite-sum sum instance of this general problem. More concretely, Huo et (2018); Lian al. (2017); Zhang Xiao (2019a) aimed to
solve the following finite-sum problem min
T (x) A r(x) Ej ( Σ g: using
SVRG or SAGA (Defazio et al., 2014). In contrast, our proposed algorithm is inspired by Zhang & Xiao (2019a) and generalizes their method to the case where the extra terms h; (2:) Eq. (2) are non-zero. We should also note that Qi et al. (2020a) proposed similar idea in the context of online learning for DRO problems with KL divergence. Our work in contrast provides guarantees for DRO with both constraints penalty terms.
2 DRO VIA FINITE-SUM COMPOSITE OPTIMIZATION
In this section, we discuss in detail how finite-sum composite optimization (2) can unify various notions of distributionally robust learning, where some which rely on heavily constrained optimiza- tion subroutines. While much research effort has been devoted to develop specialized algorithm for each notion, our reduction paves the way to developing a scalable algorithm, discussed in Section 3.
DRO with Wasserstein distance. An equivalent and tractable reformulation of Eq. (1) provided in Esfahani & Kuhn (2018); Kuhn et al. (2019), which can be regarded as a heavily constrained optimization problem as follows:
1 Σ fe()) 7T0
min &
subject to gx( 0, Vi E [m].
where g: (x) functions related to loss function as well slack variables (please see Appendix A for more details). Naively solving optimization problem (3) suffers from the computational complexity due to the large number of constraints m. To efficiently solve the optimization problem (3), inspired by Mahdavi et al. (2012) and Cotter et al. (2016), we pursue the smoothed constrained reduction approach and introduce the augmented optimization problem (see Appendix B) of the form min (x: e
(g)( and g(x:) m+1 [1 (= We can see that this optimization problem is a special case of the optimization problem Eq. (2) where r(x)) = f(x), f(= Σn (x)) = ? In (x)), and h(x)) = 0. In contrast to Cotter al. (2016)
[r(x)) In (g(=:)) where gi(x:) A exp
that requires an extra storage cost of probability distribution of dimension m, and relatively poor convergence rate in terms m and accuracy c, we propose an algorithm that simply checks a batch of constraints and achieves the optimum dependency in terms of m and c.
DRO with x2 divvergeee The second type of DRO problem we consider utilizes the x²- divergence metric follows:
Σ (.fi(aa)) - (p))
min Ø
max m
(4)
where the x² divergence is defined as the distance between the uniform distribution and arbitrary 2 Em (p. =²²² Levy et al. (2020) studied this
probability distribution p. i.e., (p) A m problem only for the of convex objectives. In this paper, allow objective functions f, for 1 < i < m to be both non-convex or strongly-convex. The following claim derives the equivalent finite-sum composite optimization.
3

---

Published as a conference paper at ICLR 2022
Reforeace
type
ComstrinnSamppl Checks cever
objective
Midtouch Cotter (2016)
Waswestein
Im Narml
Strongly
SEVR et al. (2021)
General Linenrized Wassestein
mila
Strongly comvet-cmecree min-mux
Thoorem 4.1
Waseerstin
0 (Im Rv/m) lu
Optimally strongly convex
Theorem 4.3
x² KL.
Ô min - sir)) +
Non-convex
Theorem D.I
x KI.
((m my/m ()
Optimally strongly
Table 1: Comparison of our results with prior approached. All three approaches are using variance reduction techniques. D,, and Dr respectively denotes the upper bound on the distance of initial model from optimal model and initial optimality gap. Please see Yu al. (2021) for more details. Finally, we note that while Midtouch approach in Cotter et al. (2016) requires additional storage of probability distribution of dimension m, our approach does not.
Claim 2.1. The optimization problem (4) is equivalent to the following composite problem:
min
(x) 1
2ym Σ [f((z)]
fi(
(5)
2
We note that the optimization problem (5) fits into the formulation of finite-sum composite optimiza- 1
tion (2) by choosing r(x:) = 1, h((:)
m Σm
1
(A(())) and f((())
27
(m) ga (x) fa( and f(x) 25'
with hx(x)
DRO with KL divergence. Finally, for DRO with KL-divergence, usually considered in online settings (Qi et al., 2020a), we consider solving the following optimization problem:
m Σ
min m
max 2m P
p:J((as)) + H0 ..... Pm)
(6)
OSP:S
where Hp Pm) straightforward convert the following equivalent stochastic composite optimization problem:
Σm == ps log is the entropy function. To solve problem (6). it is
m
fi(z))
min
(x)
In m
exp
As be seen, the optimization problem (7) fits into the composite optimization (2) by choosing r(æ)= = 1((x) and [g((=) = In >m exp
ff(())
OUR PROPOSED ALGORITHM
Having reduced the different notions of DRO to an instance of the composite optimization, this section we describe scalable approach for minimizing the objective f(xx) r(x) + ((x) where ((x) = 1 > h (x) + f Σx= 9i (x)). We note that the compositional structure 2 leads more challenges in optimization compared with the non-compositional finite-sum problem, since the stochastic gradient the loss function is not an unbiased estimation of the full gradient. To overcome this issue, and by building on incremental variance reduction (Zhang & Xiao, 2019b), propose a more general algorithm with a new ingredient in which we also employ variance reduction on the extra term h (a: (1/m) m (ax). To handle r(.), similar Zhang & Xiao (2019b), we assume is convex and relatively simple function. We follow the proximal gradient iterates (Beck, 2017: Nesterov, 2013) as follows:
(++)) II7 (x())) 1000-77((a' (VV((1)))
(8)
where we apply the proximal operator of r(æ) with the learning rate " 117()) A arg min, [r(v) 2 lly 2= By defining the proximal gradient mapping of v as (,
A
4

---

Published as a conference paper at ICLR 2022
Algorithm 1: Generalized Composite Incremental Variance Reduction (GCIVR (xx
Number of iterations = 1,.... T. learning rate 7, initial global model x0)), the size of epoch length Te. and mini bani-batch sizes of B, and St at time t. for / ,,...,7 ,,T do
Inputs:
Sample mini-batch B()) with size B, uniformly over [m] and compute
yo
1 B.
Σ
EEBO (aalf E), Be
20
Σ
:E), 5),,
1 E Vh(a?));
EEB
B.
Compute (2(4)) = =00 f (()) ())
T
+ w (1)
Update the model as follows: øi = II
ab (1) ()
for j = 1, ................................ 7t 1 do in parallel
Sample mini- 5/ with size St uniformly over [mi] and form the estimates
0 0 = wزー +
E
[olaf) -
s(a)21:55]
(9)
S.
2/ 2--1
(
1
Σ
EES!!
[olaa (5) vo(a{2.:t)
(10)
S.
w/y = j-1
(1)
+
1
Σ
Vh(af) vh(=)_1:3)
(11)
S
(ES
Compute (2 (1) = (21²)
T
(f(w)) (2))
+ }
Update the model as follows: 2 = II
2 (1)
{,(2)))) ())
end end
Output: Return a randomly selected solution from { (ajjyy00... O.....r
I
[ - II (x V ([zz) the updating rule in Eq. (8) can be equivalently written as x(++1)
(1) (10-79,((00) Given any y as an output of randomized algorithm, we say y achieves the stationary point of problem in Eq. (2) in expectation if [ [,))) < holds. Our goal is to achieve an stationary point with the least number of calls to a (mini-batch) stochastic oracle.
Focusing on ((-), as detailed in Algorithm 1, we apply three time-scale variance-reduced estimators for 9, (x: and its gradient Vg,(z) as well as h, (z:). For DRO with Wasserstein divergence metric with optimally strongly objective, at the beginning of each epoch we compute full-batch gradient over 1 Σ (g.(x (+) ), w
the entire data samples B, m, i... y0 (f) 1 Em 9: (xx ), = m
(t)
m
m 1== (a, In contrast, for the case of DRO with x2 or KI. divergence metrics and non- convex objectives we incrementally increase the size of the mini-batch B, S m at the beginning of each epoch until it reaches the point where we need to compute the full-batch of samples. We should also highlight that mini-batch in case of Wasserstein DRO indicates batch of constraints and in DRO with x² KL divergence metrics represents the number of data sample accessed. We denote the length of each epoch and the mini-batch size within each epoch with т, and S,, respectively. In each epoch and iteration j. we estimate mini-batch gradients from Eqs. (9), (10), and (11) Algorithm 1, with some corrections term applied from the previous iteration. We note that the variance-reduce term corresponding to the correction inspired by SARAH (Nguyen al., 2017) and SPIDER (Fang et al., 2018). Finally, the algorithm returns randomly selected solution from the iterates.
Distributed variant of Algorithm 1. As mentioned before, efficient training of the stochastic composite optimization problem has attracted increasing attention in recent years. Despite much progress, all of existing methods including Algorithm only focus on the single-machin employ Algorithm in a distributed setting with p machines, in Appendix E we propose distributed variant of proposed algorithm and establish its convergence rate for convex and non-convex objectives which enjoys speedup in terms of number of machines.
setting. To
5

---

Published as a conference paper at ICLR 2022
4 CONVERGENCE ANALYSIS
In this section we establish the convergence of proposed algorithm for different DRO notions discussed in Section 2. We start by stating the general assumptions and then discuss the obtained rates. Due to lack of space we only include the rates on the convergence DRO with Wasserstein metric for strongly convex, and x² and KL divergence metrics for non-convex objectives. We defer the analysis of x² and KL divergence metrics with strongly objectives to Appendix D. To establish the convergence rates, we first introduce some standard assumptions.
Assumption 1. We make the following assumptions the components of objective ((x) r(()) DE= hx(a)) + [( Di 96 (a));
1) Vh((11) - Vh(z2) <
Ln
||]
x2ll where I1, D2
We also assume that E Rd..
h(x1)= h(x2))l S 4,
Σ2
2) [f - (((x))-f
(a2))
<
[
E R. We also assume that x2ll where I 12
[(x)) - (xx2) <b [1
x2
3) [g((t1;E) -0l6)-VVVeee (Vg())))
S Lg
[1
- and (1g((1)8)) g(z2;;)) E) S Eg || 2t2
for Væ1. E R
4) We suppose that (x) in Eq. (2) is bounded from below that & inf (x)) -00
5) We assume r(x) E IR U {oc} is a convex and lower-semicontinues. function.
An immediate implication of above assumption is that [(g(a)) A [( E module (L + L Lg), hence (x) is smooth with module L4 & ( + Ln] (Wang et al., 2016; Zhang & Xiao, 2019b).
() is smooth with
Assumption 2 (Unbiased estimation). We assume that the mini-batch of samples & over functions g: for = 1,2, ..,,, is unbiased, that is IE [g(x;; {)] g(x) and E [Vg(<;; <) = Vg(æ)).
4.1 OPTIMALLY STRONGLY CONVEX OBJECTIVES
We here establish the convergence for optimally strongly convex objectives under Wasserstein metric. Definition 1 (Optimally strongly convex). We say that the objective function (xx) is optimally strongly convex objective with module μ if (xx) - (Px (x)) 2 æ - Pa (x)]1
According to Definition 4 of Necoara al. (2019) optimally strong objectives or quadratic functional growth property is the generalization of strongly convex condition. According to Karimi et al. (2016) below, the PL condition implies an optimally strongly convex condition but not vice versa. Therefore, optimally strongly convex generalizes PL condition as well.
Following Cotter al. (2016) and Mahdavi al. (2012), make the following assumption.
Assumption 3. There exists a constant such that if we define g(x) maxigism (x(x) we have Vg(z))l2 p.
min =())=0
Assumption 4. Function r(x) is smooth with module G.
Theorem 4.1. Assume p-optimally strongly convex and set Tt S, =B, VB V
vmann
< Lo V 7T2, +36G where Go 3 3 + T + 1,), a>
G p. and exp(-K) Let us denote In(m+1]
(k+1) GCIVR (2)(k) for k= = O,... K (using Algorithm 1). Under Assumptions 1-4 and by letting K In (1/e), the solution of DRO with Wasserstein divergence obtained by projecting a (K) onto the constraint set K. {ax g (xx < 0, 2..,...... ...... i.e., x(K) (x) In order 1.2..... to achieve (k) - (()()))) S e, we require an O ((m + / In 2) calls to the stochastic oracle.
Comparison with previous results. Compared to the MidTouch approach by Cotter et al. (2016), our obtained rate improves both on the dependency on the number of constraints m, as well as convergence error To better understand the intuition behind achieving such a double folded improvement in terms of m and e, we note that unlike Cotter et al. (2016) which utilizes a primal-dual approach in order obtain approximate the optimal distribution over the constraints, find the optimal distribution exactly. Second, while Cotter et al. (2016) does not apply any variance reduction technique to primal variable æ., our algorithm benefits from variance reduction over too.
directly

---

Published as a conference paper at ICLR 2022
Furthermore, Theorem 4.1 entails tighter rate in terms of final accuracy compared to Yu et al. (2021). These results are summarized in Table.
In Algorithm I for optimally strongly convex objectives, need do single projection at the end. The following corollary bounds the error between the solution before and after the projection.
Corollary 4.2. Under the assumptions made in Theorem 4.1, the error between the solution with and without projection bounded by
[ 1yIn(m+1 +1) ap- G ap- -
r(a - -r (K) S
+ +7 1).
(12)
Therefore, with proper choice o we can establish convergence rate obtained in Theorem 4.1. Remark 1. It is worthy to highlight that through reduction of heavily-construunee optimization to composite optimization, GCIVR algorithu can be considered as an alternative method to solving constrained optimization problems via mini-batch sampling of constraints. In particular, Theorem 4. shows that under certain conditions, we can solve any heavily-constrained optimization problem with sampling mini-batch of constraints and achieve similar guarantees compared to projection-basee counterparts while avoiding the heavy dependency on the number of constraints. Another implication of Theorem 4.1 is that we solve heavily constrained optimization with the sample complexity similar to that of an unconstruined optimization problem.
Remark 2. To understand the tightness of our obtained rate, consider which is an instance of our general optimization
ming (x) A =
problem (2). Clearly, any lower bound to solve this instance also holds for the original optimization
problem (2). Xie et al. (2019) provides lower-bound of O ((m + VKM) In (1fe)) for above instance, matching our upper bound in terms of the dependency on the number of data samples, while the dependency K. can still be improved. Furthermore, for the DRO problem with Wasserstein divergence metric, rather than solving constrained optimization problem we solve unconstrained compositional optimization problem. Thus, since solving constrained optimization is more complex than unconstrained optimization problem, we do not expect to obtain any better bound regarding m even for DRO with Wasserstein metric.
Remark 3. In a distributed setting. we are able to improve the sample complexity to O m + + +K/m) In !) with p devices. The proof can be found in Appendix F:3.
4.2 NON-CONVEX OBJECTIVES
We now turn to establishing the convergence of DRO problems with x" and KL divergence metrics for non-convex objectives by making an additional assumption on the variance of stochastic mini-batches.
Assumption 5 (Bounded variance). The mini-batch sampling has bounded variance that is E [[IVVg(#; - [](()]]²] I d² B. where B indicates the butch size.
Theorem 4.3. Under Assumptions 1,2, and using Algorithm 1 for some positive constants 3 and 0 < ( < Vm, denote To 2 -mm5 = O (Vm). For t S. To, let us set = S₁ -B, = 3t Ç and for t. > To set T2 = St Vm. Then, if / after T = Ô (min(1/ve,)) 1/
iterations, with Ô (minlym// 1/c..///.././ number of calls to the stochastic oracle it holds that (=])), < e, where we used Ō(.) notation to hide terms with logarithmic dependency. We also remark that Assumption 5 only needed for convergence until To -/m² and after > To we will not need this assumption. We also note that this assumption is not required in optimally strongly convex setting
3
utilize full batch at the beginning of cach epoch.
Discussion on lower bound. As we discussed in Remark 2, any impossibility result for optimizing Dm gz))) also holds for general compositional optimization problem in Eq. (2). For former problem, Fang et al. (2018) shows that to achieve the stationary point with error e we require at least δ (min ymm ,.b1) (almost optimal) gradient oracle calls for strongly optimal objectives. As a consequence, for the DRO with x² or KL divergence metrics we do not expect less number of constraint checks sample complexity, respectively.
ming (x) A r(x) m
7

---

algorithm with Published as a conference paper at ICLR 2022
Remark 4. In distributed setting with p devices, can improve the convergence rate of DRO with x2 and KL metrics to Ô
min{
ym y/
ctx)) )t. For details, please refer to Appendix F.3. pe
Pe
EXPERIMENTS
In this section, we empirically examine the efficacy of the proposed algorithm in different use cases. The main algorithm that we compare against is Sravily-Constrained algorithm that uses parametric multiplier model proposed in Narasimhan et al. (2020b). We call this algorithm Heavily-constrained where they learn the Lagrange multiplier values using parametric model such as neural network. The tasks we apply the algorithms are mainly focused on fairness constraints since they fit greatly to the problem definition in this paper due to the large number of constraints they add to the main learning problem. In addition, similar to distribution robust optimization approaches, the main goal of fairness constraint is to find a solution that is agnostic to the distribution of protected groups. The code for the experiments is available at this repository.
Distributionally robust optimization for fairness constraints. The first experiment is based on Narasimhan et al. (2020b); Wang et al. (2020), where we want to enforce equality of opportu- nity (Hardt et al., 2016) constraints for different groups while the group membership is noisy and changing during the training. Hence, the problem is to make the solution distributionally robust among different protected groups in the problem. Based on the setup in Narasimhan et al. (2020b), we assume we have access to the marginal probability of the true groups (P (gi = =jl = k)., where 9i is the true group membership and d is the noisy group membership). Hence, to enforce fairness constraints,
consider all possible proxy groups using this marginal probability, which can increase the number of constraints greatly. The goal in this case for equal opportunity is to have the true positive rate of each group in the vicinity of the true positive rate (tpr) of the overall data, that is: tpr(g = j)= 2 tpr(A - e for every proxy group we define.
In this experiment, we use the Adult dataset (Dua & Graff, 2017), and consider race groups of "white"", "black", and "other" as protected groups. We train a linear classifier with logistic regression, and report the overall error rate of the classifier, as well as the maximum violation of the fairness constraints (equal opportunity) over true group memberships. We set e = 0.05 and the noise level to 0.3. Again, we compare with unconstrained optimization and meavill-conssrriig a linear model as its multiplier model. First row of Figure 1 shows the results for this experiment, where the proposed GCIVR algorithm can achieve the same level of constraint violation on true group memberships as the heavily constraint while outperforms it in terms of overall error rate. Hence, the solution found by the GCIVR dominates sravil--consrrinne solution. In terms of runtime speed, the first row of Figure ((c) clearly shows the advantage of GCIVR over heavily censtly-onstrriieed with much lower overhead to the unconstrained optimization.
Fairness Constraints on intersectional groups. In this task we ought to learn a linear classifier with logistic regression to predict the crime rate for a community on Communities and Crime dataset (Dua & Graff, 2017). This dataset contains 1994 instances of communities each with 128 features to predict the per capita crime rate for each community in the US. The labels are high and low crime rates to represent if community is above the 70th percentile of the data not. To add fairness constraints, we first determine different communities based on the percentages of the Black, Hispanic and Asian population in each community, as discussed in Cotter et al. (2019); Narasimhan et al. (2020b). Similar to Narasimhan et al. (2020b), we generate 1000 thresholds of the form (71, 72, T3) [0, 1 to define each group. Consider the population of each race as (Pi, P2, Ps). then a community belongs to group .2.77 if p. 2 7, Ví E [3]. Then the fairness constraints enforce that the error rate of each group should be in the neighborhood of the overall error by margin of e. That is err (fr,,).7:)) ) < err (ALL) + Similar to Narasimhan et al. (2020b), we set e = 0.01 and not consider groups with less than 1% of data.
We compare with the unconstrained optimization and constayyc algorithm with a 2-layer neural network. each with 100 nodes as their Lagrange model. as described in their paper. We compare the trade-off between the error rate and maximum violation of faimess constraints among groups. The second row of Figure portrays this comparison for the test dataset. As it can be inferred, the proposed GCIVR algorithm achieves the same error rate as Heavily-constrainee both higher than the unconstrained optimization. However, comparing the maximum violation of constraints, it is clear that GCIVR outperforms both optimization methods. Also, the third figure shows the runtime of different algorithms. It is clear that GCIVR adding a minimal overhead to the unconstrained optimization, while constricd increases the runtime more than 100 times.
but
8

---

Published as a conference paper at ICLR 2022
DRO Fairness
4.2
Shaes Heaby
Contrsted
OZIVE
Zne The
Castuied
12
-0.1
22141
Well dack
Intersectional Fairness
Unorarund
Jeceerza rd boaly 0111k
Howoky Car suilee
0.00
Eree ftaee
Cimer Tame
MT
Tuzation
baatien
Wellclook Time (mi)
Ranking Fairness
Uncorat af
Hovely Constiient
0.00
Huadly Contraled
striked
Q0243
Max CoaL Vadalbon
2006
COIE
Teeratioss
Iteaatine
Wall-clock Tima (mie)
(a) Error Rate
(b) Max Constraint Violation
(c) Error Rate (Runtime)
Figure 1: Comparison of the proposed GCIVR algorithm with unconstrained optimization and heavily- constrained algorithm Narasimhan et al. (2020b) in three different tasks of fairness and DRO. Each row shows the result for one task based the error rate, max constraint violations and the runtime of the codes. In all the cases solutions learned by GCIVR dominates the heavily-constraiie solution and it converges way faster.
Per-query fairness constraints in ranking. In the third problem evaluate algorithm the fairness in the ranking problem, where we intend to impose per-query constraints on the learning to rank problem as defined in Narasimhan et al. (2020a;b). We divide document-query pairs into two groups based on the 40th percentile of the their QualityScore features. Hence, in this problem, we want learn ranking function 'D Q RR which maps pair of document-query features to real number as the score. Consider the groups of go and 91 as mentioned before, we want the error rate for these groups to be close each other. In other terms, if the pairwise error rate is defined as: (q) E [1 (d. q) < f (d', 4)} y > V/ d E 9i, d' E 9j], where y and y' are the respective binary labels. Then, the fairness constraints can be satisfied as ( err (9) S 4g E Q.
For this experiment, we use Microsoft Learning to Rank Dataset (MSLR-WEL 10K) (Qin & Liu, 2013), which contains 10K queries and 136 features. For this experiment we use non-convex objective, where the model is a two-layer neural network each with 128 nodes and cross-entropy as the loss function. We compare against the unconstrained optimization and the heavily-constraine algorithm with an one-layer neural network with 64 nodes its multiplier model. We use 1000 queries in the training and 100 queries in the test datasets. The third row Figure shows the error rate and maximum violation of groups constraints. As it is clear GCIVR outperforms heavily-constrane both error rate and maximum violations of groups by a large margin. In terms of runtime, GCIVR is very close the unconstrained optimization, and about 2x faster than heavily-constrained.
in
CONCLUSION
In this paper, we showed that many DRO problems or heavily constrained optimization problems can be cast into a general framework based on finite-sum composite optimization. To solve this composite finite-sum optimization, we introduced centralized and distributed algorithms. We theoretically illustrated that our algorithm converges with an almost optimal number of constraint checks (for Wasserstein distance) or gradient calls (for x² or KL divergence metrics). Finally, we validated our theory with number of experiments.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGEMENTS
Amin Karbasi acknowledges funding in direct support of this work from NSF (ISS-1455032) and ONR (N00014-19-1-2406), The work of Mehrdad Mahdavi was supported in part by NSF (CNS-195627)).
REFERENCES
Amir Beck, First-order methods optimization. SIAM, 2017.
Aharon Ben-Tal, Dick Den Hertog, Anja De Wacgenaere, Bertrand Melenberg, and Gijs Rennen. Robust solutions of optimization problems affected by uncertain probabilities. Management Science, 59(2):31 2013.
Dimitris Bertsimas, Vishal Gupta, and Nathan Kallus. Data-driven robust optimization. Mathematical Programming, (67(2)) 292, 2018.
Jose Blanchet, Yang Kang, and Karthyek Murthy. Robust wasserstein profile inference and applica- tions to machine learning. Journal of Applied Probubility, 56(3):830-857, 2019.
Robert Chen, Brendan Lucier, Yaron Singer, and Vasilis Syrgkanis. Robust optimization for non- convex objectives. arXiv preprini arXiv: 1707.0007 2017.
Andrew Cotter, Maya Gupta, and Jan Pfeifer. A light touch for heavily constrained sgd. In Conference on Learning Theory, pp. 729-771. PMLR, 2016.
Andrew Cotter, Heinrich Jiang, and Karthik Sridharan. Two-player games for efficient non-convex constrained optimization. In Algorithmic Learning Theory, pp. 300-332. PMLR, 2019.
Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. Saga: A fast incremental gradient method
with support for non-strongly convex composite objectives. In Advances in neural information processing systems, pp. 1456-1654, 2014.
Yuyang Deng, Mohammad Mahdi Kamani, and Mehrdad Mahdavi. Adaptive personalized federated learning. arXiv preprint arXiv:2003.1346/ 2020.
Yuyang Deng, Mohammad Mahdi Kamani, and Mchrdad Mahdavi. Distributionally robust federated averaging. arXiv preprint ax2iv:2/02./2666) 2021.
Michele Donini, Luca Oneto, Shai Ben-David, John Shawe-Taylor, and Massimiliano Pontil. Empiri- cal risk minimization under fairness constraints. arXiv preprint arXiv: arXiv:/802.0866: 1802.08626, 2018.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL htttt:///acciiiee. ics uci. edu/ml.
John Duchi and Hongseok Namkoong. Variance-basse regularization with convex objectives. arXiv preprint 1rXiv:1610.02581, 2016.
John Duchi and Hongseok Namkoong. Learning models with uniform performance via distribu- tionally robust optimization. The Annals of Statistics, 49(3): 137--161778 2021.
Peyman Mohajerin Esfahani and Daniel Kuhn. Data-driven distributionally robust optimization
using the wasserstein metric: Performance guarantees and tractable reformulations. Mathematical Programming, (71(1):115 166, 2018
Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non-convex optimization via stochastic path integrated differential estimator. arXiv preprint 1 2018.
Marguerite Frank, Philip Wolfe, et al. An algorithm for quadratic programming. Naval research logistics quarterly, 3(1-2):95-110, 1956.
Farzin Haddadpour and Mehrdad Mahdavi. On the convergence of local descent methods federated learning. arXiv preprint arXiv: 144.5 2019.
10

---

Published as a conference paper at ICLR 2022
Farzin Haddadpour, Mohammad Mahdi Kamani, Mehrdad Mahdavi, and Viveck Cadambe. Local sgd with periodic averaging: Tighter analysis and adaptive synchronization. Advances in Neural Information Processing Systems, 2019a.
Farzin Haddadpour, Mohammad Mahdi Kamani, Mehrdad Mahdavi, and Viveck Cadambe. Trading redundancy for communication: Speeding up distributed sgd for non-convex optimization. In ICML,, pp. 2545-25544 2019b.
Farzin Haddadpour, Mohammad Mahdi Kamani, Aryan Mokhtari, and Mehrdad Mahdavi. Fed- erated learning with compression: Unified analysis and sharp guarantees. arXiv preprint arXiv:2007.01 154, 2020.
Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning, Advances in neural information processing systems, 29:3315-3323,, 2016.
Tatsunori Hashimoto, Megha Srivastava, Hongseok Namkoong, and Percy Liang, Fairness without demographics in repeated loss minimization. In International Conference on Machine Learning. pp. 1929-1929999 PMLR, 2018.
Zhouyuan Huo, Bin Gu, Ji Liu, and Heng Huang. Accelerated method for stochastic composition optimization with nonsmooth regularization. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
Martin Jaggi.
Revisiting frank-wolfe: Projection-free sparse convex optimization. In International Conference on Machine Learning, pp. 427-4344455 PMLR, 2013.
Anatoli Juditsky, Arkadi Nemirovski, and Claire Tauvel. Solving variational inequalities with stochastic mirror-prox algorithm. Stochastic Systems, 1(1):17-58, 2011.
Dionysios S Kalogerias and Warren B Powell, Zeroth-order stochastic compositional algorithms for risk-aware learning. arXiv preprint 1rXiv:1912.09484 2019.
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the polyak-tojasiewicz condition. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 795-811. Springer, 2016.
Daniel Kuhn, Peyman Mohajerin Esfahani, Viet Anh Nguyen, and Soroosh Shafieezadeh-A Abadeh. Wasserstein distributionally robust optimization: Theory and applications in machine learning. In Operations Research & Management Science in the Age of Analytics, pp. 130-166. INFORMS, 2019.
Daniel Levy, Yair Carmon, John C Duchi, and Aaron Sidford. Large-scale methods for distributionally robust optimization. arXiv preprint arXiv:2010.05893, 2020.
Xiangru Lian, Mengdi Wang, and Liu. Finite-sum composition optimization via variance reduced gradient descent. In Artificial Intelligence and Statistics, pp. 1159-1167. PMLR, 2017.
Mehrdad Mahdavi, Tianbao Yang, Rong Jin, Shenghuo Zhu, and Jinfeng Yi. Stochastic gradient descent with only one projection. In Advances in Neural Information Processing Systems 25
(NIPS), 2012.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, et al. Communication-efficiinn learning of deep networks from decentralized data. arXiv preprint arXiv: 162..0660, 2016.
Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic federated learning. arXiv preprint 192.001902.00144 2019.
Hongseok Namkoong and John C Duchi. Stochastic gradient methods for distributionally robust optimization with f-divergences. In NIPS, volume 29, pp. 2208-2211 22,,, 2016.
Harikrishna Narasimhan, Andrew Cotter, Maya Gupta, and Serena Wang. Pairwise faimess for ranking and regression. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. $248-5255, 2020a.
11

---

Published as a conference paper at ICLR 2022
Harikrishna Narasimhan, Andrew Cotter, Yichen Zhou, Serena Wang, and Wenshuo Guo. Ap- proximate coivily-constrained learning with lagrange multiplier models. Advances in Neural Information Processing Systems, 33, 2020b.
Ion Necoara, Yu Nesterov, and Francois Glineur. Linear convergence of first order methods for non-strongly convex optimization. Mathematical Programming, 175(1):69-007, 2019.
Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach stochastic programming. SIAM Journal on optimization, 19(4):1574- 1609, 2009.
Yu Nesterov, Gradient methods for minimizing composite functions. Mathematical Programming, 140 2013.
Lam M Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáč. Sarah: novel method for machine learning problems using stochastic recursive gradient. In International Conference on Machine Learning, pp. 2613-2621. PMLR, 2017.
Farzad Pourbabaee. Robust experimentation in the continuous time bandit problem. Economic Theory, pp. 1-31, 2020.
Qi Qi, Zhishuai Guo, Yi Xu, Rong Jin, and Tianbao Yang. A practical online method for distribution- ally deep robust optimization. arXiv preprint 201.::3000.11333 2020a.
Qi Qi, Yan Yan, Zixuan Wu, Xiaoyu Wang, and Tianbao Yang. A simple and effective framework for pairwise deep metric learning. In Computer Vision-ECCV 2020: 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Part XXVII 16, pp. 375-391. Springer, 2020b.
Tao Qin and Tie- Liu. Introducing letor 4.0 datasets. arXiv preprint 10665:13 2013.
Hamed Rahimian and Sanjay Mehrotra. Distributionally robust optimization: review. arXiv 2019.
preprint ar
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. 2019.
arXiv preprint
Soroosh Shafieezadeh-Abadeh Peyman Mohajerin Esfahani, and Daniel Kuhn. Distributionally robust logistic regression. arXiv preprint 1rXiv:/509.09253 2015.
Alexander Shapiro. Distributionally robust stochastic programming. SIAM Journal on Optimization, 27(4):2258-222 2017.
Aman Sinha, Hongseok Namkoong, Riccardo Volpi, and John Duchi. Certifying some distributional robustness with principled adversarial training. arXiv preprint arXiv:1710.10571, 2017.
Mengdi Wang and Dimitri P Bertsekas. Incremental constraint projection methods for variational inequalities. Mathematical Programming, 150(2):321-36) 2015.
Mengdi Wang and Dimitri P Bertsekas. Stochastic first-order methods with random constraint projection. SIAM Journal on Optimization, 26(1):681-71) 2016.
Mengdi Wang, Ji Liu, and Ethan X Fang. Accelerating stochastic composition optimization. arXiv preprint (007.066000773000 2016
Mengdi Wang, Ethan X Fang, and Han Liu. Stochastic compositional gradient descent: algorithms for minimizing compositions of expected-value functions. Mathematical ProneeaaaaiaaaPPProooooo Programming, 161(1-2); 419-449, 2017.
Serena Wang. Wenshuo Guo, Harikrishna Narasimhan, Andrew Cotter, Maya Gupta, and Michael I Jordan. Robust optimization for fairness with noisy protected groups arXiv preprint arXiv:2002.09343. 2020.
Guangzeng Xie, Luo Luo, and Zhihua Zhang. A general analysis framework of lower complexity bounds for finite-sum optimization. arXiv preprint arXiv: /908. 08394, 2019.
12

---

Published as a conference paper at ICLR 2022
Yan Yan, Yi Xu, Qihang Lin, Lijun Zhang, and Tianbao Yang. Stochastic primal-dual algorithms with faster convergence than o(I/VT) for problems without bilinear structure. arXiv preprint arXiv:1904. 2019.
Yan Yan, Yi Xu, Qihang Lin, Wei Liu, and Tianbao Yang. Sharp analysis of epoch stochastic gradient descent ascent methods for min-max optimization. 2020.
Yaodong Yu, Tianyi Lin, Eric Mazumdar, and Michael Jordan. Fast distributionally robust learning with variance reduced min-mat max optimization. arXiv preprint arXiv:2104. 13326, 2021.
Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez-Rodriguez and Krishna P Gummadi. Fairness constraints: A flexible approach for fair classification. The Journal of Machine Learning Research, 20(1))2737-2778, 2019.
Jingzhao Zhang, Aditya Menon, Andreas Veit, Srinadh Bhojanapalli, Sanjiv Kumar, and Suvrit Sra. Coping with label shift via distributionally robust optimisation. arXiv preprint wrXiv:2010.12230 2020a.
Junyu Zhang and Lin Xiao. composite randomized incremental gradient method. International Conference on Machine Learning, pp. 7454-7462. PMLR, 2019a.
Junyu Zhang and Lin Xiao. A stochastic composite gradient method with incremental variance reduction. arXiv preprint w7X1::1906.10186, 2019b.
Mingrui Zhang, Zebang Shen, Aryan Mokhtari, Hamed Hassani, and Amin Karbasi. One sample stochastic frank-wolfe. In International Conference Artificial Intelligence and Statistics, pp- 4012-4023. PMLR, 2020b.
13

---

Published as a conference paper at ICLR 2022
Appendix
In the appendix, we provide the missing proofs and derivations from the main manuscript, as well as proposing the distributed version of Algorithm to further improve the convergence speed.
TABLE OF CONTENTS
Example of Equivalent Wessterstein Reformulation
15
B Obtaining Augmented Optimization Problem
15
Proof of Claim 2.1
15
Strongly-convex convergence for DRO with KL and x" metrics
16
Distributed Stochastic Composite Algorithm
16
F
Proof of Theorems 4.1 and F22
17
F.1
Computational complexity of Theorem 4.1 and Theorem D.I Computational Complexity of strongly-convex objectives Corresponding to Theo-
19
F22
rems 4.3
20
F33
Convergence analysis
20
G Proof of the Distributed Algorithm G.I
22
General Lemmas
22
H Approximate Approach For DRO with Wesserstein Metric with Non-convex Objectives
25
14

---

Published as a conference paper at ICLR 2022
A EXAMPLE OF EQUIVALENT WESSTERSTEIN REFORMULATION
A tractable reformulation of distributionally robust logistic regression problem by reduction to constrained optimization problem is provided in Shafieezadeh-Abadeel al. (2015) as follows:
min
r(x) A de
+
8t
m i=1
subject to
((x)) (Lg(z, y) 8,) 0, Vi E [1 m]
91 (a) (la(2, -y) Am - 83) s 0, vj [1:
ge a:) - (11311² - -12) 0
(13)
where (z(2zy) = log (1 + exp (-y (3, z))) is the associate loss with parameter 3 and the data sample (z,y) y) and we define (z, $1,.... ,m X, 3).
B OBTAINING AUGMENTED OPTIMIZATION PROBLEM
To derive the smoothed constrained variant of original optimization problem we follow the reduction method originally introduced in Mahdavi al. (2012) to get:
min (
min
r(x)
+
max
Σ (()
+ H
P1
P2
Dm
Pm++1
OSP Sa.
a
m
(g)(
min
r(x) + In
1
exp
))) + + (n ?
())(())
min
r(x) y In
exp
m +
min
(x) + y In (m + 1)
(14)
Constant
where in Eq. (14) we used the definitions (xx)) = r(x) + +y (g(x)), gi(xx) exp (0)((z) and g(x)) + [1 E (x)). Since y In (m 1) is constant, the minimizer of both (x) and ( is the same, and consequently we can solve the optimization problem for Y via finite-sum composite optimization.
C PROOF OF CLAIM 2.1
We use Lagrangian multiplier for the purpose of the proof. The Lagrangian of the optimization problem in Eq. (4) is
m
m
m
]
L(x,7; A)
max 05p:51, 2
Σ
p.l((a))) - 7 -2m
Σ
(mp: 1)2
Σ P:
(15)
i=1
1=1
1=1
By setting V,, L = we obtain
Pt [(((x) - ((i(m)) +
(16)
Then from the condition E. 1, it follows that:
x 1 Σ f()))
(17)
15

---

Published as a conference paper at ICLR 2022
Plugging the obtained values for X and p; into Eq. (4) yields
27
v(: = +
f((z))
Σ
f((z))
fi
f1(z))
1=1 7m
m
2
m
2
1
-1-
fi(xz)
Si(
27 x m
m
[f((z))]
+
f (x:
(18)
2'm
2"
2m
which completes the proof.
D STRONGLY-CONVEN CONVERGENCE FOR DRO WITH KL AND X² METRICS
Theorem D.1. Suppose Assumptions 1 and 2 hold, and also assume is p-optimally strongly
convex. If we set Tt = S: = B: mm and T 5 letting Lo+ LLttVLL++6G +36G/
2 by letring
Vmpni
using Algorithm after K = In (1/e) repetition solves the optimization problem in Eg. (2) with convergence error (z vx((()) S with O ((m + k/m)) In 2) number of gradient calls. Therefore, depending on the functionnn W this sample complexity corresponds to both DRO problem with x² and regularized KI. metrics.
(((+1) = GCIVR (x)(k) =
Based on Theorem D.I, for DRO problem with X2 divergence metric, we can achieve ( (x)))) & 7E and v (a (a( - (2(()))) I with O ((m + km/) In !) number of gradient oracle calls.
E DISTRIBUTED STOCHASTIC COMPOSITE ALGORITHM
In the main body, mainly focused studying the sample complexity of solving DRO problems centralized setting. The question we are interested that "Can we further improve the sample complexity?" ? In this section, give affirmative answer to this question via studying distributed version of DRO problem. We suppose data samples are distributed among clients For distribution- ally robust optimization problem via Wasserstein. x2 and KI. divergence metrics in the distributed fashion like federated learning setups McMahan et al. (2016); Mohri et al. (2019); Haddadpour et al. (2019b); Haddadpour & Mahdavi (2019); Haddadpour et al. (2019a); Deng et al. (2020); Haddadpour et al. (2020).
We suppose that each device has at least m/p number of data points.
16

---

Published as a conference paper at ICLR 2022
We first introduce our distributed finite-sum compositional algorithm detailed in Algorithm 2.
Algorithm 2: Distributed Generalized Composite
Incremental
Variance Reduction
(DistGCIVR(z!0)
Inputs: Number of iterations =, .,..., T, learning rate initial global model (0) and a set of triples (7r, B,, ] where Tt indicating the size of epoch length and mini-batch sizes of B, and
St at time 1.
for t ,...., T do
for i
1, .....---'' do in parallel
Sample minibatches (3()) with size B, uniformly over [m] and compute
yo (1.4)
1 B
Σ
20
(1,0)
1
Σ
;),,
w
(1.1)
1
Σ
B.
B. (EBUL.))
(EB(C.))
(EBOL.)
Server computes (1)
p -i=1 Vo
(1.1) (1) Ei=1 =0
(1.5) and (1) = p w
w
(t,i)
Server computes {z (
= (f(sh) ())) +wp (t)
2
Update the model as follows and broadcasts it to devices
(4) IT
an0 {x(2:!)) (()((()))
for j - I,..., Tt 1 do in parallel
Sample set 5(6 ((t.3) with size St over [m]. and form the estimates
[t,i)
(t.5)
Σ
[ :E) (:())
y yj 1-1
S
(ESf
2/
zj-1
(1.f)
Vgi(m!
Va((a/2155)
(19)
$E
w. w
(1,1)
1-1
(t.i)
[hi(a)(::)) Vh
(20)
S
(ES((.))
and send y (t,i) and z (f.)) back to server
Server computes yj p E Uj (1.1)
2. = Ei =/ and
(t)
1 (1) DE 3 (1,2)
Compute {~x))))) (1)
(z T (r(w) + +
Update the model as follows: (t)
2f III (2)) (0(2))))
end end end
Output: Return randomly selected solution from {xt (
We emphasize that our algorithm is developed based on Algorithm 1, so we only describe the main differences. In the the distributed setting, in epoch t, i-th device has local version of global model,
ie., y (f,i) x (1,6) w (t,4) and at the beginning and during the epochs all devices send back their local models back to the server be averaged and global model æ to be updated. Then, server broadcast global model to the devices.
F PROOF OF THEOREMS 4.1 AND F.2
Before proceeding to the proof of this theorem, we need to mention that for Wasserstein DRO problem the main objective r(æ) is an affine function of input data. This property naturally satisfies condition (5) in Assumption and will be useful distributed setting. For an illustrative example please see Appendix A.
17

---

Published as a conference paper at ICLR 2022
Proof of Theorem 4.1:
Suppose that x<*) is the solution for the following optimization problem:
minimize r(æ) 1 m
fi();)
m
(21)
subject
g1(2) 0, Vi E {1, ,
0 }]) we have
Defining ((x) A r(x) + In
m -i=1
m+II
exp
V (x)
A ((x) + y In(m + 1).
Noting that x(k) and (K) are the output of algorithm with and without projection to the constraints set
K=
fx (x) 0, Vi [1 m]]
(22)
respectively. Our proof is based on following two steps:
(1) We first show that E gence rate of stochastic compositional optimization problem depends on used algorithm without any projection.
< (x((())) + O (exp(-oX)), which indicates the conver-
(2) Second step involves showing that E [r()(K)) S ((((())++0 +0 (exp(-aK)): in other words the final projected solution converges to optimal solution of augmented objective function and is some positive constant depends condition number
We note step (1) follows directly from Theorem 8 in Zhang & Xiao (2019b). In the following, we prove step (2). First note that as (x(x)) I 0 for all 1 S S m, we have:
1
m
Og (3)
V(((+)) = r(x(()) + 7l1
exp
m7
+
i=1
r(x(()) + y
1
+
Σ (1)
m
m
= =(((
(23)
This leads
(xx(())) S r(2)(*)) + + 11)
(24)
Therefore, using item (1) have:
E
[ S (r()(()) + (expp(-a)))
(25)
On the other hand, due to the definition of (xx) and smoothed max or log-sum property, we have:
(x) 2 (k)) + max 1sism
(z)))()(()))
(26)
For the purpose of lower bounding the second term in Eq. (26) need the following Lemma:
Lemma F.1. T o xF, by defining ()) A max 9i (K)( for all [1: : m) have:
g(x((K) 2 p - (K)
(27)
The proof of this lemma can be found in Mahdavi et al. (2012) but for the sake of completeness we also include the proof.
Proof. As (K) is the projection of (K) into K:; i.c., (K) arg min - x then due to -( ())
first order optimality condition, there exists positive constant such that
(kx(K)) 0 s.t. x(K) (K) RV ( (K)
(28)
18

---

Published as a conference paper at ICLR 2022
As result we have: g(xxl)) )((x(k)) (0x(k)) 2 (2(k)) x((1) Vy(a(()) (0000) - |(( (o(orlan)
- where (80) follows from Assumption 3.
(2) - - |
(29)
Hence, we have:
+ ap (,/ - -x()))))()))) x
(30)
Moreover, note that have:
(k)x v r(xx(*)) + + In (m + 1) + 0 (exp(-aK])
(0.0)((2((3))
max
1sism
(-(z(() + 7 1) + 0 (exp(-ak))
Next, we can write:
r(xx - k() = -((x()))
+ +r(x(k)) -r(x((1)) -r(z((1)
I r()x(k)) (k)
I G [ (x x
(31)
Eqs. (24), (30) and (31) lead to the bound:
upl (af - =x(k)
S ((x)())) - (k))(k)) + + 7/1 (m + +
s < (z - x(K)) + (m (mpp
(32)
which allows us to the following:
(k) (k))
oxp - G ap - G 0 (exp(-aK))
7 mm
(33)
Finally, we have:
(()(K)) = r(# {)) - (k) + (()
s G x (K) - [1/)|| -x(11)
+ (1) (8)
G n In(m + 1)
+ ap G (oxp(-aX)) + + + 1) +r(x(+)) + (exp(-oK))
ap- G
Cost violating constraints
(34)
Therefore, by setting ? exp(-aKi ln(m+1) we achieve the desired result.
Proof of Corollary 4.2:
The proof follows directly from Eq. (34).
Proof of Theorem D.I:
The proof follows directly from Theorem 8 in Zhang & Xiao (2019b).
F.1
COMPUTATIONAL COMPLEXITY OF THEOREM 4.1 AND THEOREM D.I
Given the GCIVR algorithm, the sample complexity for Theorem 4.1 (where S., B, and T, are fixed)
is
5
5 Vmmm, /m/mm)lnn1//
0 (max 2T))) K) 0 maxxmm,
m) maxf2
Vmp
Vmpn
= =0 mmax m,
10 vmm In(1/c))
m + max
Mmpm
pn
0 00 mmm
In(1/e))
(35)
19

---

Published as a conference paper at ICLR 2022
Proof of Theorem 4.3: The proof follows directly from Theorem 4 in Zhang & Xiao (2019b).
F.2 COMPUTATIONAL COMPLEXITY OF STRONGLY-CONVES ORJECTIVES CORRESPONDING TO THEOREMS 4.3
From Theorem 4 in Zhang & Xiao (2019b) for non-convex objectives we have: if T S To
I
(, $
(36)
In
else > To:
Vmll To+1)
Considering the GCIVR algorithm and the bound in Eq. (36), the sample complexity for Theorem 4.3 (where St and Tı are fixed) can be expressed as follows:
- (B.
(B. + S
( < To = 0 (vm):
B + ST)
(10 mE) To 0 (Vm),
0 2 2 +3)2
if 0 (12) < To 0 (vm)
Vime x (m Vmym)
0 > Th 0 (vm),
(T2)
if = 0 s T. = (m
T 0= > To 0 (vm).
3/2) ((22
if ( < To 0 (Vm), T T= (1//m/ > To 0 (vm),
mm
(37)
Therefore, depending on how large /m is and also desired accuracy level c, decide choose an adaptive or a non-adaptive approach.
F.3 CONVERGENCE ANALYSIS
In this section, extend assumptions used for centralized setting to distributed counterpart as follows:
Assumption 6. We have the following assumptions:
[f((;)) - f( || < Ln
| x2ll where 3.; 22 E R. We also assume that
[(x1) - f(x2) < la |
x2
2) - (2))] < Ln [0] - Ø2l where 3 D2
E Rdd. We also assume that
hy(x1) - h < 4 ( xzll
3) (Z) (z2:
I 1 x2 and (1);(01; gj (xx2: E)ll
Ey || - x221 for Yan 22 E Rd and Sisp..
4) We suppose that (=x) in Eq. (2) is bounded from below that & inf (xx)) -00
5) We assume r(x) E I U {oc} is a convex and sevrcosemionssssus function.
Assumption 7 (Unbiased estimation). The mini-batch sampling is unbiased that is E (2; g, (x) and (x; E)] = (z) for < S p.
Convergence Analysis for Strongly Convex Objectives:
Assumption 8. We additionally for the DRO problem with Wessterstein metric suppose that the function r(x) is smooth with module G.
Theorem F22. Under Assumptions 3 and 6 to 8, when V is pu-optiallly strongly convex, if we exp( exp(-K)
2 set T. S. VB, /m and T "mppy and 7 In(m+1] letting 1j La+ +36.
and G if we let (k+1) DistBCo (x)( for O,...,K
using Algorithm after K = (I/e) stages and returning the final solution after projecting onto the constraint set (x)g(()) S 0,i 1,2,... m!) i.e., ((K) (x(xx(1)),, solves the optimization problem in Eg. (3) with convergence error ((x( - -r(x)()) S with
0'
mmm In 1 1 0 (( [m+ p
(38)
20

---

Published as a conference paper at ICLR 2022
per device number of constraint checks.
Remark 5 (Computational Complexity). The sample complexity for Theorem F.2 (where St, B₁ and Tt are fixed)
5
O (max(TBB,I755) K)
max
m) max
v vmym) In(1/e)
p Vmpnj
Vmuu
10 Vm. In(1/e)
mmx m. Vmum 0
m + max
pnj
0
m
In(L/e)
(39)
Convergence Analysis for Non-Convex Objectives: For the non-convex also need the following extra assumption.
Assumption (Bounded variance). The mini-batch sampling has bounded variance that is
(Vg Vo)(z))) s
for 1 S S m.
Theorem F.3. Under Assumptions 9 using Algorithm for some positive constants and
S < vm; denoting To & ym- (v)m), if S To, parameters are chosen to be
D
St = /B, Bt + S; and when t > To. set Ti St mm. Then, if 1) < Lo Lo+V13+120 +12G
holds that
(T
11]
27
In 0
T
if S To:
E
(40)
T To:
Vm
To+1)
This leads to the per device sample complexity of Ô (minn pc notation hides logarithmic factors. Therefore, depending on the objective function this sample complexity corresponds to both DRO problem with x² and regularized KL metrics.
m
2t3) where Ö(-)
We highlight that while in distributed setting we can not reduce computational complexity in terms of order of magnitude, we can reduce computational complexity partially linearly with number of devices.
21

---

Published as a conference paper at ICLR 2022
G PROOF OF THE DISTRIBUTED ALGORITHM
For the convince, we define the following notations
< {
to denote the set of local solutions and sampled mini-batches at iteration at different machines, respectively.
We use notation E|-] to denote the conditional expectation Egco [-]
G.1 GENERAL LEMMAS
Before proceeding to the proof of main theorems, we first review a few properties of our algorithm that will be useful in our convergence proof:
= y + -
(1,0)
(0)
= + Voi(2))) - Voi(2.f11)
E
w
(t.0) w j- + (Z ( Vhi (2)
(41)
which due to linearity and taking average over the models of all devices, leads to
yー + g(x,) (1) g(a
(t)
(42)
(1)
(t)
= =2 + Vg(z)() - Vg(a)_1)
E
(t)
w + vh(af)) vh(a/21))
(43)
Additionally, we have equivalent update rule as follows:
リ
+
Σ
[o(ay ( -0(0((211:)))
(44)
S(x)
SES(
2 2-
(0)
Vg(az))
()(x)))))) ;5) vo(a{(2:55
S(0)
(ES()
w (1)
w (8)
w-11
Vh(al ;5) vh(a/2,1
(45)
S
()
Lemma G.1. For any 1 J S Tt we have:
y 9 (zx) (1) )1
(1) (0) )1²
22,1
(9)
||]
E
y0
+
S(1
E
a
(46)
2) of (a)))) 11
(4) g (2)) (1) |1']
122
2 2001
E
<
E
(0)
s(1)
E
W - H (0 )1
<
R¹ (o05)) |||
13
E
|0.00
20
[0/
(47)
StO
We note that Lemma G.I is the generalization of Lemma in Zhang Xiao (2019b), and we provide the proof for the sake of completeness.
Proof. Our proof can be considered as a generalization of the proof in Zhang & Xiao (2019h) to distributed setting. For this end, we use the following equation for every fix vector u.
Var( (x) E || u
[2]
|
[x] ul|
(48)
22

---

Published as a conference paper at ICLR 2022
Therefore, letting = =((x,))) obtain:
E Dj 5(x,) (0)0))
B
0(x/51) /| + Var (1)0
22
(12)
12
- )| Var (0)0 (0)
(49)
The final step of proof involves bounding the term Var (u²*) (a)*) as follows:
(1000 (0) Var
Vj (
= Var
Σ
( ;5) s(m)/1i (a.50)
S(0)
SES(1)
g((z) :E) (
g(a (0)
Var
S(0)
[1((e))) {)) - 1 || | (>)"))
S(1)
E
10)
(1)
(50)
S(A)
where (e) and (s)) follows from the definition of Var(.) and Assumption 6.
The proof for Eq. (47) follows similarly.
The rest of the proof is similar to Zhang & Xiao (2019b) but for the sake of completeness add the rest of the proof. For this purpose, use the notation 4(x) & h(x) f(((x) and
{))))))) = (z/²) ('(
(1) T
(1) + w
Lemma G.2. Under Assumption 6 we have:
(o(ae))) - (2 (0)
19
Go 5Te)
Σ E || 10 - x 101
of
E
(51)
BiO)
with definitions Go 3 3 15 + 17133) and of 3 133 9770 + +0%)
Proof. Using Assumption 6, we obtain:
( (0) v |
2 ( f( ((("")) |7
E
(2)0) "( ",00
w0 n1(z,))) 12
E
(2 -(a 3E (1 1|
< 3E
|10000 11 N((m!o)) 1/
+ 3E
Assumption
3
122000 g( (1)
+
(1)
- 2, [001]|]]]
3E
m
h' (2) )
23

---

Published as a conference paper at ICLR 2022
Next step of proof is to utilize Lemma G.1 in Eq. (52), which leads to
+
( -vo(o)))]
Σ
E
10
x0(1)
+ 3.3 (1,13) E
yb 20 |9
(0) (2) |2)
S(0)
+47) 2000 2 =0/"19
3L3
|10500 20(00 ||]
wwb - 11 (a)) (ao5)) 2
)²
+
IB
+ 3B
S(t)
(gL) + +89 + LR) S(9)
(a)
2
18
+
B
(53)
where (a) comes from algorithm and computing initial full batch in the beginning of each epoch, and using Assumption 9 as well as following bounds:
(t) yo g(ab))
S
of
20 g((00)))
[1]
og.
and
wh (6)
n1(x0) (1))
) 11?
S
of.
B
B(t)
B
(54)
The rest of the proof is to show that E (x33) where (a)
7 (a)) - -aff1) and
ut a (t)
However, Algorithm 2 produces approximate proximal gradient mapping:
(z))))))
- 1 x0) =ff11)
(55)
7
So the following Lemmas connect two gradient approxima- where & ( 117 (2)) ( 17 (V(xa))
tions:
Lemma G.3. We have:
E [[,3[ s 2E
[,,(33) [22 + 21E
-
(56)
Proof. Using triangle inequality x
(10)
s+1
1|
$ 2
2
5+1
(0)
||
+2 +2|10000
(0)
2 | and the
definition of (m) (1) and Gi, (zrg), we have
G (x²3) ||"
2
(t) 2
(1 < 2
#z+1
172
( ||]
2
(z(1)
M1 (z) - (T(x (0) 1)|
2E
m
n
2E
||,,(a3)
(0())))
(0) vo(a (3)
(57)
Based on the definition (x)) & F(g(x)) + h(x) + r(x) we have the following lemma:
Lemma G.4. With definition L+ = LF + Lp. we have:
E V (a
[xx - (1 L E | + vo(aa))) - {0(06'))
(58)
24

---

Published as a conference paper at ICLR 2022
and
E
(
(1) (+1
E
||]
3m E
|
[|]
1 4nj
L
x 32 11
IE
(59)
Proof. Using Læ-Lipschitz continuity of v and the optimality of the + stronggy convex of subprob- lem (r(z)), we obtain
(a F(o(a)ff1)) + r(a
S )( +) V (3) -
vh(a))))
(0)
(0)
LF + Ln
11111 - -000 + +raaff1)
:4111 2jj
2
=F(g(a))) )) + h(2)²) ([FF((())) )) - {n(z)())
, 2/ (1)
2 J+1 -x) 1/01 + rr(fff))
(t)
21
([VF((()))) (6)
+ vh(a)/)) (F(o(=)))) ))) )
2 ,2,41 - x
(1)
(0)
1
LF + Ln
|0/011
(1) "
-
24
2
F(((a))))) + h1(z (1)) + r(())))) (1)
1
(1) (1)
2
LF + Ln
|
(1) - -x 200
27
j+1
21
2
"/
[ 11) vh(ag0)
- (g( (9) )) Vh(a,) (2)
]]]]
1
(2)
=1,
2
+
217
= -Vaag))
1 1 10 2n
92
1
LF + LA
| - 0/
+ 2
(o (0)
V (1r))
(z/)) ))( ||
2m
2
(60)
Next, we complete the proof by taking expectation from both sides of Eq. (60) concludes the proof of Eq. (58).
Next, using Lemma G.2, we have
" E ||ا,ا
||] - - BBB [10,((3))
+ "B 4
|
[|]
(61)
We can prove Eq. (59), by simply adding Eq. (61) to both sides of Eq. (58).
We note that Lemmas G.3 and G.4 are an extension of Lemma 3 and 4 in Appendix Section of Zhang & Xiao (2019b) with difference that here the function (x) includes extra function h(x),, which leads to La = LF + La which is bigger than Lr in Zhang & Xiao (2019b).
The rest of the proof is same as the proof of Theorems 4 and 8 in Zhang & Xiao (2019b) which is based on Lemmas G.3 and G.4, and for more details we refer the reader to the Appendix section of the reference Zhang& & Xiao (2019b).
H APPROXIMATE APPROACH FOR DRO WITH WESSERSTEIN METRIC WITH NON-CONVEX OBJECTIVES
For the non-convex objectives, the optimization problem in Eq. (3) can be upper-bounded with the optimization problem as follows:
m
inf sup Eq [xxx;)]] minimize ØEX QEDx
r(x)
fi(x))
(62)
x m i=1
subject to 0x(x) < 0, Vi E (1....,m)
25

---

Published as a conference paper at ICLR 2022
We note that for the case of convex objective in optimum solution inequality holds with equality; however, in case of non-convex cost functions we do not have equality necessarily. We note that Eq. (62) with non-convex constraint can not be easily solved via augmented function approach in previous section. In order to solve the upper bound optimization problem in Eq. (62) efficiently via suggested composite approach. For this end, suggest to solve the following optimization problem where in constrained are modified to be convex:
m
minimize f(x)
fi;);)
(63)
m
subject to 9: (x) + |
< 00,
m
(64)
where we choose 9i such that 9. are strongly convex. Therefore, we have the following relationship between optimization problem:
inf sup EQ [h(x; < =ex QEDN
minimize r(x) A
f((x))
(65)
1=1
subject to g:(x) S 0, Vi E {1,..., m}
1 m
minimize
r(w)
fi(x;)
(66)
m
subject to (x(x) + in | 1| S 0, vi E m
(67)
26


Reviews:
[{"review_id": "iTKVVG6jrDW", "reviewer": "Reviewer_rHQv", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well written and the method is well motivated. The theoretical analysis seems to be incremental and is very similar to those in the literature such as Fang et al. and Zhang & Xiao. \n\nCan you explain the intuition behind Assumption 3? Why is there a gradient lower bound imposed?\n\nWhat is the choice of \\gamma in Corollary 4.2 that makes the results match that in Theorem 4.1?\n\nIn the experimental results, the variance seems to be very high. How many repetitions are conducted to obtain the results?\n\nWhy did you only compare with one baseline algorithm in the experiments? Although the algorithm structure and the relaxation might be different, it will be good to see the empirical comparison of the proposed algorithm with other algorithms on distributionally robust optimization such as those in Table 1. \n", "summary_of_the_paper": "In this paper, the authors propose to study different distributionally robust optimization problems in the same form of a composite optimization problem. They propose a variance reduction type of gradient based algorithm to solve the composite optimization problem and prove the convergence rate in both (strongly) convex and nonconvex settings. \n\n", "summary_of_the_review": "My recommendation is mainly based on the contribution of this work in theoretical results compared with existing work. ", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "JSsy3m7sXJs", "reviewer": "Reviewer_Q3eH", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "The paper provided a novel view of DRO as composite optimization with theoretical guarantees.  The mini-batch constraint sampling for handling heavily-constrained optimization problem is also interesting.  The experiments on the application to fairness are comprehensive and convincing.  \n\nThe main weakness is that the convergence analysis heavily depends on the existing work (Zhang and Xiao, 2019b).  The only difference is the extra empirical risk term.  It is not clear that what is the main challenges in this slightly modified setting. \n\nOther comment:  Is optimally strongly convex condition the same as PL condition?   It seems that no reference about this condition is mentioned and no specific examples are given. \n\n\n**The authors have addressed my questions and the technical differences from (Zhang and Xiao, 2019b)", "summary_of_the_paper": "The paper views different variants of DRO are simply instances of a finite-sum composite optimization, from which efficient optimization algorithms were proposed. The convergence analysis was established for strongly-convex and non-convex settings.  The effectiveness of the proposed algorithm are well demonstrated in experiments. ", "summary_of_the_review": "In summary, the paper seems to be very interesting.  It regards DRO as a composite optimization problem and proposed a a novel mini-batch constraint sampling for handling heavily-constrained optimization problems. The efficiency of the proposed algorithm is sufficiently validated by experiments. The originality and novelty of the proof techniques are very limited. ", "strength_and_weaknesses": "", "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": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "0mLY9jTJsHQ", "reviewer": "Reviewer_Wug8", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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": "Strengths \n1. clearly written and provide comprehensive comparison among relative works\n2. The summarization of different variants of DRO are simply instances of a finite-sum composite optimization is interesting\n\nWeaknesses:\n1. While the summarization  is interesting, all of them seems already justified by other literatures. \n2. The theoretically improvement of the proposed algorithm seems not that significant. ", "summary_of_the_paper": "This paper targets on solving distributionally robust optimization (DRO) that considering   distribution shifts in the data. In this paper, they show that  how different variants of DRO are simply instances of a finite-sum composite optimization for which they provide scalable methods by utilizing variance reduction algorithm. They also provide empirical results that demonstrate the effectiveness of our proposed algorithm with respect to the prior art in order to learn robust models from very large datasets. ", "summary_of_the_review": "The paper is clearly written and provide comprehensive comparison among relative works.  The summarization of different variants of DRO are simply instances of a finite-sum composite optimization is interesting. However all of them  seems already justified by other literatures. The proposed variance reduced algorithm mainly targets on solving a  finite-sum composite optimization. However, the object function involves a new ingredient  in which they also employ the variance reduction technique to solve it. As compared to the previous variance reduction work in composite optimization, the dealing with the new ingredient   may not be that difficult to handle. Therefore, I tend to reject this paper at this time.", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The main concerns from the reviewers is the novelty of the algorithm and analysis from the CIVR algorithm of Zhang and Xiao (2019b). The author rebuttal clarified the main contributions as reformulation of DRO as composite finite-sum optimization, solving heavily constrained optimization problems through composite optimization, and extension to distributed algorithms. They indeed lead to meaningful contributions to the important topic of DRO and open new avenues for structured constrained optimization problems. The paper is written very clearly and the empirical results on realistic problems are much appreciated.
Decision: Accept (Poster)