where $\bm{x}=(\bm{x}_{1},\bm{x}_{2})$, $\bm{x}_{1}=(a,b)$,
$\bm{x}_{2}=(y_{1},\ldots,y_{d_{2}})$,
$\Omega_{\bm{x}_{1}}=[-1.5,1.5]\times[50,150]$,
$\Omega_{\bm{x}_{2}}=[-2,2]^{d_{2}}$. The function is similar to a banana
distribution which is quite difficult to approximate. The cost function
$C(\bm{x})$ for a specified $(a,b)$ has a unique global minima at
$(a,a^{2},\ldots,a,a^{2})$. However, if we do not initialize the solution from
the parabolic valley area (see Figure 16), a gradient-based solver will have
difficulty in converging to the global optima quickly. We can see from Figure
16 that TTGO samples are concentrated around this region, allowing most of
them to reach the global optima after refinement. In fact, by increasing the
$\alpha$, the TTGO samples are already very close to the global optima (as
shown in red).

Figure 17 shows how the task parameters $\bm{x}_{1}=(a,b)$ change the shape of
the function with respect to $\bm{x}_{2}$ and consequently the location of the
global optima. After the offline training, we condition our TT model on these
task parameters and sample from the conditional distribution
$\text{Pr}(\bm{x}_{2}|\bm{x}_{1}=(a,b))$. We can see in this figure that TTGO
can adapt to the new task parameters easily, as the samples are concentrated
around the new global optima.

We also test TTGO performance on Rosenbrock functions for $d_{2}$ up to $30$
and find that it can find the global optima consistently. We show in the
figures the results for the 2D case, which are easier to visualize.

####  A.2.3 Himmelblau’s function:

$\displaystyle C(a,b,y_{1},y_{2})$
$\displaystyle=(y_{1}^{2}+y_{2}-a)^{2}+(y_{1}+y_{2}^{2}-b)^{2}$ $\displaystyle
P(\bm{x})$ $\displaystyle=\exp(-C(\bm{x})^{2}),$

where $\bm{x}=(\bm{x}_{1},\bm{x}_{2})$, $\bm{x}_{1}=(a,b)$,
$\bm{x}_{2}=(y_{1},y_{2})$, $P(\bm{x})=\exp(-C(\bm{x}))$,
$\Omega_{\bm{x}_{1}}=[0,15]^{2}$, $\Omega_{\bm{x}_{2}}=[-5,5]^{2}$. The cost
function $C(a,b,y_{1},y_{2})$ for a given $(a,b)$ has multiple distinct global
optima and many local optima. The samples from the TT distribution
$\text{Pr}(\bm{x}_{2}|\bm{x}_{1}=(a,b))$ are shown in Figure 18–19 for
different choice of task parameters and the prioritized sampling parameters
$\alpha$. We can see that TTGO can generate samples from all of the modes
consistently according to the task parameters.

####  A.2.4 Mixture of Gaussians:

$P(\bm{x})=\sum_{j=1}^{J}\alpha_{j}\exp(-\beta_{j}||\bm{x}-\bm{a}_{j}||^{2}),$

We use an unnormalized mixture of Gaussian functions to define the probability
function $P(\bm{x})$ to test our framework for high-dimensional multimodal
functions. For verification, we design the mixture components so that we know
the global optima _a priori_ by carefully choosing the centers, mixture
coefficients and variances. We test it for various values for the number of
mixtures $J$, $\beta\in[1,1000]$ and the dimension $d\in(2,\ldots,50)$ of
$\bm{x}$. We choose $\bm{x}=(\bm{x}_{1},\bm{x}_{2})$ with
$\Omega_{\bm{x}}=[-2,2]^{d}$ for various choices of values and dimension of
$\bm{x}$. As TTGO does not differentiate between task parameters and
optimization variables internally, we could consider various possibilities to
segment $\bm{x}$ into $(\bm{x}_{1},\bm{x}_{2})$ as task parameters and
decision variables. We tested this problem for $d<100$, and our approach could
consistently find the optima with less than $100$ samples from the TT-model,
for arbitrary choice of variables being conditioned as task parameters. In
contrast, finding the optima using Newton-type optimization with random
initialization is highly unlikely for $\beta_{j}>1$ and $d>10$, even after
considering millions of samples from uniform distribution for initialization.

Figure 20 shows one particular example with $J=10$, $\beta_{j}=175$ and
$d=50$. To visualize, we choose $\bm{x}_{1}\in\mathbb{R}^{d-2}$ and
$\bm{x}_{2}\in\mathbb{R}^{2}$, and we generate 1000 samples from the
conditional TT distribution $\text{Pr}(\bm{x}_{2}|\bm{x}_{1})$. With low
values of $\alpha$, the samples are generated around all the different modes,
but as $\alpha$ is increased, the samples become more concentrated around the
mode with the highest probability.

(a) $\alpha=0$

(b) $\alpha=0.5$

(c) $\alpha=0.75$

(d) $\alpha=0.9$

Figure 15: $1000$ samples (shown as blue dots) from the TT distribution of a
2D sinusoidal function for different values of $\alpha$. The function has an
infinite number of global optima (on the dark circles) and we see that TTGO is
able to sample from these regions. As we increase $\alpha$, the samples become
more concentrated on the circles.

(a) $(a,b)=(1,100)$

(b) $(a,b)=(0,140)$

(c) $(a,b)=(0.5,60)$

(d) $(a,b)=(-1,100)$

Figure 16: $1000$ samples from the conditional TT distribution of a Rosenbrock
function for various choices of the task parameters $(a,b)$ and $\alpha=0$.
The function has a unique global optimum at $(a,a^{2})$ as shown in red. As
the task parameters change, the global optimum moves accordingly, but TTGO is
still able to sample from the high-density regions.

(a) $\alpha=0$

(b) $\alpha=0.5$

(c) $\alpha=0.75$

(d) $\alpha=0.9$

Figure 17: $1000$ samples from the conditional TT distribution of a Rosenbrock
function with the task parameters $a=1,b=100$ and various values of $\alpha$.
As $\alpha$ increases, the samples become more concentrated around the global
optimum (as shown in red).

(a) $(a,b)=(3,3)$

(b) $(a,b)=(3,14)$

(c) $(a,b)=(7,11)$

(d) $(a,b)=(13,5)$

Figure 18: $1000$ samples from the conditional TT distribution of a 2D
Himmelblau function for various choices of the task parameters $(a,b)$ and
$\alpha=0$. The location of the multiple global optima (in red) depend on the
task parameters, but TTGO is able to generate the samples from the high-
density regions.

(a) $\alpha=0$

(b) $\alpha=0.5$

(c) $\alpha=0.9$

(d) $\alpha=1$

Figure 19: $1000$ samples from the conditional TT distribution of a 2D
Himmelblau function with task parameters $a=7,b=11$ for various values of
$\alpha$. As $\alpha$ increases, the samples become more concentrated around
the global optima.

(a) $\alpha=0$

(b) $\alpha=0.5$

(c) $\alpha=0.75$

(d) $\alpha=0.9$

Figure 20: $1000$ samples from the conditional TT distribution of a mixture of
Gaussians with $J=10$, $d=50$, $\beta_{j}=175$, and various values of
$\alpha$. For visualization, we choose the the first $d-2$ coordinates of
$\mu_{j}$ to be the same for all $j$ and choose the task-parameters to be the
first $d-2$ coordinate of the centers. This density function has one global
optimum (in red) and some other modes that are comparable to the global
optimum. As $\alpha$ increases, the samples become more concentrated around
the mode with the highest density.

###  A.3 Inverse Kinematics Formulation

The cost function for the inverse kinematics problem in Section 5.1.2 is given
by

$C(\bm{x})=\frac{1}{3}\Big{(}\frac{C_{p}(\bm{\theta},\bm{p}_{d})}{\beta_{p}}+\frac{C_{\text{obst}}(\bm{\theta})}{\beta_{\text{obst}}}+\frac{C_{\text{orient}}(\bm{\theta})}{\beta_{\text{orient}}}\Big{)},$
(16)

where $\bm{x}=(\bm{x}_{1},\bm{x}_{2})$ and:

  * •

$C_{p}(\bm{\theta},\bm{p}_{d})=\|\bm{p}_{d}-\bm{p}(\bm{\theta})\|$, Euclidean
distance of the end effector position from the desired position.

  * •

$C_{\text{obst}}(\bm{\theta})$ represents the obstacle cost based on the
Signed Distance Function (SDF). The links are approximated as a set of spheres
(as done in CHOMP), and we use the SDF to compute the distance from each
sphere to the nearest obstacle.

  * •

$C_{\text{orient}}(\bm{\theta})$ represents the cost on the orientation of the
end-effector. In our application, we specify a desired orientation of the end-
effector, given by quaternion $\bm{q}_{d}$, while allowing a rotation around
the axis of rotation $\bm{v}_{d}$ which corresponds to the z-axis of the world
frame. This constraints the gripper orientation to be horizontal while
allowing rotation around the z-axis. This is suitable for picking cylindrical
objects from a shelf. The cost is then
$C_{\text{orient}}(\bm{\theta})=1-<\bm{v}(\bm{\theta}),\bm{v}_{d}>^{2}$ where
$\bm{v}(\bm{\theta})$ represents the screw axis (computed from the quaternion)
of the actual end-effector frame w.r.t. the desired frame. Alternatively, if
the application demands a variation in the desired orientation, one could use
the pose $(\bm{p}_{d},\bm{q}_{d})$ directly as the task parameter.

  * •

$\beta_{p},\beta_{\text{obst}},\beta_{\text{orient}}$ are scaling factors for
each cost. Intuitively, they represent the acceptable value for each cost. We
use $\beta_{p}=0.05$, $\beta_{\text{obst}}=0.01$ , and
$\beta_{\text{orient}}=0.2$ for the orientation.

For the IK problem of the 6-DoF UR10 robot, there is no obstacle cost, and the
orientation is specified to be identity (corresponding to upward-facing end-
effector orientation) without any free axis of rotation.

###  A.4 Motion Planning Formulation

For both the reaching and the pick-and-place tasks, the cost function,
$\bm{x}=(\bm{x}_{1},\bm{x}_{2})$, is given by

$\footnotesize
C(\bm{x})=\frac{1}{4}\Big{(}\frac{C_{p}(\bm{x})}{\beta_{p}}+\frac{C_{\text{obst}}(\bm{x})}{\beta_{\text{obst}}}+\frac{C_{\text{orient}}(\bm{x})}{\beta_{\text{orient}}}+\frac{C_{\text{control}}(\bm{x})}{\beta_{\text{control}}}\Big{)}$
(17)

with the following objectives:

  * •

$C_{p}(\bm{x})$ represents the cost on the end effector position(s) from the
target location(s).

  * •

$C_{\text{obst}}(\bm{x})$ represents the cost incurred from the obstacles
computed using SDF as in Section 5.1.2 but accumulated for the whole motion.

  * •

$C_{\text{orient}}(\bm{x})$ represents the cost on the orientation of the end
effector at the target location(s).

  * •

$C_{\text{control}}(\bm{x})$ represents the cost of the length of the joint
angle trajectory and the length of the end effector trajectory.

  * •

$\beta_{p},\beta_{\text{obst}},\beta_{\text{orient}},\beta_{\text{control}}$
are scaling factors for each cost. Intuitively, they represent the acceptable
nominal cost value for each cost. We use $\beta_{p}=0.05$,
$\beta_{\text{obst}}=0.1$, $\beta_{\text{orient}}=0.2$,
$\beta_{\text{control}}=2$.

We consider the initial configuration of the manipulator to be fixed (we can
relax this condition by considering the initial configuration as a task
parameter). In the reaching task, the objective is to reach an end effector
target location on the shelf. In the pick-and-place task, the objective is to
reach a target on the shelf to pick an object, then move to another target
above the box to place the object, and finally move back to the initial
configuration.

Instead of considering the target in configuration space, we focus on
Cartesian space, which presents unique challenges for optimization-based
motion planning solvers. Reaching a target in configuration space typically
yields a clear gradient to the solver, whereas reaching a Cartesian target
poses a more difficult optimization problem due to the larger solution space,
as the target may correspond to multiple configurations. A gradient-based
solver will attempt to reach the target with the configuration that is closest
to the initial configuration, particularly if initialized with a stationary
trajectory at the initial configuration. However, if this solution is
infeasible, it is challenging for the solver to find a different solution with
a final configuration significantly different from the initial one, unless
initialized well. One alternative approach is to use inverse kinematics (IK)
to identify several possible final configurations, then use motion planning
solvers to reach those configurations. However, it is not easy to select good
configurations as the target, as it is difficult to determine whether a
specific configuration is reachable from the initial configuration. Moreover,
even when a solution is found, it may be highly suboptimal.

Our approach involves tackling both the IK problem and motion planning problem
concurrently, with decision variables comprising the robot configuration(s)
for the Cartesian target(s) and the joint angle trajectory needed to achieve
those configurations. While optimizing both simultaneously can be challenging,
our TTGO formulation enables us to obtain multiple solutions. To simplify the
problem’s complexity, we use motion primitives to represent the joint angle
trajectory, as outlined in Appendix A.5. By utilizing our motion primitives
formulation and given the initial and final configurations, we ensure that the
movement always starts from the initial configuration and ends at the final
configuration while complying with joint limitations.

Consider an $m$-DoF manipulator. The configuration of the manipulator can be
represented using the joint angles
$\bm{\theta}=(\theta_{1},\ldots,\theta_{m})\in\mathbb{R}^{m}$. We can assume
that the domain of the joint angles is bounded by a rectangular domain
$\Omega_{\bm{\theta}}=\times_{i=1}^{m}[\theta_{{\min}_{i}},\theta_{{\max}_{i}}]$.
We represent the trajectory evolution in terms of the phase of the motion,
i.e., $t\in(0,1)$ with $t=1$ representing the end of the motion.

###  A.5 Motion Primitives

In our motion planning formulation, we generate motions using a basis function
representation that satisfies the boundary conditions (with respect to
phase/time) and the limits of the trajectory (the magnitude) while maintaining
zero velocity at the boundary. Suppose we are given a choice of basis
functions $\bm{\phi}=(\phi_{k})^{J}_{j=1},\phi_{j}(t)\in\mathbb{R},\forall
t\in[0,1]$. For example, we could use radial basis functions
$\phi_{j}(t)=\exp(-\gamma(t-\mu_{j})^{2})$ with
$\mu_{j}\in[0,1],\gamma\in\mathbb{R}^{+}$. We define a trajectory using a
weighted combination of these basis functions as
$\hat{\tau}(t)=\sum_{j=1}^{J}w_{j}\phi_{j}(t)$. We transform this trajectory
so that the boundary conditions and joint limits are satisfied.

Given the trajectory $\hat{\tau}(t),t\in[0,1]$, and the boundary conditions
$\tau(0)=\tau_{0},\tau(1)=\tau_{1}$ and the limits
$\tau_{\min}\leq\tau(t)\leq\tau_{\max}$, we can transform $\hat{\tau}(t)$ to
obtain a trajectory
$\tau(t)=\Psi(\hat{\tau}(t),\tau_{0},\tau_{1},\tau_{\min},\tau_{\max})$ such
that $\tau(0)=\tau_{0}$, $\tau(1)=\tau_{1}$ and
$\tau_{\min}\leq\tau(t)\leq\tau_{\max}$. We define the transformation $\Psi$
as follows:

  1. 1.

Input: $\hat{\tau},\tau_{0},\tau_{1},\tau_{\min},\tau_{\max}$

  2. 2.

Discretize the time interval $[0,1]$ uniformly to obtain
$\\{t_{i}\\}_{i=0}^{N}$ so that $dt=t_{i+1}-t_{i}$,
$t\in\\{t_{i}\\}_{i=0}^{N}$.

  3. 3.

Define
$\hat{z}(t)=\hat{\tau}(t)+\tau_{0}-\hat{\tau}(0)+t(\tau_{1}-\tau_{0}+\hat{\tau}(0)-\hat{\tau}(1))$,
which satisfies the specified boundary conditions.

  4. 4.

Clip the trajectory within the joint limits to obtain
$z(t)=\text{clip}(\hat{z}(t),\tau_{\min},\tau_{\max})$. The clipping will
result in non-smoothness.

  5. 5.

Smoothen the trajectory $z(t)$ to obtain the desired trajectory $\tau(t)$: To
do this, we append the trajectory $z(t)$ with the same values as initial value
in the beginning and with the final value at the end. Then we can apply a
moving average filter over the trajectory. This creates the desired smooth
trajectory $\tau(t)$ that has zero velocity at the boundary.

Figure 21: A distribution of $50$ smooth trajectories generated by
transforming trajectories generated by using two radial basis functions with
weights chosen uniformly in the range $[-1,1]$. The transformations are done
to maintain a boundary condition $\tau_{0}=-0.25,\tau_{1}=0.25$ and the limits
$\tau_{\min}=-1,\tau_{\max}=1$.

This way we can generate smooth motion while satisfying the boundary
conditions and the joint limits, and maintain zero velocity at the boundary.

## Acknowledgement

This work was supported in part by the Swiss National Science Foundation
through the LEARN-REAL project (https://learn-real.eu/, CHIST-ERA-17-ORMR-006)
and by the European Commission’s Horizon 2020 Programme through the MEMMO
project (Memory of Motion, https://www.memmo-project.eu/, grant agreement
780684).


* [98] B. Wang, G. Li, and Y. Li.  Enabling conversational interaction with mobile ui using large language models.  arXiv preprint arXiv:2209.08655, 2022.
  * [99] B. Wang, G. Li, and Y. Li.  Enabling conversational interaction with mobile ui using large language models.  In Proceedings of the 2023 CHI Conference on Human Factors in Computing Systems, pages 1–17, 2023.
  * [100] B. Wang, G. Li, X. Zhou, Z. Chen, T. Grossman, and Y. Li.  Screen2words: Automatic mobile ui summarization with multimodal learning.  In The 34th Annual ACM Symposium on User Interface Software and Technology, pages 498–510, 2021.
  * [101] Y.-C. Wang, A. Papangelis, R. Wang, Z. Feizollahi, G. Tur, and R. Kraut.  Can you be more social? injecting politeness and positivity into task-oriented conversational agents.  arXiv preprint arXiv:2012.14653, 2020.
  * [102] T. D. Wilson.  Models in information behaviour research.  Journal of documentation, 55(3):249–270, 1999.
  * [103] T. Wu, M. Terry, and C. J. Cai.  Ai chains: Transparent and controllable human-ai interaction by chaining large language model prompts.  In CHI Conference on Human Factors in Computing Systems, pages 1–22, 2022.
  * [104] Q. Yang, J. Cranshaw, S. Amershi, S. T. Iqbal, and J. Teevan.  Sketching nlp: A case study of exploring the right things to design with language intelligence.  In Proceedings of the 2019 CHI Conference on Human Factors in Computing Systems, pages 1–12, 2019.
  * [105] M. Zaib, Q. Z. Sheng, and W. Emma Zhang.  A short survey of pre-trained language models for conversational ai-a new age in nlp.  In Proceedings of the Australasian computer science week multiconference, pages 1–4, 2020.
  * [106] J. Zamfirescu-Pereira, H. Wei, A. Xiao, K. Gu, G. Jung, M. G. Lee, B. Hartmann, and Q. Yang.  Herding ai cats: Lessons from designing a chatbot by prompting gpt-3.  2023\.
  * [107] L. Zhang, L. Jiang, N. Washington, A. A. Liu, J. Shao, A. Fourney, M. R. Morris, and L. Findlater.  Social media through voice: Synthesized voice qualities and self-presentation.  Proceedings of the ACM on Human-Computer Interaction, 5(CSCW1):1–21, 2021.
  * [108] S. Zhong, M. Ribul, Y. Cho, and M. Obrist.  Textilenet: A material taxonomy-based fashion textile dataset.  arXiv preprint arXiv:2301.06160, 2023.
  * [109] A. F. Zuur, E. N. Ieno, N. J. Walker, A. A. Saveliev, G. M. Smith, et al.  Mixed effects models and extensions in ecology with R, volume 574.  Springer, 2009.


# Submodular Batch Selection for Training Deep Neural Networks

K J Joseph  Vamshi Teja R  Krishnakant Singh  Vineeth N Balasubramanian Indian
Institute of Technology Hyderabad
<EMAIL_ADDRESS>
###### Abstract

Mini-batch gradient descent based methods are the de facto algorithms for
training neural network architectures today. We introduce a mini-batch
selection strategy based on submodular function maximization. Our novel
submodular formulation captures the informativeness of each sample and
diversity of the whole subset. We design an efficient, greedy algorithm which
can give high-quality solutions to this NP-hard combinatorial optimization
problem. Our extensive experiments on standard datasets show that the deep
models trained using the proposed batch selection strategy provide better
generalization than Stochastic Gradient Descent as well as a popular baseline
sampling strategy across different learning rates, batch sizes, and distance
metrics.

##  1 Introduction

Deep learning methods are currently the state-of-the-art machine learning
models for many applications, including computer vision, language
understanding, and speech processing. The standard method for training deep
neural networks is mini-batch stochastic gradient descent (SGD) while using
backpropagation to compute the gradients. The mini-batch SGD is an
optimization algorithm where mini-batches of data
$D_{t}=\\{d_{1},d_{2},\cdots,d_{m}\\}$ containing $m$ examples are sampled
uniformly from the dataset $D$, at time $t$. A loss function value w.r.t. the
current model parameters $w_{t}$ is computed as
$\mathcal{L}(w_{t})=\sum_{i=1}^{m}l(d_{i}|w_{t})$ (where $l(.)$ is any
differentiable loss function for the neural network), and the weights are
updated to minimize $\mathcal{L}(w_{t})$, according to the following equation:

$\vspace{-3pt}w_{t+1}=w_{t}-\mu_{t}\frac{\partial\mathcal{L}(w_{t})}{\partial
w_{t}}\vspace{-3pt}$ (1)

where $\mu_{t}$ is the learning rate at the $t^{th}$ step.

In this work, we hypothesize and validate that not only is the update of
$w_{t}$ given $\frac{\partial\mathcal{L}(w_{t})}{\partial w_{t}}$ crucial, but
also the selection of the mini-batch $D_{t}$ used to compute the gradient. We
formulate batch selection as solving a submodular optimization problem, which
contributes to significant improvement in the generalization performance of
the model. To the best of our knowledge, this is the first such effort on
submodular importance sampling for SGD.

Each mini-batch selection is posed as a cardinality-constrained monotone
submodular function maximization problem. This helps us leverage a greedy
algorithm to solve this NP-hard combinatorial optimization problem, which
guarantees a solution for a submodular objective function which is at least
(in the worst case) $(1-\frac{1}{e})$ (approximately 0.63) of the optimal
solution Nemhauser et al. (1978).

The key contribution of our work is a new submodular sampling strategy for
mini-batch SGD, which helps train deep neural networks to have better
generalization capability. To achieve this, we formulate a submodular
objective function, which takes into account the informativeness that each
sample can add to the subset and at the same time ensure that the subset as a
whole, is diverse. Further, we propose an efficient algorithm to scale to high
sampling rates, as required for SGD while training neural networks. We conduct
extensive experimental studies of the proposed submodular mini-batch selection
methodology and show that it improves generalization capability of SGD as well
as related previous efforts such as Loss based sampling Loshchilov and Hutter
(2015). We also show that the improved performance of the proposed methodology
is consistent across different learning rates, mini-batch sizes and distance
metrics. While submodular batch selection has been used extensively in the
past for other settings such as active learning Wei et al. (2015); Chakraborty
et al. (2015) and other methods such as Determinantal Point Process (DPP)
Zhang et al. (2017) have been used to diversify minibatch selection recently,
to the best of our knowledge, this is the first submodular batch selection
methodology111We use the terms batch selection and mini-batch selection
interchangeably in this work. for SGD while training neural networks.
Importantly, our consistent increase in generalization performance over SGD is
a notable achievement, which was missing in methods proposed earlier for mini-
batch selection.

The remainder of this paper is organized as follows. We survey the literature
related to our work in Section 2; we review the concepts of submodularity,
introduce our submodular function and describe our efficient implementation
strategy in Section 3. The end-to-end algorithm is summarized in section 3.4.
The experimental setup, main results, and ablation studies are reported in
Section 4. We conclude with pointers for future work in Section 5.

##  2 Related Work

Mini-batch selection strategies have been explored in convex settings in the
past. Zhao and Zhang (2014) proposed a sampling scheme based on partitioning
data into balanced strata leading to faster convergence, while Zhao and Zhang
(2015) proved that the optimal sampling distribution is directly related to
the absolute values of the gradient of the samples for convex objectives.
However, the prohibitive cost of evaluating the gradient impedes their usage
in practice. In non-convex settings, such as in deep neural networks, there
have been fewer efforts for mini-batch selection, especially in the context of
SGD. Extensions of Zhao and Zhang (2015) to neural networks do not scale, due
to the large number of trainable parameters in the deep models. Recently,
Loshchilov and Hutter (2015); Alain et al. (2015) have tried to alleviate the
cost of computing gradients by using loss-based sampling as an approximation
to the gradients. Unfortunately, these methods are very sensitive to
hyperparameters and perform inadequately in many cases Katharopoulos and
Fleuret (2017). The work was, in fact, validated only on MNIST data, which was
acknowledged as a limitation of the work in Loshchilov and Hutter (2015). The
only other efforts to our knowledge consider more efficient approximations to
the batch gradients i.e. variance of the samples Chang et al. (2017) or an
upper bound on the gradient norm Katharopoulos and Fleuret (2018), but the
generalization performance is only comparable to SGD in most cases. On the
other hand, there have been efforts to speed up mini-batch SGD in general such
as Allen-Zhu (2017); Johnson and Zhang (2013). However, these efforts do not
focus on batch selection or importance sampling, and show lower performance
than existing importance sampling methods as noted in Katharopoulos and
Fleuret (2018).

Submodular optimization has been successfully applied to varied tasks like
document summarization Lin and Bilmes (2011), sensor placement Shamaiah et al.
(2010), speech recognition systems Wei et al. (2014), to name a few. However,
there has been no work so far on using submodularity for batch selection. Das
and Kempe (2008) proved that variance between a predictor variable using full
batch and a mini-batch is submodular. We were initially motivated by this
observation to propose a submodular batch selection strategy for SGD. The
existing efforts that are closest to ours include Determinantal Point Process
(DPP) Zhang et al. (2017), Repulsive Point Processes (RPP) Zhang et al. (2018)
and Singh and Balasubramanian (2018). Both DPP and RPP can be considered a
special case of probabilistic submodular functions (PSF), although not
explicitly called so in their work. However, these methods are computationally
inefficient. Even with faster versions, they are prohibitively costly to be
applied in deep neural networks Li et al. (2016). Singh and Balasubramanian
(2018) attempt a similar objective, but the objective considered is truly not
submodular, and their results are largely inconclusive. Another body of work
that can be considered close to our efforts are those of self-paced learning
Thangarasa and Taylor (2018) and curriculum learning Zhou and Bilmes (2018).
However, their objectives are different, and one can consider using our batch
selection strategy along with any such method too.

##  3 Submodular Batch Selection Methodology

We begin this section with a brief introduction to submodularity, before
presenting our methodology.

###  3.1 Submodularity

Given a finite set $V=\\{1,2,\cdots,n\\}$, a discrete set function
$\mathcal{F}:2^{V}\to\mathbb{R}$, that returns a real value for any subset
$S\subseteq V$ is submodular if

$\mathcal{F}(A)+\mathcal{F}(B)\geq\mathcal{F}(A\cup B)+\mathcal{F}(A\cap
B)\quad\forall A,B\subseteq V$ (2)

A more intuitive way of defining a submodular function is in terms of the
marginal gain of adding a new element to a subset. Let
$\mathcal{F}(e|S)=\mathcal{F}(e\cup S)-\mathcal{F}(S)$ denote the marginal
gain of adding an element $a$ to $S$. $\mathcal{F}$ is submodular if

$\mathcal{F}(a|S)\geq\mathcal{F}(a|T)\qquad\forall S\subseteq T\subseteq
V\setminus a$ (3)

This is also called the diminishing returns property, where the incremental
gain of adding a new element to a set decreases as the set grows from $S$ to
$T$. Hence, a subset that maximizes a submodular objective function
$\mathcal{F}(.)$ would have least redundant elements over other subsets of the
same cardinality because any redundant element will reduce the value of the
submodular objective function.

A function is monotone non-decreasing if $\forall A\subseteq
B,\mathcal{F}(A)\leq\mathcal{F}(B)$. $\mathcal{F}(.)$ is said to be normalized
if $\mathcal{F}(\emptyset)=0$. A greedy algorithm Nemhauser et al. (1978) can
be used to maximise a normalized monotone submodular function with cardinality
constraints, with a worst-case approximation factor of $1-\frac{1}{e}$. An
instance of such a greedy algorithm can be as follows: In the $i^{th}$
iteration, the algorithm selects an item $s_{i}$ that maximizes the
conditional gain, i.e. $s_{i}=\operatorname*{arg\,max}_{a\in V\setminus
S_{i-1}}\mathcal{F}(a|S_{i-1})$. The subset $S_{i}$, initially empty, is
updated as: $S_{i}\leftarrow\\{s_{i}\\}\cup S_{i-1}$. The algorithm terminates
when $S_{i}$ meets the cardinality constraint $|S_{i}|\leq k$.

###  3.2 Submodular Batch Selection

An appropriate batch selection strategy for mini-batch SGD would need to
consider multiple criteria to choose the most relevant samples. A primary
criterion we consider is that each selected sample must be as informative as
possible. We use the model uncertainty as the measure of informativeness.

Uncertainty Score [ $U(x_{i})$]: The uncertainty of each data point is
computed as the entropy of the current model $w^{t}$ at training iteration
$t$. $C$ is the set of all classes. This allows the model to select the
samples that confuses it the most in a mini-batch:

$U(x_{i})=-\sum_{y\in C}P(y|x_{i},w^{t})\log P(y|x_{i},w^{t})$ (4)

A subset that maximizes only the Uncertainty Score, would potentially lead to
the inclusion of similar data points with high entropy in the mini-batch. This
redundancy should be avoided to make the mini-batch diverse. The following
score helps to contain the inclusion of redundant data points:

Redundancy Score [ $R(x_{i})$]: Two data points $x_{i}$ and $x_{j}$ may
separately furnish valuable information, but including both may make the
subset less maximally informative. We use Redundancy Score to take this into
account. Given $\phi(.)$ to be any distance metric between the two data
points, a greater value of the minimum distance between points in the subset
would imply more diversity among the data points in the subset. (Needless to
say, this score is dependent on the choice of distance metric, and we study
this in our experiments.)

$R(x_{i})=\min_{x_{j}\in S:i\neq j}\phi(x_{i},x_{j})$ (5)

Going further, one can notice that outlier samples may maximize the above
scores. In order to counter such a selection of batches, we introduce the
following score.

Mean Closeness Score [$MC(x_{i})$]: This term encourages the selection of data
points that are closer to the mean of all the examples
($\mu=\frac{1}{|V|}\sum_{k=1}^{|V|}x_{k}$) to be picked. This avoids the
selection of outlier samples to the extent possible.

$MC(x_{i})=\phi(x_{i},\mu)\vspace{0pt}$ (6)

Finally, there has been recent work to show that closeness in the feature
space of a deep neural network may be a better indicator of how similar two
samples are (as shown by Wei et al. (2014) in the speech domain). We hence
also include a term to explicitly enforce diversity in the feature space of
the given data.

Feature Match Score [$FM(x_{i})$]: This score selects samples that are diverse
across each dimension in the feature space. $g(.)$ is a non-negative monotone
non-decreasing concave function, $U$ is a set of fixed features and
$m_{u}(x_{i})$ is a non-negative score, measuring the degree to which data
point $x_{i}$, possesses the feature $u$.

$FM(x_{i})=\sum_{u\in U}g(m_{u}(x_{i}))\vspace{-5pt}$ (7)

Our implementation of this score (as well as others) is described in Section
4.1.

We combine the abovementioned scores to form our objective function for batch
selection, $\mathcal{F}(S)$, as below and then show the submodularity of the
proposed $\mathcal{F}(S)$.

$\mathcal{F}(S)=\sum_{x_{i}\in
S}\lambda_{1}U(x_{i})+\lambda_{2}R(x_{i})+\lambda_{3}MC(x_{i})+\lambda_{4}FM(x_{i})$
(8)

Given a dataset with $N$ training data points, a mini-batch of size $k$ is
selected by solving the following cardinality-constrained submodular
optimization problem:

$\max_{S\subseteq V,|S|\leq k}\mathcal{F}(S)\vspace{-5pt}$ (9)

We now show that the score function $\mathcal{F}$ is indeed submodular and is
monotonically non-decreasing. This would allow us to solve the problem in (9)
using a greedy approach Nemhauser et al. (1978).

######  Lemma 1.

The score function $\mathcal{F}(.)$, defined in Eqn 8 is submodular.

###### Proof.

Consider two subsets of training examples from a dataset
$V=\\{x_{1},x_{2},\cdots,x_{N}\\}$; $S_{1}$ and $S_{2}$, such that
$S_{1}\subseteq S_{2}\subseteq V$. Let $a$ be an element not selected so far:
$a\in V\setminus S_{2}$. The marginal gain of adding $a$ to $S_{1}$ is given
by:

$\begin{split}\mathcal{F}(a|S_{1})=~{}&\mathcal{F}(\\{a\\}\cup
S_{1})-\mathcal{F}(S_{1})\\\ =~{}&\lambda_{1}U(a)+\lambda_{2}\min_{a_{j}\in
S_{1}}\phi(a,a_{j})+\lambda_{3}MD(a)+\lambda_{4}FM(a)\end{split}$

Similarly, the marginal gain of adding $a$ to $S_{2}$ is given by:

$\begin{split}\mathcal{F}(a|S_{2})=~{}&\mathcal{F}(\\{a\\}\cup
S_{2})-\mathcal{F}(S_{2})\\\ =~{}&\lambda_{1}U(a)+\lambda_{2}\min_{a_{j}\in
S_{2}}\phi(a,a_{j})+\lambda_{3}MD(a)+\lambda_{4}FM(a)\end{split}$

Since $S_{1}\subseteq S_{2}$, the minimum distance of the new point $a$, from
$S_{1}$ would be greater than any element from $S_{2}$, as there may exist a
point in $S_{2}$ that is much closer to $a$, than any element from its subset
$S_{1}$. Hence,

$\min_{a_{j}\in S_{1}}\phi(a,a_{j})\geq\min_{a_{j}\in S_{2}}\phi(a,a_{j})$

Thus, we can claim $\mathcal{F}(a|S_{1})\geq\mathcal{F}(a|S_{2})$. Hence, the
score function $\mathcal{F}(.)$ is submodular. ∎

######  Lemma 2.

The score function $\mathcal{F}(.)$ in Eqn 8 is a monotonically non-decreasing
function.

###### Proof.

Consider a subset $S$ and an element $a\in V\setminus S$. When $a$ is added to
$S$, the function value of $\mathcal{F}(\\{a\\}\cup S)$ changes by
$\lambda_{1}U(a)+\lambda_{2}\min_{a_{j}\in
S}\phi(a,a_{j})+\lambda_{3}MD(a)+\lambda_{4}FM(a)$. All these are non-negative
quantities. Thus, $\mathcal{F}(\\{a\\}\cup S)\geq\mathcal{F}(S)$, and the
score function $\mathcal{F}(.)$ is hence monotonically non-decreasing. ∎

######  Theorem 1.

Let $S^{*}$ denote the optimal solution of the problem in (9) and $S$ denote
the solution obtained for the same problem using a greedy approach. Then:

$\mathcal{F}(S)\geq(1-\frac{1}{e})\mathcal{F}(S^{*})\vspace{-2pt}$

###### Proof.

Having proved that score function $\mathcal{F}(.)$ is submodular in Lemma $1$
and that it is monotonically non-decreasing in Lemma $2$, the proof follows
directly from Theorem $4.3$ in Nemhauser et al. (1978). ∎

###  3.3 Scaling to High Sampling Rates

It is interesting to note that application settings where submodularity has
worked well hitherto Wei et al. (2014, 2015); Chakraborty et al. (2015); Lin
and Bilmes (2011) do not require a high sampling rate, as much as demanded by
mini-batch selection in SGD. Consider a mini-batch training algorithm that
consists of $p$ epochs and $q$ iterations in each epoch, the submodular batch
selection needs to be carried out $p\times q$ times. Concretely, for training
on the CIFAR-100 dataset having 50,000 examples and a batch size of 50 ($q$ is
hence 50000 / 50), we need 100,000 batch selections for 100 epochs ($p=100$).
Even a greedy algorithm Nemhauser et al. (1978) that uses scores such as
pairwise distance metrics has a complexity of $O(n^{2})$, where $n$ is the
dataset size. This would be too slow for use with SGD. We hence seek more
efficient mechanisms to implement the proposed batch selection strategy.

Recent efforts have attempted to make submodular sampling faster in a more
general context (not in SGD), such as Lazy Greedy Minoux (1978), Lazier than
Lazy Greedy (LtLG) Mirzasoleiman et al. (2015), and Distributed Submodular
Maximization Mirzasoleiman et al. (2013). In this work, we present a new
methodology for efficient submodular sampling inspired by Distributed
Submodular Maximization algorithm and Lazier than Lazy Greedy algorithm
(LtLG), as described in Algorithm 1. The algorithm partitions the training set
$V$ into $m$ partitions in Line 2 and runs Lazier than Lazy Greedy algorithm
(LtLG) Mirzasoleiman et al. (2015) (described later in this section) on each
partition (Lines 5 through 8) to obtain $m$ subsets, each of size $b$. These
subsets ($S_{i}s$) are then merged in Line 9. The final subset $S$ is selected
from this merged set by running LtLG again on it. This divide-and-conquer
strategy is motivated by the Distributed Submodular Maximization algorithm
Mirzasoleiman et al. (2013).

Algorithm 1 Algorithm GetMiniBatch

1:Training set $V$, Model at $k^{th}$ iteration $w_{k}$, Batch size $b$,
Number of partitions $m$, $\mathcal{F}:2^{V}\to\mathbb{R}$ (Eqn 8).

2:Mini-batch $S\subseteq V$ satisfying $|S|\leq b$.

3:$S\leftarrow\phi$

4:Partition $V$ into $m$ sets $V_{1},V_{2},V_{3},\cdots,V_{m}$.

5:for i = 1 to m do

6: $S_{i}\leftarrow\phi$

7: for j = 1 to b do $\triangleright$ Do LtLG for each partition.

8: $R\leftarrow$ a subset of size $s$ obtained by sampling randomly from
$V_{i}\setminus S_{i}$.

9: $a_{j}\leftarrow\operatorname*{arg\,max}_{a\in R}\mathcal{F}(a|S_{i})$

10: $S_{i}\leftarrow S_{i}\cup\\{a_{j}\\}$

11:$S_{merged}\leftarrow\bigcup_{i=1}^{m}S_{i}$ $\triangleright$ Merge result
of each partition.

12:for j = 1 to b do $\triangleright$ Do LtLG on the merged set.

13: $R\leftarrow$ a subset of size $s$ obtained by sampling randomly from
$S_{merged}\setminus S$.

14: $a_{j}\leftarrow\operatorname*{arg\,max}_{a\in R}\mathcal{F}(a|S)$

15: $S\leftarrow S\cup\\{a_{j}\\}$

16:Return $S$

The Lazier than Lazy Greedy (LtLG) Mirzasoleiman et al. (2015) algorithm
starts with an empty set and adds an element from set $R$, which maximizes the
marginal gain $\mathcal{F}(a|S)=\mathcal{F}(a\cup S)-\mathcal{F}(S)$. This is
repeated until the cardinality constraint ($|S|\leq b$) is met. The set $R$ is
created by randomly sampling $s=\frac{|V|}{b}log\frac{1}{\epsilon}$ items from
the superset V, where $\epsilon$ is a user-defined tolerance level. We refer
the readers to Mirzasoleiman et al. (2015) for further information. The model
at the $k^{th}$ training iteration, $w_{k}$, is used while computing
$\mathcal{F}(.)$ as defined in Equation 8.

The solution produced by Algorithm 1, $S$, has the following approximation
guarantee with the optimal solution $S^{*}$:

$\mathcal{F}(S)\geqslant\frac{(1-e^{-1})^{2}}{min(m,b)}(1-e^{-1}-\epsilon)\mathcal{F}(S^{*})$
(10)

Here, $m$ refers to the number of partitions, $b$ refers to the mini-batch
size and $e$ is the base of natural logarithm. Our empirical results (Section
4.2) shows that the approximation is much better than this lower bound in
practice.

###  3.4 Gradient Descent with Submodular Batches

The proposed batch selection strategy can work with any mini-batch gradient
descent based optimization algorithms. Algorithm 2 summarizes the end-to-end
training procedure.

Algorithm 2 Algorithm Submodular SGD

1:Training Set $V$, Optimizer $\pi(.,\eta)$, # of epochs p, Batch size $b$, #
of partitions $m$.

2:Trained model $w_{p}^{\frac{|V|}{b}}$.

3:$\tau\leftarrow 1$

4:Initialize the model $w^{1}_{\tau}$.

5:for i = 1 to p do

6: for j = 1 to $\frac{|V|}{b}$ do

7: $S\leftarrow\textsc{GetMiniBatch}(V,w^{j}_{\tau},b,m)$

8: $\nabla J(w^{j}_{\tau})\leftarrow\frac{\partial}{\partial w}\sum_{k\in
S}L(y_{k},f(x_{k},w^{j}_{\tau}))$

9: $w^{j+1}_{\tau}\leftarrow w^{j}_{\tau}+\pi(\\{w^{1:j}_{\tau}\\},\\{\nabla
J^{1:j}_{\tau}\\},\eta)$

10: $w^{1}_{\tau+1}\leftarrow w^{j+1}_{\tau}$; $\tau\leftarrow\tau+1$

11:return $w^{\frac{|V|}{b}}_{p}$

Within each iteration in each epoch, a mini-batch $S$ is selected using
Algorithm 1 (Line 5). Lines 6 and 7 update $w$ with a gradient descent
optimizer $\pi(.,\eta)$, consuming the current set $S$. $\eta$ is the learning
rate. Any differentiable loss function can be used as $L(.)$. Momentum-based
and adaptive learning rate-based gradient descent methods could be used to
further improve the learning based on submodular batches.

(a) Test Error on SVHN (b) Test Error on CIFAR-10

(c) Test Error on CIFAR-100 (d) Test Loss on SVHN

(e) Test Loss on CIFAR-10 (f) Test Loss on CIFAR-100

Figure 1: Comparison of the proposed SMDL, with SGD and loss based sampling
scheme on SVHN, CIFAR-10 and CIFAR-100 datasets. The test error and test loss
is plotted. SMDL consistently outperforms the baselines, both in terms of loss
and generalization performance.

##  4 Experiments and Results

We conduct extensive experimental evaluations to study the effectiveness of
submodular mini-batches in training deep neural networks over Stochastic
Gradient Descent (SGD) and Loss-based sampling Loshchilov and Hutter (2015),
as in earlier efforts such as Katharopoulos and Fleuret (2018). For brevity,
we refer to our proposed method of selecting submodular mini-batches for
training as SubModular Data Loader (SMDL). We study the performance on the
standard image classification task (as used in related earlier efforts) with
SVHN Netzer et al. (2011), CIFAR-10 and CIFAR-100 Krizhevsky and Hinton (2009)
datasets. ResNet 20 He et al. (2016) is used as the network architecture for
SVHN and CIFAR-10, while ResNet 32 is used with CIFAR-100. Our implementation
details are described in Sec 4.1, followed by the main result and various
ablation study results in Sec 4.2.

###  4.1 Implementation Details

Algorithm 2 gives the generalized training procedure for submodular mini-batch
selection. In each iteration, the current model $w_{\tau}^{j}$ is used to
evaluate the submodular objective score (Equation 8). The feature
representation for the images is obtained from the penultimate fully connected
layer of this model. The probability values ($P(y|x_{i},w)$) that are used in
the computation of Uncertainty Score is the softmax output from the model.
Euclidean distance between the image features is used for Redundancy Score
computation in Equation 5. We do an ablation study on the effect of using
other distance metrics in Section 4.3. Mean Closeness Score is computed as the
cosine similarity between each data-point and the mean of all the training
examples.

We follow the method used in Brahma and Othon (2018) and Zhou and Bilmes
(2018) to compute the fixed feature set $U$ used for evaluating Feature Match
Score (Equation 7). We train a corresponding neural network, say $M$, on a
random subset of training data, for an epoch. The features from the
penultimate fully connected layer of $M$ is used as $U$. Square root function
is used as $g(.)$. $m_{u}(x_{i})$ is the feature at $u^{th}$ index of the
representation of $x_{i}$ from the model $M$.

After a grid search and an empirical study, we use the following values for
the co-efficients of the terms in the objective function:
$\lambda_{1}=\text{0.2},\lambda_{2}=\text{0.1},\lambda_{3}=\text{0.5},\lambda_{4}=\text{0.2}$.
Ablation studies of the effect of the $\lambda$ parameters are presented in
Section 4.3. Each of the scores is individually normalized across the selected
pool of samples, before being combined, to ensure fair contribution. All the
score computation (which depends on the softmax output and the feature
representation from fully-connected layers) is a function of the model at each
iteration (Line 5, Algorithm 2). As we are using gradient descent for updating
the parameters, we know that the model does not change drastically between
iterations. Computational efficiency can be improved if we share the same
model between successive iterations. We use a refresh rate of 5 for all the
experiments. A study of how our method behaves with different refresh rates is
shown in Figure 2(d). We note that increasing the refresh rate decreases the
performance of the model. This is because the model changes over multiple
iterations, which in turn affects the quality of the mini-batch selected.

We develop a modularized and configuration-driven tool in PyTorch Paszke et
al. (2017), which implements submodular selection and the other two baseline
methods: SGD and Loss based sampling Loshchilov and Hutter (2015). All the
experiments are run for 100 epochs with a batch size of 50, a momentum
parameter of $0.9$ and weight decay of $0.0001$. Use of batch normalization
Ioffe and Szegedy (2015) and adaptive learning methods like Adam Kingma and Ba
(2014) will complement the reported results of SMDL and other baseline
methods. For SGD, all the reported results are the average of five runs. The
partition size ($m$ in Algorithm 1 and 2) is set to 10. Code is open-sourced:
https://josephkj.in/projects/SMDL

Dataset |  | SVHN | CIFAR-10 | CIFAR-100
---|---|---|---|---
Method |  | Loss Based | SGD | SMDL | Loss Based | SGD | SMDL | Loss Based | SGD | SMDL
Accuracy(%) | Mean | 90.87 | 93.60 | 95.46 | 81.06 | 82.54 | 84.58 | 53.77 | 53.57 | 57.23
Final | 92.44 | 94.34 | 95.49 | 84.32 | 85.63 | 87.76 | 57.22 | 58.27 | 62.95
Loss | Mean | 0.363 | 0.230 | 0.175 | 0.590 | 0.535 | 0.487 | 1.755 | 1.764 | 1.717
Final | 0.318 | 0.215 | 0.182 | 0.497 | 0.445 | 0.384 | 1.639 | 1.586 | 1.504

Table 1: Quantitative comparison of the proposed SMDL with SGD and Loss based
sampling scheme on SVHN, CIFAR-10 and CIFAR-100 datasets. Mean refers to the
mean accuracy(%) across epochs and Final refers to the final accuracy.

###  4.2 Results

We present the major result of our proposed submodular mini-batch selection
method, SMDL in Figure 1 and Table 1. We train the two network architectures
on three datasets as enumerated in Section 4. The generalization performance
of these classification models, as measured by their test accuracy and test
loss, is used as the evaluation metric. We see from Figure 1 and Table 1 that
SMDL is able to achieve lower error and loss, consistently across epochs, on
all the three datasets. It is worth noting that Loss-based sampling fails
significantly on SVHN. Such deterioration of generalization performance is
also noted in Loshchilov and Hutter (2015). The values reported on SGD are its
mean after conducting five trials.

These results support our claim that selecting a mini-batch which respects
diversity and informativeness of the samples helps in more generalizable deep
learning models.

| 0 | 0.2 | 0.5 | 0.8 | 1.0
---|---|---|---|---|---
| Mean | Final | Mean | Final | Mean | Final | Mean | Final | Mean | Final
$\lambda_{1}$ | 64.41 | 87.19 | 58.60 | 91.13 | 66.99 | 92.39 | 65.68 | 92.27 | 65.80 | 92.12
$\lambda_{2}$ | 46.17 | 83.62 | 64.55 | 91.34 | 68.28 | 92.33 | 67.70 | 90.77 | 61.34 | 85.06
$\lambda_{3}$ | 64.41 | 87.19 | 62.90 | 91.01 | 60.91 | 89.50 | 63.58 | 91.02 | 59.06 | 89.77
$\lambda_{4}$ | 64.41 | 87.19 | 62.25 | 92.14 | 63.03 | 86.90 | 65.50 | 91.03 | 60.30 | 86.61

Table 2: Ablation study of $\lambda$ parameters on subset of SVHN dataset.
Mean across epochs and accuracy(%) of the Final model is reported.

###  4.3 Ablation Studies

#### Effect of trade-off parameters.

We study the effect of trade-off parameters that control the contribution of
each of the four score functions in the submodular objective function
(Equation 8). For this, we train ResNet 20 on a small subset of SVHN dataset.
Except for the Redundancy Score (controlled via $\lambda_{2}$), all the other
terms are modular. Hence $\lambda_{2}$ should be non-zero to make the
objective function submodular. We vary each of the other
$\lambda_{i}(i\in\\{{1,3,4}\\})$ with values from $\\{0,0.2,0.5,0.8,1.0\\}$,
by fixing $\lambda_{2}$=0.5 and rest to zero. These results are reported in
row 1, 3 and 4 of Table 2. Then, we fix the best values obtained for
$\lambda_{1},\lambda_{3}\text{ and }\lambda_{4}$ and vary $\lambda_{2}$. The
result is populated in the second row of Table 2. It is evident from the table
that the following trade-off parameters (after normalization) achieves best
performance on the subset:
$\lambda_{1}=\text{0.25},\lambda_{2}=\text{0.25},\lambda_{3}=\text{0.4},\lambda_{4}=\text{0.1}$.
Empirically, we find that
$\lambda_{1}=\text{0.2},\lambda_{2}=\text{0.1},\lambda_{3}=\text{0.5},\lambda_{4}=\text{0.2}$,
achieves best performance on the whole dataset. These set of trade-off
parameters also generalises well to CIFAR-10 and CIFAR-100 datasets.

From Table 2 we can observe that each of the score function has a profound
effect on the quality of the model being trained. Setting each of them to zero
hurts the performance the most (Column 2 and 3). The second row reveals that
the submodular term has the maximal impact if we set it zero. Each of the
scores is independently competent while combining them gives the best
performance.

(a) Comparison with different distance metrics. (b) Test Error plot with
different learning rates (LR). (c) Test Error plot with different mini-batch
sizes (BS). (d) Test Error plot with different Refresh Rates (RR).

Figure 2: The figure shows the ablation results on SVHN dataset. 1)We find
that the Euclidean distance measure performs best among other distance
metrics. 2)The proposed method SMDL consistently outperforms SGD even with
different batch sizes and different learning rates. We note that a batch size
of $50$ and a learning rate of $0.1$ gives the least error for SMDL. 3) We
find that a refresh rate of 5 gives the best performance. (refer Section 4.1).

#### Variations across different distance metrics

We perform an ablation study on the impact of different distance metrics while
computing the value of the submodular objective function. We choose four
distance metrics and evaluate its impact on training an image classifier on
SVHN dataset. Assuming $u$ and $v$ as the two vectors, the distance metrics
considered are: Euclidean ($\lVert u-v\rVert_{2}$), Cosine ($1-\frac{u\cdot
v}{\lVert u\rVert_{2}\lVert v\rVert_{2}}$), Correlation
($1-\frac{(u-\bar{u})\cdot(v-\bar{v})}{\lVert(u-\bar{u})\rVert_{2}\lVert(v-\bar{v})\rVert_{2}}$)
where $\bar{u}$ is the mean elements of vector $u$ and Gaussian
($\exp{-\frac{(\lVert u-v\rVert^{2})}{2\sigma^{2}}}$).

Figure 2(a) shows the result of the experiment, where the test error is
plotted against epochs. These results suggest that the Euclidean distance
metric gives lower test error than the others.

#### Effect of learning rate and batch size

Batch size and learning rate are the most important hyper-parameters that
impact the learning dynamics of the model. In order to study the robustness of
the model trained with submodular mini-batches, we vary batch size and
learning rate, keeping all other parameters the same. We compare with SGD
trained with the same set of hyper-parameters for a fair comparison.

Figure 2(c) reports the results when mini-batch sizes are set to 50, 100 and
200. Our results agree with the common consensus Li et al. (2014) that
increasing the batch-size decreases the rate of convergence, still SMDL beats
SGD by a consistent margin (solid lines in the graph) for all the batch sizes.
We set the learning rate to 0.1, 0.01 and 0.001 and observe the same similar
pattern in Figure 2(b). These results show that the performance of SMDL is
robust to learning rate and batch size changes.

##  5 Conclusion

In this work, we cast the selection of diverse and informative mini-batches
for training a deep learning model as a submodular optimization problem. We
design a novel submodular objective and propose a scalable algorithm to do
submodular selection. Extensive experimental valuation on three datasets
reveals significant improvement in convergence and generalization performance
of the model trained with submodular mini-batches over SGD and Loss based
sampling Loshchilov and Hutter (2015). The ablation results show that the
method is robust to changes in batch size and learning rate.

It would be ideal to give the model the expressive power to decide not just
which data points to select, but also the number of such data points to train
on. This can be easily done by incorporating an additional factor into the
submodular objective function, which checks the growth of the mini-batch size.
This would be an important direction of our future work. In addition, more
efficient strategies to speed up the proposed method further would form a key
interest of ours in our future efforts.

#### Acknowledgements

We would like to thank MHRD, Govt of India for funding the personnel involved,
Microsoft Research India and ACM-India/IARCS for the travel grants to present
the work and the anonymous reviewers for their valuable feedback.

## References

  * Alain et al. [2015] Guillaume Alain, Alex Lamb, Chinnadhurai Sankar, Aaron Courville, and Yoshua Bengio.  Variance reduction in sgd by distributed importance sampling.  arXiv preprint arXiv:1511.06481, 2015.
  * Allen-Zhu [2017] Zeyuan Allen-Zhu.  Katyusha: The first direct acceleration of stochastic gradient methods.  The Journal of Machine Learning Research, 18(1):8194–8244, 2017\.
  * Brahma and Othon [2018] Pratik Prabhanjan Brahma and Adrienne Othon.  Subset replay based continual learning for scalable improvement of autonomous systems.  In CVPR Workshops, pages 1179–11798. IEEE, 2018.
  * Chakraborty et al. [2015] Shayok Chakraborty, Vineeth Balasubramanian, and Sethuraman Panchanathan.  Adaptive batch mode active learning.  IEEE TNNLS, 26(8):1747–1760, 2015.
  * Chang et al. [2017] Haw-Shiuan Chang, Erik Learned-Miller, and Andrew McCallum.  Active bias: Training more accurate neural networks by emphasizing high variance samples.  In Advances in Neural Information Processing Systems, pages 1002–1012, 2017.
  * Das and Kempe [2008] Abhimanyu Das and David Kempe.  Algorithms for subset selection in linear regression.  In ACM STOC, pages 45–54. ACM, 2008.
  * He et al. [2016] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In CVPR, pages 770–778, 2016.
  * Ioffe and Szegedy [2015] Sergey Ioffe and Christian Szegedy.  Batch normalization: Accelerating deep network training by reducing internal covariate shift.  arXiv preprint arXiv:1502.03167, 2015.
  * Johnson and Zhang [2013] Rie Johnson and Tong Zhang.  Accelerating stochastic gradient descent using predictive variance reduction.  In NIPS, pages 315–323, 2013.
  * Katharopoulos and Fleuret [2017] Angelos Katharopoulos and François Fleuret.  Biased importance sampling for deep neural network training.  arXiv preprint arXiv:1706.00043, 2017.
  * Katharopoulos and Fleuret [2018] Angelos Katharopoulos and François Fleuret.  Not all samples are created equal: Deep learning with importance sampling.  arXiv:1803.00942, 2018.
  * Kingma and Ba [2014] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  arXiv preprint arXiv:1412.6980, 2014.
  * Krizhevsky and Hinton [2009] Alex Krizhevsky and Geoffrey Hinton.  Learning multiple layers of features from tiny images.  Technical report, Citeseer, 2009.
  * Li et al. [2014] Mu Li, Tong Zhang, Yuqiang Chen, and Alexander J Smola.  Efficient mini-batch training for stochastic optimization.  In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 661–670. ACM, 2014.
  * Li et al. [2016] Chengtao Li, Stefanie Jegelka, and Suvrit Sra.  Fast dpp sampling for nystr$\backslash$” om with application to kernel methods.  arXiv preprint arXiv:1603.06052, 2016.
  * Lin and Bilmes [2011] Hui Lin and Jeff Bilmes.  A class of submodular functions for document summarization.  In ACL, pages 510–520. Association for Computational Linguistics, 2011.
  * Loshchilov and Hutter [2015] Ilya Loshchilov and Frank Hutter.  Online batch selection for faster training of neural networks.  ICLR Workshops, 2015.
  * Minoux [1978] Michel Minoux.  Accelerated greedy algorithms for maximizing submodular set functions.  In Optimization techniques, pages 234–243. Springer, 1978.
  * Mirzasoleiman et al. [2013] Baharan Mirzasoleiman, Amin Karbasi, Rik Sarkar, and Andreas Krause.  Distributed submodular maximization: Identifying representative elements in massive data.  In Advances in Neural Information Processing Systems, pages 2049–2057, 2013.
  * Mirzasoleiman et al. [2015] Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, Amin Karbasi, Jan Vondrák, and Andreas Krause.  Lazier than lazy greedy.  In AAAI, 2015.
  * Nemhauser et al. [1978] George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher.  An analysis of approximations for maximizing submodular set functions—i.  Mathematical programming, 14(1):265–294, 1978.
  * Netzer et al. [2011] Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng.  Reading digits in natural images with unsupervised feature learning.  In NIPS workshop, page 5, 2011.
  * Paszke et al. [2017] Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer.  Automatic differentiation in pytorch.  In NIPS-W, 2017.
  * Shamaiah et al. [2010] Manohar Shamaiah, Siddhartha Banerjee, and Haris Vikalo.  Greedy sensor selection: Leveraging submodularity.  In 49th IEEE conference on decision and control (CDC), pages 2572–2577. IEEE, 2010.
  * Singh and Balasubramanian [2018] Krishna Kant Singh and Vineeth N Balasubramanian.  Submodular importance sampling for neural network training.  Master’s thesis, Indian Institute of Technology Hyderabad, 2018.
  * Thangarasa and Taylor [2018] Vithursan Thangarasa and Graham W Taylor.  Self-paced learning with adaptive deep visual embeddings.  arXiv preprint arXiv:1807.09200, 2018.
  * Wei et al. [2014] Kai Wei, Yuzong Liu, Katrin Kirchhoff, Chris Bartels, and Jeff Bilmes.  Submodular subset selection for large-scale speech training data.  In ICASSP, pages 3311–3315. IEEE, 2014.
  * Wei et al. [2015] Kai Wei, Rishabh Iyer, and Jeff Bilmes.  Submodularity in data subset selection and active learning.  In ICML, pages 1954–1963, 2015.
  * Zhang et al. [2017] Cheng Zhang, Hedvig Kjellstrom, and Stephan Mandt.  Determinantal point processes for mini-batch diversification.  arXiv preprint arXiv:1705.00607, 2017.
  * Zhang et al. [2018] Cheng Zhang, Cengiz Öztireli, Stephan Mandt, and Giampiero Salvi.  Active mini-batch sampling using repulsive point processes.  arXiv:1804.02772, 2018.
  * Zhao and Zhang [2014] Peilin Zhao and Tong Zhang.  Accelerating minibatch stochastic gradient descent using stratified sampling.  arXiv preprint arXiv:1405.3080, 2014.
  * Zhao and Zhang [2015] Peilin Zhao and Tong Zhang.  Stochastic optimization with importance sampling for regularized loss minimization.  In ICML, pages 1–9, 2015.
  * Zhou and Bilmes [2018] Tianyi Zhou and Jeff Bilmes.  Minimax curriculum learning: Machine teaching with desirable difficulties and scheduled diversity.  In ICLR, 2018.

Supplementary Section

##  Appendix A Analysis of the computational complexity

The asymptotic complexity of selecting each minibatch using Algorithm 1 is
$m\times r^{2}\times d$, where $m$ is the number of partition to which the
training data is split into (Line 2 of Algorithm 1), $r$ is the sample size of
each of the Lazier than Lazy selection Mirzasoleiman et al. [2015] and $d$ is
the dimension of the feature vector.

The divide and conquer strategy, along with the parallelism that can be
achieved makes the proposed approach practically viable. The dataset $V$, is
partitioned into $m$ random samples in line 2 of Algorithm 1. Lazier than Lazy
selection is run in parallel on multiple cores for each partition $V_{i}$ to
pick $b$ samples (lines 5-8 of Algorithm 1). These $b\times m$ samples are
then combined and $b$ items are selected as mini-batch items (lines 9-14 of
Algorithm 1).

Datasets | Methods
---|---
| SMDL | Loss | SGD
SVHN | 937.2305s | 7007.7064s | 373.1943s
CIFAR 10 | 948.7460s | 5196.3846s | 142.5396s
CIFAR 100 | 764.6001s | 8221.2820s | 160.0396s
Table 3: Comparison of the average time for completing one epoch (in seconds)
taken by SMDL against Loss based sampling and SGD.

Table 3 compares average time taken for completing one epoch by SMDL, Loss
based sampling Loshchilov and Hutter [2015] and SGD. It is evident that SMDL
takes much more time than SGD but achieves better generalization capability
and is much faster than other methods that accomplish the same task like Loss
based sampling.

(a) Test Error plotted across epochs. (b) Test Loss plotted across epochs.

Figure 3: The graph brings out the importance of each of the term in the
submodular formulation (Equation 8). SMDL-{1,2,3,4} are four models which has
only one of the trade-off parameter turned on. It is compared against SGD and
standard SMDL.

(a) Comparison with different distance metrics. (b) Test Loss plot with
different learning rates (LR). (c) Test Loss plot with different mini-batch
sizes (BS). (d) Test Loss plot with different Refresh Rates (RR).

Figure 4: The figure shows the ablation results on SVHN dataset. 1)We find
that the Euclidean distance measure performs best among other distance
metrics. 2)The proposed method SMDL consistently outperforms SGD even with
different batch sizes and different learning rates. We note that a batch size
of $50$ and a learning rate of $0.1$ gives the least loss for SMDL. 3) We find
that a refresh rate of 5 gives the best performance. (refer Section 4.1).

##  Appendix B Additional ablation results on trade-off parameters

The submodular formulation (Equation 8), is a linear combination of four
terms, controlled by trade-off parameters. We study the effect of the values
for these parameters in Section 4.3. We further do one more ablation to find
out whether each of the term is really important for the superior performance
of the proposed mini-batch selector. To study this, we train a ResNet 20 on
SVHN dataset four times, with only one of the four terms set to one and others
to zero. These models are labeled SMDL-{1,2,3,4} in the Figure 3. It is
compared against the standard SMDL
($\lambda_{1}=\text{0.2},\lambda_{2}=\text{0.1},\lambda_{3}=\text{0.5},\lambda_{4}=\text{0.2}$)
and SGD.

Figure 3 shows the result of the experiment. It is evident that the red line,
which represents SMDL with contributions from all the terms achieves better
generalization performance across epochs.

##  Appendix C Test loss plots for various ablation results

Figure 2 in Section 4.3 plots the test error across epochs. Here we plot the
test loss for the exact same experiments in Figure 4. We note that Euclidean
distance metric works best. SMDL consistently outperforms SGD even with
different batch sizes and different learning rates. A batch size of 50,
learning rate of 0.1 and a refresh rate of 5 gives best performance.

##  Appendix D Training error and loss comparison

We plot the error and loss of the model on the training data across epochs in
Figure 5. It is very interesting to see that SGD and Loss based sampling
methods have lower training error. When we read these graphs along with the
results in Figure 1, where error and loss on the test set is plotted, we can
see that models trained with SMDL batch selection strategy, has higher error
on the training set and lower error on the test set. This indicates that the
models trained with SMDL over-fit less to the training data and has better
generalization capabilities.

(a) Train Error on SVHN (b) Train Error on CIFAR-10

(c) Train Error on CIFAR-100 (d) Train Loss on SVHN

(e) Train Loss on CIFAR-10 (f) Train Loss on CIFAR-100

Figure 5: The figure shows how the training error and loss varies over epochs
on different datasets. It is very interesting to note that on all the
datasets, the training error is much higher for SMDL while the error on the
test set is much lower for SMDL (Figure 1). This means that SMDL is not over-
fitting and has better generalization capability than SGD and Loss based
sampling.