Coresets for Accelerating Incremental Gradient Methods
Authors: Baharan Mirzasoleiman
Jeff Bilmes
Jure Leskovec
Venue:  (2020)

Abstract: Many machine learning problems reduce to the problem of minimizing an expected risk. Incremental gradient (IG) methods, such as stochastic gradient descent and its variants, have been successfully used to train the largest of machine learning models.  IG methods, however, are in general slow to converge and sensitive to stepsize choices. Therefore, much work has focused on speeding them up by reducing the variance of the estimated gradient or choosing better stepsizes. An alternative strategy would be to select a carefully chosen subset of training data, train only on that subset, and hence speed up optimization. However, it remains an open question how to achieve this, both theoretically as well as practically, while not compromising on the quality of the final model.  Here we develop CRAIG, a method for selecting a weighted subset (or coreset) of training data in order to speed up IG methods. We prove that by greedily selecting a subset S of training data that minimizes the upper-bound on the estimation error of the full gradient, running IG on this subset will converge to the (near)optimal solution in the same number of epochs as running IG on the full data. But because at each epoch the gradients are computed only on the subset S, we obtain a speedup that is inversely proportional to the size of S. Our subset selection algorithm is fully general and can be applied to most IG methods. We further demonstrate practical effectiveness of our algorithm, CRAIG, through an extensive set of experiments on several applications, including logistic regression and deep neural networks. Experiments show that CRAIG, while achieving practically the same loss, speeds up IG methods by up to 10x for convex and 3x for non-convex (deep learning) problems.

Under review as a conference paper at ICLR 2020
CORESETS FOR ACCELERATING INCREMENTAL GRADIENT METHODS
Anonymous authors
Paper under double-blind review
ABSTRACT
Many machine learning problems reduce to the problem of minimizing an expected risk. Incremental gradient (IG) methods, such as stochastic gradient descent and its variants, have been successfully used to train the largest of machine learning models. IG methods, however, are in general slow to converge and sensitive stepsize choices. Therefore, much work has focused on speeding them up by reducing the variance of the estimated gradient or choosing better stepsizes. An alternative strategy would be to select carefully chosen subset of training data, train only on that subset, and hence speed up optimization. However, it remains an open question how to achieve this, both theoretically well as practically, while not compromising on the quality of the final model. Here we develop CRAIG, method for selecting a weighted subset (or coreset) of training data in order speed up IG methods. We prove that by greedily selecting a subset S of training data that minimizes the upper-bound on the estimation error of the full gradient, running IG on this subset will converge to the (near)optima) solution in the same number of epochs as running IG on the full data. But because at each epoch the gradients are computed only on the subset S, we obtain a speedup that is inversely proportional to the size of S. Our subset selection algorithm is fully general and can be applied to most IG methods. We further demonstrate practical effectiveness of our algorithm, CRAIG, through an extensive set of experiments on several applications, including logistic regression and deep neural networks. Experiments show that CRAIG, while achieving practically the same loss, speeds up IG methods by up 10x for convex and 3x for non-convex (deep learning) problems.
INTRODUCTION
Mathematical optimization lies at the core of training large-scale machine learning systems, and now widely used over massive data sets with great practical success, assuming sufficient data resources are available. Achieving this success, however, also requires large amounts of (often GPU) computing, as well as concomitant financial expenditures and energy usage (Strubell al., 2019).
Significantly decreasing these costs without decreasing the learnt system's 's resulting accuracy is one of the grand challenges of machine learning and artificial intelligence today (Asi & Duchi 2019).
Training machine learning models often reduces to the problem of optimizing a regularized empirical risk function. Given a convex loss and j-strongly convex regularizer r, one aims to find model parameter vector over the parameter space X' that minimizes the loss f over the training data V:
F. E argmin f(x), f(x) = Σ f(() + +r(x), fi()) = =1(x, (a), BEX
(1)
.VV
where V = (1,... n) an index set of the training data, and functions fi : Rd. -> are associated with training examples (a,, v1), where E Rd is the feature vector, and yı is the point i's label.
The standard Gradient Descent can find the minimizer of this problem, but requires repeated com- putations of the full gradient V fzx) of the gradients over all training data points/functions and is therefore prohibitive for massive data sets. This issue is further exacerbated in case of deep neural networks where gradient computations (backpropagation) are expensive. Incremental Gradient (IG) methods, such as Stochastic Gradient Descent and its accelerated variants, including SGD with momentum QQin 1999), Adagrad (Duchi et al. 201T), Adam (Kingma & Ba 2014).

---

Under review as a conference paper at ICLR 2020
iteratively estimate the gradient on random subsets/batches of training data. While this provides an unbiased estimate of the full
SAGA (Defazio et al. 2 and SVRG (Johnson & Zhang 2013)
gradient, the randomized batches introduce variance in the gradient estimate (Hofmamn et al. 2013
and therefore stochastic gradient methods are in general slow to converge (Johnson & ZZhag 2013
Defazio al. 2014). The majority of the work speeding up IG methods has thus primarily focused
on reducing the variance of the gradient estimate (SAGA (Defazio et al., (0144), SVRG (Johnson & Zhang 2 Katysha (Allen-Zhu 2017)) or more carefully selecting the gradient stepsize (Adagrad
Duchi et al. 2011), Adadelta (Zeiler 2012), Adam (Kingma & Ba 2014)).
However, the direction that remains largely unexplored is how to carefully select a small subset S SCV of the full training data V, so that the model can only be trained on the subset S while still (approximately) converging to the globally optimal solution (i.e., the model parameters that would be obtained if training/optimizing on the full V). If such a subset S can be quickly found, then this would directly lead to a speedup of [V|/|S| (which can be very large if |S| < (V) per epoch of IG.
There are four main challenges in finding such subset S. First is that a guiding principle to select unclear. For example, selecting training points close to the decision boundary might allow the model to fine tune the decision boundary, while picking the most diverse set of data points would allow the model to get a better sense of the training data distribution. Second is that finding S must be fast otherwise identifying the set S may take longer than the actual optimization, and so no overall speed-up would be achieved. Third is that finding a subset S is not enough. One also has to decide on an ordering over S and gradient stepsize for each data point in S, they affect the convergence. And last, while the method might work well empirically on some data sets, one also requires theoretical understanding and mathematical convergence guarantees.
Here we develop CoResets for Accelerating Incremental Gradient descent (CRAIG), for selecting a subset of training data points to speed up training of large machine learning models. Our key idea is to directly approximate the gradient. That is, we aim to find a weighted and ordered subset S of training data V that is representative of the full gradient of V. We prove that the subset S that minimizes an upper-bound bound on the error of estimating the full gradient of V maximizes submodular facility location function. As a result, the subset S can be efficiently found using fast greedy algorithm. A further benefit of our approach is that set S is created incrementally which induces natural ordering over data in S. Thus, rather than processing data points in a random or arbitrary order, CRAIG processes them using in the order provided by the procedure, which we show further speeds up the convergence of the method.
We also provide theoretical analysis of CRAIG and prove the convergence of our approach. In particular, for a ju-strongly convex risk function and a subset 5 selected by CRAIG that estimates the full gradient by an error of at most c, we prove that IG method with diminishing stepsize ag a/k" at epoch &o (with < T < and 0- < a),, converges to an 2Rc/ Ps neighborhood of the optimal solution at rate (LI/Vk). Here, R = min (do. (r7maax + p)/p} where du is the initial distance to the optimum. C' an upper-bound on the norm of the gradients, r |S), and Tmax is the largest weight for the elements in the subset obtained by CRAIG. Moreover, we prove that if in addition to the strong convexity, component functions have smooth gradients, IG with the same diminishing stepsize on subset S converges to a 2 neighborhood of the optimum solution at rate ((1/kT).
The above convergence rates are the same as convergence rate of IG on V for a strongly convex risk (and smooth component functions), and therefore IG on S converges in the same number epochs as IG on the full V. But because every epoch only uses a subset S of the data, it requires fewer gradient computations and thus leads to a |V//|S| speedup over traditional IG methods, while still (approximately) converging to the optimal solution. Furthermore, CRAIG only requires the knowledge of estimated gradient differences and does not involve any (exact) gradient calculations. Therefore, CRAIG can be used as a simple preprocessing step before IG starts and no additional storage or gradient calculations are required during IG, which makes CRAIG extremely practical. As such CRAIG can be used to speed up any existing IG methods, including IG, Adam, SAGA, SVRG as we show in the experiments section.
We demonstrate the effectiveness of CRAIG via an extensive set of experiments using logistic regres- sion (a convex optimization problem) as well as training neural networks (non-convex optimization problems). We show that CR ARAGG IG speeds up incremental gradient methods, including SGD, SAGA, SVRG, Adam, Adagrad, and NAG. In particular, CRAIG while achieving practically the same loss
2

---

Under review as a conference paper at ICLR 2020
and accuracy as the underlying incremental gradient descent methods, speeds up gradient methods by up to 10x for convex and 3x for non-convex loss functions. We also demonstrate that the deliberate ordering scheme of the CRAIG algorithm significantly improves convergence time.
2 RELATED WORK
Convergence of IG methods has been long studied under various conditions (Zhi-Quan & Paul 1994
Mangasariany & Solodovy 1994 Bertsekas 1996; Solodov] 1998; [seng 1998), however IG's convergence rate has been characterized only more recently (see (Bertsekas) 2015) for survey). In particular, Nedić & Bertsekas 2001 provides a OL1/ k) convergence rate for diminishing stepsizes aj per epoch & under a strong convexity assumption, and Gürbüzzalaban al. (2015)
proves (11/k") convergence rate with diminishing stepsizes ag ((1/k") for E (0, under
an additional smoothness assumption for the components. While these works provide convergence on the full dataset, our analysis provides the same convergence rates subsets obtained by CRAIG.
has been empirically observed that ordering of data significantly affects the convergence rate of IG. However, finding favorable ordering for IG has been long standing open question. Among the few results are that of (Recht& & Re 2012) showing that wippout-replacement random sampling improves convergence of IG for least means squares problem, and the very recent result of (Gurbuzbalabur et al., 2017) showing that a Random Reshuffling (RR) method with iterate averaging and a diminishing stepsize (11/k²) for E (1/2,1) converges at rate (1/k2²T) with probability one in the suboptimality of the objective value, thus improving upon the S2 (1/k) rate of SGD. Contrary to the above randomized analysis, we propose the first deterministic ordering on the data points and empirically show that the ordering provided by CRAIG provides significant speedup for the convergence of IG.
Techniques for speeding up SGD, are mostly focused on variance reduction techniques (Roux et al. 2012; Shalev-Shwartz & Zhang 2013 3. Johnson & Zhang 2013 Hofmann et al. 2015 Allen-Zhu
al.
2016), and accelerated gradient methods when the regularization parameter is small (Frostig
et al.
2015 Lin et al. 2015 Xiao & Zhang, 2014). Very recently, HHffmnn et al. (2015); Allen-Zhu
(2016) exploited neighborhood structure further reduce the variance of stochastic gradient descent and improve its running time. Our CRAIG method and analysis are complementary to variance reduction and accelerated methods. CRAIG can be applied to these methods as well to speed them up (as we show in experiments).
al.
3 CORESETS FOR INCREMENTAL GRADIENT DESCENT (CRAIG)
We proceed as follows: First, we define an objective function L for selecting an optimal set S of size r that best approximates the gradient of the full training dataset V of size n. Then, show that L can be turned into a submodular function and thus S can be efficiently found using a greedy algorithm. Crucially, also show that the approximation eтrоr between the estimated and the true gradient can be efficiently minimized in a way that is independent of the actual optimization procedure and thus CRAIG can simply be used as preprocessing step before the actual optimization starts.
Incremental gradient methods aim at estimating the full gradient Eiev f((x)) over V by iteratively making a step based on the gradient of every function ft. Our key idea in CRAIG is that if we can find a small subset S such that the weighted sum of the gradients of its elements closely approximates the full gradient over V. we can apply IG only to the set S (with stepsizes equal to the weight of the elements in S), and we should still converge to the (approximately) optimal solution, but much faster.
Specifically, our goal in CRAIG is to find the smallest subset S V and corresponding per- per-element stepsizes 7j > 0 that approximate the full gradient with an error at most 0 for all the possible values of the optimization parameters E x
S" argmin [S], s.t. max SC SCV,,,20
Σ Vf(x)
Envt JES
FEA
TEV
Given such an S and associated weights {n}j, we are guaranteed that gradient updates on S* will be similar to the gradient updates on V regardless of the value of x.
Note that in the worst case may need |S*| s V to approximate the gradient. However, we show in experiments, in practice find that small subset is sufficient accurately approximate the gradient.
3

---

Under review as a conference paper at ICLR 2020
Unfortunately, directly solving the above optimization problem is not feasible, due two problems. Problem 1: Eq. (2) requires us to calculate the gradient of all the functions fi over the entire space X. which is too expensive and would not lead to overall speedup. In other words, it would appear that solving for 5* is as difficult as solving problem (1. as involves calculating Σiev V f(())) for various X. And Problem 2: even if calculating the normed difference between the gradients in
Eq. (2) would be fast, as we discuss later finding the optimal subset S in NP-hard. In the following, we address the above two challenges and discuss how we can quickly find a near-optimal subset S.
3.1 UPPER-BOUND ON THE ESTIMATION ERROR
We first address Problem 1, i.c., how to quickly estimate the crror/discrepancy of the weighted sum of gradients of functions f, associate with data points j E S, vs the full gradient, for every X.
Let S be a subset of r data points. Furthermore, assume that there is mapping
V + S that for every x E X' assigns every data point E to one of the elements j in S, i.e.. S2 (1) =
Let
Cj {i E [n]]s(t)) = j} S V be the set of data points that are assigned to E S, and N3 |Cj] be the number of such data points. Hence, {Czli=ı form a partition of V. Then, for any arbitrary (single) x E X' we can write
Σ ff(z))
= Σ (V.((z)) - - (x)())()) + (fe(o(()))
(3)
KEV
EV
= (V.((t) Vfc()()))) + En
(4)
EV
jES
Subtracting and then taking the norm of the both sides, we get an upper bound on the error of estimating the full gradient with the weighted sum the gradients of the functions fy forj e S. Le.,
Σ f((x))
Ei S Σ [Vff(()) - (1)
(5)
iEV
where the inequality follows from the triangle inequality. The upper-bound in Eq. ( minimized when &a assigns every E V to an element in S with most gradient similarity at or minimum Euclidean distance between the gradient vectors at x. That is: (i) E argmin V f. (z)] Hence,
min SCV
Σ v.(())
Σ Vxf(()) S Emin min [V)(()) Vzf())]
(6)
JES
SEV
JES
iEV
The right hand side of Eq. (6) is minimized when is the set of r medoids (exemplars) for all the components in the gradient space. So far, considered upper-bounding the gradient estimation error at a particular x E X. To bound the estimation error for all x E X, we consider a worst-case approximation of the estimation error over the entire parameter space X. Formally, we define distance metric dı between gradients of f; and fj as the maximum normed difference between (x) and (z)) over all X::
dij
A max [f(()) (z)())].
(7)
ZEX
Thus, by solving the following minimization problem, obtain the smallest weighted subset S* that approximates the full gradient by an error of at most e for all x E x:!
S argmin [S], such that L(S)= Σ min di Sc. SCV
JES
iEV
Note that Eq. requires that the gradient error is bounded over However, we show (Appendix B) for several classes of convex problems, including linear regression, ridge regression, logistic regression, and regularized support vector machines (SVMs). the normed gradient difference between data points can be efficiently boundedly approximated by (Allen-Zhu et al. 2016 Hofmann et al. 2015
Væ,i,j
[V/(())
(z)(2)) di I max O11==]) ||0, ayll const. ||q: - -ag-aall
ZEN
Note when ||>|| is bounded for all æ E i.e., max.ex ((1x=]) < oc, upper-bounds on the Euclidean distances between the gradients can be pre-computed. This is crucial, because it means that estimation error of the full gradient can be efficiently bounded independent of the actual optimization problem (i.e., point 2). Thus. these upper-bounde can be computed only once as a pre- pre-processing step before any training takes place, and then used to find the subset S by solving the optimization problem (8). We address upper-bounding the normed difference hetween gradients for deep models in Section 3.4
4

---

Under review as a conference paper at ICLR 2020
Algorithm 1 CRAIG (CoResets for Accelerating Incremental Gradient descent)
Input: Set of component functions f; for E = {I,-... nj..
Output: Subset S S V with corresponding per-element stepsizes {rhies, and an ordering
1: Su + 0. Sy = 0, = 0.
2: while F(S) [((su))
do
3:
j E arggma
11)
4:
S: = S
5:
0, o,=j
6:
i=i+1
7:
end while
8:
for =- 1 |S| do
9:
7/ = >iev _[j = argminges V vf)(
end for
3.2 THE CRAIG ALGORITHM
Optimization problem produces a subset S of elements with their associated weights Jes or per-element stepsizes that closely approximates the full gradient. Here, we show how to efficiently approximately solve the above optimization problem in order to find a near-optimal subset S.
The optimization problem 8 is NP-hard as it involves calculating the value of L(S) for all the 2 subsets S - V. We show, however, transform it into submodular set cover problem, for which efficient approximation algorithms exist.
Formally, F' is submodular if F(S U (e)) - f(8) 2 F(T F(T), for any $ C T C and e E V \ T. We denote the marginal utility of an element s w.r.t. a subset S as F(elS) = F(SU fe)) F(S). Function F is called monotone (el(S) 2 for any eEV\S and S C V. The submodular cover problem is defined as finding the smallest set S that achieves utility p. Precisely,
S argmin (S), such that F(S) 2 p. SCV
(10)
Although finding S* is NP-hard since it captures such well-known NP-hard problems as Minimum Vertex Cover, for many classes of submodular functions (Nemhauser et al. 1978 Wolsey 1982). simple greedy algorithm is known to very effective. The greedy algorithm starts with the empty set So = 0. and at each iteration i, it chooses an element E V that maximizes (e) i.e., S, = S U (argmaxeev (1) - F), Greedy gives us a logarithmic approximation, i.e. |S| < (1 + In(max, F F(e(0)))|S*) The computational complexity of the greedy algorithm - (()) However, its running time can be reduced O(VV) using stochastic algorithms Mirzasoleiman et al., 2015a) and further improved using lazy evaluation (Minoux 1978), and distributed implementations (Mirzasoleiman al., 20155] 2016).
Given a subset S C V, the facility location function quantifies the coverage of the whole data set V by the subset S by summing the similarities between every E V and its closest element, j E S. Formally, facility location is defined as (S) Σxev maxjes 8i.j. where 8i,j is the similarity between j E V. The facility location function has been used a number of applications, including scene and documents summarization (Simon et al.) 2007 Lin & Bilmes (2012).
By introducing an auxiliary element 8g we can turn L(S) in Eq. (8) into a monotone submodular facility location function,
F(S) - (((o)) - L(S {su)).
(11)
where L({so)) is constant. In words, F measures the decrease in the estimation error associated with the set S versus the estimation error associated with just the auxiliary element. It is easy to see that for suitable choice of sg, maximizing F is equivalent to minimizing L. Therefore, we apply the greedy algorithm to approximately solve the following problem to get the subset S defined in g
S* argmin |S], such that F(S) 2 L({so)) SCV
(12)
At every step, the greedy algorithm selects element that reduces the upper bound on the estimation error the most. In fact, the size of the smallest subset S that estimates the full gradient by an error of most depends on the structural properties of the data. Intuitively, as long as the marginal gains
5

---

Under review as a conference paper at ICLR 2020
of facility location are considerably large, need more elements to improve estimation of the full gradient. Having found S, the weight 7 of every element j E is the number of components that are closest to it in the gradient space, and are used as stepsize of element j E S during IG. The pseudocode for CRAIG subset selection method is outlined in Algorithm
3.3 ORDERING ON THE ELEMENTS OF THE SUBSET
Notice that CRAIG creates subset S incrementally one element time, which produces natural or- der a to the elements in S. Adding the element with largest marginal gain j E argmax.ey F()(S:)) improves our estimation from the full gradient by an amount bounded by the marginal gain. Formally, at every step i, we have F(S.) (1 c (1II))FFFS ), and hence
Σ Vi(()) Σ 73 (+)) jES
< ent (1-
(13)
SEV
Intuitively, the first elements of the ordering contribute the most to provide a close approximation of the full gradient and the rest of the elements further refine the approximation. Hence, the first incremental gradient updates gets us close to T., and the rest of the updates further refine the solution. We show experimentally that processing data points in the order of S leads to faster convergence than when we consider elements in S in a random order. We defer the formal proof to future work.
3.4 APPLICATION OF CRAIG TO DEEP NETWORKS
Incremental gradient methods, including SGD with momentum (Qian 1999), Adam (Kingma & Ba 2014) and Adagrad (Duchi et al.) 2011) ) are widely used to train deep networks. As discussed, CRAIG selects subset that closely approximates the full gradient, and hence can be also applied for speeding up training deep networks. The challenge here is that we cannot use inequality ( to bound the normed difference between gradients for all E X' and find the subset as preprocessing step.
However, it has been shown that for neural networks, the variation of the gradient norms is mostly captured by the gradient of the loss w.r.t. the last layer (see Section 3.2 of (Katharopoulos & Fleuret 2018)) that is often not expensive or only slightly more expensive than calculating the loss. In many cases, where we have cross entropy loss with soft-max the last layer, the gradient of the loss w.r.t. the i-th input to the soft-max is simply P; yi. where p; are logits (dimension p 1 for p classes) and y the ooe encoded label. In this case, CRAIG does not need any backward pass or extra storage. That is, CRAIG can be applied at the beginning of every epoch to find a subset for that epoch. Note that, although CRAIG needs an additional O(VVI (Š]) complexity (or O(VV) using stochastic greedy) find the subset S the beginning of every epoch, this complexity does not involve any (exact) gradient calculations and negligible compared to the cost of backpropagations performed during the epoch. Hence, as we show in the experiments CRAIG is practical and salable.
4 CONVERGENCE RATE ANALYSIS OF CRAIG
The idea of CRAIG is to selects subset that closely approximates the full gradient, and hence can be applied to speed up most IG variants as we show in our experiments. Here, we briefly introduce the original IG method, and then prove the convergence rate of IG applied to subsets found by CRAIG.
4.1 INCREMENTAL GRADIENT METHODS (IG)
Incremental gradient (IG) methods are core algorithms for solving Problem |I] and are widely used and studied. IG aims at approximating the standard gradient method by sequentially stepping along the gradient of the component functions fa in a cyclic order. Starting from an initial point =1 E Rd makes & passes over all the components. At every epoch à > 1, it iteratively updates x;_1 based on the gradient of f, for i = 1.... n using stepsize ag > 0. Formally,
x = + au (
=
(14)
with the convention that =0 rt Note that for a closed and convex subset X' of IRd, the results can be projected onto X, and the update rule becomes
,¹² Px o% (
i= 1,2, .n.
(15)

---

Under review as a conference paper at ICLR 2020
where Px denotes projection the set X' C R
IG with diminishing stepsizes converges rate (LLVVk) for strongly convex sum function (Nedić & Bertsekas, 200T]. in addition to the strong convexity of the sum function, every component function Ji is smooth, IG with diminishing stepsizes or = @(1)k*), E (0, converges rate ((1/k*) Gürbüzbalaban et al., 2015).
The convergence rate analysis of IG is valid regardless of order of processing the elements. However, in practice, the convergence rate of IG is known to be quite sensitive to the order of processing the functions (Bertsekas & Scientific 20155 Gurbuzbalaban al., (017). If problem-specifie knowledge can be used to find a favorable order a (defined as a permutation {01, :. .n) of (1,2,.., n)), IG can be updated to process the functions according this order, i.c.
x _ O So, (x/_1),
i= 1,2, ...
(16)
In general favorable order is not known in advance, and common approach is sampling the function indices with replacement from the set {1, 2.. n and is called the Stochastic Gradient Descent (SGD) method, a.k.a. the Robbins-Monro algorithm (Robbins & Monro [95I (also see
(Bottou 1998 Bertsekas 2015 Nemirovski et al. 2009 Shalev-Shwartz & Srebro, 2008
4.2 CONVERGENCE RATE OF IG ON SUBSETS FOUND BY CRAIG
Next we analyze the convergence rate IG applied the weighted and ordered subset S found by CRAIG. In particular, we show that (1) applying IG to S converges to a close neighborhood of the optimal solution and that (2) this convergence happens the same rate (same number of epochs) as IG on the full data. Formally, every step of IG on the subset becomes
Ok 7ao V 11
i 1,2, ...
8, E S
| =
(17)
Here, a is a permutation of 21,2,... r. and the per-element stepsize Ys; for every function fs, the weight of the element s; S and is fixed for all epochs.
4.3 CONVERGENCE RATE FOR STRONGLY CONVEX FUNCTIONS
We first provide the convergence analysis for the case where the sum function in Problem I is strongly convex, i.e. Vx, y E Rdd we have that fw) 2 f(x) + (VI(x), x) f1 yll
Theorem 1. Assume that Eiev f((x) is strongly convex, and S is weighted subset of size such that L(S)- Diev minjes dij S 6. Then for the iterates {I =====f² generated by applying IG to S with per-epoch stepsize ag a/kk" with
0 andd [0, 1}, we have
(i) i 1, then [ 1. 112 < 2e ReR/p + 22 C² 02/ke,,
(ii) 0 < 7 < 1, then | - x. 1| < 2cR/H
for l + 0o
(iii) T 0, then 1 12 2 < (1 ax1) 1xo x. x2,12 2cR/ + 2 max C2 /p,
where C is an upper-bound on the norm of the component function gradients, i.e. maxiev sup [I < C, Timax = maxjes 7i is the largest per-element step size, and R = min(do, (F C e)/u}, where do = ||00 x. is the initial distance to the optimum I..
All the proofs can be found in the Appendix. The above theorem shows that IG on S converges at the same rate (lIV/)) of IG on the entire data set V. However, compared to IG on V. the [V|/|S] speedup of IG on S comes at the price of getting an extra error term, 2c R/j.
4.4 CONVERGENCE RATE FOR SMOOTH AND STRONGLY CONVEX FUNCTIONS
If in addition to strong convexity of the expected risk, each component function has Lipschitz gradient, i.c. Vz E X, i E [n] we have [V)((z) ff(())) < 3,1l - y/I. then we get the following results about the iterates generated by applying IG to the weighted subset S returned by CRAIG.
7

---

Under review as a conference paper at ICLR 2020
Test Training loss oppimumm
10
IG
SVRG
SAGA
10-2
CGACR
SVRG+CRAIG
CRRIG
10-3
8.3x
8.3x
4.5x
10
50
100
150
200
250
50
100
150
200
250
50
100
150
200
250
IG
SVRG
SAGA
IG+CRAIG
SVRG+CRAIG
CRGAG
0.26
6.2x
9.6x
6.2x
250
100
200
(sec)
Time (sec)
Time (sec)
Figure 1: Loss residual and error rate of IG, SVRG, SAGA for Logistic Regression on Covtype data set with 581,012 data points. We compare performance of CRAIG (10% selected subset) vs. entire data set. We achieve the average speedup of 7x for achieving similar loss residual and error rate across the three optimization methods.
Theorem 2. Assume that Viey J((x) is strongly convex and f(xx), 1.2. n be convex
and twice continuously differentiable component functions with Lipschitz gradients on X. Given subset such that L(S)- Σiev minjes dij- S e. Then for the iterates {Ix = x generated by applying IG to S with per-epoch stepsize ag = ox/k with a > and E [0. 1), we have
(i) T 1, then I x. S 22/F u+ 3Cr
(ii) i
1, then |,rk x. S 22/14
for + 00
(iii) if = 0, then | - xx S (1 - aq1)* || - x.1l + 26/H ae3Crr
where 3 = Em= Br the sum of gradient Lipschitz constants of the component forptttion
The above theorem shows that for r >> IG applied S converges 2e 2e/p neighborhood of the optimal solution, with a rate of (1/kk) which is the same convergence rate for IG on the entire data set V. As shown our experiments, in real data sets small weighted subsets constructed by CRAIG provide a close approximation to the full gradient. Hence, applying IG to the weighted subsets returned by CRAIG provides a solution of the same or higher quality compared the solution obtained by applying IG to the whole data set, in considerably shorter amount of time.
EXPERIMENTS
In our experimental evaluation we wish to address the following questions: (1) How do loss and accuracy of IG applied to the subsets returned by CRAIG compare to loss and accuracy of IG applied to the entire data; (2) How small is the size of the subsets that
select with CR AIG and still get a comparable performance to IG applied to the entire data; (3) how does the ordering affect the performance of IG on the subset; and (4) how well does CRAIG scale to large data sets, and extend to non-convex problems. To this end, we apply CRAIG to several convex and non-convex problems. In our experiments, we report the run- run-time as the wall-clock time for subset selection with CRAIG, plus minimizing the loss using IG or other optimizers with the specified learning rates. For the classification problems, we separately select subsets from each class while maintaining the class ratios in the whole data, and apply IG to the union of the subsets.
5.1 CONVEX EXPERIMENTS
In convex experiments, apply CRAIG to IG, well variance reduction methods SVRG (Johnson & Zhang 2013), and SAGA (Defazio et al. 2014), that try to reduce the variance of SGD either based on computations of full gradients at pivot points, keeping per data point corrections
8

---

Under review as a conference paper at ICLR 2020
7.5
10
20
Speedup
5.0
10
2.5
Distance optimum
10
15
20
10
20
10
20
0.75
2.4
3.5
0.70
2.2
3.0
15
20
10
20
Subset Size (%)
Subset Size
Subset (%)
Figure 2: (top) Speedup of CRAIG applied to get similar loss residual as IG after 50 epoch, and (bottom) distance to the optimal solution vs various subset sizes for (left) Covtype, (middle) SenslT, and (right) Ijennl. Smaller subsets provides larger speedups, but may converge farther away from the optimal solution.
Training loss optimum
1
10a
10-1
10-2
CRAIG
10-2
10-3
CRAIG (shuffled)
10-3
10-3
40
10
20
30
10
20
Time (sec)
Time (sec)
Time (sec)
Figure 3: Loss residual of CRAIG for Logistic Regression on (left) Covtype, (middle) SensIT, and (right) Ijenn, where process the points of the subset according to the ordering provided by CRAIG vs three random permutations the same subset. Notice convergence is significantly faster when we process the points in CRAIG order.
in memory. We apply L2-regularized logistic regression: fi(x) In(11 1hn11+cm 1- exp(-x7 a 0.5Ax
to classify the following three datasets from LIBSVM: (1) wewtype.biarry including 581,012 data points of 54 dimensions, (2) Sens/T including 78,823 training and 19,705 test data points of dimension 100, and (3) Ijenn/ including 49,990 training and 91,701 test data points of 22 dimensions. As covtype do not come with labeled test data, we randomly split the training data into halves to make the training/test split (training and set sets are consistent for different methods). For the convex experiments, À is set to 10-5,
Figure D compares training loss residual and test error rate of IG, SVRG, and SAGA the subsets of size 10% of covtype selected by CRAIG (with corresponding per-element stepsizes) to that of IG, SVRG, and SAGA the entire data set. We used a constant learning rate of a for SAGA and SVRG, and a/vi: for IG, where a 10-3 for Covtype and Ijenn, and 10-5 for SensIT. can be seen that subsets obtained by CRAIG achieve similar loss and error rate as the entire data sets, but much faster. particular, we obtained speedup of 8.3x, 8.3x, 4.5x from applying IG, SVRG and SAGA on the subsets of size 10% obtained by CRAIG.
Figure top row, compares the speedup achieved by CRAIG reach a similar loss residual as that of IG after 50 epochs for subsets of size 5% to 25%. The bottom compares the L2-norm of the distance to optimal solution (estimated by running IG for a long time) for IG applied to the subsets of various size obtained by CRAIG. We observe that while smaller subsets provide larger speedup, IG on smaller subsets may converge to point farther away from the optimal solution.
Finally, Figure [egureB]shore shows the loss residual vs time for IG when it processes the elements of the subsets according to the ordering obtained by CRAIG compared to random permutations of the same subsets. We observe that the greedy ordering significantly improves the rate of convergence of IG.

---

Under review as a conference paper at ICLR 2020
2.5
2.5
SGD
560
Adam
Adagrad
NAG
Training Ro00
2.0
GRAIG
2.0
Adams CRAIG
2.0
Adagrad+CRAIS
2.0
NAG+ CRAG
3.0
1.5
1.5
15
1.5
2.5x
1.8x
0.5
0.5
0.5
0.5
1000
2000
4000
4000
2030
6000
2000
4000
2000
6000
Test sccurayy
0.0
2.5X
2.5X
0.8
0.8
0.0
3.7x
0.6
0.6
0.2
561D
0.4
0.4
0.-
Adagrad
KAG NAG-CRAII
500+CBAN
CRAIO
Adam-CRAIC
Adlggad-CRAIG
2006
2030
4000
6000
2030
4000
6000
2000
4000
6000
2000
4000
6000
Time (sec)
Time (sec)
Time (sec)
Time (sec)
Time (sec)
(a) MNIST
(b) CIFARIO
Figure 4: Training loss and test accuracy of CRAIG applied to (a) SGD on MNIST with a 1-layer neural network, and (b) SGD, Adam, Adagrad, NAG, on CIFAR-I0 with ResNet-56. CRAIG provides 2x to 3x speedup and a better generalization performance.
5.2 NON-CONVEX EXPERIMENTS
Our non-convex experiments involves applying CRAIG to train the following two neural networks: (1) Our smaller network is fully-connected hidden layer of 100 nodes and ten softmax output nodes; sigmoid activation and L.2 regularization with À = 0.0001 and mini-batches of size 10 on MNIST dataset of handwritten digits containing 60,000 training and 10,000 test images. (2) Our large neural network is ResNet-56 for CIFARIO 10 with convolution, average pooling and dense layers with softmax outputs and 1.2 regularization with À 2 10-1 CIFAR 10 includes 50,000 training and 10,000 test images from 10 classes, and we used mini-batches of size 128. Both MNIST and CIFAR10 data sets are normalized into [0, 1] by division with 255.
We apply CRAIG to several popular methods for training neural networks, including SGD, Nesterov Accelerated Gradient (NAG) method (Nesterov) 1983), Adagrad (Duchi al. 201 }), and Adaptive Moment Estimation (Adam) (Kingma & Ba, 2014). Momentum is method that helps accelerate SGD in the relevant direction and dampens oscillations. NAG adapts momentum updates to the slope of our error function and speed up SGD. Adagrad adapts the learning rate to the parameters, performing smaller updates (i.e. low learning rates) for parameters associated with frequently occurring features, and larger updates (i.e. high learning rates) for parameters associated with infrequent features. Adam computes individual adaptive learning rates for different parameters from estimates of first and second moments of the gradients. Fig- 4a shows loss, and error rate for training a I-layer neural net on MNIST. Fig. show similar quantities for training ResNet-56 on CIFAR1O. For both problems, we used constant learning rate of 10-2 Here, apply CRAIG to select subset of 30%-40% of the data at the beginning of every epoch and train only on the selected subset with the corresponding per-element stepsizes. Interestingly, in addition achieving speedup of 2x to 3x for training neural networks, the subsets selected by CRAIG provide a better generalization performance compared to models trained on the entire data set.
6 CONCLUSION
We developed a method, CRAIG, for selecting an ordered subset (coreset) of data points with their corresponding per-element stepsizes to speed up iterative gradient (IG) methods. In particular, we showed that weighted subsets that minimize the upper-bound on the estimation error of the full gradient, maximize a submodular facility location function. Hence, we can obtain an ordered subset of data points with their corresponding learning rates using a greedy algorithm. We showed that IG on subsets S returned by CRAIG converges at the same rate as IG on the entire data set V, while providing |VI/S|| speedup. In our set of experiments, we showed that various IG methods, including SAGA, SVRG, NAG, Adagrad and Adam runs up to 10x faster on convex and up to 3x on non-convex problems subsets found by CRAIG while achieving practically the same trining loss and test error. Finally, we empirically demonstrated the effect of the ordering found by the greedy algorithm the convergence rate of IG methods.
10

---

Under review as a conference paper at ICLR 2020
REFERENCES
Zeyuan Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods. The Journal of Machine Learning Researck, (111):81448222 2017.
Zeyuan Allen-Zhu, Yang Yuan, and Karthik Sridharan. Exploiting the structure: Stochastic gradient methods using raw clusters. Advances Neural Information Processing Systems, pp. 1642-1650, 2016.
Hilal Asi and John C Duchi. The importance of better models in stochastic optimization. arXiv preprint :.d.::/993308..11 2019.
Dimitri P Bertsekas. Incremental least squares methods and the extended kalman filter. SIAM Journal
Optimization, 6())807-822, 1996.
Dimitri P Bertsekas. Incremental gradient, subgradient, and proximal methods for convex optimization: survey. arXiv preprint 1r7iv:150.001030, 2015.
Dimitri Bertsekas and Athena Scientific. Convex optimization algorithums, Athena Scientific Belmont, 2015.
Léon Bottou. Online algorithms and stochastic approximations. In David Saad (cd.), Online Learning and Neural Networks. Cambridge University Press, Cambridge, UK, 1998. URL http::/tpp///ot bottou revised, 2012.
org/paaprs//bctcous 98x
Kai Lai Chung et al. On stochastic approximation method. The Annals of Mathematical Statistics, 25(3): 463-483, 1954.
Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. Saga: A fast incremental gradient method with support for non-strongly convex composite objectives. In Advances in neural information processing systems, pp. 2014.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 121111:211- 2011.
Roy Frostig, Rong Ge, Sham Kakade, and Aaron Sidford. Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization. In International Conference on Machine Learning, pp. 2540-2548, 2015.
Mert Gürbüzbalaban, Asu Ozdaglar, and Pablo Parrilo. Why random reshuffling beats stochastic gradient descent. arXiv preprint (tt.::::5110005000 2015.
Mert Gurbuzbalaban, Asuman Ozdaglar, and Pablo A Parrilo. On the convergence rate of incremental aggregated gradient algorithms. SIAM Journal on Optimization, 27(2):0035- 2017.
Thomas Hofmaan, Aurelien Lucchi, Simon Lacoste-Julice and Brian McWilliams. Variance reduced stochastic gradient descent with neighbors. Advances in Neural Information Processing Systems, pp. 2305 2313, 2015.
Ric Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction, In Advances neural information processing systems, pp. 311--23,22 2013.
Angelos Katharopoulos and François Fleuret. Not all samples created equal: Deep learning with importance sampling. arXiv preprint arXiv: 00940 2018.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 2014.
Hongzhou Lin, Julien Mairal, and Zaid Harchaoui. A universal catalyst for first-order optimization. In Advances in Neural Information Processing Systems, pp. 3384-3392, 2015.
Hui Lin and Jeff A Bilmes. Learning mixtures of submodular shells with application document summarization. arXiv preprint arXiv: 2012.
OL Mangasariany and MV Solodovy. Serial and parallel backpropagation convergence via nonmonotone perturbed minimization. 1994.
Michel Minoux. Accelerated greedy algorithms for maximizing submodular set functions. In Optimization techniques, pp. 234-243.. Springer, 1978.
Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, Amin Karbasi, Jan Vondrák, and Andreas Krause. Lazier than lazy greedy. In Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015a.
11

---

Under review as a conference paper at ICLR 2020
Baharan Mirzasoleiman, Amin Karbasi, Ashwinkumar Badanidiyuru, and Andreas Krause. Distributed submod- ular cover: Suceinctly summarizing massive data. Advances in Neural Information Processing Systems, pp. 2881-2889, 2015b.
Baharan Mirzasoleiman, Morteza Zadimoghaddam, and Amin Karbasi. Fast distributed submodular cover: Public-private data summarization. Advances Neural Information Processing Systems, pp. 3594-3602, 2016.
Angelia Nedić and Dimitri Bertsekas. Convergence rate of incremental subgradient algorithms. Stochastic optimization: algorithms and applications, pp. 223 264. Springer, 2001.
G.L. Nemhauser, L.A. Wolsey, and M.L. Fisher. An analysis of approximations for maximizing submodular set functions- Mathematical Programming, 14 (4(1):265-295 1978.
Arkadi Nemirovski, Anatoli Juditsky. Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on optimization, 19(4):1574-1660) 2009.
2009.
Yurii Nesterov. A method for unconstrained convex minimization problem with the rate of convergence o (1/k" 2). In Doklady AN USSR, volume 269, pp. 543 543-547, 1983.
Ning Qian. On the momentum term in gradient descent learning algorithms. Neural networks, 155-111 1999.
-eatmmetti--gommtriic Benjamin Recht and Christopher Re. Beneath the valley of the noncommutative arithmetic geometric mean inequality: conjectures, case-studies. Technical report, and consequences. Technical report, University of Bicconsin-Madison 2012.
Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathematical statistics, pp. 400 000-407,11 1951.
Nicolas L Roux, Mark Schmidt, and Francis R Bach. A stochastic gradient method with an exponential convergence rate for finite training sets. In Advances in neural information processing systems, pp. 2663- 2671, 2012.
Shai Shalev-Shwand and Nathan Srebro. Svm optimization: inverse dependence training set size. In Proceedings of the international conference on Machine learning, pp. 928 935. ACM, 2008
Shai Shalev-Shwartz and Tong Zhang. Stochastic dual coordinate ascent methods for regularized loss minimiza- tion. Journal of Machine Learning Research, 14(Fcb):567-59) 2013.
Ian Simon, Noah Snavely, and Steven M Seitz. Scene summarization for online image collections. In 2007 IEEE
11th International Conference on Computer Vision, pp. 1-8. IEEE, 2007.
Mikhail V Solodov. Incremental gradient algorithms with stepsizes bounded away from zero. Computational Optimization and Applications, 11(1):23 35, 1998.
Emma Strubell, Ananya Ganesh, and Andrew McCallum. Energy and policy considerations for deep learning in alp. arXiv preprint 190..0223... 2019.
Paul Tseng. An incremental gradient (-projection) method with momentum term and adaptive stepsize rule. SIAM Journal on Optimization, 8(2):506 531, 1998.
Laurence A Wolsey, An analysis of the greedy algorithm for the submodular set covering problem. Combinator- ica, 2(4):385-39) 3933, 1982.
Lin Xiao and Tong Zhang. proximal stochastic gradient method with progressive variance reduction. SIAM Journal on Optimization, 24(4):2057-201 2014.
Matthew D Zeiler. Adadelta: adaptive learning rate method. arXiv preprint arXiv:
Luo Zhi- Zhi-Quan and Tseng Paul. Analysis of approximate gradient projection method with applications to the backpropagation algorithm. Optimization Methods and Software, 4(2):85-001, 1994.
12

---

Under review as a conference paper at ICLR 2020
A CONVERGENCE RATE ANALYSIS
We firs proof the following Lemma which is an extension of the [Chung et al. (1954). Lemma 4]. Lemma 3. Let uk 2 0 be sequence of real numbers. Assume there exist ho such that
d e + kett'
uk+1 S (1 7 +
Vk 1426 Ko.
k
kP
where e > 0, > 0,0> are given real numbers. Then
"y S (dk: + e)((c - p - 1) k + =ok PPt))
forc e p-11pp12 1, 1
(18)
Uy = Olk k)
for p p-ppp-
(19)
uk= = 9(k79)
(20)
(21)
Proof. Let c > p - and Uik = kP -u- k(-pt1] c-p+1
Then, using Taylor approximation
(1+ ))p = (1+ + ) + o(t)) we can write
uk+1 = (k + 1)p- ux+1 - (k+ + 1)(c - -p+1) c-p+1
e
(22)
| p-1 (11 { Jun + ki
1
d
d
S 11 +
+ kpt1
(23)
b
(k+ + 1)(c - p+
c c p + 1
c- +1
tol k
+ e <(1
p-1 + t )
1
(24)
h
k
+ 22
1 + p-1 1
k
+
k
1
(k + 1) ()ccp())] 1+1) c-p+1
d
e
(25)
d
+ + 1 1- c- pppl (I---
1
Uk
+
(26)
k(c - 1p+1)
c- p-p+ pp1l
k
p p-1 1
ol
d
|+
p-1
+ )
(27)
k
122
k
d
(28)
(k + 1)(c pp-
c c-p 1-p11
= vn (1 k
+ x))
1
+
d/(c p
e(p-15 k2
d(p (1p-19 1)
0
(29)
k(k 1)
k3
Note that for Uk. have
8
c-
p
+ o 00
k
and
(c-
c(p 1) k(k+1)
d(p
1)
ol (2) (1 C- p + t +( -1
0.
1.2
1:3
k
Therefore, lime-xoc 0/ S 0, and we get Eq.
18
For p = 1, we have us S c. Hence, un converges
into the region u < G, with ratio 1 E.
Moreover, for p- 2 c we have
Uk+1 = ux+1 (k + 1) <
(1
T. )uk
C
+ e + KotI
] 1: (1 (1+
c
+
d²
+ of
1 T2
(30)
to
t 21
= -(1
2
1
Uk + kp-otI (1 + +
d
+ مل (1 | c + 0
e
1
+ ol
(31)
2k
kz
k
d'
S U/++ +
(32)
kp-c
for sufficiently large k. Summing over k, we obtain that is is bounded for p p- > e (since the
series (1/k() converges for a > 1) and Uy = O(log k) for p = c 1 (since Σ (1/8)
Ollog))
13

---

Under review as a conference paper at ICLR 2020
In addition, based on CChnng et al. (1954),
Lemma 5] for uk 2 0. write
C
e
Mk+1 - (1
uu +
0 <<s<ls<p<>
(33)
kp
Then, we have
1
Uk
C. kp-s kp--
+ of
(34)
A.1
CONVERGENCE RATE FOR STRONGLY CONVEX FUNCTIONS
PROOF THEOREM
We now provide the convergence rate for strongly convex functions building the analysis of Nedic Bertsekas 2001). For non-smooth functions, gradients can be replaced by sub-gradients.
Let vk z For every IG update subset S we have
|2 x. 11 ||al- ak V ( 2.112
(35)
= ||a - 22 2007,
a (f
(36)
< ||اسー11 x. 1..112 20
- +f
(37)
Adding the above inequalities over elements of S get
| x=.12= = I| - 22112 - 20ck
E(f((ot-)) - fz((,)) + a Σ
175 Vf
(38)
jES
JES
1|
x.112 20rk
(Us(())) f((x.)
jES
+ 20rk
Σ (J - [x(xx) + a
Σ
1h V/ (39)
JES
JES
Using strong convexity we can write
[1041 x=112 <
||:0
x.Il
2001
Ta V5z(x.) (xx- - x.) 1 100 1=.
JES
20
-((())-))-(((a))))
f2(xa) + Σ
1hs V (a
(40)
JES
jES
Using Cauchy-Schwarz inequality, we know
Σ [z)(())))) (Ix xx)] S Σ
75 (z.))) -
(41)
JES
jES
Hence,
Σ Vtvt,) (Ix x.) 1 Σ n, Vx,
|| x.ll-
(42)
jES
jES
From reverse triangle inequality, and the facts that S is chosen in way that Eiev Vf((z.))
Ejes 7i (z)())))) < and that Σiev Vfe(x.) = 0 we have EEs (fy(x)) 5
E1Eiv V(((=))] = Therefore
Σ (f 1| x.Il S c. || x= jES
(43)
For continuously differentiable function, the following condition is implied by strong convexity condition
xzll - P jES
Σ 33 Vz)(m)l
(44)
14

---

Under review as a conference paper at ICLR 2020
Assuming gradients have bounded norm max+ex, [z) 2 C, and the fact that Ejes 7/3
JEV
we can write
E V sn.
(45)
jES
Thus for initial distance ||z00 2.11 do. we have
|| z, || min(n C, R
(46)
Putting Eq.
42 to Eq. 46 together we get
[k+1 r. 1| S (1 -aa11) ) Io I. 112 + 22geR//1
20rk
(1)(1))1,6) - {,(xx)) + afr C2.
(47)
jES
Now, from convexity of every fJ for j E S we have that
fz(xx) - ( (
Ihy 11a5-1 xxll-
(48)
In addition, incremental updates gives
| x&ll S aa V aa( 1) 7mma
(49)
Therefore, get
200
((s(()) fs(a)=1)) + a C
max
jES
< 200 1=1
Tmax C' Cap(j - 1m C + agm 0²
(50)
2,2 mmax C2
(51)
Hence,
|
x.112 < (1 - ax (1)14)](z | - x2 2ageR/ / + + 22
C²,
(52)
where Ymax is the size of the largest cluster, and C is the upperbound on the gradients.
For 11 the theorem follows by applying Lemma to Eq. 52 with 11, ReR/u, and d = r 7 C
For where we have constant step size a = 1.
p we get
| 12 < (1-ap)*+ k+1 |1:0 xx
b
k C2
+ Zear R
Σ (1 - anp) / + 222 max
(1
an)
(53)
1=0
j=0
Since () a41)3 < 1
ap we get
| - -I.l" 112 < (1 - a4) 1120 -2.112+ 2eR/ PM + 2 C2/M,
(54)
and therefore,
|| - 22.11 < (1 (ot))++*llle 12 12 2eR2 / + ox 2 C²/
(55)
A.2 CONVERGENCE STRONGLY CONVEX AND SMOOTH COMPONENT FUNCTIONS
PROOF OF THEOREM 2
IG updates for cycle l on subset 5 can be written as
Ib+1
Fbk a& Σ E2fff(z - ex)
(56)
JES
6/ = Σ
-f
(57)
JES
15

---

Under review as a conference paper at ICLR 2020
Building on the analysis of Gürbüüzallaan et al. (2015), for convex and twice continuously differen- tiable function, we can write
Σ 7o Vs.() A5(xx x.) jES
(58)
JES
where A% - So fx, + T dd is average of the Hessian matrices corresponding to the (weighted) elements of S on the interval tR.
From Eq.
58
have
Vf(x)) - Vf((x.)) E ( (f))))))))) = (x
xx) Aī( Ix), (59)
KVV
jES
where Aş is average of the Hessian matrices corresponding to all the n component functions on the interval V.). Taking norm of both sides and noting that Σvev f((x..) 0 and hence
jees (x.)))))))) & e, we get
IIAA (2) x.)1==
Σ Vz())) iEV
Σ (f)l)) jES
+ Enf s
2e, 2e,
(60)
jES
where e is the estimation error of the full gradient by the weighted gradients the elements of the subset S, and used Eiev Vf(((x)) Ejes 7/ ( s.
Substituting Eq. 58 into Eq. 56 we obtain
Ik+1
(I (xx xx)) agek
(61)
Taking norms of both sides, get
| 2x S |1(I aa zx1l) ax|(ex
(62)
Now, we have
[1(1 (xx /1 x.) a xz)]l
(63)
[I xx) - ax (Aii - Ax) -x+) ax - xx.)ll
(64)
[[ As) 2.)l| + ax (A A2) xz))l
(65)
[|(/ As) - x.)ll + 205e
(66)
Substituting into Eq. 62
we obtain
| x.Il $ -
x.Il + 2aye + axllexll 1| -
(67)
From strong convexity of Eiev fi(x), and gradient smoothness of each component f((x) we have
μI, = Σ v'f()), = BIn, x x
(68)
KEV
where B 3= =iEvv B In addition, from the gradient smoothness of the components we can write
| S Σ
75881 Ix - s
(69)
JES
j-1
Σ JES
3
Σ
|| -
(70)
1=1
Σ
739 Σ
(71)
JES
B0rg
(72)
16

---

Under review as a conference paper at ICLR 2020
where in the last line used |S] Therefore,
| x- - max(I|1 - axull, || a1311)1= - x.11 + 20ge a0
(73)
$ (1 - ax/)|== - z.1l + 204e ag if ag S 1.
(74)
For 0 < S 1, the theorem follows by applying Lemma 3 to Eq.
73 with ,4 2e,
= 3Cr For 8 = 0, where we have a constant step size ak 3 we get
k Σ (1 -ap) + + 1=0
[ - x. 1 (1 - - h+ (1)))+1111300 - x.1l + 2c
Σ 1=0
11 an)
BCmmax
(75)
< (1 ap))&1 k+1 | - -x.l + 26/11 + a33rrmax! //,
(76)
$ (1 ap))& k+ | -x.ll + 20/ |z + Crrmax/ 1
(77)
where the inequality in Eq. 76 follows since En au)² S ap
B NORM OF THE DIFFERENCE BETWEEN GRADIENTS
For ridge regression f((x) ((ar, y:)² + | we have = Therefore,
a;((a;, Vi) + Ax.
(z(()))]] (Ila.- - ay11-11== 11 My 11ll
(78)
For ||a/|| $ 1, and y/+ y/ get
[vi(z> V/}(2)]| - ||:: -0]
(79)
For reguralized logistic regression with y 111,1), we have Vf((a) y1/(1 evilara)). For = Mj we get
c|10=-0)111
[V Vz)()
||as|l-
(80)
+ (a..))
For ||a:l| $ 1, using Taylor approximation et < 1 and noting that 140-30003 we get
||a - 11|1-|1=11
- V
e ||رر|| s || [1((1((==1).
(81)
For classification, require y; = Uý hence the results. On the other hand, in ridge regression we also need 1y: yy| to be small. Similar results be deduced for other loss functions including square loss, smoothed hinge loss, etc.
select subsets from each class and then merge
Assuming |||||| is bounded for all x E X', upper-bounds on the euclidean distances between the gradients can be pre-computed.
C ADDITIONAL EXPERIMENTS
17

---

Under review as a conference paper at ICLR 2020
CRAIG
weighted
Random unweighted
Training optimum
10-3
10-4
10-3
10-8
50
60
Time (sec)
Figure 5: Loss residual vs. time for IG on 10 subsets of size 10%, 20%. 30%. .... 100% selected by CRAIG, random subsets, and random subsets weighted by |V//S). Stepsizes are tuned for every subset separately, by preferring smaller training loss from a large number of parameter combinations for two types of learning scheduling: exponential decay 17()) ///lt/n with parameters тo and adjust and (-inverse 7t() (1 + blt/nl) // with and b to adjust.
0.45
0.93
0.40
Test accuracy
0.92
Training
0.35
0.30
CRAIG
0.89
SGD
SCD + Random subset
25
50
75
125 Time (sec)
100
150
175
200
25
50
75
100
325
150
175
200
Time (sec)
Figure 6: Training loss and test accuracy for SGD applied to full MNIST vs. subsets of size 60% selected by CRAIG and random subsets of size 60%. Both the random subsets and the subsets found by CRAIC change at the beginning of every epoch.
18


Reviews:
[{"review_id": "Hkg22VYtKH", "reviewer": "AnonReviewer1", "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 novel extension to SGD/incremental gradient methods called CRAIG. The algorithm selects a subset of datapoints to approximate the training loss at the beginning of each epoch in order to reduce the total amount of time necessary to solve the empirical risk minimization problem. In particular, the algorithm formulates a submodular optimization problem based on the intuition that the gradient of the problem on the selected subset approximates the gradient of the true training loss up to some tolerance. Each datapoint in the subset is a medoid and assigned a weight corresponding to the number of datapoints in the full set that are assigned to that particular datapoint. A greedy algorithm is employed to approximately solve the subproblem. Theory is proven based on based on an incremental subgradient method with errors. Experiments demonstrate significant savings in time for training both logistic regression and small neural networks.\n\nStrengths:\n\nThe proposed idea is novel and intriguing, utilizing tools from combinatorial optimization to select an appropriate subset for approximating the training loss. Based on the experiments provided in the paper, it does appear to yield a significant speedup in training time. It is interesting to observe how the order of the datapoints matter significantly for training, and that CRAIG is also able to naturally define a good ordering of the datapoints for SG training. This is strong algorithmic work.\n\nWeaknesses:\n\nSome questions I had about the work:\n\n- How well does one have to approximate $d_{ij}$ in order for the method to be effective? The authors provide an approach to approximate this for both logistic regression and neural networks. How does one guarantee that one is obtaining the maximum over $x in \\mathcal{X}$ for neural networks via backpropagating only on the last layer? Does taking this maximum matter?\n- How does one choose $\\epsilon$? Is this related to how $d_{ij}$’s are approximated?\n- If one were to consider an algorithm that samples points from this new distribution over the data given by CRAIG, if one were to include the weight $\\gamma_j$ into the algorithm, would the sample gradient be unbiased? What if one were to simply use $\\gamma_j$ to weight that particular sample in the new distribution?\n- In machine learning, the empirical risk (finite-sum) minimization problem is an approximation to the true expected risk minimization problem. What is the effect of CRAIG on the expected risk? Is there any deterioration in generalization performance?\n- In page 4, what does the $\\min_{S \\subseteq V}$ refer to? Should the equation be interpreted as with the set $S$ fixed or not?\n- Theorems 1 and 2 are stated a bit non-rigorously. Are these theorems for fixed $k$? What does it mean for these bounds that $k \\rightarrow \\infty$?\n- In Theorems 1 and 2, what is the bound on the steplength in order to obtain the convergence result for $\\tau = 0$?\n- In Theorem 1 for $0 < \\tau < 1$, why does one obtain a result where $\\|x_k – x_*\\|^2 \\leq 2 \\epsilon R / \\mu$, why is the distance to the solution bounded by a constant? What if one were to initialize $x_0$ to be such that $\\|x_0 – x_*\\|^2 > 2 \\epsilon R / \\mu$? (Similar for Theorem 2.)\n- In the experiments, how is the steplength and other hyperparameters tuned? Are multiple trials run? \n- Is $\\epsilon$ used to determine the subset or is it based on a predetermined subset size?\n- How do the final test losses compare between CRAIG and the original algorithms?\n- How do the relative distances (rather than the absolute distance) to the solution behave?\n- How does CRAIG perform over multiple epochs? How does the algorithm transition when the subset is changed (as in neural networks)?\n- Why does CovType appear more stable with the shuffled version over the other datasets? Is the stability related to the distribution of the weights $\\gamma_j$?\n\nSome grammatical errors/typos/formatting issues:\n\n- Equation (9) needs more space between the $\\forall x, i, j$ and the rest of the equation.\n- What is $\\Delta$ on page 5? Is it supposed to be $F$?\n- On page 8, And should not be capitalized.\n- Page 14, prove not proof\n- Page 14, subtracting not subtracking\n- Page 16, cycle not cycke\n\nOverall, although I like the ideas in the paper, the paper still needs some significant amount of refining in terms of both writing and theory, as well as some additional experiments to be convincing. If the comments I made above were addressed, I would be open to changing my decision. ", "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 thoroughly."}, "extra_text": {}}, {"review_id": "H1l_fhnnqH", "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": "The paper proposes a theoretically founded method to generate subsets of a dataset, together with corresponding sample weights in a way that the average gradient of the subset is at most epsilon far from the average gradient of the full dataset. Given such a subset, the authors provide theoretical guarantees for convergence to an epsilon neighborhood of the optimum for strongly convex functions. The proposed algorithm to create such a subset is a greedy algorithm that relies on parameter independent similarities between samples, namely similarity scores that are true regardless of the current value of the function parameters.\n\nAlthough I find the approach interesting, I have three main concerns with the proposed method.\n1. The experimental setup is lacking significant information, baselines and baseline tuning (see below for more in depth comments).\n2. The proposed upper bound which has been used for a similar purpose by [1] becomes nonsensical in high dimensions and although for [1] this would mean sampling with a non optimal sampling distribution for CRAIG it means converging very far from the optimum. What are the values of epsilon that you observe in practice?\n3. I do not see how CRAIG would be applied to deep learning. The argument in section 3.4 is that the variance of the gradient norm is captured by the gradient of the last layer or last few layers, however this is true given the parameters of the neural network. The gradients can change arbitrarily after a very small number of parameter updates as shown by [2].\n\nExperimental setup\n----------------------------\n\nFor the case of the convex problems, the learning rate is not tuned independently for each method. Even more importantly the stepsizes of CRAIG are all numbers larger than 1 so the expected learning rate is multiplied by the average step size. This makes it difficult to understand whether the speedup is due to a larger learning rate or due to CRAIG. Similarly for figure 3 the result could be due to a non decreasing step size because of \\gamma_j while for CRAIG \\gamma_j are ordered in decreasing order.\n\nIn addition, there is no experimental analysis of the epsilon bound and the actual difference of the gradients for the subset and the full dataset. There are also no baselines that use a subset to train. A comparison with a baseline that uses 1. random subset or 2. a subset selected via importance sampling from [1] would contribute towards understanding the particular benefits of CRAIG.\n\nRegarding the neural network experiments:\n1. There is no explicit definition of the similarity function used for the case of neural networks. If we assume based on 3.4 that the algorithm requires an extra forward pass in the beginning of every epoch there should be visible steps in Figure 3 where time passes but the loss doesn't move.\n2. 2000 seconds and 80% accuracy on MNIST points towards a mistake on the implementation of the training. On a laptop CPU it takes ~15s per epoch and achieves ~95% test accuracy from the first epoch for the neural network described.\n3. Similarly 80% accuracy on CIFAR10 is sufficiently low for Resnet-56 to be alarming.\n\n[1] Zhao, Peilin, and Tong Zhang. \"Stochastic optimization with importance sampling for regularized loss minimization.\" international conference on machine learning. 2015.\n[2] Defazio, Aaron, and Léon Bottou. \"On the ineffectiveness of variance reduced optimization for deep learning.\" arXiv preprint arXiv:1812.04529 (2018).", "extra_scores": {"experience_assessment": "I have published one or two 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 carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "BkghxNl2OS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "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 presents a method for subselecting training data \nin order to speed up incremental gradient (IG) methods (in terms of computation time). \nThe idea is to train a model on a representative subset of the data such \nthat the computation time is significantly decreased without \nsignificantly degrading performance. Given a dataset D and \nsubset S selected by the proposed method, it is shown that \ntraining on subset S achieves nearly the same loss as training on the full \ndataset D would, while achieving significant computational speedups.\n\nThis paper is a clear accept. The approach is novel and has well-developed \ntheory supporting it. The empirical evaluation of the method shows \nlarge speedups in training time without degradation in performance \nfor reasonably large subsets (e.g. 20% of the data). The paper is \nvery clear, well-written, and was a genuinely fun read.\n\nClarifying questions:\n  - In results reporting speedups, does the reported training time for CRAIG \n  include the preprocessing time? Or only the time spent running IG on the resulting \n  subset?\n  - How many runs are the experiments averaged over? There don't seem to be \n  error bars, which makes it difficult to assess whether the speedups are \n  statistically significant\n  - I imagine that an approach like this would be desirable when working with  very large datasets. Has \n  CRAIG been evaluated in settings with millions of datapoints? Or does it become impractical? I think \n  that the paper stands on its own without such a demonstration, but it would go a long way towards \n  encouraging mainstream adoption of your method.\n  - Figure 3, left: What could be happening at around 40s? It looks like \n  all three of the random permutations have a spike in loss at around the same time, despite being \n  different permutations of the sub-selected data\n  - How were hyperparameters, such as the regularization parameter, step-size etc. chosen? One of the \n  main claims of the paper is that using the subset selected by CRAIG doesn't significantly \n  effect the optimization performance. But if the baselines weren't thoroughly tuned, it could be the case \n  that IG on the CRAIG subset performs similarly to IG on the full training data, but that neither \n  is actually reaching satisfactory performance in a given domain.\n  - Figure 4: isn't 2000s \\approx 30min really slow for MNIST? From what I remember, reasonable test accuracy \n  on MNIST with a feed-forward network with a single layer takes only a few minutes? Though admittedly, I could \n  be misremembering this.\n  \nSomewhat open-ended questions:\n  - To what extent are the results hardware dependent? Do you see similar results on \n  different hardware? I'm wondering how much of the speedup could be attributed to \n  something like better memory locality when using the smaller subset selected using CRAIG.\n  - Section 3.4 mentions that the O(|V||S|) complexity can be reduced \n  to O(|V|) using a stochastic greedy algorithm. Has the performance \n  when training on a subset selected via the stochastic algorithm \n  been compared to the performance when training on a subset selected by the \n  deterministic version? \n\nI have only minor suggestions:\n  - The CRAIG Algorithm \n    - When F is introduced, I had trouble conceptualizing what kind of object it was. I think \n      mentioning what spaces it's mapping between could increase readability.\n    - Mirzasoluiman et al. (2015a) looks like it is supposed to be a parenthetical citation\n  - Figure 4: The caption labels appear to be swapped. In the figure, (a) is MNIST, but in the \n    caption, (b) is MNIST\n  - 5.1: There is a vertical space issue between the introduction of section 5 and section 5.1. \n  I suspect this was necessary to make the max page requirements. If space is an issue, my suggestion would \n  be to move Algorithm 1 to the appendix. It's nice to have a concrete algorithm specification, but I personally \n  did not find that it aided my understanding of your paper.", "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 carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper investigates the practical and theoretical consequences of speeding up training using incremental gradient methods (such as stochastic descent) by calculating the gradients with respect to a specifically chosen sparse subset of data. 

The reviewers were quite split on the paper. 

On the one hand, there was a general excitement about the direction of the paper. The idea of speeding up gradient descent is of course hugely relevant to the current machine learning landscape. The approach was also considered novel, and the paper well-written. 

However, the reviewers also pointed out multiple shortcomings. The experimental section was deemed to lack clarity and baselines.  The results on standard dataset were very different from expected, causing worry about the reliability, although this has partially been addressed in additional experiments. The applicability to deep learning and large dataset, as well as the significance of time saved by using this method, were other worries.

Unfortunately, I have to agree with the majority of the reviewers that the idea is fascinating, but that more work is required for acceptance to ICLR.  
Decision: Reject