SGD with Hardness Weighted Sampling for Distributionally Robust Deep Learning
Authors: Lucas Fidon
Sebastien Ourselin
Tom Vercauteren
Venue:  (2020)
Keywords: distributionally robust optimization
distributionally robust deep learning
over-parameterized deep neural networks
deep neural networks
AI safety
hard example mining

Abstract: Distributionally Robust Optimization (DRO) has been proposed as an alternative to Empirical Risk Minimization (ERM) in order to account for potential biases in the training data distribution. However, its use in deep learning has been severely restricted due to the relative inefficiency of the optimizers available for DRO compared to the wide-spread Stochastic Gradient Descent (SGD) based optimizers for deep learning with ERM. In this work, we demonstrate that SGD with hardness weighted sampling is a principled and efficient optimization method for DRO in machine learning and is particularly suited in the context of deep learning. Similar to a hard example mining strategy in essence and in practice, the proposed algorithm is straightforward to implement and computationally as efficient as SGD-based optimizers used for deep learning.  It only requires adding a softmax layer and maintaining an history of the loss values for each training example to compute adaptive sampling probabilities.  In contrast to typical ad hoc hard mining approaches, and exploiting recent theoretical results in deep learning optimization, we prove the convergence of our DRO algorithm for over-parameterized deep learning networks with ReLU activation and finite  number  of  layers  and parameters.  Preliminary results demonstrate the feasibility and usefulness of our approach.

Under review as a conference paper at ICLR 2020
SGD WITH HARDNESS WEIGHTED SAMPLING FOR DISTRIBUTIONALLY ROBUST DEEP LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Distributionally Robust Optimization (DRO) has been proposed as alternative to Empirical Risk Minimization (ERM) in order to account for potential biases the training data distribution. However, its use in deep learning has been severely restricted due to the relative inefficiency of the optimizers available for DRO comparison the wide-spread Stochastic Gradient Descent (SGD) based opti- mizers for deep learning with ERM. In this work, we propose SGD with hardness weighted sampling. principled and efficient optimization method for DRO in machine learning that is particularly suited in the context of deep learning. Sim- ilar to an online hard example mining strategy in essence and in practice, the proposed algorithm is straightforward to implement and computationally as effi- cient as SGD-based optimizers used for deep learning. It only requires adding a softmax layer and maintaining history of the loss values for each training exam- ple to compute adaptive sampling probabilities.
contrast to typical ad hoc hard mining approaches, and exploiting recent theoretical results in deep learning opti- mization, we prove the convergence of our DRO algorithm for over-parameterized deep learning networks with ReLU activation and finite number of layers and pa- rameters. Preliminary results demonstrate the feasibility and usefulness of our approach.
INTRODUCTION
In standard deep learning pipelines, a neural network with parameters 0 is trained by minimizing the mean of per-example loss L over training dataset {(x,, y)) where x, are the inputs and y; are the labels. This corresponds to Empirical Risk Minimization (ERM), defined as the non-convex optimization problem
arg min Σ c (h(xx;))))
Since the empirical risk is equal to the expectation of the per-example loss over the empirical training data distribution, an approximate solution of (I] can be obtained efficiently by Stochastic Gradient Descent (SGD) with a uniform sampling over the training data (Bottou al., 2018).
This approach has led to remarkable results in terms of average performance, but may lead to outliers with high loss values compared the average loss. Such cases can even be observed for elements belonging to the training data set. This is because solutions of ERM are prone to ignore few hard examples order to obtain a low mean per-example loss.
In practice, outlier results have, for example, been consistently reported in the context of deep learn- ing for brain tumor segmentation, as illustrated in the recent annual BRATS challenges (Bakas al.) 2018). For safety-critical systems, such as those used in healthcare, where outliers must be avoided, this is not satisfactory.
Efficient biased sampling methods, including Online Hard Example Mining (OHEM) (Shrivastaval et al. 2016 Loshchilov Hutter, [015 Chang et al. 2017) and weighted sampling (Bouchard et al. 2015 Berger al. [2018] Gibson al. 2018), have been proposed to mitigate this issue. However, even though these works typically start from an ERM formulation, is not clear how those heuristics actually relate ERM in theory.

---

Under review as a conference paper at ICLR 2020
Distributionally Robust Optimization (DRO) is alternative ERM that takes into account uncertainty in the empirical data distribution. Formally, training a deep neural network with DRO corresponds to the min max non-convex-coneayy optimization problem
Σ q: (k(x)))))
arg min max
B o (nq))
Σ 1 n
(2)
where é a convex function that defines a d-divergence (Csiszár et al. 2004 y responds to an arbitrary sampling distribution over the training data, and 0 is a robustness parameter. Instead of minimizing the mean per-example loss on the training dataset, DRO seeks the hardest weighted empirical training data distribution around the (uniform) empirical training data distribution. This suggests a link between DRO and OHEM.
(q:)²=1 cor-
The parameter allows DRO to interpolate between ERM (B - 0) and the minimization of the maximum per-example loss (3 - +00). Motivations for using the minimization of the maximum per-example loss for safety-critichs applications have been discussed in SSalee-SSwarrz & Wexler 2016).
DRO generalization of ERM for machine learning has been studied in (Duchi al. 2016 Rafique et al.] 2018 Namkoong & Duchi 2016 Chouzenoux et al., (019), but still lacks optimiza- tion methods that are computationally efficient as SGD in the non-convex setting of deep learning.
If one could efficiently solve the inner maximization problem in (2) for a given 0, DRO could be addressed by alternating between this maximization problem and minimization scheme akin to the standard ERM (T). but over an adaptively weighted empirical distribution. However, even when closed-form solution available for the inner maximization problem, it requires performing forward pass over the entire training dataset at each iteration. This cannot be done efficiently for large dataset.
Previously proposed optimization methods for large-scale nat--onvexx-ooncvae problem of the form of (2) are based on the min max min-max structure of the problem, and consist alternating between approx- imate maximization and minimization steps (Rafique et al. 2018 Lin et al. 2019 Jin et al. 2019). However, they differ from SGD methods for ERM by the introduction ters for the optimizer such as second learning rate and a ratio between the number of minimization and maximization steps. As a result, DRO is difficult to use as a replacement of ERM in practice. In addition, those min-max methods do not the link between DRO and adaptive weighted sam- pling, therefore departing from efficient heuristics used hard example mining. From a theoretical perspective, they further make the assumption that the model is either smooth weakly-convex, but none of those properties are true for deep neural networks with ReLU activation functions that are largely used in practice.
additional hyperparame-
In this work, we propose SGD with hardness weighted sampling, novel, principled optimization method for training deep neural networks with DRO (2) and inspired by OHEM. Compared to SGD, our method only requires introducing an additional softmax layer and maintaining history of the stale per-example loss to compute sampling probabilities over the training data. Since the loss is already computed at each iteration for SGD, our SGD with hardness weighted sampling for DRO computationally as efficient as SGD for ERM. practice, we show that our method performs favorably to SGD in the case of class imbalance.
We also formally link DRO our method with OHEM (Shrivastava al. 2016). As result, our method can be controls the trade-off between exploitation and exploration in the OHEM process.
principled OHEM approach. In this context, the robustness parameter /
Last but not least, we generalize recent results in the convergence theory of SGD with ERM and over-parameterized deep learning networks with ReLU activation functions (Allen-Zhu et al. 2019 2018 Cao & Gul 2019; Zou & Gu 2019) to SGD with hardness weighted sampling for DRO. This is, to the best of our knowledge, the first convergence result for deep learning networks with ReLU trained with DRO.
2

---

Under review as a conference paper at ICLR 2020
2 RELATED WORK IN DRO WITH A WASSERSTEIN DISTANCE
In this work, we focus on DRO with a d-divergence (Csiszár al. 2004). In this case, the data distributions that are considered in the DRO problem are restricted to sharing the support of the empirical training distribution. In other words, the weights assigned to the training data can change, but the training data itself remains unchanged.
Another popular formulation is DRO with a Wasserstein distance (Sinha et al. 2017 Duchi et al, 2016 Staib & Jegelka 2017 Chouzenoux et al. al. (019)). In contrast to d-divergences, using Wasser- stein distance in DRO seeks to apply small data augmentation to the training data to make the deep learning model robust small deformation of the data, but the sampling weights of the training data distribution typically remains unchanged. In this sense, DRO with a g-divergence and DRO with a Wasserstein distance can be considered as orthogonal endeavours.
While we show that DRO with o-divergence can be seen as a principled OHEM method, it has been shown that DRO with Wasserstein distance be seen principled adversarial training method (Sinha et al. 2017: Staib & Jegelka 2017).
3 MACHINE LEARNING WITH DRO AND Ó-DIVERGENCE
In machine learning based Empirical Risk Minimization (ERM), a predictor h is trained using a training dataset {(x; y:) }== to perform well on average on a task for which the performance is measured on per-example basis by smooth criteria L. Note that parameter regularization terms can easily be embedded in L since they are independent of the example. For ease of presentation, we focus on the supervised machine learning setting ,here æ + y, and omit explicitly mentioning any parameter regularisation term.
Let An C RR be the set of empirical weighted training data distributions defined according to given training dataset
A {p -p:) E [0, 1|" PP:-1
(3)
and let Pdata be the uniform empirical training data distribution. i.c. for all i, Pdata.) 1 n Let 0 be the set of parameters of the predictor :)::0) æ + y we want to train, and h : 0 + (h( 0))" be the vector of inferred outputs from the training data. We assume L a smooth and potentially non-convex function. We also denote ((h(O)) (L(h(a,, 0), y:))
Definition 3.1 (Mean Loss).
n
M ((()(O))) -Epaaaa ()( y)1 = Oh(xx:)).)))
(4)
The ERM predictor, used in most learning settings, is obtained by minimizing the mean loss (4). Definition 3.2 (Empirical Risk Minimization (ERM) predictor).
i arg min M(C(h(0))
However, Pdata is typically biased compared to the true data distribution. Therefore, predictors trained with ERM are prone to fail on examples that are not well represented in the training dataset.
Distributionally Robust Optimization (DRO) is alternative to ERM that mitigates this issue by encouraging robustness to bias in the empirical training data distribution. DRO, in its simplest form, based on the notion of o-divergence that we use to induce robustness with respect the set of all the empirical distributions of the training dataset A,,.
Definition 3.3 (g-divergencee. Let Ø Rt, (R((+o) be a closed, convex, lower semi-continuous
function such that Vz E R4, o(2) 2 ((1) = O. The o-divergence D& is defined as, for all =
(p.) = )d An
Do (gllp) =
Σ
9i p;
(6)
1=1
3

---

Under review as a conference paper at ICLR 2020
Example 3.1. For Φ :2 + zlog(2), D& is the Kullback-Leibler (KL) divergence:
Do(allp) DRL(alP))
Σ
Ti log
qi
pi
2=1
And, for 2:2+ (z 1)2, Dø is the Pearson x² divergence:
(gi p+)
Dolallp) (g Σ
(8)
pi
Definition 3.4 (Distributionally Robust Loss).
R(C(h(0))) = max E2 [C (hx:xx; 0). - PEA,
(9)
Σ 4: [h(x;)))) 0), gEAn.
max
(nq:)
nB
where B > 0 is hyperparamette that controls the amount of robustness.
For given é o-divergence, we define the DRO predictor, that is obtained by minimizing the distribu- tionally robust loss (9) instead of the mean loss
Definition 3.5 (Distributionally Robust Optimization (DRO) predictor).
arg min R(C(h(O))
(10)
DRO interpolates between ERM as 3 0 and the minimization of the maximum loss as 3 oo, and is equivalent to a mean-variance trade-off when B + 0 small (Gotoh et al. 2018), i.e.
max OEA,
Eg [c(h (x: 0). 8 Dolglldduca))
Epiaa
[C(h (x: 0)]
V Pana [C(h 0). + o(3) (11)
(1)
max yEA,
E. [C(h (x: 0),0) .y]
3 Dolgl DolllPaaaaa
max C(h (x; .y)
+-0
where V Vpuaa is the empirical variance.
Furthermore, we observe that the distributionally robust loss (9 is an upper bound to the mean loss (independently to the choice of & and B), i.c. for all ø-divergence and all
Ye, M(C(h(O) < R(C(h(0))
(12)
We now make assumptions for the o-divergence simplify the derivations of optimization method for DRO (10) in the remainder the paper.
Assumption 3.1 (Regularity Φ). á R4 + R is two times continuously differentiable on [0, ml.
p-strongly convex nl, i.e.: 3p O, Vz, z' E m]. d(z') 6(2) (2( =) ( 2')
and satisfies (see D.1 for a justification): Vz E R, d(z) 2 Φ(1) = 0, (( = 0.
These assumptions are verified by most d-divergences used in practice (e.g. the KL divergence).
SGD WITH HARDNESS WEIGHTED SAMPLING
4.1 DISTRIBUTIONALLY ROBUST OPTIMIZATION WITH SGD AND ADAPTIVE SAMPLING
Existing optimization methods for DRO with non-convex predictor h alternae between approxi- mate minimization and maximization steps (Rafique et al., 2018)) Ji et al. 2019 Lin et al. 2019). requiring the introduction of additional hyperparameters compared SGD. These diffiult to
4

---

Under review as a conference paper at ICLR 2020
tune in practice and convergence has not been proven for deep neural networks with ReLU activa- tion functions.
In this section, highlight properties that allows to link DRO with SGD combined with adap- tive sampling. Our analysis relies on Fenchel duality (Moreau 1963 and the notion of Fenchel conjugate (Fenchel 1949) that now define.
Definition 4.1 (Fenchel Conjugate Function). Let ʃ Rm R
SRRU(+oo (+00) be a proper function. The Fenchel conjugate of f is defined Vu E R", (*) maXxER" (v, f(x).
Let
Vp E R", G(p) 1
D + do (p)
(13)
where &2, is the characteristic function of the closed convex set A i.e.
0
p A.,
Vp E E", (p)
(14)
+00 otherwise
One can remark that the distributionally robust loss R. 9 can be rewritten using the Fenchel conju- gate function of G. This allows us to obtain regularity properties for R.
Lemma 4.1 (Regularity R). e satisfies Assumption 3.7 3.7 then G and R satisfy the following:
np 3
G is
-strongly convex
(15)
4O, R(C(N(O)) = max ((C(h(0)). G* QER"
(16)
B
R is
-gradient Lipschitz continuous.
(17)
np
Equation (16) follows from Definition
Proofs of (5) and can be found in Appendix D.3
According to 15 the optimization problem 16 is strictly convex and admit unique solution in A,, Let us denote this solution
p(C(H(O))) arg max ((C(h(0)), G(g))
(18)
qER"
The following lemma shows that the gradient, with respect to 0, of the distributionally robust loss (9) at a given 0 can be rewritten as the expectation, with respect to the weighted empirical distribution pl p())) of the per-example loss gradient. We further show that straightforward analytical for- mulas exist for when relying on classical d-divergences. This result motivates our Algorithm 4.1 for efficient training with the distributionally robust loss.
Lemma 4.2 (Stochastic Gradient of the Distributionally Robust Loss). For all 9 we have
(((()(0)) (..((((())))
(19)
(o o L h)) = Ep(c(m()) (Vo C (h(x;)),
where V,, is the gradient of R with respect to its imput.
The proof is found in Appendix D.4 It is apparent from 19 that, given p. an estimate of (a Lo)) could easily be provided by sampling a batch according to p and estimating the per-example loss gradients in the batch per standard practice. We now provide closed-form formulas for given (()(O)) for the KL divergence and the Pearson x² divergence.
Example 4.1. For the KL divergence (i.e. o: z + log(2) - 2 + 1), we have (see D.2 for a proof) p(C(h(0))) softmax (3 (()()))
(20)
And for the Pearson x2 divergence (i.e. & z + (z - 1)²), we have:
vi, (.((((O)) ReLU
1
B
((h(0)),
1 n
Σ
c(h(0));
(21)
n
n
In both cases, can verify consistency with 11)
Vi E nI,
pi(C(h(O))
(22)
8-00 n
5

---

Under review as a conference paper at ICLR 2020
Algorithm SGD-HWS: SGD with Hardness Weighted Sampling for Kullback-Leibler DRO
1: Input: Training data { 3 number of epochs > 1, robustness parameter > 0, learning rate 1j O, batch size E pl..
2: Initialization:
3: Initialise 0 randomly
4: Initialise the loss history C =
5: Warm start:
6: // Split the training data into batches and run one epoch with classic SGD
7: for {Zz, Bee in B do
8: Run forward pass and store losses for all the samples the batch for i E do
9:
C; + L(h(ar;; 0), Mi)
11: // Run backward pass and update the parameters of the model 7/ Eier Vo [h((2, 0), ys)
13: SGD with dynamic hardness weighted sampling:
14: for epoch = 2,
do
(1 +11 do
for iteration
16:
// Run softmax update the sampling probabilities of the samples softmax(3C)
17:
18:
Draw a batch with replacement using the probability distribution ç
(1 yt)rez such that Lid. p and |4]
20:
// Run forward pass and update losses for all the samples in the batch for i I do
22:
L. + L(h(as;; v1)
Run backward pass and update the parameters of the model 0- 0 1 Σier Vo [(h(z,;; 0).
24:
25:
Output:
4.2
EFFICIENT ALGORITHM FOR DISTRIBUTIONALLY ROBUST DEEP LEARNING
The second equality in 19) implies that Vo (0), y:) is an unbiased estimator of the distribu- tionally robust loss gradient when is sampled with respect ((C(h(0)) This suggests that the distributionally robust loss can be minimized efficiently by SGD by sampling mini-batches with re- spect p()) each iteration. However, even though closed-form formulas were provided for p. evaluating exactly L(h(O)). i.e. doing one forward pass on the whole training dataset at each iteration, is computationally prohibitive for large training dataset.
In practice, we propose to use a stale version of C(h(O)) by maintaining an online history of the loss values of the training examples during training (C(h(w;; ((+)), (())) Where for all i, 4 is the last iteration at which the per-example loss of example i has been computed. Using the Kullback-Leibler divergence o-divergence, this leads to the SGD with hardness weighted sampling algorithm pro- posed in Algorithm 4.1 This would also apply the Pearson x2 divergence mutatis mutandis.
In contrast to alternate min-mas miin-mxx optimization methods, our SGD with an adaptive sampling strategy similar to the SGD-based optimizers used by the vast majority of deep learning practitioners. Compared to standard SGD-based training optimizers for the mean loss, our algorithm requires only an additional softmax operation per iteration and to store an additional vector of size n (number of training examples), thereby making it ideally suited for deep learning applications.
4.3 CONVERGENCE OF SGD WITH HARDNESS WEIGHTED SAMPLING FOR DEEP NEURAL NETWORKS WITH ReLU
Convergence results for wer-parameterized deep learning has recently been proposed in (Allen- Zhu et al. 2019). Their work gives convergence guarantees for deep neural networks h with any activation functions (including ReI.U), and with any (finite) number of layers and parameters m,

---

Under review as a conference paper at ICLR 2020
under the assumption that m is large enough. At the time of writing, this is the most realistic setting for which a convergence theory of deep learning exists.
In this section, extend the convergence theory developed by (Allen-Zhu et al., 2019) for ERM and SGD to DRO and the proposed SGD with hardness weighted sampling (as stated in Algorithm 4.1
Theorem 4.1 (Convergence of Algorithm 4.1 for over-parameterizes neural networks with ReLU). Let L be smooth per-sample loss function, b E (1.....n) be the batch size, and c > O. If m is large enough, and the learning rate is small enough, then, with high probability over the randomness of the initialization and the mini-batches, Algorithm 4.7 finds (V o L (o)) S e after finite number of iterations.
more detailed version of this theorem is described in B.2 and the proof can be found in D
4.4 DRO AS PRINCIPLED ONLINE HARD EXAMPLE MINING
In this section, discuss the relationship between DRO and Online Hard Example Mining (OHEM) (Shrivastava et al., 2016). SGD with an ad hoc adaptive sampling strategy is already used in practice while starting from mean loss optimization formulation in the OHEM litera- ture (Loshchilov & Hutter] 2015 Shrivastava et al.) 2016). Similarly to our algorithm, in OHEM heuristics, the hard examples, those training examples with relatively high values of the loss, sampled more often. We formalize this in the following definition for OHEM sampling.
Definition 4.2 (Online Hard Example Mining Sampling). Any adaptive sampling method such that the probability Ps of sampling example x; an non-decreasing function of the (potentially stale) loss value associated with X;.
Theorem 4.2. The proposed hardness weighted sampling is a hard example mining sampling for any o-divergence that satisfies Assumption 3.1 In addition, the probability p: of sampling example x; is an non-increasing function of the loss value associated with X, for all } +i.
See Appendix D.5] for the proof. The second part of Theorem implies that as the loss of an example diminishes, the sampling probabilities of all the other examples increase. As a result, the proposed SGD with hardness weighted sampling balances exploitation (i.e. sampling the identified hard examples) and exploration (i.e. sampling any example to keep the record of hard examples up to date).
5 EXPERIMENTS
We now illustrate the properties of our SGD with hardness weighted sampling described in Algo- rithm 4.1 for training deep neural networks with ReLU activation functions for DRO (I0).
5.1 ROBUSTNESS TO DOMAIN GAP
We create a bias between training and testing data distribution of MNIST (LeCun 1998) by keep- ing only 1% of the digits 3 in the training dataset, while the testing dataset remains unchanged. Implementation details can be found in Appendix A.
Comparison of ERM with SGD and DRO with our SGD with hardness weighted sampling for / 10 at testing can be found in Figure I More values of 33 and the learning curves during training can be found in Figure
Our experiment suggests that DRO and ERM lead to different optima. Indeed, DRO for / 10 outperforms ERM by more than 10% of accuracy on the under-represenned class, as illustrated in Figure ! This suggests that DRO leads to better generalization than ERM. Especially, it appears that DRO is more robust than ERM to domain gaps between the training and the testing dataset. In addi- tion, Figure I suggests that DRO with our SGD with hardness weighted sampling can convergence faster than ERM with SGD.
Furthermore, the variations of learning curves with 3 that can be found in Figure 2 are consistent with our theoretical insight. As B decreases to 0, the learning curve of DRO with our Algorithm 4.1 converges to the learning curve of ERM with SGD.
7

---

Under review as a conference paper at ICLR 2020
Testing Accuracy for All Digits (in %)
Testing Accuracy Digit 3 (in %)
80
95.0
92.5
65.0
20-
ERM (beta-O Ir- 0.)
DRO (beta-10, Ir-0.01)
100
200
300
400
500
100
200
300
400
500
epoch
epoch
Comparison learning curves for ERM with SGD (blue) and DRO with our SGD with hardness weighted sampling (red). The models are trained on imbalanced MNIST dataset (only 1% of the digits kept in the training datatset) and evaluated on the original MNIST testing dataset. This suggests that SGD with hardness weighted sampling more robust than SGD to domain gap between the training and the testing dataset.
Figure 1:
5.2 STABILITY OF DRO
For large values of 3 (here 3 2 10), instabilities appear in the testing learning curves at the begining of training, illustrated in Figure [ and in the top panels of Figure 2 For ERM this usually suggests that the learning rate is too high.
However, observed that reducing the learning rate does reduce those instabilities. The bottom left panel of Figure 2 shows that the training loss curves for 3 2 10 were actually stable there. We also observe that during the iterations for which instabilities appear on the testing set, the standard deviation of the per-sample loss on the training set increases and then decreases. Following (20) the higher the standard deviation of the per-sample loss history, the more our weighted sampler focuses on hard examples. Therefore, instabilities on the testing set during training with DRO are due to the sampler focusing on hard examples.
6 CONCLUSION AND DISCUSSION
We have shown that efficient training of deep neural networks with Distributionally Robust Opti- mization (DRO) with ó-divergence (10) is possible. Our Stochastic Gradient Descent (SGD) with hardness weighted sampling
principled Online Hard Example Mining (OHEM) method. It is as straightforward to implement, and as computationally efficient as SGD for Empirical Risk Min- imization (ERM). can used for deep neural networks with any activation function (including ReLU), and with any per-example loss function. We have shown that the proposed approach can formally be described as principled online hard example mining strategy. addition, we prove the convergence of our method for peeepparameterized deep neural networks. Thereby, extending the convergence theory of deep learning (Allen-Zhu et al. 2019). This is, to the best our knowledge, the first convergence result for training deep neural network based on DRO.
Our experiments on an imbalanced MNIST dataset illustrate the practical usefulness and feasibility of our methods. SGD with hardness weighted sampling is more robust domain gaps between the training and the testing dataset and converges faster than SGD.
However, adapting acceleration methods for ERM with SGD, like momentum updates, to DRO remains non-trivial because of the inner maximization of DRO. Investigating accelerated extension of our method is left for future work.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Zeyuan Allun-Zhu, Yuanzhi Li, and Zhao Song. On the convergence rate of training recurrent neural networks. arXiv preprint arXiv: 1810. 2065,, 2018.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. convergence theory for deep learning via over- parameterization. In ICMI, pp. 242-252, 2019.
Spyridon Bakas, Mauricio Reyes, Andras Jakab, Stefan Bauer, Markus Rempfler, Alessandro Crimi, Russell Takeshi Shinohara, Christoph Berger, Sung Min Ha, Martin Rozycki, et al. Identifying the best machine learning algorithms for brain tumor segmentation, progression assessment, and overall survival prediction in the brats challenge. arXiv preprint arxiv:1811.000 026629, 2018.
Yoshua Bengio. Practical recommendations for gradient- training of deep architectures. In Neural networks: Tricks of the trade, pp. 437-478. Springer, 2012.
Lorenz Berger, Hyde Eoin, M Jorge Cardoso, and Sébastien Ourselin. An adaptive sampling scheme to efficiently train fully convolutional networks for semantic segmentation. In Annual Conference on Medical Image Understanding and Analysis, pp. 277-286. Springer, 2018.
Léon Bottou, Frank Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. Siam Review, 60(2):223-311, 2018.
Guillaume Bouchard, Théo Trouillon, Julien Perez, and Adrien Gaidon. Online learning to sample. arXiv preprint arXiv:1506.0000 09006, 2015.
Yuan Cao and Quanquan Gu. A generalization theory of gradient descent for learning over- parameterized deep relu networks. arXiv preprint urXiv:/902.01:: 2019.
Haw-Shiuan Chang, Erik Leilned-Miller and Andrew McCallum. Active bias: Training more accu- rate neural networks by emphasizing high variance samples. In Advances in Neural Information Processing Systems, pp. 1002-1012, 2017.
Emilie Chouzenoux, Henri Gérard, and -ean-Christophe Pesquet. General risk measures for robust machine learning, arXiv preprint urXiv:1904.10 1et.119947.177 2019.
Imre Csiszár, Paul C Shields, et al. Information theory and statistics: A tutorial. Foundations and Trends in Communications and Information Theory, 1(4):417-528, 2004.
John Duchi, Peter Glynn, and Hongseok Namkoong. Statistics of robust optimization: A generalized empirical likelihood approach. arXiv preprint urXiv:1610.03442. 2016.
Werner Fenchel. On conjugate convex functions. Canadian Journal of Mathematics, 1(1):73-77, 1949.
Eli Gibson, Wenqi Li, Carole Sudre, Lucas Fidon, Dzhoshkun Shakir, Guotai Wang, Zach Eaton- Rosen, Robert Gray, Tom Doel, Yipeng Hu, et al. Niftynet: a deep-learning platform for medical imaging. Computer methods and programs in biomedicine, 158:113-122, 2018.
Jun-ya Gotoh, Michael Jong Kim, and Andrew EB Lim. Robust empirical optimization is almost the same as vean-variance optimization. Operations research letters, 46(4):448 452, 2018.
Jean-Band Man-BBatiste HiriartUUrutty and Claude Lemaréchal. Convex analysis and minimization algorithms Fundamentals, volume 305. Springer science & business media, 2013.
Chi Jin, Praneeth Netrapalli, and Michael I Jordan. Minmax optimization: Stable limit points of gradient descent ascent are locally optimal. arXiv preprint arXiv:1902.0066 2019.
Yann LeCun. The mnist database of handwritten digits. htip://yann. lecun. com/exdb/mmist// 1998.
Tianyi Lin, Chi Jin, and Michael I Jordan. On gradient descent ascent for nonconvex-comcave minimax problems. arXiv preprint arXiv:1906.003: 2019.
Ilya Loshchilov and Frank Hutter. Online batch selection for faster training of neural networks. arXiv preprint arXiv: /51 063343, 2015.

---

Under review as a conference paper at ICLR 2020
Jean-Jacques Moreau. Proximité et dualité dans espace hilbertien. Bulletin de la Société mathématique de France, 93:273-299, 1965.
Hongseok Namkoong and John C Duchi. Stochastic gradient methods for distributionally robust optimization with f-divergences. In Advances Neural Information Processing Systems, pp. 2208-2216, 2016.
Hassan Rafique, Mingrui Liu, Qihang Lin, and Tianbao Yang. Non-convex min-max optimization: Provable algorithms and applications in machine learning. arXiv preprint arXiv:1810.02060, 2018.
Shai Shalev-Shwartz and Yonatan Wexler. Minimizing the maximal loss: How and why. In ICML,, pp. 193-801, 2016.
Abhinav Shrivastava, Abhinav Gupta, and Ross Girshick. Training region- based object detectors with online hard example mining. In Proceedings of the IEEE conference on computer vision and patter recognition, pp. 761-769, 2016.
Aman Sinha, Hongseok Namkoong, and John Duchi. Certifying some distributional robustness with principled adversarial training. arXiv preprint 1710. 10571, 2017.
Matthew Staib and Stefanie Jegelka. Distributionally robust deep learning as generalization of adversarial training. In NIPS workshop Machine Learning and Computer Security, 2017.
Sergey Zagoruyko and Nikos Komodakis. 1rXiv:1605.07146, 2016.
Wide residual networks.
arXiv preprint
Difan Zou and Quanquan Gu. An improved analysis of training over-parameterized deep neural networks, arXiv preprint arXiv: 1906.04688, 2019.
10

---

Under review as a conference paper at ICLR 2020
A MORE ON OUR EXPERIMENTS
A.1
EXPERIMENTS ON MNIST
Testing Accuracy for Digits (in %)
Testing Accuracy for Digit (in %)
100.0
100
92.5
60-
ERM (beta-0.0, lr-0.01)
DRO (beta-0.1, (r-0.01)
DRO (beta=1.0, (r=0.01)
DRO (beta=10, Ir=0.01)
82.5
DRO (beta=100, lr=0.01)
100
200
300
400
500
100
20c
300
400
500
epoch
epoch
Training Loss
Training Per-sample Loss Standard Deviation
ERM (beta=0.0, Ir=0.01)
DRO (beta=0.1, 0n00.)
DRO (beta=1.0, Ir=0001)
0.8
DRO (beta=10, lr=0.01)
15
DRO (beta=100, lr=0.01)
0.4
0.5
0.1
50 100
150
200
250
300
50
100
150
200
25.0
300
epoch
epach
Comparison of learning curves at testing (top panels) and at training (bottom panels) for ERM with SGD (blue) and DRO with our SGD with hardness weighted sampling for different values of 3 on MNIST (8 0.1, B = 1, 3 10, 8 100). The models are trained on an imbalanced MNIST dataset (only 1% of the digits kept in the training datatset) and evaluated on the original MNIST testing dataset.
Figure 2:
A.1.1 IMPLEMENTATION DETAILS
For experiments MNIST, used Wide Residual Network (WRN) (Zagoruyko & Ko- modakis 2016). The familly of WRN models has proved to be very efficient and flexible, achieving state-of-the-ane accuracy several dataset. More specifically, used WRN-16-1 (see Zagoruyko & Komodakis 2016, section 2.3).
For the optimization used learning rate of 0.01. No momentum weight decay used. No data augmentation was used.
A.1.2 COMMENT ON EARLY-STOPPIN WITH ERM AND DRO
is worth noting that we do not use the knowledge of the training dataset bias in our method. For less obvious bias, would have access to the accuracy the inder-representated subset of the training set. As a result, in general, convergence criteria can be based only on the global measure of accuracy (in our case the top left panel of Figure 2..

---

Under review as a conference paper at ICLR 2020
Early-stopping is widely used heuristic for selecting the optimal number of epochs prevent overfitting (Bengio 2012). Early-stopping crucially depends on the patience parameter. In the top left panel of Figure there is no improvement of the accuracy of ERM of more than 0.04% between epoch 20 and 30. As result, if the patience parameter is too low, ERM might be considered to plateau an epoch at which it ERM achieves accuracy of 0% on the under-represented class.
This suggests two things. First, the mean accuracy is not good criteria to decide when to stop the training of ERM for safety-critical systems. Second, our SGD with hardness weighted sampling converge faster than SGD to a safe solution, and is more robust to the hyperparameters of early- stopping.
B CONVERGENCE OF SGD WITH HARDNESS WEIGHTED SAMPLING FOR OVER- PARAMETERIZED DEEP NEURAL NETWORKS WITH ReLU (DETAILED STATEMENT)
In this section, we give a detailed statement of the convergence results presented in 4.3
Our analysis is based the results developed in (Allen-Zhu et al. 2019) which is simplified version of (Allen-Zhu et al. 2018). Improving on those theoretical results would automatically improve our results well. We focus on providing theoretical tools that could be used to generalize
any convergence result for ERM using SGD to DRO using Algorithm|4.) 1 In addition, we compared our conditions and results the one obtained for ERM and SGD in (Allen-Zhu the implication of those differences.
2019) and discuss
Let us first state our assumptions on the neural network h, and the per-example loss function C. Assumption B.1 (Deep Neural Network). In this section, use the following notations and as- sumptions similar to (Allen-Zhu et al. 2019):
h is a fully connected neural network with 2 layers, ReLU activation finction, and m nodes in each hidden layers
n1), we denote : 0 - h,(2;;; 0) the output d dimensional scores For all (l....,
applied to example I; of dimension d.
0 = (0)) the set of parameters of the neural network h, where O₁ is the set of weights for layer with 0g E R xm, OL+1 E RRxdd and 0₁ E m.m for any other l.
(Data separation) It exists 8 > 0 such that for all i, E ifi j. 1|, - Iz 2 6.
We assume 2 Si(d x poly(n, L, ())) for some sufficiently large polynomial poly, and 8 ス (+). We refer the reader to (Allen-Zhie Zhu et al. 2019) for details about poly.
The parameters 0 = (00))
1+t are initialized at random such that:
-Oolss .' (0, 2) for every (i,5) E {1....,
m] x { (1,...,0} D
-1iil. ~ M (0, ".) for every (1.j) E [1,....,m] and l [1....,
- 10L+1le, ~ ~ (0, 2) for every (t.j) E (l.....d} x mm)
Assumption B.2 (Regularity of L). For all L, is C(V -gaddient Lipschitz continuous, C(C)-
Lipschitz continuous, and bounded (potentially non-convex) function.
We first generalize the convergence of SGD (lllen-hhu et al., 2019 Theorem 2) the minimiza- tion of the distributionally robust loss using SGD and an exact hardness weighted sampling (9). i.c. with an exact non-stale loss history.
Theorem B.1 (Convergence of Robust SGD with exact Loss History). Let batch size S < and O. Suppose there exists constants C1, C2. Cg
O such that the number of hidden units satisfies m 2 C2(de x poly(n, L, (,8--)),, 2 (+)), and the learning rate be Nexact = hid
O3 min (1, (012)+2mp0iVE P X Loly(n,L)m (mm)
There exists constants Cs. Cs > such
12

---

Under review as a conference paper at ICLR 2020
that with probability at least - exp (-Ca(log((m)) over the randomness of the initialization and the mini-batches, Robust SGD with exact loss vector finds [[V (R o (o)) |I S 6 after T Os
Tine
iterations.
where a = ming min; Pi( (O)) is lower bound on the sampling probabilities. For the Kullback- Leibler @-divergence, and for any o-divergence satisfying assumption 3.1 with robustness param- eter / small enough, we have a > We refer the reader to (Allen-Zhu et al. 2019 Theorem 2) for the values of the constants C1. C2. C3, Ca. C3 and the definitions of the polynomials. Compared to (Allen-Zhie et al. 2019 Theorem 2) only the learning rate differs. The min operation the formula for Mexact allows
guarantee that Mexact S '/' where n/ is the learning rate of (Allen-Zhu et al. 2019 Theorem 2). The proof can be found Appendix D.7.3]
It is worth noting that for the KL o-divergence, p
In addition, in the limit 8 + 0, which
corresponds ERM, we have a + 1, As a result, we recover exactly Theorem 2 of (Allen- Zhu ct al. 2019) as extended in their Appendix A for any L that satisfies assumption B.2 with C(VL)
When the amount of distributionally robustness increases the sampling differs more and more from the uniform sampling and becomes more sensitive to changes of the loss distribution. One way to mitigate this issue is to reduce the learning rate. The conditions of Theorem B.1 are consistent with this observation since when 3 increases, a and Teanac decreases.
In practice in algorithm 4.1 we have access only to stale loss history. We know restate the conver- gence of Robust SGD with stale loss history and a warm-up as in Algorithm 4.1
Theorem B.2 (Convergence of Robust SGD with Stale Loss History and warm-up). Let batch size S b S n, and
O. Under the conditions of Theorem B.1 the same notations, and with the
/2d 1-6)
learning rate Mstale Co min
Mexoct for constant Co O.
BC(C)A( C) And7 log" (og)
With probability at least exp -Ca(log' (m))) (m))) over the randomness of the initialization and the mini-batches, Robust SGD with exact loss vector finds [[Vo(R (O)l S after T
Cs (atatabe)
Lnd iterations.
Where C(C) > O is constant such that C is C(C)-Lipsciitz continuous. and A(V L) > 0 is constant that bound the gradient of with respect to input. C(C) and A(V L) are guaranteed to exist under assumptions B.1 The proof can be found in Appendix D.8
Compared to Theorem B. only the learning rate differs. Similarly Theorem B.1 when 3 tends
to zero we recover Theorem 2 of (Allen-Zhu et al. (019)).
2/2 log( It is worth noting that when 3 increases, 3CIC)A(V Lm 1og decreases. This implies that nstale decreases faster than Mezact when / increases. This was to expected since the error that made by using the stale loss history instead of the exact loss increases when / increases.
C SUMMARY OF THE NOTATIONS USED IN THE PROOFS
For the ease of following the proofs we first summarize our notations.
C.I PROBABILITY THEORY NOTATIONS
An tp (p:) E 1[", E;p=
Let (q:) E A., and function, we denote [x] ;= En af(xs).
Let g E A,, and f function, we denote V,[/(x)) = Σi= (x;))(;;))))))))))(()) E. [x))]]
Pdata is the uniform training data distribution, i.c. Pdata = (1) 1=1 E An,
C.2 MACHINE LEARNING NOTATIONS
the number of training examples
13

---

Under review as a conference paper at ICLR 2020
d is the dimension of the output
the dimension of the input
training data: {(1) 1=))= where for E (I,...,)) n), ai R and ys E Rdd
h : æ > is the predictor
0 is the set of parameters of the predictor
For all i, h 0 ~ h(x;; 0) is the output of the network for example i function of 0
is the objective function
D h; + C(2,, ys) the objective functtin for example i.
By abuse of notation we also denote by L the function L (14) + (Ci(h:))
b nu is the batch size
7J 0 the learning rate
ERM is short for Empirical Risk Minimization
C.3 DISTRIBUTIONALLY ROBUST OPTIMISATION NOTATIONS
Forall 0, R(C()(O)) maxgE Eny [ (h(x; 0)) (allllaaata) is the Distribu- tionally Robust Loss evaluated at 0, where 3 > 0 is the parameter that adjusts the distri- butionally robustness (see (9) for more details). For short, we also used the term Robust Loss for R()()(0))
DRO is short for Distributionally Robust Optimisation
C.4 MISCELLANEOUS
By abuse of notation, and similarly to (Allen-Zhu et al.
2019), the Bachmann-Landat nota- tions to hide constants that do not depend on our main hyper-parameters. Let f and g be two scalars,
note:
0
E>
s.t.
f < eg
12 (g)
Ee > 0
cg
Og)
3c1 > 0 and 3cm C1
s.t.
C1g S f S c2g
D PROOFS
D.1 ASSUMPTIONS FOR THE Ó-DIVERGENCE
Let D& d-Divergence, and e E R. One can note that for &e 2 o(2) + c(1 - 2)) we have for all p (p:) 9 (q)) E An,
n
D&. (gllp)
Σ
Pidc
qi
pi
Pi
+
Pi
Pi
(23)
1=1
D& (dllp) +c
pi
Σ
91
Do (gllp)
In other words, D& is not uniquely defined by o under the definition 3.3 can assume without loss of generality that o' O.
If ó is differentiable, one
For more detailed discussion, refer the interested reader (Sissár al. 2004
14

---

Under review as a conference paper at ICLR 2020
D.2 PROOF OF EXAMPLE 4. FORMULA OF THE SAMPLING PROBABILITIES FOR THE KL DIVERGENCE
We give here simple proof of the formula of the sampling probabilities for the KL divergence as d-divergence (i.e. Φb + z log(z) - = 1)
vO, p(C(h(0)) = softmax (3 (()())))
For any 8, the distributionally robust loss ( for the KL divergence at 0 is given by
RoLoh(O) = max PEá.
Σ qi Lo ho) ii
Σ di log (nq))
B
im1
max qEAn.
qi Co (4) 39 log (1q::)
To simplify the notations, let us denote v = (w:)i=r = Lo h() = (L, ((()) and (p.)=11 = (()))
Thus ((C(h(0)) is, by definition, solution of the optimization problem
arg max
Σ
qiv, 3 log (nqq))
(24)
First, let us remark that the function Σ 9s log (ng,) is strictly convex the non empty closed convex set An as sum strictly convex functions. This implies that the optimization (2) has unique solution and result ((C(((0)) is well defined.
We now reformulate the optimization problem (24 as convex smooth constrained optimization problem by writing the condition An as constraints.
1
3 q6 log (ng::)
arg max N
(25)
s.t.
4
There exists Lagrange multiplier RR such that the solution p of 25 is characterized by
1
Vi E (1....... n).
0
(log (np.) + 1) A = 0
B
(26)
V P p=
1=1
Which we can rewrite as
Vi n1,
p: = exp (3 (c; + A) -1)
n
(27)
exp ( (v, A) 1)
n
The last equality gives
exp (BX 1)
n
E exp (Bus)
And by replacing in the formula of the pi
Vi (1, (1...,,,,
D. - exp (Boi) exp (BA
exp (B0z)
Σブ exp (30,)
Which corresponds exactly to
1 softmax (Bo)
15

---

Under review as a conference paper at ICLR 2020
D.3 PROOF OF LEMMA 4.1
REGULARITY PROPERTIES OF R
For the ease of reading, let us first recall that given a d- (d-Divergence that satisfies assumptions have defined in (
3.1
R: + R
max Σ q:v; gEAn
1 D
(28)
And in 13
G : R 7 R
(29)
p De (pl Ptrain) + وي, (p)
where òA, is the characteristic function of the closed convex set A.. i.e.
O p An
Vp E R" (p)
(30)
+00
otherwise
We prove Lemma 4.1 on the regularity of R.
Lemma D.1 (Regularity of Restated from Lemma and R satisfy
4.1
Let & that satisfies Assumption 3.7
G
np 3 ((C(h(0)), G (C(h(O))
G is
-strongyy convex
(31)
R(C(N(O)) max "EE
(32)
B
R is
gradient Lipschitz continuous.
(33)
np
is p-strongly convex m] so
Vz, y E [0, nJ VA [0, o) (1 - A)v) S + X)o(1) PA(1-
ly xz (34)
2
Letp= (p)) 9 ( An. and x E [0, 1]. using 33 and the convexity of 82., we obtain:
1
G(Ap + (1 - (1-))
2 (nAp: n(1 ()g.) + Ss, (Ap (1 A)q)
3n
< <GG(p) + (1 (1- ()G(()
1
pA(1 - 2)
[1qe -ppi-
mpal?
(35)
3n 1=1
2
n1p X(1 X)
< <G(()) (1- A)G(g)
119 pl1
B
This proves that G is ze stsstrongly convex.
3
Since G convex, R G* is also convex, and R (G')) G Efiriart-Urruy & Lemaréchal 2013).
We obtain (32) using Definition
We now show that is Frechet differentiable on R", Let E R".
G' is strongly-convex, so in particular G' is strictly convex. This implies that the following optimiza- tion problem has unique solution that we denote p(v).
arg max ((v, q) G(g)) 0ER"
(36)
In addition
D A,, solution of 36
0 E OG(p)
* v AG(p)
P E QG*(v) (v)
P E @R(v)
16

---

Under review as a conference paper at ICLR 2020
where we have used (Hiriart- Urruty & Lemaréchal 2013 alence, and (32 for the last equivalence.
Proposition 6.1.2 p.39) for the third equiv-
As result, @R(e) (p(e)). this implies that R admit a gradient at 2, and
R(R(c) = p(v)
(37)
Since this holds for any E RR,, we deduce that is Frechet differentiable on IR".
We are now ready to show that R is B ggrddient Lipchitz continuous by using the following lemma UHiriartUUrutty & Lemaréchal 2013, Theorem 6.1.2 p.280).
Lemma D.2. necessary and sufficient condition for a convex function f R R to be c- strongly convex a convex set C is that for all 21,22 C
(82 81, T2 - r1) 2 c 2|122 21ll? for all 8, (.f(z))) 1,2.
Using this lemma for G //5 and C A.. we obtain:
For all Pr.P2 P2 E An for all 81 E (p(p))) V2 (G((2).
(U2 - -1 - p1) 2 np
3 1| - pi 1
In addition, for {1, 2}. os aG(p:)
+ Pi OR(vi) [(.)(.
And using Cauchy Schwarz inequality
002 vil 1122 - Pill 2 (D2 - U1
p1) -1)
We conclude that
np 3
[(,)) V.R(1 S |100 - -1
Which implies that R is
8 no
gradient Lipchitz continuous.
D.4 PROOF OF LEMMA 4.2
FORMULA OF THE DISTRIBUTIONALLY ROBUST LOSS GRADIENT
We prove Lemma 4.2 that restate here for the ease of reading.
Lemma D.3 (Stochastic Gradient of the Distributionally Robust Loss Restated from Lemma For all 0, we have
p(C(h(0)) V.((((((()))) Vo o h) (0) (((((())) Vo L (1(x;)),))
(38)
(39)
where V. R is the gradient of R with respect to its input.
For given 0, equality 38
special case of (37 for e L(h(0)).
Then using the chain rule and 38
OR
()
(Co ((o)) ())
((CC(h()))Vo(CColl h)))
Ep(C(n(O) (Vo L (1(x: 0).
D.5 PROOF OF THEOREM 4.2 DISTRIBUTIONALLY ROBUST OPTIMIZATION AS PRINCIPLED HARD EXAMPLE MINING
Let D an d-divergence satisfying Assumption 3.1 and v (u;) E R". u will play the role of generic loss vector.
17

---

Under review as a conference paper at ICLR 2020
is strongly convex, and A is closed and convex, the following optimization problem has one and only one solution:
(u,p)
(np,)
(40)
p= ( EA"
Bn
Making the constraints associated with p E An explicit, this can be rewritten
max p= (m)) ER"
(v,
((pp)
Bn
S.L. Vi {I,...,,.). n), pi
(41)
s.t. Pi P=
==1
There exists KKT multipliers À E R and Vi, p4 0 such that the solution p = (p:) satisfies:
Vi {1...., n),
0. ('(p.) + 14
iA E {1..... n,),
P.P: = 0 Pt 2 0
ii (1....,m),
(42)
Σ Pr
Since & continuously differentiable and strongly convex, we have (6')-1 = (o+). where o² is the Fenchel conjugate of é HeriHrraatt-mmen & Lemaréchal 2013 Proposition 6.1.2). As result, can be rewritten has:
Vi E fl,...,,1.. n.),
D. (0') (3(1 + x-
Vi E (l,...,.).
n p&Pt = 0 pt 2 0
Vi (l,...,11) ,
(43)
(0*) (8(1; - ps)) =
t=1
We now show that the KKT multipliers are uniquely defined.
The 24 's are uniquely defined by and A: Since Vi E (1....,n), paP. 0, Pe and μ4 2 for all Vi E {1....,n). n), either ps or H4 0.
In the case p. = 0, using 43
it comes (6+) (B(r + m.) =0
is strongly convex and continuously differentiable, so ø' and (6*)² ( are continuous and strictly increasing functions. result, it exists unique μęi (dependent to and X) such that:
According to assumption 3.1
(0 + A - -)))) =
And 443 can be rewritten as:
pj ReLU 1 (3'))(((1) mD) 1 R ((0*) (8(s: + A)))
Vi E (I...,n),,
(44)
ReLU ((0') (3(m; + X))) =1
n
18

---

Under review as a conference paper at ICLR 2020
À is uniquely defined by and continuous function of
Let E that satisfies
We have Di= ReLU ((o*) (3(e) + A])) = 1. So there exists at least one index in such that
ReLU (10*) (8(0), + x))) = (6*) (8(e), + + 21
Since (6*)-1 continuous and striclty increasing, + ReLU (1Ø*) (3(15o + +X)) is continuous and strictly increasing on neighborhood of X.
In addition ReLU is continuous and increasing, so for all i E n.....,n... X + ReLU (10") (3(us + X))) is a continuous and increasing function.
ReLU ((0*)' (3(u; + X))) is continuous function that is increasing on RR and strictly increasing on neighborhood of
As result, X - E
This implies that À is uniquely defined by c, and that v X(v) is continuous.
Hard Example Mining Sampling:
For any pscudo loss vector (u4) E R2 there exists unique and unique that satisfies so we can define the mapping:
D: Rn A U p(;;
(45)
where for all v, X(v) is the unique À E R satisfying 44
We will now demonstrate that each Pso (v) for ig E fI...., n is an increasing function of e and decreasing function of the u; for * ig. Without loss of generality we assume in
Let (u:) E R", and 0.
Let us define o' = (wD"_1 E R", such that of = 1n + e and E (2,....n). of 04.
Similarly in the proof of the uniqueness of À above, show that there exists 17 0 such that the function
F: X ReLU ((0*) (B(uz + (B(u++X)) +())
continuous and strictly increasing on (A(v) 7, A(v) + 1/J, and F(A(v)) 1.
V + X(v) is continuous, so for small enough A(o') E (X(u) - 7), A(v) + +v]-
Let now prove by contradiction that A(u') S A(r). Therefore, let assume that A(r') > A(v)- Then, as ReLU (ø*) an increasing function and F is strictly increasing (A(u) 77 A(v) n], and > 0 we obtain
ReLU ((0t) (8(1) x(()))
ReLU ((0*) (3(r, X(11)))
F(X('))
F((())
1
which is a contradiction. As a result
X(0') & M())
(46)
19

---

Under review as a conference paper at ICLR 2020
Using 46 . n
and the fact that ReLU (Ø*)' is an increasing function, obtain for all
pa(e')
ReLU ((0)) (f(c(+
71
ReLU ((6') (3(1 + X(1))))
(47)
v ReLU ((0*) (3(1, + (()))))
S Pi(v)
In addition
n
Σ (v(1) = 1= Σ (((
So necessarily
p1(d'22((())
(48)
This holds for any in and any e, which concludes the proof.
D.6 PROOF THAT Ro L IS ONE-SIDED GRADIENT LIPCHITZ
This property that R L is one-sided gradient Lipschitz is key element for the proof of the semi- smoothness theorem for the distributionally robust loss Theorem [.T]]
Under assumption
3.1 we have shown that R gradient Lipchitz continuous. And under as- B.2 for all i, L, is C(C)-Lipschitz continuous and C(V C)-gradient Lipschitz. continuous.
sumption
Let (=))
(=))= Rd
We want to show that Ro L is one-sided gradient Lipschitz, i.e. we want to prove the existence of constant C 0, independent and z', such that:
(V2(Ro (=) V2(Ro f)()),)))))))))))))))))))))))))) x²) s C0|== -=1====11 z'11
We have
()) (. (){)),
V (Ro [)() (Ro 4-20) 2/)
Σ ( - -(())))))) f(=/), =1)
(49)
Σ (c((())) V., ((x)) ((=)),2--2) -0
Σ ( V, ((2))
Where for all i E .I. we have used the chain rule
0R"
V (Ro [)(=) = Σ
(C(z)) G(z)) ( c(xz)
Du;
1=1
Let
A=
Σ
((([())) ((z) Vz, ((=)),===))
20

---

Under review as a conference paper at ICLR 2020
For all i, C, is C(V L) gradieett Lipchitz continuous, so using Schwarz inequality
C(V - =1I² - C(V 1'11²
(50)
2=1
Let
72 ==
Σ - ((2)) 21
Using the triangular inequality:
B <
-x (((=))-(())
Σ (Fx(C(z)) F.(((2)))))))))) (4(2) + &. f(z), = -((x))
(V(R)) V(H)) ((x) ((2))
(51)
+ 2 Σ f(=) + .. f(+)) 23 - =)) - -f(z))
3 [1((2) -(>))1² +2 C(VL)
|| - z11²
np
2
$ BC(C)²
+ +(( ||2 2112
Combining 449
50)
and
51
we finally obtain:
2// (R) (R L)(z), - (SCLC) +2((V 2)) ||= 1==2=1|
(52)
np
From there, we can obtain the following inequality that will be used for the proof of the semi- smoothness property in Theorem D.I]
R(C(=)) R(((=)) (V-(Ro ())2, =)
(V L) (2 - 2)) - -v.RR (2),) - 2)
(53)
1=0
BC(C)² + +2C(V 2)) 2|2 - -
$ 2 np
D.7 PROOF OF THE CONVERGENCE OF ROBUST SGD
In this part, we prove the results of Therem B.I and B.2
They are generalizations of the convergence result for SGD presented in Theorem 2 of (Allen-Zhu al. 2019).
For the ease of reading the proof, we remind here the chain rules for the distributionally robust loss that we are going to use intensively the following proofs.
Chain rule for the derivative of R o L with respect to the network outputs h:
VA ())())) (V (Ro ()(())))
Σ aR j-1 do, (L(h(O))) (()
Vi (1....n), VR ()(()))
(54)
P.((CC())) ((h.(0))
21

---

Under review as a conference paper at ICLR 2020
Chain rule for the derivative of R o oo with respect to the network parameters 0:
(Ro
((C(M)))VV>.(V>> (():(0)) (())))
(55)
Σ (xCCcMO))V((cchh.11 1=1
where for all (1,...n). nn., (0) is the transpose of the Jacobian matrix of h2 function of 0.
D.7.1 SEMI-SMOOTHNESS PROPERTY FOR THE DISTRIBUTIONALLY ROBUST Loss
We prove the following lemma which is generalization of Theorem 4 in (Allen-Zhu et al. 2019) for the distributionally robust loss (
Theorem D.1 SSemi-smoothness of the Distributionally Robust Loss).
Let E s
4/22
log" (m) and the ((0) being initialized randomly as de-
m3/3 1 L3/2 3/235/((m) [mm)
scribed in assumption
B. With probubility as least exp -0mmm3// I.) over the initialization,
we have for all 0, 0' (IR mamx "R)" with ||e 0 11 I w, and 1|0 0' S w
R(C(h(O')) S R(C(M())+++++))))00)()))) (VolRo (oh) 0
L3 mm log(m)
+ ()
1 0112,00
Vd
(56)
+0 ((
(BC(L) + +2C(VE))
100 )
nT d
0 2,00
where for all layer
E fl....,4i L). 0, is the vector of parameters for layer I, and
2,00 = max |00 01112 00
1 0 012,00
110 max
0:113] mmxx 110; 0rll
VR ()((R) 12,1 =
Vn. Roo 2)(h()))l1
(((CCN()))V&<<((h(0))) (chain rule (54))
To compare this semi-smoothness result the one (Allen-Zhu al. 2019 Theorem 4), let us first remark that
V (R ()(( I vn (Ro
As a result, our result is analogous to (Allen-Zhu et al. 2019 Theorem 4). up to an additional multiplicative factor (BC(C)² 2C(V C) the last term the right-hand side. It is worth noting
that there also implicitly an additional multiplicative factor C(V L) in Theorem of (Allen-Zhu et al. 2019) since (Allen-Zhu et al. 2019) make the assumption that C(V L) 1 (see Allen-Zhu
al.
2019 Appendix A).
Let 0, 0' E (Rmxmy² verifying the conditions of Theorem D.1
Let A = R(C(h(O)) R(C(h()) (Vo(Ro Loh) 0' 0) the quantity want bound.
22

---

Under review as a conference paper at ICLR 2020
Using 53 for h(0) and z' = h(6"), obtain
1 [C(L)² +2C(VE) 2)) [I((0") h(0))lz
- 2
np
(57)
(V ()((0),, - h()))
o (O)
Then using the chain rule 55
)C
+ 20((V ()) [1(()') h(0)
A Σ
2
np
(58)
Vn, (R (H((),, (0 (Voh,(0)) (0' -0)
For all i E (1..... n let us denote loss: == RA (R o ())) to match the notations used in (Allen-Zhu et al., 2019) for the derivative of the loss with respect to the output of the network for example of the training set.
With this notation, we obtain exactly equation (11.3) (Allen-Zhu et al. 2019) up to the multiplica- (SC(C)² 2C(V 2)) for the distributionally robust loss.
tive factor
Tap
From there the proof of Theorem (Allen-Zhu et al. 2019) being independent to the formula for loss;, we can conclude the proof of our Theorem D.1 (as in Allen-Zhu et al. 2019 Appendix A).
D.7.2 GRADIENT BOUNDS FOR THE DISTRIBUTIONALLYY ROBUST Loss
We prove the following lemma which is generalization of Theorem 3 in (Allen-Zhu et al. 2019) for the distributionally robust loss (
Theorem D.2 (Gradient Bounds for the Distributionally Robust Loss).
Let w E O
7 log (m)) ) and ( being initialized randomly as described in assump-
83/2
B. With probability as least 1 exp (-D(mw312..) over the initialization, we have for all (I"mmm) with ||e | 2
tion
WE (1. n) vE (1 ..... L), 7L R
p..( (C) 0
m
p.( ((M(01))
d
W (1, (L,...,L}}, L}, 7L R
(59)
0
mm
(.(( f(h,(0))
p. (C) (Cou)
Ω
mo
(..(C)
dn²
is worth noting that the loss vector å used for computing the robust probabilities p(2)) (x((2) does not have to be equal to L(h()))
We will use this for the proof of the Robust SGD with stale loss history.
The adaptation of the proof of Theorem 3 in (Allen-Zhu al. 2019) is straightforward.
Let (R.xm>² satisfying the conditions of Theorem
D.2 and 2 E RR.
23

---

Under review as a conference paper at ICLR 2020
Let us denote v (m,( ()())(1))) applying the proof of Theorem in Allen-Zhuu et al. 2019 to our e gives:
:=1
vi nI), n), 4 (T......,
p [C) (c (0) || So
d [c) ((h,
4 f1. 1) 7A E R
Σ
pe Vo (Coh))
mn
Σ ==1
pi(C)V
((h:(0)))
d
2
((n())))))))))))))
pe ( Σ
max
dn
2
In addition
max (Ib.COVV. ((h,0)))
1
p. ((h,(0))))))
This allows us to conclude the proof of our Theorem
D.2
D.7.3 CONVERGENCE OF ROBUST SGD WITH EXACT Loss HISTORY
We can now prove Theorem B.1
Theorem D.3 (Convergence of Robust SGD with exact Loss History Restated from Theorem B. Suppose batch size S b I n, number of hidden units m 2 (de x poly(n, L, L,8-))), and à O (+.). Let 0, and the learning rate be Mexact with probability at least 1 - exp (-S2(log" (m))) over the randomness of the initialization and the mini-batches, Robust SGD with exact loss vector finds Vo(R f ())l s cafter T = =0 18c2 iterations.
an
böd
(CCC))+2M0C(V 2) x poly(n,L)m log?
Lnd
Similarly to the proof of the convergence of SGD for the mean loss (4) (Theorem 2 in (Allen-Zhu al. 2019),, the convergence of SGD for the distributionally robust loss will mainly rely the semi-smoothhes property (Theorem D.I) and the gradient bound (Theorem D.2) that we have proved previously for the distributionally robust loss.
Let E (Rmmmm>* satisfying the conditions of Theorem B.1 and 2 be the exact loss history at O, i.e.
č= (4(h:(0))"
(60)
imi
For the batch size b E (I,...,m), let S {i,))_ a batch of indices drawn from x(2) without replacement, i.e.
Vj (1,...b). b), ig lid. p(()
(61)
Let 6' E (R be the values of the parameters after stochastic gradient descent step at 0 for the batch S.
0'= 0 " Σ Vo ( oh, (C,)) (0)
(62)
where 77 > 0 is the learning rate.
24

---

Under review as a conference paper at ICLR 2020
Assuming that 0 and 0' satisfies the conditions of Theorem D.1 obtain R(C(h(0') <R(((h(0)) n (o))(()))))((), (o(Con,)
L L/ 1/3
m log(m)
+ nvnn (a ()((())))2 O
Vo
ch:)
vd
b
iES
2,00
+r²0 (( (BC(L)) +2C(V 2) nL²m)
Σ SES
Vo
(o(Coh))())
no
b
2,00
(63)
where we refer (55) for the form of Vo Vo(RoL (o) (h) and to (54) for the form of (Ro
In addition, we make the assumption that for the set of values of considered the hardness weighted sampling probabilities admit upper-bound
min min p; (C(0))
(64)
Which is always satisfied under assumption B.2 for Kullback-Leibler d-divergeenc,, and for any ø-divergence satisfying assumption 3.1
with a robustness parameter small enough.
Let IEs be the expectation with respect to S. Applying Es to (63) we obtain Es (R(C(M(0') <R(C(H(0)) (oORO
nL?w 13 / /mllg(m)
TO Σ
+ ( ()
max
Vd
((8CL0" - 20(V
)
nL'm
+no0
Ve (C)h))
max
np
d
(65)
where we have used the following results:
For any integer k: 2 1, and all (a:) E (R+*)" we have (see the proof in D.7.4
Es b
= E 22) [ai]
(66)
iES
Using (66) for (a:) = (Vo (0)) and the chain rule (55)
Es
Σ Vo(Coh))((
= Vo ((C))o(()h)))))
(o))
(67)
iES
Using the triangular inequality
Vo
vo(Con))0))
(68)
2,00
iES
2,00
iEs
And using
66 for (at)
(IVo(C,
(1)) 1=1'
Es
V (ch,))
(C)
Vo (h))))))())) 2,00
b
ES
2,00
E=1
max
Vo, (p. (2) ( (o)
(69)
Vn
Σ max (F. ( foh
25

---

Under review as a conference paper at ICLR 2020
where we have used Cauchy- Seccha-S inequality for the last inequality.
Using (68) and the convexity of the function I + x²
Vo(C
vo(Con)(0))
(70)
b
8
2,00
iE
2,00
EE
And using (66) for (a;);=1 = (1Vo (h, i=1' _
n
Es
Σ
V Vo(Coh.)00
S
Σ (c)
Vo (f.) vo(fohh)())
SES
2,00
(
(71)
max
(.(C)
1=
1 max Vo, (p,(( ( coli)(o)
Important Remark: is worth noting the apparition of a in 7T.. we were using uniform sampling for ERM (i.e. for DRO in the limit 3 - 0), we would have a = 4. So although our inequality (7I) may seem brutal, it is consistent with equation (13.2) in (Allen-Zhu et al. 2019) and
the corresponding inequality in the case of ERM.
The rest of the proof of convergence will consist in proving that v V o L Lhh (0) dominates the two last terms in (63). As result, we can already state that either the robustness parameter 3, or the learning rate will have to be small enough to control a. This is consistent with what we observed in our experiments.
Indeed, combining (63)
with the chain rule (5), and the gradient bound Theorem D.2 where we use
our 2 defined in (60)
mmm
Es [R(C(H(O') S R(C(H(O)) - Ω
dn
nL2 /3
m log(m)
+ 0n
Vd
((SCLC) + 22((V
mL3m
+ +1²0
np
d
< R(C(((O)) -
ymd dn
(p(c)V ((h:(0))1
+0 m 2/3 Iog(m)
17 (m//a)))2
K
d2
2
(72)
where we have used
K SC(C)2 +2C(V L)
(73)
np
There are only two differences with equation (13.2) in Allen-Zhu et al. 2019):
in the last fraction have n/a instead of n² (see remark D.7.3 for more details), and an additional multiplicative term K. So in total, this term differs by a multiplicative factor an from the analogous term in the proof of (Allen-Zhu et al. 2019).
we have Em (C)V) (0) instead of ((W()). In fact they are analogous since in equation (13.2) in (Allen-Zhe Ahhu al. 2019). F(W(S) is the squared norm of the
26

---

Under review as a conference paper at ICLR 2020
mean loss for the L loss. We don't make such strong assumption the choice of C (see assumption (..2). . It is worth noting that the same analogy is used in (Allen-Zhut et al. 2019 Appendix A) where they extend their result to the mean loss with other objective function than the 1,2 loss.
Our choice of learning rate in Theorem B.2 can be rewritten as
an²p
böd
Tezact
θ
BC(L)) + 2npC(V 2)
X
poly(n, L)m log log)(m)
θ
on
x
bdd
(74)
K
poly(n, L)m log (m)
an K
n
And we also have
Mezaet S n/'
(75)
where v/ is the learning rate chosen in the proof of Theorem 2 in (Allen-Zhu et al. 2019). We refer the reader to (Allen-Zhu et al. (219)) for the details the constant in "O" and the exact form of the polynom poly(n, L).
As result, for 7) Teract, the term Ω
mmn drz
dominates the other term of the right-hand side of
inequality (72) as in the proof of Theorem in (Alenn-Zhu et al. 2019).
This implies that the conditions of Theorem D.2 are satisfied for all g(t) and that we have for all iteration > 0
Es. B(C(h(B((+))) & R(C(h((()) Ω
1mmo dn
p, ((h,
(76)
And using result in Appendix A of (Allen-Zhu et al. 2019). since under assumption B.2 the distributionally robust loss non-convex and bounded, we obtain for all
se' if T= 0 dn
VA(Ro (
(77)
22
njme!
where according to
54
(R ()(((()))
Σ (C) ((h;(0
(78)
However, we are interested in bound on (ol(Rooo))(00 rather than (R ()((((() 2.2'
Using the gradient bound of Theorem Vo
D.2 and the chain rules 55 and 54
Lmn
S Sci
Vn ()((0)))
(79)
2,2
2,2
(V L/maa
where e₁ > 0 is the constant hidden in O
So with c Limn E e, we finally obtain
Lmn
Va(Ro ((((0(T))
S
c11
2,2
d
2,2
Lmn
(80)
$ c1
5
If
T=
dn
=0
(dn²
dn²
Lmn
o T.m
(81)
njme
nóm de?
17622
which concludes the proof.
27

---

Under review as a conference paper at ICLR 2020
D.7.4 PROOF OF TECHNICAL LEMMA 1
For any integer k 2 1, and all (a=) E (IR*)", we have
n Pie (2)
Es
b
a
Σ
b ==1
dis
iES
b
Σ gm1
Psy (2) ai,
II
Pie (2)
b
1S Sn
Pig (2) dis
II Pie (2)
1sti Sn
(82)
n
Y2
Pig (C) oz,
II
Pio (23)
b
8==1
Σ Pi(C)ai
b
(C)
B P(2) [a.]
D.8 CONVERGENCE OF ROBUST SGD WITH STALE LOSS HISTORY
The proof of the convergence of Algorithm under the conditions of Theorem B.2 follows the same structure as the proof of the convergence of Robust SGD with exact loss history D.7.3 We will reuse the intermediate results D.7.3 when possible and focus on the differences between the two proofs due to the inexactness of the loss history.
Let an iteration number so that the warm-up of Algorithm 4.T is already over at f.
Let (1)) E (IR
/ the parameters of the deep neural network at iteration t.
We define the stale loss history iteration as
È (((h((o)))))))
(83)
t=1
where for all i, (.(1) < l corresponds to the latest iteration before I which the loss for example i has been updated. Or equivalently, it corresponds to the last iteration before when example i was drawn be part of mini-batch.
Thanks to the warm-up stage of Algorithm 4.1 it is guaranteed that the loss value of every example has been computed at least once before start using the adaptive sampling. As result, for all iteration after the warm-up. the stale loss history 2 is well defined.
We also define the exact loss history that is unknown in Algorithm 4.1 as
= (c(h:(0")))
(84)
Remark on the warm-up stage of Algorithm 4.1:
The iterations performed during the warm-up stage amounts to classic SGD to minimize the mean loss (4). As result, the convergence results of (Allen-Zhu et al. 2019 Theorem 2) apply during the warm-up. This guarantees that the condition on of Theorem B.2 remains satisfied during the warm-up if it was satisfied by the initial parameters.
28

---

Under review as a conference paper at ICLR 2020
Similarly
62 define
( = 0(0)
T
vol[oh,)
(85)
iES
and using Theorem D.I. similarly to 63 we obtain
((C((()))) =((((((()) ( " Vooo
Σ
EE
L/
m log(m)
+ (n (1(((0)))
V V (c(Co))
Vd
LES
2,00
+ +1o0 (( (8CCLCP
nL3m) d
+ 20(V2))
Vo Vo(C oli))
np
2,00
(86)
We still define in 64
min min pi(((0)) > 0
(87)
where we guaranteed that 0 under assumptions B.1
Since Theorem D.2
independent to the choice of É, taking the expectation with respect to S,
similarly to 722. we obtain
a Σ
Es [((CC(((((D)) < (CCC(loe))-W/o(ooooooooo
L/ /nmloggm
+ (R (a(Ro ()M((1))
Σ
P.(C)V C(h(0())
1,2
vd
+ +
((80L0) np
nI²m 22(V22)
0
m
V. ((())) 1
d
da
(88)
where the differences with respect to here, i.e. C + Σ. which leads to
72 comes from the fact that not the exact loss history
Vo (o)) =
p. (c) (C())((C
(89)
p. ((C))o((chh)(01))
And
n
(R ()((0()))
A(()VV ((N:(0
1.2
(90)
(c(C) ((h,((())))
Let
Lm 3/2 log2 (m)
K' = =())AVCC
(91)
1/ pd3/ blg
Where C(C) > a constant such that C is Cipsshipstitzz continuous, and A(V L) constant that bound the gradient of L with respect to its input.
> 0 is
29

---

Under review as a conference paper at ICLR 2020
C(C) and A(V C) are guaranteed to exist under assumptions B.1
We prove that, with probability at least - exp (-S2 (log((m))
according to lemma D.8.1
(0() ((C))-(12)
( -(2)
- Σ (Di(0) - -i(3)) S nark'
n
(92)
according to lemma D.8.2
Vo(RooLh))(l
Pi of Σ pi of
(93)
S K' n
o(h))o((chh)))0))))
according to lemma D.8.3
VA(RO ((((0())
3 (vn++
(94)
Combining those three inequalities with 88 we obtain
Es [
R(C(h((())))
md
nL mL2m /lo(mm)
pc(C) ((1(00))) |
"
-
dn
+
d
(n/a) L2
12
K
(1 d
K"
Vc ((A1(011))1
d²
(95)
One that compared to 722 Using our choice of 17.
there is only the additional term (1+ 7 K'.
1]stale I <0
n2
Mexact
(96)
where Nexact is the learning rate of Theorem B.I
we have
Ω
mmo dn
2 20
0
1p (1 + 171
K3)
(97)
As result, 7/2 (1+ 77) K' is dominated by the term ?
gmd dn
In addition, since Nstale S Mexacts
Q
ymmd dn
still dominates also the ther terms as in the proof of
Theorem B.1
As consequence, we obtain as in 776) that for any iteration
(after the end of the warm-up)
Es, [((C(C((((+)) < R(C()(())
Ω
m
Σ
a
[,) ((h,
(98)
dn
This concludes the proof using the same arguments as the end of the proof of Theorem B. from (76).
starting
30

---

Under review as a conference paper at ICLR 2020
D.8.1
PROOF OF TECHNICAL LEMMA 2
Using Lemma 4.2 and Lemma
we obtain
((()) - 0(2)
-|Vod((2) v.1l(2)1
(99)
2 2|]
np
Using assumptions B.2 and Allen-Zhhu et al.
2019
Claim 11.2)
((()) p(0)1|
B
Co (((0))) f h ((((:())))
np
B C(C)C(h)
Σ (1e(t) ((+((t)) 2.2
(100)
np
BLmm
CC(C)
Σ ||(00) 0(1,(0))
n2di/2
Where C(C) is the constant of Lipschitz continuity of the per-example loss (see assumptions B.2 and C(h) is the constant of Lipschitz continuity of the deep neural network h with respect to its parameters 0.
By developing the recurrence formula of g(() 85
obtain
(0(2) -(2) s s(())
(8Tml/2
0(.(0))
41 Σ
D Σ VolLoh))((n))
(()(())
n2dd1/2
b
r=t(())
JES,
2.2
[Tam2/2
S nC(CO
Σ
volLo (0()))
npd
T=)
jES,
2,2
Let A(V L) bound on the gradient of the per-example loss function. Using Theorem D.2 and the chain rule
Vj. VT
m AA(V
(
(101)
2,2
And using the triangular inequality
Σ
velCo ()(()()))
())())))))
b
(=t(() JES.
2.2
T=1(())
JES,
2,2
(102)
m A(V (m)
T=M())
$ A(V 0) (m)
m
(t (t-14 (4)1) (t-))())
As result, we obtain
[LLm3/2
((10)-0(2)) < ,C(())(( C)O
Σ
(())2²
(103)
mpd3/22
For all and for any the probability that the sample not in batch S, is lesser than at).
31

---

Under review as a conference paper at ICLR 2020
Therefore, for any and for any
P (())) k) (1 a)
(104)
For 2 1.02
log²
we have (1 a)*h 1 exp (-S2 (log" (m))). and thus with probability at
log T=
least 1 - exp (-S2 S2 (log (m))),
log l
vt, t-t(t)
(105)
blog I-a
As result, we finally obtain that with probability at least 1 - -xp (-S2 (log" (m)));
[LLm8/2
log (m)
|[C) - -12)
SCCCC)A(VD)) CJ0
Vno
mpd3/2
blog
I-aa
(106)
3Lm 3/2 log" (m)
an 222 log 1-a
1
S naKK
D.8.2 PROOF TECHNICAL LEMMA 3
Let us first denote
Vo - - [2(()V((C)h))00)) [a,C)o((chhh000))
A
(107)
-p())) Vo((ohi)((())) Σ [D(C)vo(Coh))00111)
Using Cauchy-Schward Schwarz inequality
A
Σ (.((C) -b(()) Vo((oh.)(0(11))
Σ
py Vc
(108)
< 10(2) - 1100111
Σ (o((oo))(0))
Σ
p. Vo (o),
Let
B = (Vo(Coh))(
py (,(2) Vo(())o((c
(109)
Using again Cauchy-Schward inequality
< Vo Vo(Cohi)(((t1))
Σ py (C)
(110)
2.2
2,2
32

---

Under review as a conference paper at ICLR 2020
As result, A becomes
As p(2) $12)
Σ
pg (2)Voo (())))((())))000
Vo (o((oh))(01)))
2.2
1=1
i=
< =10(0) p(2111
Σ py ((())o((ch)))000))
n Σ a²
(c(h)o(((h))))11))
2
2,2
$ 1 010) p10111
Σ py Ve(C)o
2,2
(111)
Using the triangular inequality, Theorem D.2 and Lemma D.8.1
we finally obtain
m A - ad p(() =((2 || Σ
py
pf(C)
((h,
2,2
(112)
< m K" Σ
Py(C)Vn, ((n,(010))
d
2,2
D.8.3 PROOF OF TECHNICAL LEMMA 4
We have
Vn ()((((())
Σ pE) -Bp(())
Wn, ((h (0()))
5=1
2.2
Σ (c)
Vny ((h)(0(0))
(113)
2.2
+ Σ
pz(()) - -P,(C)
p,(C)
Vn, 3
((h)(
P2(CC
j=1
2.2
Using Schwarz inequality
p2(()= (x(2)-p((0)
1
2
((((O
S
Vn+
Σ
py(C)V (0,(000))
1,2
1C(
2,2
(114)
Using Lemma D.8.I
2
p,(2) - -P,(0) (C(
1 _ [00) M12011
(115)
I nk
Therefore, we finally obtain
S +vv++ nK²)
Σ
(C(C) ((h)(0
(116)
2,2
33


Reviews:
[{"review_id": "Hkx76YqLqr", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a method for Distributionally Robust Optimization (DRO). DRO has recently been proposed (Namkoong and Duchi 2016 and others) as a robust learning framework compared to Empirical Risk Minimization (ERM).  My analysis of this work in short is that the problem that this paper addresses is interesting and not yet solved. This paper proposes a simple and efficient method for DRO. However, convergence guarantees are weak which is reflected in their weak experimental results. And for a 10-page paper, the writing has to improve quite a lot.\n\nSummary of contributions:\nThe phi-divergence variation of DRO introduces a min-max objective that minimizes a maximally reweighted empirical risk. The main contribution of this work is as follows:\n- Show that for two common phi-divergences (KL-divergence and Pearson-chi2 divergence), the inner maximization has a simple solution for the weights that depends on the value of the loss on the training set.\n- Use the above algorithm and modify SGD by changing the sampling of data according to the weights.\n- Convergence proofs for the above algorithm for wide networks (not necessarily infinite-width).\n\n\nCons:\n- Fig 1, ERM should not be so bad as if predicting randomly. This suggests a problem in the experimental setting. At least more ablation study is needed, e.g. try varying the percentage of data kept and show the final test accuracy as a function of this percentage for ERM. In the worst case, the accuracy for ERM should be ~90% on 9 classes and zero on 10th which is ~80% for uniform test accuracy. Another point, what is the train accuracy on cats? ERM should be overfitting to those few cats in the training set and achieve some non-zero accuracy at test. But it seems the test accuracy is almost exactly 0 at test time.\n- In Theorem 5.1 that provides convergence proofs, the learning rate eta_exact has a dependence on 1/beta, which means much smaller learning rates should be used for the proposed method. However, in the experiments it seems that the same learning rate is used for all methods. This seems to trouble the convergence very clearly as the curves start to fluctuate considerably by increasing for larger betas. There is no bounds on beta which in practice can force us to use orders of magnitude smaller learning rates.\n- Section 4.3 aims at linking hard negative mining to the proposed method. What they actually do is propose a new definition for hard-negative mining which is satisfied by the proposed method. There is little basis for suggesting this definition. There are myriads of work on hard-negative mining and suggesting a new definition needs a more thorough study of related works.\n- Section A.1.1 argues we would stop ERM when it plateaus, but it doesn't look like it has plateaued in fig 2 left.\n- Section A.3, I'm not sure lr=1 would be stable wide resnet. Maybe there is a problem with the experimental setting.\n- There is such much non-crucial details in the main body that increased the main text to 10 pages. At least 2 pages could be saved by moving details of theorems and convergence results to the appendix.\n\nAfter rebuttal:\nI'm keeping more score. The manuscript has been improved quite a lot.  My main concern remains the experiments. Both texts and mathematical statements still need more edits.\n\nThe authors have completely removed experiments on cifar10. Paper now has only one set of experiments on MNIST with little ablation study. I still think my suggested ablation study is interesting. As a minimal sanity check, I'd like to see the performance of DRO on the original MNIST dataset. Basically, how much do we lose by using a robust method on a balanced dataset? Even with full ablation studies, I don't think MNIST is not enough for testing methods based on hard-negative mining.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HklDPH9QsS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Disclaimer: I was able to read the other reviews and the author’s responses before finalizing this review.\n\nThe paper proposes an easy-to-implement algorithm for DRO on example weights, with the same computational cost as SGD.  The algorithm is based on hardness weighted sampling and links are shown to hard example mining.  Convergence results are shown for (finitely) wide networks.  Additionally, the paper claims to demonstrate the usefulness of the algorithm in deep learning.\n\nI am unable to assess how the convergence results place in the literature, but I believe they motivate the algorithm.  The claims of practical usefulness in deep learning do not seem supported by the provided empirical evidence.\nFor the CIFAR experiments, the ERM baseline does not seem to train - probably due to the choice of learning rate.  This makes it unclear how the proposed algorithm compares.  They claim the algorithm is more robust to the learning rate, so is it possible to train with the original learning rate used for the ERM baseline?  Why was a different learning rate chosen?\n\nIf the experimental results showed an improvement over a properly trained ERM baseline on CIFAR I would lean toward weak accept.\n\nMany state-of-the-art deep learning pipelines do not use plain SGD - for example, the WideResNet you used on CIFAR. How is Algorithm 1 used on these? Do we only make changes to the update on line 24?  Using momentum with nested optimization can introduce instabilities. Perhaps combining momentum with nested optimization of loss weights and parameters is why the baseline does not train?  Maybe you could try an architecture that trained using vanilla SGD, so you can better leverage your theoretical results?\n\nIt would provide evidence of the usefulness of the algorithm if we could take various pipelines and just drop their optimizer updates into algorithm 1 - hopefully without having to spend time re-tuning their optimizer parameters. It would also be nice to see the training loss/accuracy - perhaps over all classes and just cats - in the appendix.\n\n\nThings to improve that did not impact the score:\n\n(Page 1) “in term” -> “in terms”\n(Page 1 & 2) “an history” -> “a history”\n(Page 2) “Optmization” -> “Optimization”\n(Page 5) “allows to link” -> “allows us to link”\n(Page 7) “we focus at” -> “we focus on”\n(Page 8) “allows to guarantee” -> “allows us to guarantee”\n(Page 19) “continous” -> “continuous", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BklCcLSacS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the Distributionally Robust Optimization (DRO), in the sense that the weights assigned to the training data can change, but the training data itself remains unchanged. They demonstrate that SGD with hardness weighted sampling is a principled and efficient optimization method for DRO in machine learning and is particularly suited in the context of deep learning. On the theoretical side, they prove the convergence of our DRO algorithm for over-parameterized\ndeep learning networks with ReLU activation and finite number of layers and parameters.\n\nThe DRO problem studied in this paper is relatively easy, in the sense that the inner maximization has close form solution (at least for KL divergence). Therefore, the proposed method is straightforward. All the derivations in Section 3 and 4 are strainghtforward and sensible. I do not know any paper that has proposed Algorithm 1 (or something similar) before, but I will be surprised there is not. I do not check the derivations in Section 5, but I suppose that it is a small modification of the proof in Allen-Zhu et al., 2019. I suppose that the theorem is correct, but it provides nearly no practical guidance.\n\nIn Algorithm 1 Line 18-19, the algorithm proposes to do sampling with replacement using the softmax probability \\hat{p}. How about directly multipling the weights \\hat{p} to the current minibatch of samples. (i.e., re-weighting the samples instead of re-sampling the samples). What's the difference between these two choices?\n\nSecond, both experiments are not convincing enough. In the CIFAR10 experiment (Figure 1), the baseline method ERM is too low. I guess that this low number is due to the large initial learning rate 1. The authors should provide the best performance IRM can achieve, and compare with the best performance DRO can achieve. Although the authors are claiming that the proposed DRO works with larger learning rate, Figure 1 (Left) simply gives readers the wrong information that ERM does not work. \"Figure 2 suggests that if we train ERM long enough it will converge to the same accuracy as DRO.\" The objectives of ERM and DRO are different. Their accuracy may become closer to each other, but I'm not sure they will finally achieve the same accuracy (the same optimum). Can the authors elaborate on this?\n\nFinally, the focal loss has achieved good empirical results in object detection. I feel that it can be formulated as a special case of the Equation (2) and Algorithm 1, by picking up some proper \\phi-divergence and using the (un-normalized) re-weighting scheme. It will good if the authors can provide a principled view of focal loss through the lens of DRO. \n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a modification of SGD to do distributionally-robust optimization of deep networks.  The main idea is sensible enough, however, the inadequate handling of baselines and relatively toy nature of the experiments means that this paper needs more work to be accepted.
Decision: Reject