Efficient Generalization with Distributionally Robust Learning
Authors: Soumyadip Ghosh
Mark S. Squillante
Ebisa D. Wollega
Venue: NeurIPS 2021 Poster (2021)
Keywords: distributionally robust learning
distributionally robust optimization
generalization
robust learning

Abstract: Distributionally robust learning (DRL) is increasingly seen as a viable method to train machine learning models for improved model generalization. These min-max formulations, however, are more difﬁcult to solve. We provide a new stochastic gradient descent algorithm to efﬁciently solve this DRL formulation. Our approach applies gradient descent to the outer minimization formulation and estimates the gradient of the inner maximization based on a sample average approximation. The latter uses a subset of the data sampled without replacement in each iteration, progressively increasing the subset size to ensure convergence. We rigorously establish convergence to a near-optimal solution under standard regularity assumptions and, for strongly convex losses, match the best known $O(\epsilon{ −1})$ rate of convergence up to a known threshold. Empirical results demonstrate the signiﬁcant beneﬁts of our approach over previous work in improving learning for model generalization.

Efficient Generalization with Distributionally Robust Learning
Soumyadip Ghosh, Mark S. Squillante Mathematical Sciences, IBM Research Al Thomas Watson Research Center Yorktown Heights, NY 20198, USA ghoshs, mss@us lmm..cc... com
Ebisa Wollega Department of Engineering
Colorado State University- Pueblo
Pueblo, CO 81001, USA
exolleg@csupuebll edu
Abstract
Distributionally robust learning (DRL) is increasingly seen viable method train machine learning models for improved model generalization. These minimax formulations, however, are more difficult to solve. We provide a new stochastic gradient descent algorithm to efficiently solve this DRL formulation. Our approach applies gradient descent to the outer minimization formulation and estimates the gradient of the inner maximization based sample average approximation. The latter uses subset of the data sampled without replacement in each iteration, pro- gressively increasing the subset size to ensure convergence. We rigorously establish convergence to a near-optimal solution under standard regularity assumptions and, for strongly convex losses, match the best known O(c-1) rate of convergence up to a known threshold. Empirical results demonstrate the significant benefits our approach over previous work improving learning for model generalization.
1 Introduction
Consider a general formulation of the distributionally robust learning (DRL) problem of active interest. Let X denote sample space, P denote probability distribution X, and θ C Rd denote a parameter space. Let us define Lp(0) = Ep]((0, {)] to be the expectation with respect to (w.r.t)) P of loss function | θ x X I representing the estimation enror for learning model with parameters E θ over data & E X. Further define the worst-case expected loss function R(0)) Ep- [)] sup (Ir(O)), which maximizes the loss Lp over well- defined set measures P. Letting Ps denote base distribution, this set often takes the form = (P) D(P, < p. dP(()) = P({) 2 0} where .) is distance function on the space of probability distributions on X and the constraints limit the feasible candidates to be within distance of p from Ps. We seek find parameters 0 θ that solve the DRL problem formulated as
R(Oros) min BE0
{R(0)}
min see
{ sup sup (0)))
PPP
for given X and P. In practice, training with DRL amounts to dynamically reweighing the data using the inner optima P*(f) at any value the parameters f take over the space θ The inner maximization problem sets these weights to emphasize data that experience high loss This reweighing approach arises from solid theoretical foundations and can provide strong guarantees on model generalization.
DRL and Model Generalization: In machine learning, optimal values for the model parameters are calculated from a finite training dataset (of size N) and this model is then used for inference over other test datasets, all of which are typically assumed be identically distributed [33] (4). The equal-weight empirical distribution UN {1/N} over the finite training dataset is the non- parametric maximum likelihood estimator 23 of the (unknown) distribution underlying the datasets.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Let 0 denote the minimizer of the empirical loss (.w(.) over θ In real-world applications, any two finite datasets sampled from the same underlying distribution can violate the identical distribution assumption, leading to poor generalization when using Oe over other datasets [24]. Popular model selection techniques, such as vross-validttion [32] seek to improve the estimation error between training and testing datasets, but they can be computationally prohibitive and lack rigorous guarantees.
With roots in non- non-parametric statisties [3 and optimization [28] several studies 20 2 [9
have proposed as an alternative approach the DRL formulation using the empirical distribution UN over the finite training dataset as the base distribution Po. This alternative approach explicitly treats the ambiguity in the identity of the true (stationary but unknown) distribution, denoted by Po. In general, we know that Un not equal to Po and it is highly likely that, 6%6. the worst- case distribution P (0ros) is not equal to Po- However, for Wasserstein distance metrics and an appropriately chosen value of p in the set of measures P. Blanchet et al. [2] show that P contains a distribution P whose relevant loss function characteristics are the same as those for the true (unknown) distribution Po with high probability. A broad guideline provided in 2 21 such that these high probability guarantees are achieved by setting P - ((v2/N) for binary classification with logistic models. The DRL approach thus holds great promise and general theory is actively being pursued.
Goal: Our main objective is solve the DRL problem (I) in an efficient manner to ensure is viable alternative approach for model generalization. The primary difficulty is the minimax formulation, particularly the inner maximization problem. While solution may be explicitly available in some cases e.g., constraining P by certain Wasserstein distance metrics admits an explicit characterization of the robust objective function p-)) (1(0, {)]
S these reductions do not hold in general for all interesting Wasserstein distance metrics and they require solving a convex non-linear program ( Namkoong, and Duchi [21] show that the inner maximization can be efficiently solved (see Section under x xi-divergence constraints. Hence, we focus on the entire general class of dPP. ø-divergence distance functions: (P,P, = [o ..P. ){, where ((s) is a non-neeative convex function having the value 0 only s Members of this class include the modified x² divergence, with (bs) = (8- (8-1)) 1)2, and the Kullback-Leibler (KL) divergence, with Φ(s) = s log s - 1. Defining the vector P == (Pn) of dimension N and setting the base P, to the uniform empirical distribution
30
UN. we then have that the loss function and constraint set P are given by (p = > Pnl(O, En)
and P- (PI Em Pr. = 1, 2 O, Vn, Ds = t N ((Np,) S p). respectively.
Related Work: Assuming convex loss functions ((-, En). the DRL problem I is convex in 0. Ben- Tal et al. (I] consider the typical Lagrangian dual algorithm used for this convex-concave case; see (1O) in the supplement. Such reformulation renders a standard stochastic optimization problem. which they solve by applying classical stochastic gradient descent (SGD) methods. However, when / non-convex, this approach camnot guarantee convergence to global optima. Moreover, Namkoong and Duchi (20] observe that the characteristics of certain dual variables can cause instability in SGD,
Namkoong and Duchi (20) therefore propose an alternative approach, for convex losses [(0,E), E) that interleaves stochastic mirror-descent steps in each of the and P variables. This requires a computationally demanding step that samples an -isized non-uniform pmf, which requires O(N) computational effort, and is only slightly smaller than the effort needed to solve the inner maximization problem exactly (see below). Coupled with the iterations in a composite dimension d' + N. this results in slow convergence, as observed in our empirical results in the supplement. To rectify this, Namkoong and Duchi [21] propose directly obtain the optimal P* (#) that defines R(8), namely solving (1) as a large deterministic problem that is well-defined for finite N. For x² diverrgee, they show that the inner maximization can be reduced to two one- mi-dimensional root- moot-finding problems, which can be solved via bisection search, thus requiring an expensive O(N log N) computational effort (see Proposition 2 at each iteration. They also establish a guarantee that the deterministic algorithm for convex losses / converges to an c-optimal solution with O(Ne22) computational effort.
Recent work [10 15 seeks to reduce the computational effort of this costly full-gradient method by developing an algorithm to efficiently estimate the gradient of the inner maximization problem through multi-level Monte Carlo randomization procedure introduced by Giles [2]. Although there are important differences in the two algorithms and the theoretical arguments supporting each algorithm and its parameters (see the discussion below), both approaches hold great promise in theory especially for large datasets where, for convex losses I, Levy et al. [15] establish a computational effort complexity of O(e -3) under their algorithm and we establish computational effort complexity of ((e-2) under the algorithm in [10 Despite this great promise, our analysis and experiments

---

expose two adverse factors. Each iteration is more expensive because it solves multiple inner maximization problems. At the same time, the algorithm inherently produces an increase in the variance of the gradient estimator of the robust loss as result of the added randomization of the Giles estimator; this can negatively impact both the computational effort and solution quality of the overall approach.
Our Contributions: Our main focus is to devise an algorithmic approach and theoretical results to efficiently solve DRL formulations and to improve generalization more consistently and more quickly than alternative methods. We consider in Section 2 a new SGD algorithm, tailored to large DRL problems, where our Algorithm significantly reduces the expense of solving the inner maximization over the full training dataset by subsampling the support of P from the (finite) training dataset in the iterates of the algorithm and estimating the robust loss via a sample average approximation. Subsampling (mini-batching) typically works well with SGD because the gradient estimates are unbiased. However, in the DRL context, our Theorem (ocoormm3shhne shows that subsampling produces bias in the estimation of the robust loss gradient because, with fixed mini-batch subsampling, chances are high that critical data that suffer high loss will be missed, leading to optimistic estimation of the robust loss; empirical results (in the supplement) illustrate the important impact of this bias.
Namkoong and Duchi [2 bypass this important issue of bias by assembling the full-data gradient, whereas the Giles estimator approach of Levy et al. (15) and Ghosh and Squillante [TO] randomizes the choice of the
size over the entire dataset. Although Levy et al. [15] provide an analysis of the bias induced by maiiibbtchhing our algorithm fundamentally different in that we are the first to solve the DRL. formulation by assembling the mini-batch through sampling without replacement from the training dataset [11, whereas in strong contrast sampling with replacement is employed in (20, 21 15. Our alternative Giles estimator approach [10], devised independently of and simultaneously to the Giles estimator approach of Levy et al. [15, also employs sampling without replacement. While our general theory in the without-replacement sampling approach is harder to establish because the individual samples in the mini-batch are not distributionally independent, our analysis establishes stronger theoretical results that show our without-replacement sampling approach herein is able to match the best-known convergence guarantees of SGD. Thus the estimation is significantly improved for the same computational effort by only considering unique samples & and their losses 1(0, E) in approximating R(0). Indeed, an M -szed set sampled with replacement has on average only about N(1 - e M/N) unique support points (see the supplement); this issue leads Levy et al. [15] to show that the variance of their R(0) estimator may not vanish with increasing batch size, thus contributing to their worse computational effort complexity which can not achieve the best-known SGD convergence guarantees.
Our Algorithm | reduces the identified inherent bias by progressively increusing the subsample size with the iterates up to the maximum size N. This represents the first such approach to simultaneously reduce bias and decrease the computational burden of solving large DRL formulations, together with the first analysis of a general progressively increasing subsampling- based approach in the context of DRL and bias reduction. Shamir (26 considers sampling with and without replacement, but in the context of standard (single-level) SGD, showing that SGD without replacement achieves similar performance on the same order as SGD with replacement, which is in strong contrast to our corresponding results in the DRL setting. We establish in Theorem 4 that convergence to a close neighborhood of local optimal solution is assured, even for non-convex losses I, provided that the subsamples increase a certain minimal rate. We further extend our analysis for strongly convex losses in Theorem 6 to show that our algorithm achieves O(e effort to reduce the optimality gap to e, matching the best SGD rates known for stochastic optimization 222. The dependence on N is via poly-log terms. This holds for all c 2 E O(N- where 8 is small positive value. Hence, for strongly convex losses, we match the best rates of standard SGD w.r.t. c, like [1] (but without their ONN) dependence). with only poly-log N dependence, like [[5]] (but without their worse order). A forthcoming article extends these theoretical results to the case of convex losses l. Our theoretical results guide the setting of key algorithm parameter values to realize this optimally balancing of the fundamental tradeoff between computational effort and stochastic error. Additional theoretical results, all proofs and further technical details can be found in the supplement.
Our empirical results in Section consider convex DRL formulations of binary classification problems. We compare the computation and generalization performance of our algorithm with the corresponding performance under the algorithms proposed in (0) 21 [5] [0] and under a regularized ERM formula- tion tuned via f-fold cross validation (CV), the standard practical approach for model generalization.
3

---

Our results show that A atttinn equivalent or (often) superior generalization performance as k-fold CV and the other DRL methods. Meanwhile, our algorithm provides sigmificant improvements in the computational effort required by the other DRL, methods and orders of magnitude reductions in the computational effort required by k-fold CV. Furthermore, the key parameters of our DRI. algorithm do not require fine tuning and are set based on our theoretical results, whereas the key parameters of the other DRL methods require fine tuning while also impacting both the solution quality and computation effort of the Giles approach. Additional empirical results, including the impact of key algorithmic parameters, and related technical details can be found the supplement.
Algorithm and Analysis
Algorithm presents our progressively sampled subgradient descent algorithm that follows SGD-like iterations for the outer minimization problem in ( according to
0:11 0. - (o...O))
0. -7,Gr,
(2)
where Y/ is the step size (or gain sequence or learning rate), R.(-) is a sample-average approximation
of the robust loss R(.) from the inner maximization formulation over Dø-constrained P, and G₁ :=
V fe (0.), ). Our algorithm uses progressively increasing sample sizes Mf to estimate G., This view of ①1 permits us to depart from the convex-concave formulations of Ben-Tal et al. [ and consider non-convex losses I, as long as the subgradient Voll,()) approximates the gradient V--(.) sufficiently well. We first establish that the gradient Voli(-) exists, recalling that R(0), as the optimal value of the inner maximization problem, is extreme value function. Let us define the set 0g := {0 1(0. 5n,) = I(0, Enz). 1n,, n2) and, for a small < > O, define the set 0 := Ue (0 0 0o1 < <} be the c-neighborhood of θg. We assume in Proposition I that the learning model precludes this neighborhood set in order to avoid a degenerate case in which the inner maximization objective function does not depend the decision variables pa, and the entire feasible set is optimal. The existence and form of V R()) ) is then derived in part by exploiting Danskin's Theorem 29 Theorem 7.21].
Proposition 1. Let the feasible region O be compact and assume + C 0 for a small & >> O. Further suppose & in the Dægconsttaint has strictly convex level sets, and let < p(N, o) with p(N,)) o) defined in the supplement. Then: (i) the optimal solution P of R(0) (0))) is unique, and the gradient is given by VgR(0) = EmEN PT Vol(O, En); and (ii) for all p. the gradient Rg(( is a sub- gradient of R(0).
Algorithm I ProgressiveSSD(7, (M4), 0o. p)
Algorithm 2 InnerMax(2,,M.p))
Given: Step size 7; Sample sizes {M,)- My = N; Initial 0o: Do constraint p small
Given: loss values 2; subsampled support M; Dø constraint p.
8 0.
I < maxm (2m 2m E Mr vm E EM 2)
M + [M]. base Po = {
for t= 1,2....., do
(Sample M, without replacement)
M' {m M : 2m 2) and M' I'
Mr -
P' { 1 I4m M'), Vm E M]
My If D& P* Po) S then
for m = ml Mj do
Sm ~ Uniform (W) \ Me)
p P and return P
M. Mr U }
for E [0, a] do
end for
for E [1 do
M' + {m X < am add (0))
Assemble 2, + {1(A): Vm E Mc}
P' - (1 1 (0')
Em ) E M'}
(1-6)/2
Pt + p+ (1 Mr ++)
If P'm 0. then
P P'(a) t P', and break
Pe InnerMax(2,,) 22, Set G. t Σ EmEM, Pi,m Vollbe,
end for
If D& (a), Pb) = P. then P f- (aa) and break
Set l141 t Ot 7
end for return 0T
end for return P
Next, we construct the estimate RS from the inner maximization problem restricted only to a relatively small subset M, of the full datasct with size [Ml = -,. Define P == (pm) of dimension M, and

---

define the objective coefficients Zm := 1(0, Em)
We then have
(0)
max
Σ mEM.
Pm 2m
s.t.
Σ
((M,pm) S MePr.
Σ Pm 1, Pm 2
(3)
(=(
mEM.
mEM.
The uncertainty radius Pt P p+ Tr now changes with the iteration where tt represents small additional inflation; Theorem below motivates why this is included. Now suppose P7( = (0). is optimal solution to Then valid subgradient for R2(O:) is obtained as an expression analogous to that in Proposition Tū) under appropriate substitutions w.r.t. 8,, P and M,. Writing the Lagrangian objective of (3) as L(a, X, P). with explicit expression given in the supplement, we then have the optimal objective value (t)(0) (0) = min max 20 L(a, X, P); refer to [8]. The optimal primal and dual variables can then be obtained for various Ø functions by the general Algorithm 2 to solve the Lagrangian formulations. Importantly, a worst-case bound on the computational effort required to obtain an e-optimal solution to (3) can be obtained.
Proposition 2. For any é-divergence, Algorithm 2 finds a feasible primal- dual solution (P;,ā", xX*)
(3) with an objective function value R2 such that [i (0)- Ri| with worst-case computational effort bounded by OM, log M, + (log 2))), where is small precision parameter.
The machine-preeiste
does not relate to any formulation or algorithm parameters (e.g., Mr, N, p). and it is required because 2 solves two one-dimension bisection searches in sequence. In the sequel we assume that is fixed small value and Algorithm returns the exact unique solution (Pr a", X*) to problem and that the computational effort is bounded by OM, log M,).
2.1 Small-Sample Approximation of V R(0)
In Algorithm T the gradient R is approximated using the gradient expression in Proposition Tii) with the optimal P." for a small sample size M,. This estimate is expected to suffer a bias because subsample of the full dataset might miss data where loss is high when subsampling the dataset, and this leads to optimistic estimation of the robust loss R(0) and its gradient. Let the mass vector p (pr .p......P' ,Pr) be the optimal solution the full-data version of 3), i.e., with M, N, and let the mass vector Pt = (pi...., PMM,) ) be the optimal solution when restricted to any subset Mr.
Assumption 1. The d-divergence satisfies uniformly for all 8 and ( < So the continuity condition (for constants Co. K1, K2 > 0): (0{s(1 ()) <(+)) S (0())) K2G.
The above condition, as described in (29]. only allows for (local) linear growth in Φ. and it can be verified for many common o-divergences of interest including the modified x² and KL-divergences. Let E., and Pr, respectively denote expectation and probability w.r.t. the random set Mr.
Theorem 3. Suppose Assumption Nnd the assumptions of Proposition holld and further suppose the gradient V R2 (0) is the optimal solution to (3) over subxample M, of size Mj sampled uniformly without replacement from a set of size N. Define Tt- = c( T.. (2-6))) for small constants c, and set the D Dæ-targel in B3 to be Pt. = p T)- Then, there exists a small positive M' defined in the supplement and of order o(N) such that, for all M, 2 M', the subgradient V R,,(()) and full-
gradient V R(())) satisfy for any C 00 and 1 Te O 00)2/11- 28/(1-0)):
Peln ( V. R()) C) 2 Ft
Corollary 1. !f the conditions for Theorem 3 are satisfied, then (o
0
The proof of Theorem 3 (in the supplement) includes exact expressions for the corresponding constants such as Fr, whose dependence on the constant C' and on the magnitude of V R(()) is made explicit in Lemma
Theorem 3 provides bound on the squared bias in approximating the true gradient Vo V0)( with the subsample estimate V (() as function of the sample size M,. Levy et al. [13 develop an analogous bias result for the case when the subsample M, is gathered through sampling support points &., with replacement by building on standard concentration bounds. In strong contrast, our Mr is sampled without replacement which, as previously motivated, is more practical in terms of avoiding repeated computation with sample points that get sampled multiple times. Unlike the with-replacement case, the samples within our M, are no longer independent. Consequently, our analysis is built from the ground up starting with tools of probability related to sampling finite sets without replacement; the start of Appendix A.3 Motivating the form of Tj, note that sampling
5

---

subset of size M uniformly without replacement from a larger finite set of size N induces variance terms of the form ( x) in place of the standard M
To provide an outline of the proof, it starts by constructing Pr, restriction of the (unique) P onto the (random) subset M, in the restricted problem (3), where Pt Pmm Vm M₁ The assumptions ensure with probability at least Ft that Pm # O. With the same high probability, pa is also a feasible solution to (3) when Pt is inflated as assumed. Next, we establish that its objective function value is within Ti of the optimum with high probability, which yields the desired result. The Corollary [ which is the main form of Theorem 3 used in the sequel, follows from Theorem 17.4 in [3].
Note that the bias identified in Theorem 3 vanishes only with Mr / N as t + oo. Since fixed bias in gradients violates a basic requirement for SGD [ Section 4.3] that the gradient estimator
V R0)] ((Vo (using standard time complexity notation [31), then the convergence of 2 cannot be guaranteed when M,- M for all f, where M < N. To address this bias issue, in strong contrast with using the full-data gradient V, R()) [21] or randomizing the subset size Mt over the entire dataset [13] [0], our algorithm chooses to grow the mini- size M, progressively with t. Bottou et al. [3] Section 5.1] show that even with unbiased gradient estimation, keeping step sizes Th fixed and directly increasing the mini-batch size Mt more advantageous because (informally) the larger M, makes the gradient estimates more accurate. In our case, we grow the sample size in the SGD algorithm (2) to eliminate bias. Since this also provides decrease in stochastic error as a consequence, it is no longer necessary to diminish the step size 7/ indeed, doing so negates the benefits of the extra work in computing gradients using a larger Mc. Algorithm [I] therefore takes fixed-length steps y. The maximum size N is reached after (large) finite number of iterations T, at which point our algorithm reduces to deterministic full- full-gradient optimization approach.
2.2 Convergence of Algorithm !
Seen in the above light, for finite N. the strictly increasing M, sequence will eventually end at an iterate T < oo where Mr = NN, that is T == { 2 N). Hence, Algorithm [ is not guaranteed to converge by the Tth iteration. We can nevertheless provide finite-stop guarantee on the performance of the method over any loss function with Lipschitz gradients.
Theorem 4. Suppose the constant step size iit = 7y satisfies y S Σ.z a lower bound Rint exists for the robust loss function R(O), v0 E O and the conditions of Theorem of the estimate V (0) calculated over the sampled- hiteeld-wwwhho---peeeeeee Mj obeys
3 hold. Then, the variance Me with subsample size ((0)] S CC(., N). Further assume the gradient V R() is
L- L-Lipschitz. Then, at termination,
T
R(0o) Rinf
T In +1 In+1 + +C
Σ 2
(4)
[2 - L7)
2 - La 1=1
The first result in Theorem A establishes that the variance of V Ri (0) obeys a bound which is as to be expected for sampling without replacement from any finite set [35]. Combining this with the bias (see Corollary D allows us progressively decrease the mean squared error. This leads the result 4 in Theorem which shows that the sum of the gradients of R(0,) at iterates visited by the algorithm is bounded above, in particular, by ET MT. (1 If this summation remains finite as T - xo, then the upper bound of ( remains finite, and thus the gradients || |/ at the iterates converge to 0; in other words, the algorithm converges to local optimal solution. The summation can converge for M, increasing moderately, such as at a polynomial rate.
Theorem 4 assumnes that the gradient VeR(O) of the robust loss is Lipschitz continuous. The gradients of such extreme value functions are in general not Lipschitz even if the objective function is Lipschitz. For example, a linear objective 1(6, (x.) = Ø'C. leads to R(0) maxp P.f'' and when maximized over a polyhedral constraint set will not preserve the 0-Lipschitzness of the objective functions, because the optimal solutions P* are picked from the discrete set of vertices of the polyhedron and thus Rg)( is piecewise discontinuous. Our Proposition I assumptions yield an inner maximization with non-zero linear objective over strictly convex feasible set. The desired smoothness can then be obtained with some additional conditions on the loss functions ((,,E). Proposition 5 provides one such condition where the Lipschitzness of VoR(() follows from

---

the Hessian of R(O) being bounded in norm, which is often satisfied by common statistical learning losses, e.g., log-logistic and squared losses of linear models over compact spaces.
Proposition Assume the conditions in Proposition 7 hold. Further suppose that the Hessians (0 {n) exist, 40 and each Ea, and are bounded in Frobenious norm || [V (a)llr S L,, v0, n. Then, the robust loss also follows V R(0))l= S M for some positive M- < 20.
A key consideration then is to obtain O as close as possible to the minimizer Grob that attains Rint. The tradeoff in (4) suggests that increasing Mr aggressively will lead to smaller gradients at termination, but this will also increase the computational effort in each iteration. In the remainder of the section, we study this tradeoff under an additional assumption that the loss functions [(., are strongly convex for each Ç. which we will show in Theorem 6 yields the strong convexity of R(O). Consequently, it also provides unique minimizer oob for ( that satisfies Rinf = R( We therefore seek a lower bound on how close the value of R(OT) and its gradient at termination of our progressively sampled Algorithm cann get to the unique optimal solution
function of the sample growth sequence (M,) and also seek to establish convergence guarantees for the computational effort needed by our algorithm to attain desired optimality gap larger than this lower bound.
Our notion of efficiency will be developed w.r.t. the total computational effort We that is expended up until iterate I, where W.- Eese W, and wa is the individual work in each iterate s. From the discussion following Proposition we assume the relation wi; = M2 log Mj holds for some constant ke. Defining the ratio v, == / as the growth factor of the sequence (M,), we consider two important cases: (i) Diminishing- factor growth with 1/ > 1 as t, c.g., the polynomial growth of v = 1 + :: and (ii) Constant-factor growth with V4 = V > 1, Vt. Assuming Mo = 1,
the algorithm employs subsample set size M,- = I[ Ms] in iteration I, until maximum of T iterations when MM 2 N. For constant growth sequences, we have T = [log(N)) log v/, and we use the notation [v> and (I()) to denote the total iterations and total computational effort as functions of v. Our final result characterizes guarantees on the rate at which the expected optimality R((rss)) decreases w.r.t Wy. Recall that ó defines the parameter n in Theorem 3 and denote by Eg the optimality gap at the starting iterate. We drop the integrality requirement sequences like II[,, v,,1 in analysis of Theorem 6 to provide clear and insightful exposition, but note that the conclusions remain unaltered.
gap Ey := -
Theorem 6. Suppose all the conditions of Theorem Pare satisfied and the loss functions 1(0, En) c-strongly convex. Then the function R(0) is c-strongly convex. Further suppose that 7 S
min(
1 TL 4c) is fixed. Then: (i) For diminishing growth sequences M,, we have that WT - 00
as V2 + ++; and (ii) For constant growth sequences, we have that the total effort WT(v) is a decreasing function over E (1,c0), with lim,- (v (v) = (N log N - (N 1))- Moreover, (V) < ET(y) where (T(p) is an increasing function over V E (1, oo) with its infimum E- = =in=nf,, inf,,E,(')) ET()) = (1/N1-5)(E) + )C) attained as v + 1 Finally, we have
lim,--1 1 WT(v) (Er(v)- - E") ) E*) = SCLLE(1 (1-)e2(1111111111 - 7.) ke (N log N - -(N - - (1))))))
Several key properties of our Algorithm| D are apparent from Theorem 6 for the case of strongly- convex R(0). To understand these results, first note (referring to the supplement for details) that if
the full batch-gradient method is applied in each iteration (M; = N), strongly-conver objective R would enjoy a linear (i.e., constant factor) reduction of size (1 - 7 7/cc) in the error R(O,) R(Oms) for a step-size y chosen to satisfy the conditions of Theorem 6 The average optimality gap can be written as sum of this deterministic error and an additional term representing the stochastic error induced by the subsampling of the support. The best convergence results for SGD methods on strongly convex objective functions ensure that -eexpected-optimality--e gap solutions are obtained with O(E-2) work complexity (29). Theorem 6[ establishes that any general diminishing-face -fctor growth of M, will lead to the stochastic error decreasing to zero much slower than the geometric drop in the deterministic error, and thus the stochastic error dominates. Consequently, there is a suboptimal reduction in the optimality gap Ey w.r.t. the total computational effort WT.
Constant factor sequences, however, can achieve balance in the tradeoff between the rate of reduction in stochastic error and the drop in deterministic error. Note first that, for smaller v > 1, the sample size sequence M, grows more slowly, hence leading to larger terminating iteration T and total computational effort Wf; an exact expression for Wv(v) is provided in the supplement for any v E (1, oo). Consequently, WT falls as the growth factor v grows. This also leads to a poorer guarantee Ev(v) on the attainable optimality gap and thus requiring + 1 to improve the
7

---

guarantees on Ey. Theorem 6 characterizes an absolute limit in E. on how much optimality gap reduction can be guaranteed this regime because the algorithm takes only a finite T number of iterations, and shows E ONN independent of the step length y. This theorem also leads to the following corollary that our algorithm attains any desired gap E + e with O(e=)) effort.
Corollary 2. Suppose all the conditions of Theorem o are satisfied and solution with guar- anteed expected optimality gap within E- + E is desired. Then, there exists a v. E (1, 20) such that when Algorithm [ is run with sample size sequence Mc- [v:l. it terminates with T(c) = [log / log steps and produces the desired solution with total computation effort WT(e) = (K1V, + (v - 1) + of (v!-ba (22=--11) ) where K1, K2 E (17, o0) for a fixed yj > 0 for all 0. Moreover, Ve 1 $lass O.
(The expression a, =(b,,) denotes that a, /,,/b,, + 0 as oc.) Expressions for the constants 61 and K2 are given in the proof of the corollary in the supplement. Since 5 is an arbitrarily small chosen constant, K1 and K2 depend on N only through poly-log terms. Hence, for such a desired c, our progressively subsampled algorithm for the DRL formulation matches the best rate results for the SGD family of algorithms for strongly convex stochastic optimization formulations.
3 Empirical Results
Numerous experiments were conducted to empirically evaluate our progressively sampled subgradient descent (PSSG) Algorithm | with the main objectives of reaching the optimal solutions of the DRL formulation and improving model generalization more consistently and more quickly than alternative methods. In addition, we seek to understand the characteristics of our PSSG method and assess the efficacy of the DRL approach in general as a viable alternative to regularized ERM in producing good model generalization. Specifically, we compare the performance of PSSG with that of competing algorithms to solve the DRL formulation (I). namely the full-support gradient (FG) algorithm of (21) and the multi-level Monte Carlo (Giles) algorithm of [15] and [10]; given the benefits established here and in [10] for sampling without replacement over sampling with replacement, our empirical results focus on the multi-level Monte Carlo (Giles) algorithm of [10. We also include in supplement B consideration of the standard SGD (fixed minibatch M, = M) method to gauge the impact of the bias shown in Theorem [ and further include consideration of the SGD method of [20) for a small dataset to demonstrate that the method was not competitive. These methods were all re-implemented since full source code was not made available with the corresponding publications.
Following 21, all examples use a logistic binary classification loss I(0, (x. y)) = log(1 + exp(-yf'x) x)) where represents samples with d features and y represents the class labels 1
All algorithms sampled the initial Og uniformly from the hypercube []1, All experiments were implemented in Python 3.7 and run on a 16-core 2.6GHz Intel Xeon processor with 128GB memory. Additional empirical results and technical details can be found in the supplement.
Generalization. We investigate whether the DRL formulation (T) can improve the generalization of learning models against an ERM-trained model that is regularized via 10-fold CV. Experiments were conducted over 13 public-domain datasets as detailed in Table 1 with sizes ranging from O(1?²) to O(10)). We include MNIST, a non-convex neural-netwer only the last logistic classification layer into the DRL formulation. Table presents presents comparison of the test misclassification produced by the DRL algorithms and the regularized ERM algorithm at termination for the 13 datasets. (The parameter settings for each algorithm are detailed below). The 95% confidence intervals (CIs) are calculated over 10 permutations of the datasets into training (80%) and testing (20%) sets. We highlight in bold the methods that produce a generalization error (within its Cls) that is clearly the best. As evident, at least one DRL method always including PSSG produces models of equal or better quality as the regularized ERM formulation for all datasets.
model, where we follow [15] and admit
Recall that the DRL methods provide this level of performance by solving a single instance of the DRL formulation ( thus avoiding the burdensome 10-fold CV enumeration. Table I provides the average CPU time in seconds recorded over the 10 permutations. The average time taken by the ERM 10-fold regularization in solving its formulation multiple times a serial computing mode to identify the best regularization parameter (parameter X below) exceeds that taken on average to solve the DRL. formulation by one to two orders of magnitude. The computation time of a single PSSG DRI, run is of the same order as that of a single ERM run, as anticipated by Theorem 6 and its Corollary 2
8

---

Dataset
V
Test Misclassified (%)
CPU Time (secs)
FG
Giles
PSSG
ERM
FG
Giles
PSSG
ERM
adult"
0.051
17.1=0.0
16.7+10.1
16.610.11
16.7+0.1
45
214
36
2542
fabert!
0.312
9.111.2
9.910.2
9.2110.1
9.910.1
32
61
20
4128
sina_agnosticl
0.529
13.240.1
15.4400.
13.140.2
15.940.7
33
21
13
1765
gina iina_prior'
0.475
13.7:0.4
14.3:1.0
12.7.0.3
14.610.7
34
38
1147
guillermo
0.463
30.7:0.2
34.110.3
30.710.2
32.010.4
908
505
116
31547
hiv1'
0.166
5.910.1
6.3+
5.8+0.0
6.1=0.1
41
45
35
1012
MDB.drama
0.091
36.120.1
37.0:10.1
36.2+0.0
36.2=0.1
176
865
89
19436
lals
2.029
9.3+0.00
8.3+
8.2
9.0+0.1
17
2456
MNIST
1.342
2.010.1
1.720.1
1.510.0
1.810.1
39
28
20
984
OVA Breast
2.660
3.240.1
3.8+0.4
3.010.1
3.4:0.2
140
23
37
4310
rev1
0.242
5.7+0.0
5.340.0
5.1.0.0
6.3.0.0
2628
1271
543
701843
riccardo
0.463
4.940.1
2.0+0.1
1.5+0.1
1.740.1
259
201
120
86575
tr31.we
3.305
2.7+0.3
2.7+00.4
2.7+0.2
2.9+0.3
6
14
6
987
Table I: Comparison of the DRO and regularized ERM formulations over 13 publicly available machine learning (ML) datasets, from UCI 17], OpenML [6. MN [14] and SKLeamn
[16]. The first set of four columns provides 95% confidence interval of the percentage misclassified over withheld test datasets. The second set four columns provides the average CPU time taken.
hvr p 0.160
ls wc 0000
riocardo 0.30
Giics
PSSG
LP
10
10-1
10t
Cunulalvve GPU Time (saiz))
Curnuctive CRU
Cumulative CPU Tine (s00)
Figure 1: Comparison of PSSG (green), FG (red) and Giles (blue) on the fraction of misclassification in testing (y-axis) versus cumulative CPU time (log-scale r-axis) over the hiv1, lais wc and riccardo datasets, with p set as noted.
This indicates significant computational savings in using DRL because of the elimination of the expensive typer-parameter tuning step.
The main parameter of the DRL formulation is the uncertainty radius for the set of measures P. and following 21] is set to the same (base-10) order of magnitude as the value /d/N; Table records this quantity for each dataset. We provide in supplement B detailed comparisons of the three DRL methods over multiple p values (and other key parameter values) for several datasets. These results illustrate similar performance trends and insensitivities across the datasets relative to the O d/N) guideline for FG and PSSG (which are independent of its growth factor). The Giles method, however, exhibits complex interactions between P and its minimum mini-batch size parameter that significantly impact both the solution quality and the computation time. Thus, fine tuning of these two key parameters of the Giles method is required to achieve the best quality solution and the smallest computational effort. In strong contrast, the interactions between p and the key parameters of PSSG are relatively weak, with the growth factor only impacting the computational effort (and not the solution quality). Hence, it is sufficient to run PSSG with key parameters that are set based on our theoretical results without any fine tuning. This lack of fine tuning requirements is another important advantage of PSSG, in addition to its solution quality and computational advantages.
Among the DRL methods, PSSG takes the least time to solve the problem for all datasets (with one exception), often significantly so, while providing equal or better performance, including significant performance improvement over ERM in several cases. As expected, FG takes more time to solve the problem than PSSG for all datasets (comparable time for tr31.wc) wc). For all but one dataset, Giles takes significantly more time than PSSG to solve the problem, by an order of magnitude in several cases. These longer computation times are due in large part to the added variability experienced by the Giles method arising from the Monte Carlo randomization. The effect of this added variability is

---

also evident in the consistently wider CIs of the misclassification errors for Giles, as well as in the wider range of CPU times with an isolated case terminating the fastest LOVA_Breast and several cases terminating the slowest among DRI. methods (e.g., adult, fabert, IMDB. drama, lais wc).
Figure | presents three representative comparisons of the empirical DRL runs over time, where the sample paths of all ten runs for each method are plotted along with their average shown in bold; corresponding plots for other datasets are provided in the supplement. The sample paths for PSSG (green) exhibit relatively low variability overall with reductions in variability as the sample size M, grows with the iterations t. In strong contrast, the sample paths for Giles (blue) exhibit much higher variability across the iterations, and are computationally more expensive, for the reasons explained above. Although FG (red) also exhibits low variability, is clearly more expensive computationally.
PSSG DRL. Our Algorithm 1 starts with an initial sample size of 1, the fixed step length y = 0.5 and, following Theorem 6 the constaan--rowit factor 1.001 is chosen close to 1. Although the parameter ō appears prominently in the inflation of to individual P: as defined in Theorem 3 5 is required only to be a small positive constant. Since the empirical results were found not sensitive to 6, we set d = 0.01. All DRL algorithms solved the inner-maximization formulation to within e-accuracy where e 10-7. Each method monitors the performance of the current model in correctly classifying the withheld test validation set every (1/20)th of an epoch, and stops if the average of the last 20 misclassification fraction values does not improve more than 1% when compared with the average of the previous 80 evaluations. Hence, an algorithm run stops if the misclassification error in the validation set over the current epoch not improved by more than 1% over the four past epochs.
Theorem 3 provides the fundamental relationship between the bias suffered by a fixed batch size SGD) (M, = M) method in solving (1) and the batch size M. The important impact of this bias is illustrated by empirical results presented in the supplement. Under a small growth factor of v = 1.001, the iterations of PSSG operate with M, = 1 until & 400 when it then rises to M, = 2. Hence, PSSG initially enjoys the benefits of fast objective value reduction similar to SGD with fixed batch size, but then eventually eliminates the introduced bias and thus also enjoys fast convergence. PSSG therefore avoids the expense of hyper-parameter tuning the batch size of standard SGD for bias reduction.
We also consider the impact of two key algorithm parameters: sample size growth factor y and step length y. Following Theorem [ these settings are broadly expected to impact the computation times and solution quality. Empirical results (in the supplement), contrasting the performance of PSSG keeping one of the parameters 7 and v fixed while varying the other, show that the performance is insensitive to v for values smaller than 1.001 and y larger than 0.5, indicating that an error floor E has been reached. Hence we use these parameter values for all experiments in Table [
FG DRL. The step lengths of the FG algorithm are determined by the LBFGS-B algorithm with a maximum of 0.5 for all experiments. This parameter can have a notable impact on the speed of convergence, and our results in the supplement show this to be the best choice over many datasets.
Giles DRL. The parameters of the Giles algorithm are minimum mini-batch size of and a stepsize sequence of ?/ = 0.5 150000/5000 + t)) for all experiments. As noted above, the minimum mini-batch size has a significant impact on the performance of the Giles method. The value was chosen after careful study over multiple datasets as described in the supplement.
Regularized ERM. The 10-fold CV procedure partitions the full training dataset into 10 equal parts and trains a regularized model over each dataset formed by holding out one of the 10 parts as the validation dataset. The ERM loss objective is regularized by A||0 12 term, and a fixed-batch SGD (size 10) is used for each combination of partition and X values. Enumeration is employed to find the optimal À from grid of 20 points in the range [10 6, 10%), starting with 10ah and backtracking until the average performance over the 10 validation datasets does not improve for three À enumerations. Note that the computational benefits of PSSG would be even larger if all values over all grid points were enumerated. Our results in the supplement show significant amount of variability in the optimal À over all the datasets, with no evident pattern relating to dataset characteristics, which highlights the need for ERM computations over wide range of À values for each dataset.
Summary. Our empirical results support our theoretical results and show that PSSG achieves the main objectives of reaching optimal solutions of the DRL formulation and improving model generalization more consistently and more quickly than other methods. In particular, PSSG produces equal or better quality models as FG, Giles and regularized ERM with significantly less computational effort, often by orders of magnitude, thus providing a strong alternative approach to generalization.
10

---

References
[1] A. Ben-Tal, D. Den Hertog, A. De Waegenaere, B. Melenberg, and G. Rennen. Robust solutions of optimization problems affected by uncertain probabilities. Management Science, 59(2): 341-357, 2013.
[2] J. Blanchet, Y. Kang, and K. Murthy. Robust wasserstein profile inference and applications to machine learning. Journal of Applied Probubility, 56(3) 857, Sep 2019. ISSN 1475-6072. doi: 10.1017//p:22199.99 URL /Ttx::::/xx.coo doi. org/ 10. 1017/jpr 2019.4999
[3] L.. Bottou, F. E. Curtis, and J. Nocedal. Optimization Methods for Large-Scale Machine Learning. SIAM Review, 60(2):223-311, 2018.
[4] R. Chen and I. Paschalidis. A Robust Learning Approach for Regression Models Based on Distributionally Robust Optimization. Journal of Machine Learning Research, 19(13):1-45 2018.
[5] Esfahani and D. Kuhn. Data-driven distributionally robust optimization using the Wasserstein metric: performance guarantees and tractable reformulations. Mathematical Programming, 171: 115-166, 2018.
[6] M. Feurer, N. van Rijn, A. Kadra, Gijsbers, N. Mallik, S. Ravi, A. Mueller, J. Vanschoren, and F. Hutter. OpenML-Python
extensible Python API for OpenML. arXiv, 1911.02490, wtt.://1911...099...11
2019. URL https: / //wxxv..iv/vv/////////////aaa/
[7] R. Gao and A. J. Kleywegt. Distributionally Robust Stochastic Optimization with Wasserstein Distance. arXiv e-prints, art. arXiv:1604.02199 Apr. 2016.
[8] R. Gao, X. Chen, and A. J. Kleywegt. Wasserstein Distributional Robustness and Regularization in Statistical Learning. arXiv e-prints, art. 1rXiv:1712.06050, Dec. 2017.
[9] Ghosh and H. Lam. Robust analysis in stochastic simulation: Computation and performance guarantees. Operations Research, 67(1), 2019.
[10] S. Ghosh and M. S. Squillante. Unbiased Gradient Estimation for Distributionally Robust Learning. arXiv e-prints, art. arXiv:2012.12361 Dec. 2020.
[11] S. Ghosh, M. S. Squillante, and E. Wollega. Efficient Stochastic Gradient Descent for Learning with Distributionally Robust Optimization. arXiv e-prints, art. 1XXiv:88050087250 May 2018.
[12] M. B. Giles. Multilevel monte carlo path simulation. Operations Research, 56(3))607-617, 2008. doi: 10. 10770.09e.0000.44966
(tL.https://doi..rr 10. 1w17/1887pprre 1070 0496
[13] Jacod and P. Protter. Probability Essentials. Universitext. Springer Berlin Heidelberg, 2004. ISBN 9783540438717.
[14] Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied document recognition. Proceedings of the IEEE, 86(1) 86(11):2278-2324 1998. doi: 10. 109/5.726791.
[15] D. Levy, Y. Carmon, J. C. Duchi, and A. Sidford. Large- scale methods for distributionally robust optimization. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems 33. 2020.
[16] Lewis, Y. Yang, T. Rose, and F. Li. RCV1: A new benchmark collection for text categorization research. Journal of Machine Learning Research, 5:361-397, 2004.
[17] M. Lichman. UCI machine learning repository, 2013. URL https://archive www.rchiveiic....om uci edu/ml/datasets
[18] D. G. Luenberger. Optimization by Vector Space Methods. John Wiley & Sons, 1969.
[19] F. Luo and S. Mehrotra. Decomposition Algorithm for Distributionally Robust Optimization using Wasserstein Metric with an Application to a Class of Regression Models. European Journal of Operational Research, 278(1):20-3) Oct. 2019.

---

[20] H. Namkoong and J. C. Duchi. Stochastic gradient methods for distributionally robust optimiza- tion with f-divergences. D. D. Lee, M. Sugiyama, U. V. Luxburg. I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems 29, pages 2208-222 Curran Associates, Inc., 2016.
[21] H. Namkoong and J. C. Duchi. Variance-based regularization with convex objectives. In Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems 30, pages 2971-2980. Curran Associates, Inc., 2017.
[22] J. Nocedal and S. Wright. Numerical Optimization. Springer Series in Operations Research and Financial Engineering. Springer New York, 2006. ISBN 9780387400655, URL https //books google. com
[23] A. B. Owen. Empirical L Likelihood. Chapman Hall, 2001.
[24] C. Perlich, F. Provost, and J. S. Simonoff. Tree Induction vs. Logistic Regression: A Learning- Curve Analysis. Journal of Machine Learning Research, 1-2211255, 2003.
[25] T. Rognvaldsson, I.. You, and D. Garwicz. State of the art prediction of hiv-1 protease cleavage sites. Bioinformatics, 3108):1204-2200, 2014.
[26] O. Shamir.
Without--eplacemmen sampling for stochastic gradient methods. In D. Lee, M. Sugiyama, U. Luxburg, Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems 29. 2016.
[27] A. Shapiro. Second-order derivatives of extremal-value functions and optimality conditions for semi-infinite programs. Math. of OR, 10:207-219, 1985. doi: 1287/moor.10...207
[28] A. Shapiro. Worst-case distribution analysis of stochastic programs. Math. Program., 107:
9 91-96. 06 2006. doi: 10.10077110107-005-000000
[29] A. Shapiro, D. Dentcheva, and A. Ruszczynski. Lectures on Stochastic Programming Modeling and Theory. SIAM, Philadelphia, 2009.
[30] A. Sinha, H. Namkoong, and Duchi. Certifying Some Distributional Robustness with Principled Adversarial Training, In ICLR 2018. Oct. 2017.
[31] M. Sipser. Introduction to the Theory of Computation. Course Technology Inc., 2006. ISBN 0-619-21764-2.
[32] M. Stone. Cross-validatory choice and assessment of statistical predictions. Journal of the Royal Statistical Society, 36:111-147, 1974.
[33] V. Vapnik. Statistical Learning Theory. Wiley, 1998.
[34] G. Wahba. Spline Models for Observational Data. Society for Industrial and Applied Mathe- matics, 1990.
[35] S. S. Wilks. Mathematical Statistics. John Wiley & Sons, 1962.
Funding Transparency Statement
All work performed as part of this paper was conducted by the authors under the employment of our respective organizations; all computing was performed on internal resources the IBM Research organization
12

---

Checklist
The checklist follows the references. Please
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A] We do not
anticipate any negative impacts, and hope that improved generalization performance will bring benefits.
(d) Have you read the ethics review guidelines and ensured that your paper conforms them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] They are included in the supplement.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material URL)? [Yes]
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g.. with respect the random seed after running experi-
ments multiple times)? [Yes] We include them as confidence intervals.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes]
4. If you using cxisting assets (c.g., code, data, models) curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] We use scikit-learn and Openml and provide a citation for each.
(b) Did you mention the license of the assets? [N/A] They are very popular commonly used libraries.
(c) Did you include any assets either in the supplemental material URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you't 're using/curating? [N/A] We use only public domain datasets from well-known public sources.
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A] We use only public domain datasets from well-known public sources.
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "fmOxZOInl0Y", "reviewer": "Reviewer_pvnB", "summary": "The paper studies a stochastic gradient descent algorithm to solve DRO problems with phi-divergence based ambiguity set, where the gradient estimate is computed from an increasing mini-batch size. The proposed algorithm is then tested numerically to demonstrate its efficiency.", "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": "The paper makes valuable contributions, and the numerical section is extensive. A few comments about the paper:\n\n- The authors develops an efficient algorithm to solve DRO problem. However, it is unclear to me why the proposed approach leads to better generalizations. I am a bit confused because different algorithms solving the same DRO problem should not give different results or lower misclassification error. \n\n- How does Table 1 change if the misclassification error is replaced with averaged logloss on test samples?\n\n- What is the stopping criteria for all algorithms reported in Table 1?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "By moving procedure 1 to the main text and having a more in-depth literature review, the authors could improve the readability of the paper.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "_53tqFyDr4I", "reviewer": "Reviewer_Nbtt", "summary": "The paper studies distributionally robust optimization, with a SGD method and sampling without replacement for the inner problem. ", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well-written, clearly organized and easy to follow. The results seem to be correct though I didn't check all the proof details. The convergence analysis using sampling without replacement is novel and interesting, which is also more practical and efficient. Therefore I incline to accept the paper.\n\n1. Can the author add more explanations to what is exactly the total computational effort? And how taking a small $\\nu$ decreases computational effort.\n2. Since $M_{t}$ are integers, it's not clear to me what does it mean by saying $\\nu$ is a constant (it might be more problematic when $\\nu \\to 1+$). Can the author explain more?\n3. The convergence rate $O(1/\\epsilon)$ seems asymptotic in terms of $\\nu$. Is it possible to derive this rate for a fixed $\\nu$, with possibly rebooting sampling?)", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The $O(1/\\epsilon)$ convergence rate is asymptotic.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "PqT_wQ08d8", "reviewer": "Reviewer_6QkA", "summary": "This paper develop and analyze an efficient double-loop-based stochastic algorithms for solving DRO problems. ", "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": "This paper is mainly an extension of Namkoong and Duchi [21]. The authors utilize Danskin's theorem to ensure the existence and form of subgradient of the inner function, thus can avoid solving the min-max problem directly. As the algorithm scheme mimics \"bilevel optimization\", the author significantly reduces the expense of solving the inner maximization over the full training dataset by subsampling technique in the iterates of the algorithm and estimating the robust loss via a sample average approximation. Moreover, the authors can control the inherent bias from the subsampling by progressively increasing the subsample size with the iterates up to the maximum size N. This doubling trick has been widely used in the stochastic second-order methods, which is nothing new and in expection. \n\n\nOverall, the paper is well-written and easy to follow. However, the author didn't submit the supplementary material. Thus, I cannot check the correctness of the technical results and quantify the technical contributions. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "2 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper gives a new method for solving the distributed robust learning problem. The new method uses a subsampling technique for the inner maximization problem which lead to faster convergence. The paper also demonstrates the effectiveness of the new method in practical settings. The reviewers have raised several concerns initially about novelty and theoretical guarantees, but they were addressed in the response period. Now the reviewers believe that the paper is technically sound and the empirical results are convincing.
Decision: Accept (Poster)