Faster Algorithms for Large-scale Machine Learning using
Simple Sampling Techniques

arXiv:1801.05931v2 [cs.LG] 5 Feb 2018

Vinod Kumar Chauhan 1 Kalpana Dahiya 2 Anuj Sharma 1

Abstract
Now a days, the major challenge in machine
learning is the ‘Big Data’ challenge. The big data
problems due to large number of data points or
large number of features in each data point, or
both, the training of models have become very
slow. The training time has two major components: Time to access the data and time to process (learn from) the data. In this paper, we have
proposed one possible solution to handle the big
data problems in machine learning. The idea is to
reduce the training time through reducing data access time by proposing systematic sampling and
cyclic/sequential sampling to select mini-batches
from the dataset. To prove the effectiveness of
proposed sampling techniques, we have used Empirical Risk Minimization, which is commonly
used machine learning problem, for strongly convex and smooth case. The problem has been
solved using SAG, SAGA, SVRG, SAAG-II and
MBSGD (Mini-batched SGD), each using two
step determination techniques, namely, constant
step size and backtracking line search method.
Theoretical results prove the same convergence
for systematic sampling, cyclic sampling and
the widely used random sampling technique, in
expectation. Experimental results with bench
marked datasets prove the efficacy of the proposed sampling techniques.

1. Introduction
The technological developments and the availability of a
number of data sources have evolved the data into ‘Big
Data’, where the meaning of ‘Big’ in ‘Big Data’ is continuously changing because of increasing of size of datasets.
Big data has multiple aspects, like, volume, velocity,
variety and veracity etc., and one aspect, namely, volume,
i.e., size of datasets have posed a challenge to the machine
learners to train the models over these large datasets.
These problems which can be called as large-scale or big
data problems, have large number of data points or large
number of features in each data point, or both, which lead

to slow training of models. So now a days, the major
challenge is to develop efficient and scalable learning
algorithms for dealing with big data problems (Zhou et al.,
2017; Chauhan et al., 2017; 2018). The training time of
models have two major components (Yu et al., 2010) as:
training time = time to access data + time to process data.
As it is known that for processing any data or running any
program, it should be first brought into memory, more
precisely into RAM (Random Access Memory), from hard
disk. The time taken in brining the data or program from
hard disk into memory is called access time. Access time
has, further, three components, namely, seek time (it is
the time taken by the reading head to move from current
position up to the track containing the data), rotational
latency time (it is the time taken by the reading head
from the current position to reach up to the sector/block
containing the data) and transfer time (it is the time taken
to transfer data from sector/block over the disk to memory).
Moreover, data is not read content wise rather block-wise,
where each block can have multiple sectors. Now, it is
interesting to note that for data stored on the contiguous
memory or in the close proximity, has lesser data access
time as compared with the data dispersed far away from
each other. This is due to lesser seek, latency and transfer
times. In case of SSD (Solid State Disk) and RAM
(Random Access Memory), there are no seek and latency
times because they do not have moving parts and they
are based on direct access mechanism, but transfer time
still plays its role. Since data are read/written block-wise
so for contiguous data access, there would be one or two
transfer times but dispersed data access would require
more number of transfer times. Moreover, cache memory
strategies also favor the contiguous memory access and
make it faster as compared to dispersed data access. Thus
contiguous data access time is faster than dispersed data
access, in all the cases where data is stored on RAM, SSD
or HDD. But the difference in access time would be more
prominent for HDD. The second component of training
time is processing (learning) time which is the time taken
by the CPU (Central Processing Unit) to process the data
to solve for model parameters. Due to mini-batching and
iterative learning algorithms, the accessing and processing
of data is intermixed and occurs quite frequently. The data

Faster Algorithms for Large-scale Machine Learning

access time is dependent on the sampling technique and
processing time is dependent on the method used to solve
the problem. Till this date, to improve the training time,
most of the focus is given only to improve the processing
time by using different methods. The training time is
dependent on both data accessing time and data processing
time, and this is to be noted that, generally, data access
time is very high as compared to the data processing time.
Thus, efforts should be equally done to improve the data
accessing time. This paper has tried to reduce the training
time for big data problems by reducing the data access
time using systematic sampling technique (Madow, 1949;
Madow & Madow, 1944) and cyclic sampling to select
mini-batches of data points from the dataset.

where Bj is the selected mini-batch of data points. The iteration complexity for solving this reduced subproblem is
O(n) (for one data point) or O(n|Bj |) (for mini-batch of
data points) where |Bj | is the size of mini-batch, which is
very low and independent of l. Since it is easier to solve
the problem (2) and this is widely used approach to handle large-scale problems so the paper uses this reduced subproblem approach.

1.1. Optimization Problem

1.2. Literature Review

Empirical Risk Minimization (ERM) problem (Reddi,
2016) is a commonly used in machine learning and
statistics, which typically consists of loss function and
a regularizing term. In this paper, l2-regularized ERM
problem with the assumptions of strong convexity and
smoothness, is used for demonstrating the effectiveness
of proposed sampling techniques. For the training data
{(x1 , y1 ) , (x2 , y2 ) , ..., (xl , yl )}, where xi ∈ Rn , yi ∈ R,
and for loss functions f1 , f2 , ..., fl : Rn → R, model
parameter vector w ∈ Rn and regularization coefficient
C > 0, l2-regularized ERM problem is given by

Big data challenge is one of the major challenge in
machine learning (Zhou et al., 2017; Chauhan et al.,
2017). For dealing with big data problems, stochastic
approximation (and coordinate descent) approaches are
widely used (e.g., (Chang et al., 2008; Johnson & Zhang,
2013; Konečný & Richtárik, 2013; Defazio et al., 2014;
Wright, 2015; Xu & Yin, 2015; Schmidt et al., 2016;
Chauhan et al., 2017)), which take one or more data points
(one or block of features in coordinate descent) to form
a reduced subproblem during each iteration. This helps
in reducing the computational complexity per iteration
and thereby helps in solving large-scale problems. But
due to stochastic noise, like in SGD (Stochastic Gradient
Descent) method, stochastic approximation affects the
solution of problem. This stochastic noise can be reduced
using different techniques, like, mini-batching (Tak et al.,
2013), decreasing step sizes (Shalev-Shwartz et al., 2011),
importance sampling (Csiba & Richt, 2016) and variance reduction techniques (Johnson & Zhang, 2013),
as discussed in (Csiba & Richt, 2016). For selecting
one data point or mini-batch of data points from the
dataset in stochastic approximation approach, random
sampling (e.g., (Byrd et al., 2016; Defazio et al., 2014;
Johnson & Zhang, 2013; Konečný & Richtárik, 2013;
Li et al., 2014; Nemirovski et al., 2009; Schmidt et al.,
2016; Shalev-Shwartz et al., 2011; Tak et al., 2013;
Wang et al., 2017; Xu & Yin, 2015; Zhang, 2004)) is
widely used, and other sampling technique are importance
sampling (e.g., (Csiba & Richt, 2016; Csiba & Richtárik,
2016; Needell et al., 2014; Qu & Richt, 2015; Zhang & Gu,
2016; Zhao & Zhang, 2015)), stratified sampling
(Zhao & Zhang, 2014) and adaptive sampling (Gopal,
2016). Importance sampling is a non-uniform sampling
technique, which uses properties of data for finding probabilities of selection of data points in the iterative process,
leading to the acceleration of training process. Importance
sampling involves some overhead in calculating the
probabilities and the average computational complexity

l

min f (w) =
w

1X
fi (w) + Ckwk2 ,
l i=1

(1)

where first term is the data fitting term and second term
is used for avoiding the over-fitting of data. Commonly
2
used loss functions are the square loss
wT xi − yi , the

logistic loss log 1 + exp
−yi wT xi and the hinge loss

max 0, 1 − yi wT xi . In this paper, experimentation
uses logistic loss function. When problem represented
by eq.(1) is a large-scale or big data problem then per
iteration complexity of learning algorithms with traditional
methods like Gradient Descent is O(nl) which is very high.
This is because, such problems have large number of data
points (l) or large number of features (n), or both, and each
iteration updates n variables over l data points. Because of
this high computational complexity per iteration it would
be very expensive or even infeasible for single machine to
process a single iteration of learning algorithm. Stochastic
approximation approach is widely used for handling
such cases (e.g., (Zhang, 2004; Nemirovski et al., 2009;
Shalev-Shwartz et al., 2011; Johnson & Zhang, 2013;
Konečný & Richtárik, 2013; Tak et al., 2013; Li et al.,
2014; Defazio et al., 2014; Xu & Yin, 2015; Byrd et al.,
2016; Schmidt et al., 2016; Chauhan et al., 2017)), which
uses one data point or mini-batch of data points during

each iteration. The reduced subproblem with mini-batch
of data points is given by
min
w

1 X
fi (w) + Ckwk2 ,
|Bj |

(2)

i∈Bj

Faster Algorithms for Large-scale Machine Learning

per iteration of importance sampling could be more than
the computational complexity of the iteration in some
cases, like, when it is implemented dynamically. Stratified
sampling technique divides the dataset into clusters of
similar data points and then mini-batch of data points are
selected from the clusters. In adaptive sampling (Gopal,
2016), information about the classes, i.e., data-labels is
used for selecting the data points; this technique gives good
results for problems with large number of classes. Random
sampling is widely used in mini-batching for large-scale
learning problems (e.g., (Byrd et al., 2016; Li et al., 2014;
Shalev-Shwartz et al., 2011; Tak et al., 2013)), as only
(Csiba & Richt, 2016) is known importance sampling
technique in mini-batching. In this paper, we have focused
on simple sampling techniques which do not involve
any extra overhead and can be effective for dealing with
large-scale learning problems. Two simple sampling techniques, namely, systematic sampling and cyclic/sequential
sampling techniques have been proposed for selecting
mini-batches. To the best of our knowledge, systematic
sampling is not used in machine learning for selecting data
points. We are the first to introduce systematic sampling
in machine learning for selection of mini-batches of data
points from the dataset. Before this, cyclic sampling was
used in coordinate descent and block coordinate descent
methods (e.g.,(Wright, 2015)) for selecting one coordinate
or block of coordinates, respectively, and to the best of
our knowledge, cyclic sampling is not used for selecting
mini-batches.
Both sampling techniques are simple,
effective and easy to implement. The proposed sampling
techniques try to reduce the training time of models by
reducing the data access time. Before this, for reducing
the training time of models, the focus is mainly given on
reducing the processing time, but this paper has focused
on reducing the data access time by changing the sampling
techniques.
1.3. Contributions
The contributions of the article are summarized below:
• Novel systematic sampling and sequential/cyclic sampling techniques have been proposed for selecting
mini-batches of data points from the dataset for solving large-scale learning problems. The proposed techniques focus on reducing the training time of learning
algorithms by reducing the data access time.
• Experimental results prove the efficacy of systematic
sampling and cyclic sampling in reducing the training time. The results have been proved using different methods each using two step determination techniques, namely, constant step size and backtracking
line search methods.

• Theoretical results prove the same convergence of
learning algorithms using random, cyclic and systematic sampling techniques in expectation.

2. Systematic Sampling
Sampling is the way of selecting one mini-batch of data
points (or one data point) from the whole dataset. Iterative approximation methods used for solving the problem
use sampling again and again during each iteration/epoch.
The convergence of learning algorithm depends upon the
type of sampling used since sampling controls two things:
data access time and diversity of data. In general, when
consecutive data points are used they reduce the data access time which reduces the training time but selected
data points might not be diverse which affects the convergence of learning algorithm. On other hand, when data is
used from different locations then the data access time is
more which increases the training time but selected data
points might be diverse which can improve the convergence. Thus, sampling has a significant role in the learning
algorithms. Three sampling techniques, namely, random
sampling, cyclic sampling and systematic sampling are discussed below and used in learning algorithm as they are
simple, easy to implement and do not involve any extra
overhead and thus effective in handling large-scale problems.
2.1. Definitions
Suppose a mini-batch B of m data points is to be selected
from a training dataset {(x1 , y1 ) , (x2 , y2 ) , ..., (xl , yl )} of
l data points.
• Random Sampling: Random sampling (RS) can be of
two types, RS with replacement and RS without replacement. RS with replacement first selects one data
point randomly from the whole dataset where each
data point has equal probability of selection, then, similarly, second data point is selected randomly from
the whole dataset where previously selected point has
equal probability of selection, and so on to select m
data points. RS without replacement first selects one
data point randomly from the whole dataset where
each data point has equal probability of selection, then,
similarly, second data point is selected randomly from
the remaining l − 1 points without considering the
previously selected point, and so on to select m data
points.
• Cyclic/Sequential Sampling: First mini-batch is selected by taking the first 1 to m points. Second minibatch is selected by taking next m + 1 to 2m points
and so on until all data points are covered. Then again
start with the first data point.

Faster Algorithms for Large-scale Machine Learning

• Systematic
Sampling:
(Madow,
1949;
Madow & Madow, 1944) It randomly selects the
first point and then selects the remaining points
according to a fixed pattern, e.g., it randomly selects
a data point, say i, and then selects data points as
i, i + k, ..., i + (m − 1)k as mini-batch where k is
some positive integer. For simplicity, k = 1 can be
taken.
Example: Suppose the training dataset is given by
S = {1, 2, 3, ...., 20} and size of mini-batch to be selected is m = 5, then four mini-batches can be selected/drawn from S using different sampling techniques
as follows: mini-batches selected using random sampling with replacement are - B1 = {15, 2, 20, 2, 1},
B2 = {3, 10, 20, 6, 1}, B3 = {5, 9, 19, 2, 7} and B4 =
{1, 11, 18, 3, 16}; mini-batches selected using random sampling without replacement are - B1 = {15, 2, 20, 11, 6},
B2 = {3, 10, 8, 14, 1}, B3 = {16, 4, 17, 7, 19} and B4 =
{9, 5, 12, 18, 13}; mini-batches selected using cyclic sampling are - B1 = {1, 2, 3, 4, 5}, B2 = {6, 7, 8, 9, 10},
B3 = {11, 12, 13, 14, 15} and B4 = {16, 17, 18, 19, 20};
and mini-batches selected using systematic sampling are
- B1 = {16, 17, 18, 19, 20}, B2 = {1, 2, 3, 4, 5}, B3 =
{6, 7, 8, 9, 10} and B4 = {11, 12, 13, 14, 15}. As it is
clear from the above examples, in random sampling with
replacement, points are selected randomly with repetition
inside the mini-batch or within mini-batches. Cyclic sampling is the simplest and non-probabilistic sampling, and
selects the points in a sequential manner. For systematic sampling, first point is selected randomly then the
remaining points are selected back to back, here idea of
replacement and without replacement can be applied between mini-batches but only sampling without replacement
within mini-batches is demonstrated.
It is interesting to note that for RS, data points of the minibatch are dispersed over the different sectors of the disk, so
every data point needs its own seek time and latency time.
Since the data is read block-wise and not content-wise so
it is possible that each data point is present in a different
block and thus needs its own transfer time also. For CS
only one seek time is needed for one mini-batch because it
starts with first data point and then moves till end and for
SS one seek time is needed per mini-batch because only
first element is determined randomly but rest points of the
mini-batch are stored on contiguous memory locations. So,
seek time is the least for CS and the most for RS. The transfer time is almost equal for CS and SS but less as compared
with RS because in RS, generally, each data point needs a
separate transfer time but for other case it needs as many
transfer times as the number of blocks required to fit the
mini-batch of data points. Thus, the overall access time to
access one mini-batch of data points is minimum for CS
and is maximum for RS. It is observed that RS gives the

best solution as compared with the CS for a given number
of epochs but the access time of RS is the most. On the
other hand for CS the access time is the least for a given
number of epoch but the convergence is the slowest. So
there is a trade-off between reducing the data access time
and convergence of learning algorithm. SS balances this
trade-off since SS has the best of both techniques, like CS
the data points are stored on the contiguous memory locations and like RS it has some randomness as it draws the
first point randomly. Overall, methods using CS and SS
converges faster as compared with methods using RS, as
discussed in Sec. 4.
2.2. Learning using Systematic Sampling
A general learning algorithm with systematic sampling
to solve large-scale problems is given by Algorithm 1.
Similar learning algorithms can be obtained for cyclic and
random sampling techniques by using the corresponding
sampling technique for selecting the mini-batch at step 5 of
Algorithm 1. The algorithm starts with the initial solution.
Algorithm 1 A General Learning Algorithm with Systematic Sampling
1: Inputs: m = #mini-batches and n =max #epochs.
2: Initialize: Take initial solution w0 .
3: for k = 1, 2, ..., n do
4:
for j = 1, 2, ..., m do
5:
Select one mini-batch Bj using systematic sam-

pling without replacement.
Formulate a subproblem using mini-batch Bj as
given in eq.(2).
7:
Solve eq.(2) and update the solution.
8:
end for
9: end for

6:

It divides the dataset into m mini-batches using systematic
sampling for selecting mini-batches. Inside the inner
loop, it takes one mini-batch Bj , formulates a subproblem
over Bj and solves the sub-problem thus formed. This
process is repeated until all the sub-problems over all m
mini-batches are solved. Then this solution process is
repeated for the given number of epochs or other stopping
criteria can be used in the algorithm. At step 7 of Algorithm 1, different solvers can be used to update the solution,
like, SAG (Schmidt et al., 2016), SAGA (Defazio et al.,
2014), SVRG (Johnson & Zhang, 2013), SAAG-II
(Chauhan et al., 2017) and MBSGD (Chauhan et al., 2017;
Cotter et al., 2011; Shalev-Shwartz et al., 2011).

3. Theoretical Analysis
The proposed sampling techniques are simple but effective for solving large-scale learning problems with differ-

Faster Algorithms for Large-scale Machine Learning

ent solvers, as discussed in Section 4. The convergence
proof of learning algorithms have been provided using the
simplest solver MBSGD (mini-batched Stochastic Gradient Descent) method with constant step size, for the simplicity of proofs as the focus of study is only on sampling
techniques and not on solvers. l2-regularized ERM problem has been solved under the following assumptions to
demonstrate the efficacy of proposed sampling techniques.
It is assumed that the regularization term is hidden inside
the loss function term for notational convenience otherwise
it needs to write separate gradients for regularization term.
Assumption 1 (LIPSCHITZ CONTINUOUS GRADIENT). Suppose function f : Rn → R is convex and
differentiable on S, and that gradient ∇f is L-Lipschitzcontinuous, where L > 0 is Lipschitz constant, then, we
have,
k∇f (y) − ∇f (x)k ≤ Lky − xk,
(3)
and,

f (y) ≤ f (x) + ∇f (x)T (y − x) +

L
ky − xk2 .
2
(4)

Assumption 2 (STRONG CONVEXITY). Suppose function f : Rn → R is µ-strongly convex function for µ > 0
on S and p∗ is the optimal value of f , then, we have,
f (y) ≥ f (x) + ∇f (x)T (y − x) +
and,

f (x) − p∗ ≤

µ
ky − xk2 ,
2

1
k∇f (x)||2
2µ

(5)
(6)

Theorem 1. Suppose for function given by eq. (1), under Assumptions 1, 2 and constant step size α, and taking
solver MBSGD, Algorithm 1, converges linearly in expectation for cyclic, systematic and sequential sampling techniques.
Proof. By definition of MBSGD, we have,
α X
wk+1 = wk −
∇fi (wk )
|Bj |

(7)

i∈Bj

f (wk+1 )
L
wk+1 − wk
≤ f (wk ) + ∇f (wk )T wk+1 − w +
2


1 P
k
∇f
(w
)
= f (wk ) − α∇f (wk )T
i
|Bj | i∈Bj
2
2
Lα
1 P
+
∇fi (wk ) ,
2
|Bj | i∈Bj



 Lα2 R02
EBj f (wk+1 ) − p∗ ≤ (1 − 2αµ) f (wk ) − p∗ +
2
Applying inequality recursively, we have,


EBj f (wk+1 ) − p∗
 Lα2 R02 Pk
≤ (1 − 2αµ)k+1 f (w0 ) − p∗ +
(1 − 2αµ)i
22 2 i=0
 Lα R0 1
k+1
≤ (1 − 2αµ)
f (w0 ) − p∗ +
.
,
2
2αµ
P∞ i
Pk
i
=
≤
inequality follows since
i=0 r
i=0 r
1
, krk < 1.
1−r


 LαR02
k+1
f (w0 ) − p∗ +
EBj f (wk+1 ) − p∗ ≤ (1 − 2αµ)
.
4µ

Thus, algorithm converges linearly with initial error proportional to α.
Case-II: Mini-batch Bj is selected using Cyclic/Sequential
Sampling (SS)

By L-Lipschitz continuity of gradients,


k

Taking expectation on both sides over mini-batches Bj and
subtracting optimal value (p∗ ), we have,


EBj f (wk+1 ) − p∗


1 P
k
∇f
(w
)
≤ f (wk ) − p∗ − α∇f (wk )T EBj
i
|Bj | i∈Bj
2
2
1 P
Lα
∇fi (wk )
EBj
+
2
|Bj | i∈Bj
Lα2
2
≤ f (wk ) − p∗ − α∇f (wk )T ∇f (wk ) +
kR0 k ,
2


1 P
k
∇f
(w
)
=
inequality follows using EBj
i
|Bj | i∈Bj
2
1 P
k
∇f (wk ) and taking
≤
∇f
(w
)
i
|Bj | i∈Bj
R0 , ∀j, w.


EBj f (wk+1 ) − p∗
Lα2 R02
2
≤ f (wk ) − p∗ − α ∇f (wk ) +
,
2

Lα2 R02
≤ f (wk ) − p∗ − α.2µ f (wk ) − p∗ +
,
2
inequality follows from strong convexity results.

2

equality follows from the definition of MBSGD.
Case-I: Mini-batch Bj is selected using random sampling
(RS) without replacement or Systematic Sampling (SS) without replacement

Taking summation over number of mini-batches and dividing by number of mini-batches (m), and subtracting p∗ , we
have,

1 Pm 
k+1
) − p∗
j=1 f (w
m

1 Pm 
k
∗
≤
j=1 f (w ) − p
m


1 Pm
1 P
k
−α∇f (wk )T
∇f
(w
)
i
m j=1 kBj | i∈Bj
2
2
1 P
Lα 1 Pm
k
,
+
i∈Bj ∇fi (w )
j=1
2 m
|Bj |
Lα2 2
≤ f (wk ) − p∗ − α∇f (wk )T ∇f (wk ) +
R0 ,
2

Faster Algorithms for Large-scale Machine Learning

inequality
follows

1 P
1 Pm
k
∇f
(w
)
= ∇f (wk )
i
m j=1 kBj | i∈Bj
1 P
∇fi (wk ) ≤ R0 .
and
|Bj | i∈Bj
m


1 X
k+1
f (wk+1 ) − p∗ ≤ (1 − 2αµ)
m j=1

since

Table 1. Datasets used in experimentation

Dataset
HIGGS
SUSY
protein
 LαR02 rcv1.binary
0
∗
, ijcnn1
f (w ) − p +
4µ

inequality follows from the Case-I derivation. Thus, algorithm converges linearly with initial error proportional to α.
Hence, theorem is proved.

4. Experiments
4.1. Experimental Setup
Experiments have been performed using five methods,
namely, SAG, SAGA, SAAG-II, SVRG and MBSGD with
five bench marked datasets1 as presented in the Table 3.
Each method has been run with two mini-batches of size
500 and 1000 data points, and two techniques to find step
size, namely, constant step size method and backtracking
line search method for a predefined number of epochs.
Constant step size method uses Lipschitz constant L and
takes step size as 1/L for all methods. Backtracking
line search is performed approximately only using the
selected mini-batch of data points because performing
backtracking line search on whole dataset could hurt
the convergence of learning algorithm for large-scale
problems by taking huge time. For one dataset, one
method runs for 12 times (3(sampling techniques) ∗
2(mini-batches)
∗
2(step size finding techniques)),
and for one dataset, three sampling techniques are
compared on 20 different settings (5(methods) ∗
2(mini-batches) ∗ 2(step size finding techniques)). Thus
100(20 ∗ 5(datasets)) settings have been used to compare
the results for three sampling techniques. As training
time depends on the configuration of machine over which
experiments are performed so this is to be noted that all the
experiments have been conducted on MacBook Air (8GB
1600 MHz DDR3, 256GB SSD, 1.6 GHz Intel Core i5).
4.2. Implementation Details
For each sampling technique, i.e., Random Sampling (RS),
Cyclic Sampling (CS) and Systematic Sampling (SS), same
algorithmic structure is used with difference only in selecting the mini-batch for each sampling technique. And for
each sampling technique, the dataset is divided into predefined number of mini-batches, as per the Algorithm 1. For

#classes
2
2
3
2
2

#features
28
18
357
47,236
22

#datapoints
11,000,000
5,000,000
17,766
20,242
49,990

simplicity, dataset has been divided into equal sized minibatches except the last mini-batch which might has data
points less than or equal to other mini-batches. For RS,
during each epoch, an array of size equal to the number of
data points in the dataset is taken and this array contains
the randomized indexes of data points. To select the minibatches, array contents equal to mini-batch size or till the
end of array, are selected sequentially. For CS, during each
epoch, an array of size equal to the number of data points
in the dataset is taken, containing indexes of data points
in sorted order. To select the mini-batches, array contents
equal to mini-batch size or till the end of array, are selected
sequentially. For SS, during each epoch, an array of size
equal to the number of mini-batches is taken and this array
contains the randomized indexes of mini-batches. To select
a mini-batch, an array element is selected in the sequence.
This array element gives us the first index of data point in
the selected mini-batch. The other data points are selected
sequentially from the starting index of the mini-batch equal
to the size of a mini-batch or till the last data point in the
dataset.
4.3. Results
Experimental results2 plot the difference between objective
function and optimum value against training time for three
sampling techniques, namely, Random Sampling (RS),
Cyclic/Sequential Sampling (CS) and Systematic Sampling
(SS), which are represented by Figs.1–5. To save space,
results for different samplings with constant step size and
backtracking line search methods are plotted in same figure (red color for constant step size and blue for line search
(LS)). As it is clear from figures, 20 different settings over
one dataset compare CS, SS and RS, and prove that methods with CS and SS converges faster than with RS. In general, SS gives the best results as per the intuition but sometimes CS produces better results than SS since CS and SS
are quite similar. The results with constant step size and
backtracking line search methods show similar results. For
larger datasets, like SUSY and HIGGS, SS and CS show
clear advantage over RS, than for smaller dataset and thus
prove the efficacy/suitability of CS and SS for large-scale
2

Experimental
results
can
be
reproduced
datasets used in the experiments are available at:
using
the
code
available
at
following
link:
https://www.csie.ntu.edu.tw/˜cjlin/libsvmtools/datasets/
https://drive.google.com/file/d/0B0eJTvATUWXmb0dVckFtMkdL
1

Faster Algorithms for Large-scale Machine Learning
SUSY-SAG-CvsT-mBatch-500

0

10

-1

10

-2

10

-3

10

-4

10

-5

10

-6

10

SAG-RS-LS
SAG-CS-LS
SAG-SS-LS
SAG-RS
SAG-CS
SAG-SS

0

100

200

300

Objective - Optimal value

10

Objective - Optimal value

learning problems. For some of the results, like, with
HIGGS dataset and SAG method, learning algorithms with
all the sampling techniques converge quickly to same value
but careful examination reveals that CS and SS converges
earlier than RS. Please look into supplementary material
for tabular representation of experiments which represents
couple of tables comparing the training time against objective function value for a given number of epochs.

400

SUSY-SAG-CvsT-mBatch-1000

0

10

-1

10

-2

10

-3

10

-4

10

-5

10

-6

SAG-RS-LS
SAG-CS-LS
SAG-SS-LS
SAG-RS
SAG-CS
SAG-SS

0

50

100

Time (seconds)

5. Conclusion

(a) SUSY-SAG-500

-3

-4

10

-5

10

-6

0

150

200

250

300

10 -2
10

-3

10

-4

10

-5

10

-6

0

50

100

(c) SUSY-SAGA-500

-3

10

-4

10

-5

10

-6

0

50

100

150

200

Objective - Optimal value

10 -2
10

10

SVRG-RS-LS
SVRG-CS-LS
SVRG-SS-LS
SVRG-RS
SVRG-CS
SVRG-SS

10 -1

10

-1

10

-2

SVRG-RS-LS
SVRG-CS-LS
SVRG-SS-LS
SVRG-RS
SVRG-CS
SVRG-SS

10 -3
10 -4
10 -5
10

250

-6

0

50

100

-1

10

-2

10

-3

10

-4

Chauhan, Vinod Kumar, Dahiya, Kalpana, and Sharma,
Anuj. Mini-batch block-coordinate based stochastic average adjusted gradient methods to solve big data problems. In 9th ACML, 2017.

Cotter, Andrew, Shamir, Ohad, Srebro, Nathan, and Sridharan, Karthik. Better Mini-Batch Algorithms via Accelerated Gradient Methods. NIPS, 2011.
Peter.

Importance

0

100

200

300

400

10

-1

10

-2

10

-3

10 -5
10 -6

500

SAAG2-RS-LS
SAAG2-CS-LS
SAAG2-SS-LS
SAAG2-RS
SAAG2-CS
SAAG2-SS

10 -4

0

100

-1

10

-2

10

-3

10

-4

10

-5

10

-6

10

MBSGD-RS-LS
MBSGD-CS-LS
MBSGD-SS-LS
MBSGD-RS
MBSGD-CS
MBSGD-SS

0

50

100

150

200

Time (seconds)

(i) SUSY-MBSGD-500

Objective - Optimal value

10

300

400

(h) SUSY-SAAG-II-1000

SUSY-MBSGD-CvsT-mBatch-500

0

200

Time (seconds)

(g) SUSY-SAAG-II-500
10

250

SUSY-SAAG-II-CvsT-mBatch-1000

0

Time (seconds)

Objective - Optimal value

Chauhan, Vinod Kumar, Dahiya, Kalpana, and Sharma,
Anuj. Problem formulations and solvers in linear svm
- a review. Artificial Intelligence Review, 2018. doi:
https://doi.org/10.1007/s10462-018-9614-6.

10

SAAG2-RS-LS
SAAG2-CS-LS
SAAG2-SS-LS
SAAG2-RS
SAAG2-CS
SAAG2-SS

10 -5
10 -6

200

(f) SUSY-SVRG-1000

Objective - Optimal value

Objective - Optimal value

Chang, Kai-Wei, Hsieh, Cho-Jui, and Lin, Chih-Jen. Coordinate descent method for large-scale l2-loss linear support vector machines. JMLR, 9:1369–1398, 2008.

10

150

Time (seconds)

SUSY-SAAG-II-CvsT-mBatch-500

0

250

SUSY-SVRG-CvsT-mBatch-1000

0

(e) SUSY-SVRG-500
10

200

(d) SUSY-SAGA-1000

SUSY-SVRG-CvsT-mBatch-500

10 0

150

Time (seconds)

Time (seconds)

Byrd, Richard H., Hansen, S. L., Nocedal, Jorge, and
Singer, Yoram. A stochastic quasi-newton method for
large-scale optimization. SIAM Journal on Optimization,
26(2):1008–1031, 2016.

Dominik and Richt,

100

300

SAGA-RS-LS
SAGA-CS-LS
SAGA-SS-LS
SAGA-RS
SAGA-CS
SAGA-SS

10 -1

Time (seconds)

References

Csiba,

50

Objective - Optimal value

Objective - Optimal value

10 -2

10

250

SUSY-SAGA-CvsT-mBatch-1000

10 0

SAGA-RS-LS
SAGA-CS-LS
SAGA-SS-LS
SAGA-RS
SAGA-CS
SAGA-SS

10 -1

10

200

(b) SUSY-SAG-1000

SUSY-SAGA-CvsT-mBatch-500

10 0

Objective - Optimal value

In this paper, novel systematic sampling and cyclic sampling techniques have been proposed, for solving largescale learning problems, for improving the training time by
reducing the data access time. Methods have same convergence in expectation with random, cyclic and systematic
sampling techniques, but with cyclic and systematic sampling the training is up to six times faster than widely used
random sampling technique, at the expense of fractionally
small difference in the minimized objective function value,
for a given number of epochs. Thus, systematic sampling
technique is suitable for solving large-scale problem with
low accuracy solution. Random shuffling of data can be
used before the data is fed to the learning algorithms with
systematic and cyclic sampling to improve their results for
the cases where similar data points are grouped together.
These sampling techniques can be extended to parallel and
distributed learning algorithms.

150

Time (seconds)

250

SUSY-MBSGD-CvsT-mBatch-1000

0

10

-1

10

-2

10

-3

10

-4

10

-5

10 -6

MBSGD-RS-LS
MBSGD-CS-LS
MBSGD-SS-LS
MBSGD-RS
MBSGD-CS
MBSGD-SS

0

50

100

150

200

Time (seconds)

(j) SUSY-MBSGD-1000

Figure 1. Comparison of Random Sampling (RS), Cyclic Sampling (CS) and Systematic Sampling (SS).

Faster Algorithms for Large-scale Machine Learning

4

5

6

-2

10 -3
0

0.5

Time (seconds)

Objective - Optimal value

Objective - Optimal value

-1

10 -2

0

1

2

3

4

10 -2

5

0

0.5

0.35

1

0.3

0.2

2

3

4

0

rcv1-train.binary-SAAG-II-CvsT-mBatch-500

Objective - Optimal value

Objective - Optimal value

10 0

-1

-2

0

0.5

1

1.5

0.5

1

2

2.5

10

10

3

1.5

-1

10

-2

3

1

1.5

2

2

Time (seconds)

(i) rcv1-MBSGD-500

2.5

0

2.5

0

0.5

1

SVRG-RS-LS
SVRG-CS-LS
SVRG-SS-LS
SVRG-RS
SVRG-CS
SVRG-SS

10 -1

10 -2

2

0

1.5

2

0.5

1

ijcnn1-SAAG-II-CvsT-mBatch-1000

10 1

SAAG2-RS-LS
SAAG2-CS-LS
SAAG2-SS-LS
SAAG2-RS
SAAG2-CS
SAAG2-SS

10 0

10 -1

10 -2

10 -3

1.5

0

0.5

0.4

0.6

0.8

1

Time (seconds)

ijcnn1-MBSGD-CvsT-mBatch-1000

10 0

10 -2

0.2

1.5

(h) ijcnn1-SAAG-II-1000

MBSGD-RS-LS
MBSGD-CS-LS
MBSGD-SS-LS
MBSGD-RS
MBSGD-CS
MBSGD-SS

0

1

Time (seconds)

ijcnn1-MBSGD-CvsT-mBatch-500

10 -1

1.5

(f) ijcnn1-SVRG-1000

10 -2

10 0

1

Time (seconds)

10 -1

10 -3

-2

0.5

1.5

SAAG2-RS-LS
SAAG2-CS-LS
SAAG2-SS-LS
SAAG2-RS
SAAG2-CS
SAAG2-SS

0.5

1.5

ijcnn1-SVRG-CvsT-mBatch-1000

Time (seconds)

rcv1-train.binary-MBSGD-CvsT-mBatch-1000

0

1

ijcnn1-SAAG-II-CvsT-mBatch-500

0

1

(d) ijcnn1-SAGA-1000

(g) ijcnn1-SAAG-II-500

10 -1

0.5

Time (seconds)

10 0

3

MBSGD-RS-LS
MBSGD-CS-LS
MBSGD-SS-LS
MBSGD-RS
MBSGD-CS
MBSGD-SS

10

0

10 0

10 1

10 -3

0.5

10 -2

2

Time (seconds)

-2

0

1.5

10 -1

(e) ijcnn1-SVRG-500

-1

10

Objective - Optimal value

Objective - Optimal value

10 -1

1

2.5

1

SVRG-RS-LS
SVRG-CS-LS
SVRG-SS-LS
SVRG-RS
SVRG-CS
SVRG-SS

10

1.5

SAGA-RS-LS
SAGA-CS-LS
SAGA-SS-LS
SAGA-RS
SAGA-CS
SAGA-SS

ijcnn1-SVRG-CvsT-mBatch-500

0

(h) rcv1-SAAG-II-1000

MBSGD-RS-LS
MBSGD-CS-LS
MBSGD-SS-LS
MBSGD-RS
MBSGD-CS
MBSGD-SS

0.5

0.5

Time (seconds)

rcv1-train.binary-MBSGD-CvsT-mBatch-500

0

2

SAAG2-RS-LS
SAAG2-CS-LS
SAAG2-SS-LS
SAAG2-RS
SAAG2-CS
SAAG2-SS

(g) rcv1-SAAG-II-500

10 -2

1.5

rcv1-train.binary-SAAG-II-CvsT-mBatch-1000

Time (seconds)

10 0

0

(f) rcv1-SVRG-1000

SAAG2-RS-LS
SAAG2-CS-LS
SAAG2-SS-LS
SAAG2-RS
SAAG2-CS
SAAG2-SS

10

-3

Time (seconds)

(e) rcv1-SVRG-500
10 0

10

1

ijcnn1-SAGA-CvsT-mBatch-1000

Time (seconds)

0.15

0

10

-2

10

0.25

0.5

(b) ijcnn1-SAG-1000

(c) ijcnn1-SAGA-500

SVRG-RS-LS
SVRG-CS-LS
SVRG-SS-LS
SVRG-RS
SVRG-CS
SVRG-SS

0.4

0

Time (seconds)

10 -1

2.5

rcv1-train.binary-SVRG-CvsT-mBatch-1000

Time (seconds)

10

2

0.45

Objective - Optimal value

Objective - Optimal value

rcv1-train.binary-SVRG-CvsT-mBatch-500

10 -2

4

10 0

(d) rcv1-SAGA-1000

-1

10 -2

1.5

3

SAGA-RS-LS
SAGA-CS-LS
SAGA-SS-LS
SAGA-RS
SAGA-CS
SAGA-SS

Time (seconds)

SVRG-RS-LS
SVRG-CS-LS
SVRG-SS-LS
SVRG-RS
SVRG-CS
SVRG-SS

10

1

2

ijcnn1-SAGA-CvsT-mBatch-500

10 0

10 -1

(c) rcv1-SAGA-500
0

1

10 -1

(a) ijcnn1-SAG-500

SAGA-RS-LS
SAGA-CS-LS
SAGA-SS-LS
SAGA-RS
SAGA-CS
SAGA-SS

Time (seconds)

10

0

SAG-RS-LS
SAG-CS-LS
SAG-SS-LS
SAG-RS
SAG-CS
SAG-SS

Time (seconds)

rcv1-train.binary-SAGA-CvsT-mBatch-1000

10 0
SAGA-RS-LS
SAGA-CS-LS
SAGA-SS-LS
SAGA-RS
SAGA-CS
SAGA-SS

10

2

(b) rcv1-SAG-1000

rcv1-train.binary-SAGA-CvsT-mBatch-500

0

1.5

Time (seconds)

(a) rcv1-SAG-500
10

1

Objective - Optimal value

10

10 -2

Objective - Optimal value

3

-1

Objective - Optimal value

2

ijcnn1-SAG-CvsT-mBatch-1000

10 0
SAG-RS-LS
SAG-CS-LS
SAG-SS-LS
SAG-RS
SAG-CS
SAG-SS

Objective - Optimal value

1

10

ijcnn1-SAG-CvsT-mBatch-500

0

Objective - Optimal value

0

Objective - Optimal value

-2

-1

Objective - Optimal value

10

0

10

10

SAG-RS-LS
SAG-CS-LS
SAG-SS-LS
SAG-RS
SAG-CS
SAG-SS

Objective - Optimal value

-1

10

rcv1-train.binary-SAG-CvsT-mBatch-1000

1

Objective - Optimal value

0

10

10

SAG-RS-LS
SAG-CS-LS
SAG-SS-LS
SAG-RS
SAG-CS
SAG-SS

Objective - Optimal value

10

rcv1-train.binary-SAG-CvsT-mBatch-500

1

Objective - Optimal value

Objective - Optimal value

10

1.2

MBSGD-RS-LS
MBSGD-CS-LS
MBSGD-SS-LS
MBSGD-RS
MBSGD-CS
MBSGD-SS

10 -1

10 -2

10 -3

0

0.2

0.4

0.6

0.8

1

1.2

Time (seconds)

Time (seconds)

(j) rcv1-MBSGD-1000

Figure 2. Comparison of Random Sampling (RS), Cyclic Sampling (CS) and Systematic Sampling (SS).

(i) ijcnn1-MBSGD-500

(j) ijcnn1-MBSGD-1000

Figure 3. Comparison of Random Sampling (RS), Cyclic Sampling (CS) and Systematic Sampling (SS).

Faster Algorithms for Large-scale Machine Learning

1

10 -4

1.5

0

0.5

Time (seconds)

(a) protein-SAG-500

10 -3

0

0.5

1

1.5

2

10 -1

10 -2

10 -3

10 -4

2.5

protein-SVRG-CvsT-mBatch-500

0

0.5

Objective - Optimal value

Objective - Optimal value

10 -3

0.5

1

1.5

2

10 -1

0

Objective - Optimal value

Objective - Optimal value

10 -4

1.5

0.5

2

10

-2

10

-3

10

-4

10

-5

1

1.5

1.5

Time (seconds)

(i) protein-MBSGD-500

2

10

-2

10

-3

10

-4

10

-3

10

-4

10

-5

10

-6

0

200

1

Objective - Optimal value

10

-4

10

-5

10

-6

0

200

10

-3

10

-4

10

-5

10

-6

800

200

300

SAGA-RS-LS
SAGA-CS-LS
SAGA-SS-LS
SAGA-RS
SAGA-CS
SAGA-SS

10 -1
10 -2
10

-3

10

-4

10

-5

10

-6

0

200

2

10

400

10

500

10 -2
10

-1

10

-2

SVRG-RS-LS
SVRG-CS-LS
SVRG-SS-LS
SVRG-RS
SVRG-CS
SVRG-SS

10 -3
10 -4
10 -5
-6

0

200

10

-6

0

2.5

200

400

1.5

600

800

1000

1200

10

-1

10

-2

10

-3

2

Time (seconds)

(j) protein-MBSGD-1000

Figure 4. Comparison of Random Sampling (RS), Cyclic Sampling (CS) and Systematic Sampling (SS).

10

SAAG2-RS-LS
SAAG2-CS-LS
SAAG2-SS-LS
SAAG2-RS
SAAG2-CS
SAAG2-SS

-1

10 -2
10

-3

10 -4
10

-5

10

-6

0

200

400

10

MBSGD-RS-LS
MBSGD-CS-LS
MBSGD-SS-LS
MBSGD-RS
MBSGD-CS
MBSGD-SS

10 -4
-5

200

400

600

800

1000

1200

(h) HIGGS-SAAG-II-1000

HIGGS-MBSGD-CvsT-mBatch-500

0

800

Time (seconds)

(g) HIGGS-SAAG-II-500
0

600

HIGGS-SAAG-II-CvsT-mBatch-1000

10 0

Time (seconds)

10

400

(f) HIGGS-SVRG-1000

-3

-5

800

Time (seconds)

10 -4
10

600

HIGGS-SVRG-CvsT-mBatch-1000

0

10

10

600

SAAG2-RS-LS
SAAG2-CS-LS
SAAG2-SS-LS
SAAG2-RS
SAAG2-CS
SAAG2-SS

-1

400

(d) HIGGS-SAGA-1000

HIGGS-SAAG-II-CvsT-mBatch-500

10 0

800

Time (seconds)

SVRG-RS-LS
SVRG-CS-LS
SVRG-SS-LS
SVRG-RS
SVRG-CS
SVRG-SS

100

600

HIGGS-SAGA-CvsT-mBatch-1000

10 0

HIGGS-SVRG-CvsT-mBatch-500

0

400

(b) HIGGS-SAG-1000

600

10 -2

10 -6

0.5

400

10 -1

10

0

-3

(e) HIGGS-SVRG-500

MBSGD-RS-LS
MBSGD-CS-LS
MBSGD-SS-LS
MBSGD-RS
MBSGD-CS
MBSGD-SS

10 -1

10

Time (seconds)

protein-MBSGD-CvsT-mBatch-1000

10 0

MBSGD-RS-LS
MBSGD-CS-LS
MBSGD-SS-LS
MBSGD-RS
MBSGD-CS
MBSGD-SS

0.5

10 -2

2.5

10 -4

1

-2

SAG-RS-LS
SAG-CS-LS
SAG-SS-LS
SAG-RS
SAG-CS
SAG-SS

Time (seconds)

10 -1

(h) protein-SAAG-II-1000

protein-MBSGD-CvsT-mBatch-500

0

2

10 -3

0.5

800

SAGA-RS-LS
SAGA-CS-LS
SAGA-SS-LS
SAGA-RS
SAGA-CS
SAGA-SS

10 0

10 -2

0

600

HIGGS-SAGA-CvsT-mBatch-500

Time (seconds)

Objective - Optimal value

Objective - Optimal value

10

1.5

10 -1

10 -5

2.5

(g) protein-SAAG-II-500

-1

1

400

10

(c) HIGGS-SAGA-500

SAAG2-RS-LS
SAAG2-CS-LS
SAAG2-SS-LS
SAAG2-RS
SAAG2-CS
SAAG2-SS

Time (seconds)

10 0

200

-1

Time (seconds)

protein-SAAG-II-CvsT-mBatch-1000

10 0

10 -3

1

0

(f) protein-SVRG-1000

SAAG2-RS-LS
SAAG2-CS-LS
SAAG2-SS-LS
SAAG2-RS
SAAG2-CS
SAAG2-SS

0.5

-6

Time (seconds)

protein-SAAG-II-CvsT-mBatch-500

0

2.5

10 -3

10 -4

2.5

10 -2

10 -5

2

10 -2

(e) protein-SVRG-500

10 -1

1.5

SVRG-RS-LS
SVRG-CS-LS
SVRG-SS-LS
SVRG-RS
SVRG-CS
SVRG-SS

Time (seconds)

10 0

1

protein-SVRG-CvsT-mBatch-1000

10 0

SVRG-RS-LS
SVRG-CS-LS
SVRG-SS-LS
SVRG-RS
SVRG-CS
SVRG-SS

0

10

(d) protein-SAGA-1000

10 -2

10 -4

10

-5

Time (seconds)

(c) protein-SAGA-500

10 -1

-4

10 0

SAGA-RS-LS
SAGA-CS-LS
SAGA-SS-LS
SAGA-RS
SAGA-CS
SAGA-SS

Time (seconds)

10 0

10

10

(a) HIGGS-SAG-500

Objective - Optimal value

Objective - Optimal value

Objective - Optimal value

10 -2

10 -4

10

-3

HIGGS-SAG-CvsT-mBatch-1000

0

Time (seconds)

protein-SAGA-CvsT-mBatch-1000

10 0

SAGA-RS-LS
SAGA-CS-LS
SAGA-SS-LS
SAGA-RS
SAGA-CS
SAGA-SS

10 -1

1.5

-2

(b) protein-SAG-1000

protein-SAGA-CvsT-mBatch-500

10 0

1

10

Time (seconds)

Objective - Optimal value

0.5

Objective - Optimal value

0

Objective - Optimal value

10 -5

10 -3

-1

Objective - Optimal value

10 -4

10

-2

10

10

SAG-RS-LS
SAG-CS-LS
SAG-SS-LS
SAG-RS
SAG-CS
SAG-SS

Objective - Optimal value

10 -3

10

HIGGS-SAG-CvsT-mBatch-500

0

Objective - Optimal value

10 -2

-1

10

SAG-RS-LS
SAG-CS-LS
SAG-SS-LS
SAG-RS
SAG-CS
SAG-SS

Objective - Optimal value

Objective - Optimal value

Objective - Optimal value

10 -1

protein-SAG-CvsT-mBatch-1000

10 0

SAG-RS-LS
SAG-CS-LS
SAG-SS-LS
SAG-RS
SAG-CS
SAG-SS

Objective - Optimal value

protein-SAG-CvsT-mBatch-500

10 0

600

Time (seconds)

(i) HIGGS-MBSGD-500

800

HIGGS-MBSGD-CvsT-mBatch-1000

0

10

-1

10

-2

10

-3

10

-4

10

-5

10

-6

MBSGD-RS-LS
MBSGD-CS-LS
MBSGD-SS-LS
MBSGD-RS
MBSGD-CS
MBSGD-SS

0

200

400

600

800

Time (seconds)

(j) HIGGS-MBSGD-1000

Figure 5. Comparison of Random Sampling (RS), Cyclic Sampling (CS) and Systematic Sampling (SS).

Faster Algorithms for Large-scale Machine Learning

Sampling for Minibatches.
2016.
https://arxiv.org/abs/1602.02283.

URL

Csiba, Dominik and Richtárik, Peter. Coordinate Descent Face-Off: Primal or Dual?
2016. URL
https://arxiv.org/abs/1605.08982.
Defazio, Aaron, Bach, Francis, and Lacoste-Julien, Simon.
Saga: A fast incremental gradient method with support
for non-strongly convex composite objectives. In NIPS,
2014.
Gopal, Siddharth. Adaptive Sampling for SGD by Exploiting Side Information. Icml, 2016.
Johnson, Rie and Zhang, Tong. Accelerating stochastic
gradient descent using predictive variance reduction. In
NIPS. 2013.
Konečný, Jakub and Richtárik, Peter.
SemiStochastic Gradient Descent Methods. 2013. URL
http://arxiv.org/abs/1312.1666.
Li, Mu, Zhang, Tong, Chen, Yuqiang, and Smola, Alexander J. Efficient mini-batch training for stochastic optimization. In KDD, 2014.
Madow, William G. On the theory of systematic sampling,
ii. The Annals of Mathematical Statistics, 20:333–354,
1949.
Madow, William G. and Madow, Lillian H. On the theory
of systematic sampling, i. The Annals of Mathematical
Statistics, 15:1–24, 1944.
Needell, Deanna, Ward, Rachel, and Srebro, Nati. Stochastic gradient descent, weighted sampling, and the randomized kaczmarz algorithm. In NIPS. 2014.
Nemirovski, A., Juditsky, A., Lan, G., and Shapiro, A. Robust stochastic approximation approach to stochastic programming. SIAM J. Optim., 19(4):1574–1609, 2009.
Qu, Zheng and Richt, Peter. Randomized Dual Coordinate
Ascent with Arbitrary Sampling. NIPS, 2015.
Reddi, Sashank J. New Optimization Methods for Modern
Machine Learning. PhD thesis, 2016.
Schmidt, Mark, Le Roux, Nicolas, and Bach, Francis. Minimizing finite sums with the stochastic average gradient.
Math. Program., pp. 1–30, 2016.
Shalev-Shwartz, Shai, Singer, Yoram, Srebro, Nathan, and
Cotter, Andrew. Pegasos: primal estimated sub-gradient
solver for svm. Math. Program., 127(1):3–30, 2011.
Tak, Martin, Bijral, Avleen, Richtrik, Peter, and Srebro,
Nathan. Mini-batch primal and dual methods for svms.
In ICML, pp. 537–552, 2013.

Wang, Xiao, Wang, Shuxiong, and Zhang, Hongchao. Inexact proximal stochastic gradient method for convex composite optimization. Computational Optimization and
Applications, 2017.
Wright, Stephen J. Coordinate descent algorithms. Math.
Program., 151(1):3–34, 2015.
Xu, Yangyang and Yin, Wotao. Block stochastic gradient
iteration for convex and nonconvex optimization. SIAM
J. Optim., 25(3):1686–1716, 2015.
Yu, Hsiang-Fu, Hsieh, Cho-Jui, Chang, Kai-Wei, and Lin,
Chih-Jen. Large linear classification when data cannot
fit in memory. In KDD, 2010.
Zhang, Aston and Gu, Quanquan. Accelerated stochastic block coordinate descent with optimal sampling. In
KDD, 2016.
Zhang, Tong. Solving large scale linear prediction problems using stochastic gradient descent algorithms. In
ICML, 2004.
Zhao, Peilin and Zhang, Tong.
Accelerating
Minibatch
Stochastic
Gradient
Descent
using Stratified Sampling.
2014.
URL
http://arxiv.org/abs/1405.3080.
Zhao, Peilin and Zhang, Tong. Stochastic Optimization
with Importance Sampling for Regularized Loss Minimization. ICML, 37, 2015.
Zhou, Lina, Pan, Shimei, Wang, Jianwu, and Vasilakos,
Athanasios V. Machine learning on big data: Opportunities and challenges. Neurocomputing, 237:350 – 361,
2017.

Faster Algorithms for Large-scale Machine Learning

A. Results in tabular form

B. Results with more datasets

10

-1

Objective - Optimal value

SAG-RS-LS
SAG-CS-LS
SAG-SS-LS
SAG-RS
SAG-CS
SAG-SS

10 -2

10

-3

10

-4

0

2

4

6

combined-SAG-CvsT-mBatch-1000

0

10

-1

10

-2

SAG-RS-LS
SAG-CS-LS
SAG-SS-LS
SAG-RS
SAG-CS
SAG-SS

10 -3

10

8

-4

0

2

(a) combined-SAG-500

10

combined-SAGA-CvsT-mBatch-500

0

10
SAGA-RS-LS
SAGA-CS-LS
SAGA-SS-LS
SAGA-RS
SAGA-CS
SAGA-SS

-1

10 -2

10

-3

10

-4

10 -5

0

2

4

6

8

10

-1

10

-2

10

-3

10

-4

SAGA-RS-LS
SAGA-CS-LS
SAGA-SS-LS
SAGA-RS
SAGA-CS
SAGA-SS

0

2

4

-1

10

-2

10

-3

10 -4

combined-SVRG-CvsT-mBatch-500

10

SVRG-RS-LS
SVRG-CS-LS
SVRG-SS-LS
SVRG-RS
SVRG-CS
SVRG-SS

0

2

4

6

10

-1

10

-2

10

-3

10 -4

8

SVRG-RS-LS
SVRG-CS-LS
SVRG-SS-LS
SVRG-RS
SVRG-CS
SVRG-SS

0

2

-1

10

-2

combined-SAAG-II-CvsT-mBatch-500

10

SAAG2-RS-LS
SAAG2-CS-LS
SAAG2-SS-LS
SAAG2-RS
SAAG2-CS
SAAG2-SS

10 -3

10

-4

10

-5

0

5

10

15

20

10

-1

10

-2

SAAG2-RS-LS
SAAG2-CS-LS
SAAG2-SS-LS
SAAG2-RS
SAAG2-CS
SAAG2-SS

10 -3

10

-4

10

-5

0

2

10

-1

10

-2

10

-3

-5

10

-6

combined-MBSGD-CvsT-mBatch-500

2

4

8

10

6

Time (seconds)

(i) combined-MBSGD-500

combined-MBSGD-CvsT-mBatch-1000

10 0

MBSGD-RS-LS
MBSGD-CS-LS
MBSGD-SS-LS
MBSGD-RS
MBSGD-CS
MBSGD-SS

0

6

(h) combined-SAAG-II-1000

10 -4
10

4

Time (seconds)

(g) combined-SAAG-II-500
0

8

combined-SAAG-II-CvsT-mBatch-1000

0

Time (seconds)

10

6

(f) combined-SVRG-1000

Objective - Optimal value

Objective - Optimal value

10

4

Time (seconds)

(e) combined-SVRG-500
0

10

combined-SVRG-CvsT-mBatch-1000

0

Time (seconds)

10

8

(d) combined-SAGA-1000

Objective - Optimal value

Objective - Optimal value

10

6

Time (seconds)

(c) combined-SAGA-500
0

8

combined-SAGA-CvsT-mBatch-1000

0

Time (seconds)

10

6

(b) combined-SAG-1000

Objective - Optimal value

Objective - Optimal value

10

4

Time (seconds)

Objective - Optimal value

Results with SUSY dataset are presented in Table 4. As it
is clear from the table, it shows good results like HIGGS
dataset. CS and SS techniques are faster than RS technique
by around two to four times while the objective function
values are same up to three to eight decimal places. Methods with constant step and with backtracking line search
show similar trends for the results.

10

combined-SAG-CvsT-mBatch-500

0

Time (seconds)

Objective - Optimal value

Experimental results can be presented using tables comparing the training time and objective function value, for given
number of epochs (number of passes through dataset), for
CS, SS and RS. Since it is easy to understand the graphs
so experiments are documented using figures. Results for
SUSY and HIGGS are also represented using Tables 2 and
4, which prove faster training for CS and SS than RS, while
their values are same up to certain decimal places. As it is
clear from the table, SAG method with mini-batch of size
200 and constant step size, the training time for Systematic
Sampling (SS) and Cyclic Sampling (CS) are faster than
for Random Sampling (RS) by a factor of more than three
while the values of objective function are same up to four
decimal places. The training times for SS and CS are very
close as expected. For mini-batch of 1000 data points and
constant step size, SAG method runs three and half times
faster for SS and CS as compared with RS while the values of objective function are same up to six decimal places.
With backtracking line search for determining the step size,
SAG method runs more than two times faster with minibatch of 200 and more than three and half times with minibatch of size 1000, for SS and CS as compared with RS
while the values of objective function are same up to eight
decimal places. SAGA with constant step size runs more
than two times faster with mini-batches of 200 and 1000
for CS and SS as compared with RS while the values of objective function are same up to five and four decimal places
for mini-batches of 200 and 1000, respectively. With backtracking line search, SAGA performs even better for CS
and SS and runs more than two times faster with mini-batch
of 200 and more than three and half times with mini-batch
of size 1000 as compared with RS while the values of objective function are same up to eight decimal places with
mini-batch of size 200 and up to six decimal places with
mini-batch of size 1000. Similar trend are followed for
SAAG-II, SVRG and MBSGD methods where CS and SS
are around two to more than three and half times faster and
objective values are same up to six to nine decimal places
as compared with RS with constant step and backtracking
line search (LS).

Objective - Optimal value

10

8

10

-1

10

-2

MBSGD-RS-LS
MBSGD-CS-LS
MBSGD-SS-LS
MBSGD-RS
MBSGD-CS
MBSGD-SS

10 -3

10 -4

10

-5

0

2

4

6

8

10

Time (seconds)

(j) combined-MBSGD-1000

Figure 6. Comparison of Random Sampling (RS), Cyclic Sampling (CS) and Systematic Sampling (SS).

Faster Algorithms for Large-scale Machine Learning

Table 2. Comparison of Training Time (in seconds) and objective function values after 30 epochs using dataset HIGGS

Method

SAG

SAGA

SAAG-II

SVRG

MBSGD

Sampling
RS
CS
SS
RS
CS
SS
RS
CS
SS
RS
CS
SS
RS
CS
SS
RS
CS
SS
RS
CS
SS
RS
CS
SS
RS
CS
SS
RS
CS
SS

Batch
200

1000

200

1000

200

1000

200

1000

200

1000

Constant Step
Time
Objective
229.220102 0.3258410619
66.378361 0.3258375894
67.867812 0.3258410840
234.129248 0.3258356616
63.957239 0.3258358353
65.908254 0.3258356562
302.318358 0.3258637650
147.235962 0.3258659974
148.402540 0.3258636638
301.003253 0.3259746991
145.917197 0.3259814282
147.646753 0.3259748885
297.134694 0.3263398874
174.232600 0.3263398971
176.845275 0.3263398982
299.840227 0.3258550019
171.384496 0.3258550023
172.268358 0.3258550036
297.620959 0.3258923266
172.405902 0.3258923398
172.612984 0.3258923141
297.259155 0.3261069018
172.227776 0.3261069217
172.601618 0.3261068804
267.252470 0.3258635308
144.769059 0.3258635315
140.241334 0.3258635313
268.102817 0.3259704996
139.586141 0.3259704998
135.646766 0.3259704994

Line Search
Time
Objective
495.873963 0.3258353956
214.083371 0.3258353935
214.533017 0.3258353956
535.821883 0.3258354793
126.807235 0.3258354785
148.786983 0.3258354792
432.787547 0.3258353922
182.545531 0.3258353924
177.698227 0.3258353937
445.741781 0.3258354946
112.433248 0.3258355048
120.481113 0.3258354828
708.881659 0.3258353918
380.852014 0.3258353920
338.122579 0.3258353920
687.638964 0.3258354037
209.564000 0.3258354039
213.877001 0.3258354041
406.229956 0.3258354055
213.151577 0.3258354059
185.538374 0.3258354064
497.501496 0.3258357363
159.518159 0.3258357365
151.230547 0.3258357352
312.865696 0.3258353862
121.004686 0.3258353865
122.396247 0.3258353867
306.236327 0.3258354906
82.340378 0.3258354912
81.486252 0.3258354909

Table 3. More Datasets used in experimentation

Dataset
SensIT Vehicle
(combined)
mnist
covtype.binary

#classes
3

#features
100

#datapoints
78,823

10
2

780
54

60,000
581,012

Faster Algorithms for Large-scale Machine Learning

Table 4. Comparison of Training Time (in seconds) and objective function values after 30 epochs using dataset SUSY

Method

SAG

SAGA

SAAG-II

SVRG

MBSGD

Sampling
RS
CS
SS
RS
CS
SS
RS
CS
SS
RS
CS
SS
RS
CS
SS
RS
CS
SS
RS
CS
SS
RS
CS
SS
RS
CS
SS
RS
CS
SS

Batch
200

1000

200

1000

200

1000

200

1000

200

1000

Constant Step
Time
Objective
84.331058 0.3759925588
20.571099 0.3759958448
20.380268 0.3759925419
86.462106 0.3761630312
19.652540 0.3764117775
23.803318 0.3761654289
119.419700 0.3761615578
49.054361 0.3761668056
50.032764 0.3761616154
115.240795 0.3767228974
48.484855 0.3767380851
53.076179 0.3767231692
122.687745 0.3761359459
57.748874 0.3761359525
58.840208 0.3761359506
114.239646 0.3759934574
58.377580 0.3759934575
67.017390 0.3759934576
128.216331 0.3763077569
57.819864 0.3763078069
60.425710 0.3763079011
112.850682 0.3773260313
58.064456 0.3773259828
66.207054 0.3773261006
101.673967 0.3761560102
47.587231 0.3761559893
48.042649 0.3761559954
103.513668 0.3766979888
47.346182 0.3766979329
55.683464 0.3766979490

Line Search
Time
Objective
267.199348 0.3759914171
96.172599 0.3759912712
136.218536 0.3759914133
261.746213 0.3759920053
45.862451 0.3759919137
56.056274 0.3759920025
244.424858 0.3759911729
88.012460 0.3759911528
125.125252 0.3759911723
218.120526 0.3759920084
41.586102 0.3759920131
47.792283 0.3759919544
319.227862 0.3759910754
150.975243 0.3759910741
156.970161 0.3759910768
336.178564 0.3759912580
88.889686 0.3759912583
88.760368 0.3759912574
215.183518 0.3759913085
88.178545 0.3759913110
98.404560 0.3759913135
192.681710 0.3759936315
57.283939 0.3759936439
58.508361 0.3759936213
174.388236 0.3759910145
58.634676 0.3759910107
63.347389 0.3759910169
128.650218 0.3759918962
31.396945 0.3759918950
41.701046 0.3759918931

Faster Algorithms for Large-scale Machine Learning

10

-6

0

2

4

6

8

10

-5

10 -6

10

5

-1

10

-2

10

-3

10

-4

10

-5

10

-6

10

SAGA-RS-LS
SAGA-CS-LS
SAGA-SS-LS
SAGA-RS
SAGA-CS
SAGA-SS

0

5

10

15

20

25

Objective - Optimal value

Objective - Optimal value

10

30

10

-1

10

-2

10

-3

10

-4

10

-4

10

-5

10

-6

0

5

10

15

20

10

25

10

10

-3

10

-4

10

-5

10

mnist-SAAG-II-CvsT-mBatch-500

-6

5

10

-3

10

-4

10

-5

10

-6

0

5

15

20

-2

10

-3

10

-4

10

-5

10

25

-1

10

-2

10

10

mnist-MBSGD-CvsT-mBatch-500

10

MBSGD-RS-LS
MBSGD-CS-LS
MBSGD-SS-LS
MBSGD-RS
MBSGD-CS
MBSGD-SS

-4

-5

0

2

4

6

15

20

10

-6

10

-8

10

-10

10

-12

10

8

10

Time (seconds)

(i) mnist-MBSGD-500

12

-3

10

-4

10 -5

0

2

4

6

8

40

50

60

10

20

30

10

40

10 -4
10

-6

10

-8

50

10

-6

10

-8

10

-10

10

-12

40

60

0

20

10

-2

10

-4

10

-6

10

-8

10

-10

10

-12

-4

10

-6

10

-8

20

30

60

SVRG-RS-LS
SVRG-CS-LS
SVRG-SS-LS
SVRG-RS
SVRG-CS
SVRG-SS

-10

0

10

20

30

40

50

80

-2

10

-4

10

-6

SAAG2-RS-LS
SAAG2-CS-LS
SAAG2-SS-LS
SAAG2-RS
SAAG2-CS
SAAG2-SS

10 -8
10 -10
10 -12

100

covtype.binary-SAAG-II-CvsT-mBatch-1000

0

10

0

20

40

60

80

Time (seconds)

(h) covtype-SAAG-II-1000
10

40

Time (seconds)

50

covtype.binary-MBSGD-CvsT-mBatch-1000

0

10

-2

10

-4

10

-6

10

-8

10

10

50

covtype.binary-SVRG-CvsT-mBatch-1000

0

10

10

MBSGD-RS-LS
MBSGD-CS-LS
MBSGD-SS-LS
MBSGD-RS
MBSGD-CS
MBSGD-SS

0

40

(f) covtype-SVRG-1000

covtype.binary-MBSGD-CvsT-mBatch-500

0

30

Time (seconds)

(g) covtype-SAAG-II-500

10

10

Time (seconds)

10

30

SAGA-RS-LS
SAGA-CS-LS
SAGA-SS-LS
SAGA-RS
SAGA-CS
SAGA-SS

10 -2

10

60

-12

20

25

covtype.binary-SAGA-CvsT-mBatch-1000

10 -4

10

10 -10

0

20

(d) covtype-SAGA-1000

SAAG2-RS-LS
SAAG2-CS-LS
SAAG2-SS-LS
SAAG2-RS
SAAG2-CS
SAAG2-SS

-2

15

Time (seconds)

covtype.binary-SAAG-II-CvsT-mBatch-500

0

30

10 -2

10

10

10 -2

(e) covtype-SVRG-500

MBSGD-RS-LS
MBSGD-CS-LS
MBSGD-SS-LS
MBSGD-RS
MBSGD-CS
MBSGD-SS

10 -1

5

Time (seconds)

mnist-MBSGD-CvsT-mBatch-1000

0

0

10 0

SVRG-RS-LS
SVRG-CS-LS
SVRG-SS-LS
SVRG-RS
SVRG-CS
SVRG-SS

0

20

25

30

10 -4

10

5

20

10 -2

(h) mnist-SAAG-II-1000

10 -3

10

10

Time (seconds)

Objective - Optimal value

Objective - Optimal value

10

15

SAAG2-RS-LS
SAAG2-CS-LS
SAAG2-SS-LS
SAAG2-RS
SAAG2-CS
SAAG2-SS

0

-10

(b) covtype-SAG-1000

covtype.binary-SVRG-CvsT-mBatch-500

10 0

-6

(g) mnist-SAAG-II-500
0

10

10 -1
10

-8

Time (seconds)

mnist-SAAG-II-CvsT-mBatch-1000

0

10

(c) covtype-SAGA-500

SVRG-RS-LS
SVRG-CS-LS
SVRG-SS-LS
SVRG-RS
SVRG-CS
SVRG-SS

Time (seconds)

10

0

25

mnist-SVRG-CvsT-mBatch-1000

10 -2

10

SAAG2-RS-LS
SAAG2-CS-LS
SAAG2-SS-LS
SAAG2-RS
SAAG2-CS
SAAG2-SS

0

20

(f) mnist-SVRG-1000

Objective - Optimal value

Objective - Optimal value

-2

15

-1

10

10 -6

10

25

SAGA-RS-LS
SAGA-CS-LS
SAGA-SS-LS
SAGA-RS
SAGA-CS
SAGA-SS

Time (seconds)

10 -1
10

-8

-12

(e) mnist-SVRG-500
0

-6

10

10

Time (seconds)

10

10

10

0

10 -4

Time (seconds)

10 -4

-6

10

20

10 -2

-5

5

15

covtype.binary-SAGA-CvsT-mBatch-500

10 0

10

0

10

SAG-RS-LS
SAG-CS-LS
SAG-SS-LS
SAG-RS
SAG-CS
SAG-SS

-2

(a) covtype-SAG-500

-10

10

SVRG-RS-LS
SVRG-CS-LS
SVRG-SS-LS
SVRG-RS
SVRG-CS
SVRG-SS

10 -2
-3

5

10

covtype.binary-SAG-CvsT-mBatch-1000

0

Time (seconds)

(d) mnist-SAGA-1000

mnist-SVRG-CvsT-mBatch-500

-1

10

0

Time (seconds)

Objective - Optimal value

Objective - Optimal value

10

-10

20

SAGA-RS-LS
SAGA-CS-LS
SAGA-SS-LS
SAGA-RS
SAGA-CS
SAGA-SS

(c) mnist-SAGA-500
0

15

mnist-SAGA-CvsT-mBatch-1000

0

Time (seconds)

10

10

-8

(b) mnist-SAG-1000

mnist-SAGA-CvsT-mBatch-500

0

10

Time (seconds)

(a) mnist-SAG-500
10

10 -6

10

0

Time (seconds)

Objective - Optimal value

-4

10 -4

Objective - Optimal value

10 -5

10

-2

Objective - Optimal value

-4

-3

10

SAG-RS-LS
SAG-CS-LS
SAG-SS-LS
SAG-RS
SAG-CS
SAG-SS

Objective - Optimal value

10

10

10

covtype.binary-SAG-CvsT-mBatch-500

0

Objective - Optimal value

-3

-2

Objective - Optimal value

10

10

Objective - Optimal value

-2

-1

Objective - Optimal value

10

10

10

SAG-RS-LS
SAG-CS-LS
SAG-SS-LS
SAG-RS
SAG-CS
SAG-SS

Objective - Optimal value

-1

Objective - Optimal value

Objective - Optimal value

10

mnist-SAG-CvsT-mBatch-1000

10 0

SAG-RS-LS
SAG-CS-LS
SAG-SS-LS
SAG-RS
SAG-CS
SAG-SS

Objective - Optimal value

mnist-SAG-CvsT-mBatch-500

10 0

MBSGD-RS-LS
MBSGD-CS-LS
MBSGD-SS-LS
MBSGD-RS
MBSGD-CS
MBSGD-SS

-10

10 -12

0

10

20

30

40

Time (seconds)

Time (seconds)

(j) mnist-MBSGD-1000

Figure 7. Comparison of Random Sampling (RS), Cyclic Sampling (CS) and Systematic Sampling (SS).

(i) covtype-MBSGD-500

(j) covtype-MBSGD-1000

Figure 8. Comparison of Random Sampling (RS), Cyclic Sampling (CS) and Systematic Sampling (SS).

