Title: MINIMAX CURRICULUM LEARNING: MACHINE TEACHING WITH DESIRABLE DIFFICULTIES AND SCHEDULED DIVERSITY

Abstract: We introduce and study minimax curriculum learning (MCL), a new method for adaptively selecting a sequence of training subsets for a succession of stages in machine learning. The subsets are encouraged to be small and diverse early on, and then larger, harder, and allowably more homogeneous in later stages. At each stage, model weights and training sets are chosen by solving a joint continuousdiscrete minimax optimization, whose objective is composed of a continuous loss (reflecting training set hardness) and a discrete submodular promoter of diversity for the chosen subset. MCL repeatedly solves a sequence of such optimizations with a schedule of increasing training set size and decreasing pressure on diversity encouragement. We reduce MCL to the minimization of a surrogate function handled by submodular maximization and continuous gradient methods. We show that MCL achieves better performance and, with a clustering trick, uses fewer labeled samples for both shallow and deep models. Our method involves repeatedly solving constrained submodular maximization of an only slowly varying function on the same ground set. Therefore, we develop a heuristic method that utilizes the previous submodular maximization solution as a warm start for the current submodular maximization process to reduce computation while still yielding a guarantee.

1. INTRODUCTION:

Inspired by the human interaction between teacher and student, recent studies (Khan et al., 2011; Basu & Christensen, 2013; Spitkovsky et al., 2009) support that learning algorithms can be improved by updating a model on a designed sequence of training sets, i.e., a curriculum. This problem is addressed in curriculum learning (CL) (Bengio et al., 2009) , where the sequence is designed by a human expert or heuristic before training begins. Instead of relying on a teacher to provide the curriculum, self-paced learning (SPL) (Kumar et al., 2010; Tang et al., 2012a; Supancic III & Ramanan, 2013; Tang et al., 2012b) chooses the curriculum during the training process. It does so by letting the student (i.e., the algorithm) determine which samples to learn from based on their hardness. Given a training set D = {(x 1 , y 1 ), . . . , (x n , y n )} of n samples and loss function L(y i , f (x i , w)), where x i ∈ R m represents the feature vector for the i th sample, y i is its label, and f (x i , w) is the predicted label provided by a model with weight w, SPL performs the following:

min w∈R m min ν∈[0,1] n n i=1 ν i L (y i , f (x i , w)) -λ n i=1 ν i .

(1)

SPL jointly learns the model weights w and sample weights ν, which end up being 0-1 indicators of selected samples, and it does so via alternating minimization. Fixing w, minimization w.r.t. ν selects samples with loss L(y i , f (x i , w)) < λ, where λ is a "hardness parameter" as it corresponds to the hardness as measure by the current loss (since with large λ, samples with greater loss are allowed in). Self-paced curriculum learning (Jiang et al., 2015) introduces a blending of "teacher mode" in CL and "student mode" in SPL, where the teacher can define a region of ν by attaching a linear constraint a T ν ≤ c to Eq. ( 1). SPL with diversity (SPLD) (Jiang et al., 2014) , adds to Eq. (1) a negative group sparse regularization term -γ ν 2,1 -γ b j=1 ν (j) 2 , where the samples are divided into b groups beforehand and ν (j) is the weight vector for the j th group. Samples coming from different groups are thus preferred, to the extent that γ > 0 is large.

CL, SPL, and SPLD can be seen as a form of continuation scheme (Allgower & Georg, 2003) that handles a hard task by solving a sequence of tasks moving from easy to hard; the solution to each task is the warm start for the next slightly harder task. That is, each task, in the present case, is determined by the training data subset and other training hyperparameters, and the resulting parameters at the end of a training round are used as the initial parameters for the next training round. Such continuation schemes can reduce the impact of local minima within neural networks (Bengio et al., 2013; Bengio, 2014) . With SPL, after each round of alternating minimization to optimize Eq. ( 1), λ is increased so that the next round selects samples that have a larger loss, a process (Khan et al., 2011; Tang et al., 2012b; Basu & Christensen, 2013 ) that can both help avoid local minima and reduce generalization error. In SPLD, γ is also increased between training rounds, increasingly preferring diversity. In each case, each round results in a fully trained model for the currently selected training samples.

Selection of training samples has been studied in other settings as well, often with a different motivation. In active learning (AL) (Settles, 2010) and experimental design (Montgomery, 2006) , the learner can actively query labels of samples from an unlabeled pool during the training process, and the goal is to reduce annotation costs. The aim is to achieve the same or better performance using fewer labeled samples by ruling out uninformative ones. Diversity modeling was introduced to AL in (Wei et al., 2015) . It uses submodular maximization to select diverse training batches from the most uncertain samples. However, changing the diversity during the learning process has not been investigated as far as we know. In boosting (Schapire, 1990; Freund & Schapire, 1997) , the goal is to learn an ensemble of weak classifiers sequentially; it does this by assigning weights to all samples, with larger weights given to samples having larger loss measured by an aggregation of previously trained models. Both active learning and boosting favor samples that are difficult to predict, since they are the most informative to learn. For example, uncertainty sampling (Culotta & McCallum, 2005; Scheffer et al., 2001; Dagan & Engelson, 1995; Dasgupta & Hsu, 2008) selects samples that are most uncertain, while query by committee (Seung et al., 1992; Dagan & Engelson, 1995; Abe & Mamitsuka, 1998) selects the ones that multiple models most disagree on. With machine teaching (Khan et al., 2011; Zhu, 2015; Patil et al., 2014; Zhu et al., 2018) , a separate teacher helps the training procedure find a good model.

The SPL approach starts with a smaller set of easy samples and gradually increases the difficulty of the chosen samples as measured by the sample loss of the model produced by previous round's training. One of the difficulties of this approach is the following: since for any given value of λ the relatively easiest samples are chosen, there is a good chance that the process can repeatedly select a similar training set over multiple rounds and therefore can learn slowly. This is precisely the problem that SPLD address -by concomitantly increasing the desired diversity over rounds, the sample selection procedure chooses from an increasingly diverse set of different groups, as measured by ν 2,1 . Therefore, in SPLD, early stages train on easier not necessarily diverse samples and later stages train on harder more diverse samples.

There are several challenges remaining with SPLD, however. One is that in early stages, it is still possible to repeatedly select a similar training set over multiple rounds since diversity might not increase dramatically between successive rounds. Potentially more problematically, it is not clear that having a large diversity selection weight in late stages is desirable. For example, with a reasonably trained model, it might be best to select primarily the hardest samples in the part of the space near the difficult regions of the decision boundaries. With a high diversity weight, samples in these difficult decision boundary regions might be avoided in favor of other samples perhaps already well learnt and having a large margin only because they are diverse, thereby leading to wasted effort. At such point, it would be beneficial to choose points having small margin from the same region but that might not have the greatest diversity, especially when using only a simple notion of diversity such as the group sparse norm v 2,1 . Also, it is possible that late stages of learning can select outliers only because they are both hard and diverse. Lastly, the SPL/SPLD min-min optimization involves minimizing a lower bound of the loss, while normally one would, if anything, wish to minimize the loss directly or at least an upper bound.

Motivated by these issues, we introduce a new form of CL that chooses the hardest diverse samples in early rounds of training and then actually decreases, rather than increases, diversity as training rounds proceed. Our contention is that diversity is more important during the early phases of training when only relatively few samples are selected. Later rounds of training will naturally have more diversity opportunity simply because the size of the selected samples is much larger. Also, to avoid successive rounds selecting similar sets of samples, our approach selects the hardest, rather than the easiest, samples at each round. Hence, if a set of samples is learnt well during one training round, those samples will tend to be ill-favored in the next round because they become easier. We also measure hardness via the loss function, but the selection is always based on the hardest and most diverse samples of a given size k, where the degree of diversity is controlled by a parameter λ, and where diversity is measured by an arbitrary non-monotone submodular function. In fact, for binary variables the group sparse norm is also submodular where ν 2,1 = b j=1

|C j ∩ A| = F (A) where A is the set for which ν is the characteristic vector, and C j is the set of samples in the j th group. Our approach allows the full expressive class of submodular functions to be used to measure diversity since the selection phases is based on submodular optimization.

Evidence for the naturalness of such hardness and diversity adjustment in a curriculum can also be found in human education. For example, courses in primary school usually cover a broad, small, and relatively easy range of topics, in order to expose the young learner to a diversity of knowledge early on. In college and graduate school, by contrast, students focus on advanced deeper knowledge within their majors. As another example, studies of bilingualism (Bialystok et al., 2012; Li et al., 2014; Mechelli et al., 2004; Kovács & Mehler, 2009) show that learning multiple languages in childhood is beneficial for future brain development, but early-age multi-lingual learning is usually not advanced or concentrated linguistically for any of the languages involved. Still other studies argue that difficulty can be desired at early human learning stages (Bjork & Bjork, 1992; McDaniel & Butler, 2011) .

1.1. OUR APPROACH: MINIMAX CURRICULUM LEARNING:

We introduce a new form of curriculum learning called minimax curriculum learning (MCL). MCL increases desired hardness and reduces diversity encouragement over rounds of training. This is accomplished by solving a sequence of minimax optimizations, each of which having the form: min

EQUATION

)

The objective is composed of the loss on a subset A of samples evaluating their hardness and a normalized monotone non-decreasing submodular function F : 2 V → R + measuring A's diversity, where V is the ground set of all available samples. A larger loss implies that the subset A has been found harder to learn, while a larger F (A) indicates greater diversity. The weight λ controls the trade-off between hardness and diversity, while k, the size of the resulting A, determines the number of samples to simultaneously learn and hence is a hardness parameter.

It is important to realize that F (A) is not a parameter regularizer (e.g., 1 or 2 regularization on the parameters w) but rather an expression of preference for a diversity of training samples. In practice, one would add to Eq. ( 2) an appropriate parameter regularizer as we do in our experiments (Section 3).

Like SPL/SPLD, learning rounds are scheduled, here each round with increasing k and decreasing λ.

Unlike SPL/SPLD, we explicitly schedule the number of selected samples via k rather than indirectly via a hardness parameter. This makes sense since we are always choosing the hardest k samples at a given λ diversity preference, so there is no need for an explicit real-valued hardness parameter as in SPL/SPLD. Also, the MCL optimization minimizes an upper bound of the loss on any size k subset of training samples.

The function F (•) may be chosen from the large expressive family of submodular functions, all of which are natural for measuring diversity, and all having the following diminishing returns property: given a finite ground set V , and any

A ⊆ B ⊆ V and a v / ∈ B, F (v ∪ A) -F (A) ≥ F (v ∪ B) -F (B).

(3) This implies v is no less valuable to the smaller set A than to the larger set B. The marginal gain of v conditioned on A is denoted f (v|A) f (v ∪ A) -f (A) and reflects the importance of v to A. Submodular functions (Fujishige, 2005) have been widely used for diversity models (Lin et al., 2009; Lin & Bilmes, 2011; Batra et al., 2012; Prasad et al., 2014; Gillenwater et al., 2012; Iyer & Bilmes, 2015; Bilmes & Bai, 2017) .

Although Eq. ( 2) is a hybrid optimization involving both continuous variables w and discrete variables A, it can be reduced to the minimization of a piecewise function, where each piece is defined by a subset A achieving the maximum in a region around w. Each piece is convex when the loss is convex, so various off-the-shelf algorithms can be applied once A has been computed. However, the number of possible sets A is n k , and enumerating them all to find the maximum is intractable. Thanks to submodularity, fast approximate algorithms (Nemhauser et al., 1978; Minoux, 1978; Mirzasoleiman et al., 2015) exist to find an approximately optimal A. Therefore, the outer optimization over w will need to minimize an approximation of the piecewise function defined by an approximate A computed via submodular maximization.

2. MINIMAX CURRICULUM LEARNING AND MACHINE TEACHING:

The minimax problem in Eq. ( 2) can be seen as a two-person zero-sum game between a teacher (the maximizer) and a student (the minimizer): the teacher chooses training set A based on the student's feedback about the hardness (i.e., the loss achieved by current model w) and how diverse according to the teacher (λF (A)), while the student updates w to reduce the loss on training set A (i.e., learn A) given by the teacher. Similar teacher-student interaction also exist in real life. In addition, the teacher usually introduces concepts at the beginning and asks a small number of easy questions from a diverse range of topics and receives feedback from the student, and then further trains the student on the topics the student finds difficult while eschewing topics the student has mastered. MCL's minimax formulation is different from the min-min formulation used in SPL/SPLD. For certain losses and models, L(y i , f (x i , w)) is convex in w. The min-min formulation, however, is only bi-convex and requires procedures such as alternative convex search (ACS) as in (Bazaraa et al., 1993) . Furthermore, diversity regularization of ν in SPLD leads to the loss of bi-convexity altogether.

Minimizing the worst case loss, as in MCL, is a widely used strategy in machine learning (Lanckriet et al., 2003; Farnia & Tse, 2016; Shalev-Shwartz & Wexler, 2016) to achieve better generalization performance and model robustness, especially when strong assumptions cannot be made about the data distribution. Compared to SPL/SPLD, MCL is also better in that the outer minimization over w in Eq. ( 2) is a convex program, and corresponds to minimizing the objective g(w) in Eq. (4). On the other hand, querying g(w) requires submodular maximization which can only be solved approximately.

The goal of this section, therefore, is to address the minimax problem in Eq. (2), i.e., the minimization min w∈R m g(w) of the following objective g(w).

g(w):

max

EQUATION

If the loss function L(y i , f (x i , w)) is convex w.r.t. w, then g(w) is convex but, as mentioned above, enumerating all subsets is intractable. Defining the discrete objective G w : 2

EQUATION

shows that computing g(w) in involves a discrete optimization over G w (A), a problem that is submodular since G w (A) is weighted sum of a non-negative (since loss is non-negative) modular and a submodular function, and thus G w is monotone non-decreasing submodular. Thus, the fast greedy procedure mentioned earlier can be used to approximately optimizes G w (A) for any w.

Let Âw ⊆ V be the k-constrained greedy approximation to maximizing G w (A). We define the following approximate objective:

EQUATION

and note that it satisfies αg(w) ≤ ĝ(w) ≤ g(w) where α is the approximation factor of submodular optimization. For w within a region around w, ĝ( w) will utilize the same set Âw . Therefore, ĝ(w) is piecewise convex, if the loss function L(y i , f (x i , w)) is convex w.r.t. w, and different regions of within R m are associated with different Â although not necessarily the same regions or sets that define g(w). We show in Section 2.2 that minimizing ĝ(w) offers an approximate solution to Eq. ( 2).

With ĝ(w) given, our algorithm is simply gradient descent for minimizing ĝ(w), where many off-the-shelf methods can be invoked, e.g., SGD, momentum methods, Nesterov's accelerated gradient (Nesterov, 2005) , Adagrad (Duchi et al., 2011) , etc. The key problem is how to obtain ĝ(w), which depends on suboptimal solutions in different regions of w. It is not necessary, however, to run submodular maximization for every region of w. Since we use gradient descent, we only need to know ĝ(w) for w on the optimization path. At the beginning of each iteration, we fix w and use submodular maximization to achieve the Âw that defines ĝ(w). Then a gradient update step is applied to ĝ(w). Let A * w represent the optimal solution to Eq. ( 5), then Âw satisfies G( Â) ≥ αG(A * ).

Algorithm 1 Minimax Curriculum Learning (MCL)

1: input: π(•, η), γ, p, ∆,α 2: output: w 0 T 3: initialize: τ ← 1, w 0 τ , λ, k, 4: while not "converged" do 5:

for t ∈ {0, • • • , p} do 6: G(A) ← i∈A L (y i , f (x i , w t τ )) + λF (A); 7: Â ← WS-SUBMODULARMAX(G, k, Â, α); 8: ∇ĝ(w t τ ) = ∂ ∂w i∈ Â L (y i , f (x i , w t τ )); 9: w t+1 τ ← w t τ + π {w 1:t τ }, {∇ĝ(w 1:t τ )}, η ; 10:

end for 11:

w 0 τ +1 ← w p τ , λ ← (1-γ)•λ, k ← k +∆, τ ← τ +1; 12: end while

Algorithm 1 details MCL. Lines 5-10 solve the optimization in Eq. ( 2) with λ and k scheduled in line 11. Lines 6-7 finds an approximate Â via submodular maximization, discussed further in Section 2.1. Lines 8-9 update w for the current Â by gradient descent π(•, η) with learning rate η. The inner optimization stops after p steps and then λ is reduced by factor 1 -γ where γ ∈ [0, 1] and k is increased by ∆. The outer optimization stops after T steps when a form of "convergence", described below, is achieved. Given Âw , ĝ(w) has gradient

EQUATION

and thus gradient descent method can update w. For example, we can treat Â as a batch if k is small, and update w by w ← w -η∇ĝ(w) with learning rate η. For large Âw , we can use SGD that applies an update rule to mini-batches within Âw . More complex gradient descent rules π(•, η) can take historical gradients and w t τ 's into account leading to w t+1 ← w t + π {w 1:t }, {∇ĝ(w 1:t )}, η . Considering the outer loop as well, the algorithm approximately solves a sequence of Eq. ( 2)s with decreasing λ and increasing k, where the previous solutions act as a warm start for the next iterations. This corresponds to repeatedly updating the model w on a sequence of training sets Â that changes from small, diverse, and hard to large.

2.1. SUBMODULAR MAXIMIZATION:

Although solving Eq. ( 5) exactly is NP-hard, a near-optimal solution can be achieved by the greedy algorithm, which offers a worst-case approximation factor of α = 1 -e -1 (Nemhauser et al., 1978) . The algorithm starts with A ← ∅, and selects next the element with the largest marginal gain f (v|A) from V \A, i.e., A ← A ∪ {v * } where v * ∈ argmax v∈V \A f (v|A), and this repeats until |A| = k. It is simple to implement, fast, and usually outperforms other methods, e.g., those based on integer linear programming. It requires O(nk) function evaluations for ground set size |V | = n. Since Algorithm 1 runs greedy T p times, it is useful for the greedy procedure to be as fast as possible. The accelerated, or lazy, greedy algorithm (Minoux, 1978) reduces the number of evaluations per step by updating a priority queue of marginal gains, while having the same output and guarantee as the original (thanks to submodularity) and offers significant speedups. Still faster variants are also available Mirzasoleiman et al. (2015; 2016) . Our own implementation takes advantage of the fact that line 7 of Algorithm 1 repeatedly solves submodular maximization over a sequence of submodular functions that are changing only slowly, and hence the previous set solution can be used as a warm start for the current algorithm, a process we call WS-SUBMODULARMAX outlined in Algorithm 2.

The greedy procedure offers much better approximation factors than 1 -e -1 when the objective G(A) is close to modular. Specifically, the approximation factor becomes α = (1 -e -κ G )/κ G (Conforti & Cornuejols, 1984) , which depends on the curvature κ

EQUATION

When κ G = 0, G is modular, and when κ G = 1, G is fully curved and the above bound recovers 1 -e -1 . G(A) becomes more modular as the outer loop proceeds since λ decreases. Therefore, the approximation improves with the number of outer loops. In fact, we have:

Lemma 1. Let G(A) = L(A) + λF (A)

where F is a monotone non-decreasing submodular function with curvature κ F , L is a non-negative modular function, and

λ ≥ 0. Then κ G ≤ κ F /(c 1 /λ + 1)

where c 1 = min j∈V L(j)/F (j).

The proof is given in Appendix 4.1. In MCL, therefore, the submodular approximation improves (α → 1) as λ grows, and the surrogate function ĝ(w) correspondingly approaches the true convex objective g(w).

2.2. CONDITIONS AT CONVERGENCE:

In this section, we study how close the solution ŵ is of applying gradient descent to ĝ(w), where we assume p is large enough so that a form of convergence occurs. Specifically, in Theorem 1, we analyze the upper bound on ŵ -w * 2 2 based on two assumptions: 1) the loss L (y i , f (x i , w)) being β-strongly convex w.r.t. w; and 2) ŵ is achieved by running gradient descent in lines 6-9 of Algorithm 1 until convergence, defined as the gradient reaching zero. In case the loss L (y i , f (x i , w)) is convex but not β-strongly convex, a commonly used trick to modify it to β-strongly convex is to add an 2 regularization (β/2) w 2 2 . In addition, for non-convex L (y i , f (x i , w)), it is possible to prove that with high probability, a noise perturbed SGD on ĝ(w) can hit an -optimal local solution of g(w) in polynomial time -we leave this for future work. In our empirical study (Section 3), MCL achieves good performance even when applied to non-convex deep neural networks. The following theorem relies on the fact that the maximum of multiple β-strongly convex functions is also β-strongly convex, shown in Appendix 4.2.

Theorem 1 (Inner-loop convergence). For the minimax problem in Eq. (2) with ground set of samples V and λ ≥ 0, if the loss function L (y i , f (x i , w)) is β-strongly convex and |V | ≥ k, running lines 6-9 of Algorithm 1 until convergence (defined as the gradient reaching zero) yields a solution ŵ satisfying

EQUATION

ŵ is the solution achieved at convergence, w * is the optimal solution of the minimax problem in Eq.( 2), g(w * ) is the objective value achieved on w * , and α is the approximation factor that submodular maximization can guarantee for G(A).

The proof is given in Appendix 4.3.

It is interesting to note that the bound depends both on the strong convexity parameter β and on the submodular maximization approximation α. As mentioned in Lemma 1, as λ gets smaller, the approximation factor α approaches 1 meaning that the bound in Equation ( 9) improves.

We mention the convergence criteria where the gradient reaches zero. While it is possible, in theory, for lines 6-9 of Algorithm 1 to oscillate amongst the non-differentiable boundaries between the convex pieces, with most damped learning rates, this will eventually subside and the algorithm will remain within one convex piece. The reason for this is line 7 of the algorithm always chooses one Â thereby selecting one convex piece associated with the region around w t τ , and with only small subsequent adjustments to w t τ , the same Â will continue to be selected. Hence, the algorithm will, in such case, reach the minimum of that convex piece where the gradient is zero.

We can restate and then simplify the above bound in terms of the resulting parameters, and corresponding λ, k values, used at a particular iteration τ of the outer loop. In the following, ŵτ is the solution achieved by Algorithm 1 at the iteration τ of the outer loop, and the optimal solution of the minimax problem in Eq.( 2) with λ, k set as in iteration τ is denoted w * T . Corollary 1. If the loss function L (y i , f (x i , w)) is β-strongly convex, the submodular function F (•) has curvature κ F , and if each inner-loop in Algorithm 1 runs until convergence, then the solution ŵτ at the end of the τ th iteration of the outer-loop fulfills:

EQUATION

where w * τ is the optimal solution of the minimax problem in Eq. (2) with λ set as in the τ th outer loop iteration.

Thus, if k starts from k 0 and linearly increases via k ← k + ∆ (as in line 11 of Algorithm alg:mcl),

EQUATION

Otherwise, if k increases exponentially, i.e., k

EQUATION

In the above, λ 0 and k 0 are the initial values for λ and k, c

1 = min j∈V,t∈[1,τ ] [L (y i , f (x i , ŵt τ )) /F (j)], c 2 = max A⊆V,|A|≤k F (A), and g(w * ∞ ) = min w∈R m max A⊆V,|A|≤k i∈A L (y i , f (x i , w)).

The proof can be found in Appendix 4.5. On the one hand, the upper bound above is in terms of the ratio λ/k which improves with larger subset sizes. On the other hand, submodular maximization becomes more expensive with k. Hence, Algorithm 1 chooses a schedule to decrease λ exponentially and increase k only linearly. Also, we see that the bound is dependent on the submodular curvature κ F , the strongly-convex constant β, and c 1 which relates the submodular and modular terms (similar to as in Lemma 1). These quantities (κ F /β and c 1 ) might be relevant for other convex-submodular optimization schemes.

2.3. HEURISTIC IMPROVEMENTS:

There are several heuristic improvements we employ that are described next.

Algorithm 1 stops gradient descent after p steps. A reason for doing this is that ŵp can be sufficient as a warm-start for the next iteration if p is large enough. We also have not observed any benefit for larger p, although we do eventually observe convergence empirically when the average loss no longer change appreciably between stages. Also, lines 6-7 of Algorithm 1 require computing the loss on all the samples, and each step of the greedy algorithm needs to, in the worst case, evaluate the marginal gains of all of the unselected samples. Moreover, this is done repeatedly in the inner-most block of two nested loops. Therefore, we use two heuristic tricks to improve efficiency.

Fist, rather than selecting individual samples, we first cluster the data and then select clusters, thereby reducing the ground set size from the number of samples to the number of clusters. We replace the per-sample loss L (y i , f (x i , w)) with a per-cluster loss L Y (i) , f (X (i) , w) that we approximate by the loss of the sample closest to the centroid within each cluster:

EQUATION

where C (i) is the set of indices of the samples in the i th cluster, and x (i) with label y (i) is the sample closest to the cluster centroid. We find that the loss on x (i) is sufficiently representative to approximately indicate the hardness of the cluster. The set V becomes the set of clusters and A ⊆ V is a set of clusters, and hence the ground set size is reduced speeding up the greedy algorithm. When computing F (A), the diversity of selected clusters, cluster centroids again represent the cluster. In line 8, the gradient is computed on all the samples in the selected clusters rather than on only x (i) at which point the labels of all the samples in the selected clusters are used. Otherwise, when selecting clusters via submodular maximization, the labels of only the centroid samples are needed. Thus, we need only annotate and compute the loss for samples in the selected clusters and the representative centroid samples x (i) of other clusters. This also reduces the need to label all samples up front as only the labels of the selected clusters, and centroid samples of each cluster, are used (i.e., the clustering process itself does not use the labels).

We can further reduce the ground set to save computation during submodular maximization via prefiltering methods that lead either to no (Wei et al., 2014a) or little (Zhou et al., 2017; Mirzasoleiman et al., 2015) reduction in approximation quality. Moreover, as λ decreases in the MCL objective and G(A) becomes more modular, pruning method become more effective. More details are given in Section 4.6. In this section, we apply different curriculum learning methods to train logistic regression models on 20newsgroups (Lang, 1995) , LeNet5 models on MNIST (Lecun et al., 1998) , convolutional neural nets (CNNs) with three convolutional layers1 on CIFAR10 (Krizhevsky & Hinton, 2009) , CNNs with two convolutional layers2 on Fashion-MNIST ("Fashion" in all tables) (Xiao et al., 2017) , CNNs with six convolutional layers on STL10 (Coates et al., 2011) , and CNNs with seven convolutional layers on SVHN (Netzer et al., 2011) 3 . Details on the datasets can be found in Table 3 of the appendix. In all cases, we also use 2 parameter regularization on w with weight 1e -4 (i.e., the weight decay factor of the optimizer).

3. EXPERIMENTS:

We compare MCL and its variants to SPL (Kumar et al., 2010) , SPLD (Jiang et al., 2014) and SGD with a random curriculum (i.e., with random batches). Each method uses mini-batch SGD for π(•, η) with the same learning rate strategy to update w. The methods, therefore, differ only in the curriculum (i.e., the sequence of training sets).

For SGD, in each iteration, we randomly select 4000 samples (20newsgroups) or 5000 samples (other datasets) and apply mini-batch SGD to the selected samples. In SPL and SPLD, the training set starts from a fixed size k (4000 samples for 20newsgroups, 5000 samples for other datasets), and increases by a factor of 1 + µ (where µ = 0.1) per round of alternating minimization (i.e., per iteration of the outer loop)4 . We use ρ to denote the number of iterations of the inner loop, which aims to minimize the loss w.r.t. the model w on the selected training set. In SPLD, we also have a weight for the negative group sparsity: it starts from ξ and increases by a factor of 1.1 at each round of alternating minimization (i.e., per iteration of the outer loop). We test five different combinations of {ρ, µ} and {ρ, ξ} for SPL and SPLD respectively. The best combination with the smallest test error rate is what we report. Neither SPL nor SPLD uses the clustering trick we applied to MCL: they compute the exact loss on each sample in each iteration. Hence, they have more accurate estimation of the hardness on each sample, and require knowing the labels of all samples (selected and unselected) and cannot reduce annotation costs. Note SPLD still needs to run clustering and use the resulted clusters as groups in the group sparsity (which measures diversity in SPLD). We did not select samples with SPL/SPLD as we do with MCL since we wanted to test SPL/SPLD as originally presented -intuitively, SPL/SPLD should if anything only do better without such clustering due to the more accurate sample-specific hardness estimation. The actual clustering, however, used for SPLD's diversity term is the same as that used for MCL's cluster samples. We apply the mini-batch k-means algorithm to the features detailed in the next paragraph to get the clusters used in MCL and SPLD. Although both SPL and SPLD can be reduced to SGD when λ → ∞ (i.e., all samples always selected), we do not include this special case because SGD is already a baseline. For SGD with a random curriculum, results of 10 independent trials are reported.

In our MCL experiments, we use a simple "feature based" submodular function (Wei et al., 2014b) where c u (A) = i∈A c u (i), where c u (i) is the nonnegative feature u of the centroid for cluster i, and can be interpreted as a nonnegative score for cluster i. We use TF-IDF features for 20newsgroup. For the other datasets, we train a corresponding neural networks on a small random subset of training data (e.g., hundreds of samples) for one epoch, and use the inputs to the last fully connected layer (whose outputs are processed by softmax to generate class probabilities) as features. Because we always use ReLU activations between layers, the features are all nonnegative and the submodularity of F (A) follows as a consequence. These features are also used by mini-batch k-means to generate clusters for MCL and SPLD.

F (A) = u∈U ω u c u (A)

For MCL, we set the number of inner loop iterations to p ≤ 50. For each dataset, we choose p as the number among {10, 20, 50} that reduces the training loss the most in the first few iterations of the outer loop, and then use that p for the remaining iterations. As shown in Table 4 , we use p = 50 for 20newsgroups, MNIST and Fashion-MNIST, and p = 20 for the other three datasets.

We consider five variants of MCL: 1) MCL(∆ = 0, λ = 0, γ = 0) having neither submodular regularization that promotes diversity nor scheduling of k that increases hardness; 2) MCL(∆ = 0, λ > 0, γ > 0), which decreases diversity by exponentially reducing the weight λ of the submodular regularization, but does not have any scheduling of k, i.e., k is fixed during the algorithm; 3) MCL(∆ > 0, λ > 0, γ = 0), which only uses the scheduling of k shown in Algorithm 1, but the diversity weight λ is positive and fixed during the algorithm, i.e., with γ = 0; 4) MCL-RAND(r,q), which randomly samples r clusters as a training set Â after every q rounds of the outer loop in Algorithm 1, and thus combines both MCL and SGD; 5) MCL(∆ > 0, λ > 0, γ > 0), which uses the scheduling of both λ and k shown in Algorithm 1. We tried five different combinations of {q, r} for MCL-RAND(r,q) and five different ∆ values for MCL(∆ > 0, λ > 0, γ > 0), and report the one with the smallest test error. Other parameters, such as the initial values for λ and k, the values for γ and p, and the total number of clusters are the same for different variants (the exact values of these quantities are given in Table 4 of the Appendix). In MCL, running greedy is the only extra computation comparing to normal SGD. To show that in our implementation (see Section 4.6) its additional time cost is negligible, we report in Table 2 the total time cost for MCL(∆ > 0, λ > 0, γ > 0) and the time spent on our implementation WS-SUBMODULARMAX.

We summarize the main results in Figure 1 2 3 4 5 6 7 8 . More results are given at the end of the appendix (Section 4.7). In all figures, grey curves correspond to the ten trials of SGD under a random curriculum. The legend in all figures gives the parameters used for the different methods using the following labels: 1) SPL (ρ, µ); 2) SPLD(ρ, ξ); and 3) MCL-RAND(q, r). SPL(ρ = 15, μ = 0.2) SPLD(ρ = 15, ξ = 0.1) MCL(, = 0, λ = 0, γ = 0) MCL(, > 0, λ > 0, γ = 0) MCL(, = 0, λ > 0, γ > 0) MCLΔRAND(μ = 4, r = 8) MCL(, > 0, λ > 0, γ > 0)

Figure 2 : Test error rate (%) vs. number of distinct labeled samples ever needing loss gradient calculation (left) and number of training batches (right) on CIFAR10 (grey curves represents 10 random trials of SGD). corresponding to training time. Note only MCL and its variants use the clustering trick, while SPL/SPLD need to compute loss on every sample and thus require knowledge of the labels of all samples. The left plot shows only the number of loss gradient calculations needed -1) in MCL, for those clusters never selected in the curriculum, the loss (and hence the label) of only the centroid sample is needed; 2) in SPL/SPLD, for those samples never selected in the curriculum, their labels are needed only to compute the loss but not the gradient, so they are not reflected in the left plots of all figures because their labels are not used to compute a gradient. Therefore, thanks to the clustering trick, MCL and its variants can train without needing all labels, similar to semi-supervised learning methods. This can help to reduce the annotation costs, if an MCL process is done in tandem with a labeling procedure analogous to active learning. The right plots very roughly indicate convergence rate, namely how the test error decreases as a function of the amount of training. SPL(ρ = 10, μ = 0.1) SPLD(ρ = 10, ξ = 0.2) MCL() = 0, λ = 0, γ = 0) MCL() = 0, λ > 0, γ > 0) MCLΔRAND(μ = 5, r = 10) MCL() > 0, λ > 0, γ = 0) MCL() > 0, λ > 0, γ > 0) SPL(ρ = 10, μ = 0.1) SPLD(ρ = 10, ξ = 0.2) MCL(Δ = 0, λ = 0, γ = 0) MCL(Δ > 0, λ > 0, γ = 0) MCL(Δ = 0, λ > 0, γ > 0) MCLΔRAND(μ = 5, r = 10) MCL(Δ > 0, λ > 0, γ > 0) On all datasets, MCL and most of its variants outperform SPL and SPLD in terms of final test accuracy (shown in Table 1 ) with comparable efficiency (shown in the right plots of all figures). MCL is slightly slower than SGD to converge in early stages but it can achieve a much smaller error when using the same number of labeled samples for loss gradients. Moreover, when using the same learning rate strategy, they can be more robust to overfitting, as shown in Figure 2 . Comparing Figure 1 with Figure 2 3 4 5 6 , MCL has the advantage when applied to deep models. Among the five variants of MCL, MCL(λ > 0, γ > 0, ∆ > 0) achieves the fastest convergence speed in later stages and the smallest final test error, while MCL(∆ = 0, λ = 0, ∆ = 0) usually achieves the worst performance (the only exception is on News20). Comparison between MCL(∆ = 0, λ > 0, γ > 0) and MCL(λ = 0, γ = 0, ∆ = 0) shows that decreasing diversity improves the performance. MCL(λ > 0, γ > 0, ∆ > 0) always outperforms MCL(∆ = 0, λ > 0, γ > 0). This indicates that increasing k can bring advantages, e.g., more improvements in later stages. MCL(λ > 0, γ > 0, ∆ > 0) always outperforms MCL(∆ > 0, λ > 0, γ = 0), which supports our claim that it is better to decrease the diversity as training proceeds rather than keeping it fixed. In particular, MCL(∆ > 0, λ > 0, γ = 0) shows slower convergence than other MCL variants in later stages. In our experiments in the MCL(∆ > 0, λ > 0,γ = 0) case, we needed to carefully choose λ and use a relatively large ∆ for it to work at all, as otherwise it would repeatedly choose the same subset (with small ∆, the loss term decreases as training proceeds, so with fixed λ the diversity term comes to dominate the objective). This suggests that a large diversity encouragement is neither necessary nor beneficial when the model matures, possibly since k is large at that point and there is ample opportunity for a diversity of samples to be selected just because k is large, and also since encouraging too much loss-unspecific diversity at that point might only select outliers.

(ρ = 25, ξ = 0.01) MCL-RAND(μ = 3, r = 16) MCL() > 0, λ > 0, γ = 0) MCL() = 0, λ > 0, γ > 0) MCL() = 0, λ = 0, γ = 0) MCL() > 0, λ > 0, γ > 0)

The combination of MCL and random curriculum (MCL-RAND) speeds up convergence, and sometimes (e.g., on MNIST, SVHN and Fashion-MNIST) leads to a good final test accuracy, but requires more labeled samples for gradient computation and still cannot outperform MCL(λ > 0, γ > 0, ∆ > 0). These results indicate that the diversity introduced by submodular regularization does yield improvements, and changing both hardness and diversity improves performance.

Figure 7 and Figure 8 shows how the "number of distinct labeled samples ever needing loss gradient calculation" changes as training proceeds. It shows how the different methods trade-off between "training on more new samples" vs. "training on fewer distinct samples more often." Thanks to the clustering trick, MCL and its variants usually require fewer labeled samples for model training than SGD but more than SPL and SPLD.

4. APPENDIX:



4.1. PROOF OF LEMMA 1:

Proof. We have

κ G = 1 -min j∈V L(j) + λF (j|V \j) L(j) + λF (j) = λ • max j∈V F (j) -F (j|V \j) L(j) + λF (j) = λ • max j∈V 1 -F (j|V \j) F (j) L(j) F (j) + λ ≤ λ • κ F min j∈V L(j) F (j) + λ = κ F c 1 /λ + 1

Where c 1 min j∈V L(j) F (j) .

4.2. PROOF OF PROPOSITION 1:

Proposition 1. The maximum of multiple β-strongly convex functions is β-strongly convex as well.

Proof. Let g(x) = max i g i (x), where g i (x) is β-strongly convex for any i. According to a definition of strongly convex function given in Theorem 2.1.9 (page 64) of (Nesterov, 2004) , ∀λ ∈ [0, 1], we have

g i (λx + (1 -λ)y) ≤ λg i (x) + (1 -λ)g i (y) - β 2 λ(1 -λ) x -y 2 2 , ∀i.

The following proves that g(x) is also β-strongly convex:

g(λx + (1 -λ)y) = max i g i (λx + (1 -λ)y) ≤ max i [λg i (x) + (1 -λ)g i (y)] - β 2 λ(1 -λ) x -y 2 2 ≤ max i λg i (x) + max i (1 -λ)g i (y) - β 2 λ(1 -λ) x -y 2 2 =λg(x) + (1 -λ)g(y) - β 2 λ(1 -λ) x -y 2 2 .

4.3. PROOF OF THEOREM 1:

Proof. The objective g(w) of the minimax problem in Eq. ( 2) after eliminating A is given in Eq. ( 4). Since G(A) in Eq. ( 5) is monotone non-decreasing submodular, the optimal subset A when defining g(w) in Eq. ( 4) always has size k if |V | ≥ k. In addition, because the loss function L (y i , f (x i , w)) is β-strongly convex, g(w) in Eq. ( 4) is the maximum over multiple kβ-strongly convex functions with different A. According to Proposition 1, g(w) is also kβ-strongly convex, i.e.,

EQUATION

Since the convex function g(w) achieves minimum on w * , it is valid to substitute ∇g(w * ) = 0 ∈ ∂g(w * ) into Eq. ( 14). After rearrangement, we have

EQUATION

In the following, we will prove g(w * ) ≥ α • g( ŵ), which together with Eq. ( 15) will lead to the final bound showing how close ŵ is to w * .

Note ĝ(w) (Eq. ( 6)) is a piecewise function, each piece of which is convex and associated with different Â achieved by a submodular maximization algorithm of approximation factor α. Since Â is not guaranteed to be a global maxima, unlike g(w), the whole ĝ(w) cannot be written as the maximum of multiple convex functions and thus can be non-convex. Therefore, gradient descent in lines 6-9 of Algorithm 1 can lead to either: 1) ŵ is a global minima of ĝ(w); or 2) ŵ is a local minima of ĝ(w). Saddle points do not exist on ĝ(w) because each piece of it is convex. We are also assuming other issues associated with the boundaries between convex pieces do not repeatedly occur.

1) When ŵ is a global minima of ĝ(w), we have

g(w * ) ≥ ĝ(w * ) ≥ ĝ( ŵ) ≥ α • g( ŵ).

(16) The first inequality is due to g(•) ≥ ĝ(•). The second inequality is due to the global optimality of ŵ. The third inequality is due to the approximation bound ĝ(•) ≥ α • g(•) guaranteed by the submodular maximization in Step 7 of Algorithm 1.

2) When ŵ is a local minima of ĝ(w), we have ∇ĝ( ŵ) = 0. Let h(w) be the piece of ĝ(w) where ŵ is located, then ŵ has to be a global minima of h(w) due to the convexity of h(w). Let A denote the ground set of Â on all pieces of ĝ(w), we define an auxiliary convex function g(w) as

EQUATION

It is convex because it is defined as the maximum of multiple convex function. So we have ĝ(w) ≤ g(w) ≤ g(w), ∀w ∈ R m .

(18) The first inequality is due to the definition of A, and the second inequality is a result of A ⊆ 2 V by comparing g(w) in Eq. ( 4) with g(w) in Eq. ( 17). Let w denote a global minima of g(w), we have

EQUATION

The first inequality is due to Eq. ( 18), the second inequality is due to the global optimality of w on g(w), the third inequality is due to the definition of g(w) in Eq. ( 17) (g(w) is the maximum of all pieces of ĝ(w) and h(w) is one piece of them), the fourth inequality is due to the global optimality of ŵ on h(w), the last inequality is due to the approximation bound ĝ(•) ≥ α • g(•) guaranteed by the submodular maximization in Step 7 of Algorithm 1.

Therefore, in both cases we have g(w * ) ≥ α • g( ŵ). Applying it to Eq. ( 15) results in

EQUATION

4.4. PROPOSITION 2:

Proposition 2. If x ∈ [0, 1], the following inequality holds true.

x 1 -e -x -1 ≤ x.

(21)

Proof. Due to two inequalities e x ≤ 1 + x + x 2 /2 for x ≤ 0 and 1 -e -x ≥ x/2 for x ∈ [0, 1],

EQUATION

4.5 PROOF OF COROLLARY 1

Proof. Applying the inequality in Proposition 2 and the approximation factor of lazy greedy α = (1 -e -κ G )/κ G to the right hand side of Eq. ( 9) from Theorem 1 yields

EQUATION

where κ G is the curvature of submodular function G(•) defined in Eq. ( 5). Substituting the inequality about κ G from Lemma 1 into Eq. ( 23) results in

EQUATION

We use subscript as the index for iterations in the outer-loop, e.g., ŵT is the model weights w after the T th iteration of outer-loop. If we decrease λ exponentially from λ = λ 0 and increase k linearly from k = k 0 , as Step 11 in Algorithm 1, we have

EQUATION

According to the definition of g(•) in Eq. ( 4), for g(w * T ) we have g(w *

T ) = min

EQUATION

EQUATION

Substituting Eq. ( 26) to Eq. ( 25) yields

EQUATION

If we can tolerate more expensive computational cost for running submodular maximization with larger budget k, and increase k exponentially, i.e., k

EQUATION

)

This completes the proof.

4.6. SUBMODULAR MAXIMIZATION STARTING FROM A PREVIOUS "WARM" SOLUTION:

Algorithm 1 repeatedly runs a greedy procedure to solve submodular maximization, and this occurs two nested loops deep. In this section we describe how we speed this process up.

Our first strategy reduces the size of the ground set before starting a more expensive submodular maximization procedure. We use a method described in (Wei et al., 2014a) where we sort the elements of V non-increasingly by G(i|V \ i) and then remove any element i from V having G(i) < G(δ(k)|V \ δ(k)) where δ(k) is k th element in the sorted permutation. Any such element will never be chosen by the k-cardinality constrained greedy procedure because for any ∈ {1, 2, . . . , k}, and any set A, we have

G(δ( )|A) ≥ G(δ( )|V \ δ( )) ≥ G(δ(k)|V \ δ(k)) > G(i) ≥ G(i|A)

and thus greedy would always be able to choose an element better than i. This method results in no reduction in approximation quality, although it might not yield any speedup at all. But with a decreasing λ, G(A) becomes more modular, and the filtering method can become more effective. Other methods we can employ are those such as (Zhou et al., 2017; Mirzasoleiman et al., 2015) , resulting in small reduction in approximation quality, but we do not describe these further.

The key contribution of this section is a method exploiting a potential warm start set that might already achieve a sufficient approximation quality. Normally, the greedy procedure starts with the empty set and adds elements greedily until a set of size k is reached. In Algorithm 1, by contrast, a previous iteration has already solved a size-k constrained submodular maximization problem for the previous submodular function, the solution to which is one that could very nearly already satisfy a desired approximation bound for the current submodular function. The reason for this is that, depending on the weight update method in line 9 of Algorithm 1 between inner loop iterations, and the changes to parameters ∆ and γ between outer iterations, the succession of submodular functions might not change very quickly. For example, when the learning rate η is small, the Â from the previous iteration could still be valued highly by the current iteration's function, so running a greedy procedure from scratch is unnecessary. Our method warm-starts a submodular maximization process with a previously computed set, and offers a bound that trades off speed and approximation quality.

The approach is given in Algorithm 2, which (after the aforementioned filtering in line 3 (Wei et al., 2014a) ) tests in linear time if the warm start set Â already achieves a sufficient approximation quality, and if so, possibly improves it further with an additional linear or quasilinear time computation.

To test approximation quality of Â, our approach uses a simple modular function upper bound, in line 4, to compute an upper bound on the global maximum value. For the subsequent improvement of Â, our approach utilizes a submodular semigradient approach (Iyer et al., 2013) (specifically subgradients (Fujishige, 2005) in this case). If the warm-start set Â does not achieve sufficient approximation quality in line 5, the algorithm backs off to standard submodular maximization in line 11 (we use the accelerated/lazy greedy procedure (Minoux, 1978) here although other methods, e.g., (Mirzasoleiman et al., 2015) , can be used as well).

Algorithm 2 Start (WS) WS-SUBMODULARMAX(G, k, Â, α ∈ [0, 1))

1: Input: G(•), k, Â, α 2: Output: Ã 3: Reduce ground set size: arrange V non-increasingly in terms of G(i|V \i) in a permutation δ where δ(k) is the k th element, set V ← {i ∈ V |G(i) ≥ G(δ(k)|V \δ(k))}; 4: Compute upper bound to maximum of Eq. ( 5):

τ = max A∈V,|A|≤k i∈A L y i , f (x i , w t ) + λF (i) 5: if G( Â) ≥ α • τ then 6:

Permutation σ of V : the first k elements have S σ k = Â and are chosen ordered non-increasing by κ G (v); the remaining n -k elements V \ Â for σ are chosen non-increasing by κ G (v).

7: Define modular function h:

Â(A) i∈A h Â(i) with h Â(σ(i)) = G(S σ i ) -G(S σ i-1 ); 8: Compute tight, at Â, lower bound L(A) of G(A): L(A) G( Â) + h Â(A) -h Â( Â) ≤ G(A) 9: Ã ← argmax A∈V,|A|≤k L(A); 10: else 11: Ã ← LAZYGREEDY(G, V, k); 12: end if

Line 4 computes the upper bound τ ≥ max A∈V,|A|≤k G(A) which holds due to submodularity, requiring only a modular maximization problem (which can be done in O(|V |) time, independent of k, to select the top k elements). Line 5 checks if an α approximation to this upper bound is achieved by the warm-start set Â, and if not we back off to a standard submodular maximization procedure in line 11.

If Â is an α approximation to the upper bound τ , then lines 6-9 runs a subgradient optimization procedure, a process that can potentially improve it further. The approach selects a subgradient defined by a permutation σ = (σ(1), σ(2), . . . , σ(n)) of the elements. The algorithm then defines a modular function L(A), tight at Â and a lower bound everywhere else, i.e., L( Â) = G( Â), and ∀A, L(A) ≤ G(A). Any permutation will achieve this as long as Â = {σ(1), σ(2), . . . , σ(k)}. The specific permutation we use is described below. Once we have the modular lower bound, we can do simple and fast modular maximization. Lines 6-9 of Algorithm 2 offer a heuristic that can only improve the objective -letting Ã be the solution after line 9, we have

G( Ã) ≥ L( Ã) ≥ L( Â) = G( Â).

(30) The first inequality follows since L(•) is a lower bound of G(•); the second inequality follows from the optimality of Â+ ; the equality follows since L is tight at Â.

The approximation factor α is distinct from the submodular maximization approximation factor α achieved by the greedy algorithm. Setting, for example α = 1 -1/e would ask for the previous solution to be this good relative to τ , the upper bound on the global maximum, and the algorithm would almost always immediately jump to line 11 since achieving such approximation quality might not even be possible in polynomial time (Feige, 1998) . With α large, we recover the approximation factor of the greedy algorithm but ignore the warm start. If α is small, many iterations might use the warm start from the previous iteration, updating it only via one step of subgradient optimization, but with a worse approximation factor. In practice, therefore, we use a more lenient bound (often we set α = 1/2) which is a good practical tradeoff between approximation accuracy and speed (meaning lines 6-9 execute a reasonable fraction of the time leading to a good speedup, i.e., in our experiments, the time cost for WS-SUBMODULARMAX increases if α = 1 by a factor ranging from about 3 to 5). In general, we have the following final bound based on the smaller of α and α. SPL(ρ = 25, μ = 0.1) SPLD(ρ = 25, ξ = 0.4) MCL(Δ > 0, λ > 0, γ = 0) MCL(Δ = 0, λ > 0, γ > 0) MCLΔRAND(μ = 3, r = 12) MCL(Δ = 0, λ = 0, γ = 0) MCL(Δ > 0, λ > 0, γ > 0) SPL(ρ = 10, μ = 0.1) SPLD(ρ = 10, ξ = 0.2) MCL(, = 0, λ = 0, γ = 0) MCL(, = 0, λ > 0, γ > 0) MCLΔRAND(μ = 5, r = 10) MCL(, > 0, λ > 0, γ = 0) MCL(, > 0, λ > 0, γ > 0) SPL(ρ = 10, μ = 0.1) SPLD(ρ = 10, ξ = 0.2) MCL() = 0, λ = 0, γ = 0) MCL() = 0, λ > 0, γ > 0) MCLΔRAND(μ = 5, r = 10) MCL() > 0, λ > 0, γ = 0) MCL() > 0, λ > 0, γ > 0) SPL(ρ = 10, μ = 0.1) SPLD(ρ = 10, ξ = 0.2) MCL(Δ = 0, λ = 0, γ = 0) MCL(Δ = 0, λ > 0, γ > 0) MCLΔRAND(μ = 5, r = 10) MCL(Δ > 0, λ > 0, γ = 0) MCL(Δ > 0, λ > 0, γ > 0) 

Dataset:

(ρ = 25, ξ = 0.4) MCL(Δ > 0, λ > 0, γ = 0) MCL(Δ = 0, λ > 0, γ > 0) MCLΔRAND(μ = 3, r = 12) MCL(Δ = 0, λ = 0, γ = 0) MCL(Δ > 0, λ > 0, γ > 0)

(ρ = 25, ξ = 0.4) MCL(Δ > 0, λ > 0, γ = 0) MCL(Δ = 0, λ > 0, γ > 0) MCLΔRAND(μ = 3, r = 12) MCL(Δ = 0, λ = 0, γ = 0) MCL(Δ > 0, λ > 0, γ > 0)

:

The "v3" network from https://github.com/jseppanen/cifar_lasagne.

A variant of LeNet5 with 64 kernels for each convolutional layer.

The network structures for STL10 and SVHN can be found at https://github.com/ aaron-xichen/pytorch-playground

Similar to(Jiang et al., 2014), instead of specifying the absolute value of λ in each iteration, we find that specifying the number of selected samples k is more robust empirically. Because directly setting λ can result in selecting too many or too few samples, but SPL/SPLD needs to increase training samples gradually.

Figures and Tables:

Figure 1: Test error rate (%) vs. number of distinct labeled samples ever needing loss gradient calculation (left) and number of training batches (right) on 20newsgroups (grey curves represents 10 random trials of SGD).

Figures 1-6 show how the test error changes with (on the left) the number of distinct labeled samples ever needing a loss gradient calculation, and (on the right) the number of training batches,

Figure 3: Test error rate (%) vs. number of distinct labeled samples ever needing loss gradient calculation (left) and number of training batches (right) on Fashion-MNIST (grey curves represents 10 random trials of SGD).

Figure 4: Test error rate (%) vs. number of distinct labeled samples ever needing loss gradient calculation (left) and number of training batches (right) on STL10 (grey curves represents 10 random trials of SGD).

Figure 5: Test error rate (%) vs. number of distinct labeled samples ever needing loss gradient calculation (left) and number of training batches (right) on SVHN (grey curves represents 10 random trials of SGD).

Figure 6: Test error rate (%) vs. number of distinct labeled samples ever needing loss gradient calculation (left) and number of training batches (right) on MNIST (grey curves represents 10 random trials of SGD).

Figure 7: Number of distinct labeled samples ever needing loss gradient calculation vs. number of training batches for News20 (left), CIFAR10 (middle) and MNIST(right) (grey curves represents 10 random trials of SGD).

Figure 8: Number of distinct labeled samples ever needing loss gradient calculation vs. number of training batches for Fashion-MNIST (left), STL10 (middle) and SVHN (right) (grey curves represents 10 random trials of SGD).

Figure 9: Training error rate (%) vs. number of distinct labeled samples ever needing loss gradient calculation (left) and number of training batches (right) on 20newsgroups (grey curves represents 10 random trials of SGD).

Figure 10: Training loss vs. number of distinct labeled samples ever needing loss gradient calculation (left) and number of training batches (right) on 20newsgroups (grey curves represents 10 random trials of SGD).

Figure 11: Test loss vs. number of distinct labeled samples ever needing loss gradient calculation (left) and number of training batches (right) on 20newsgroups (grey curves represents 10 random trials of SGD).

Figure 12: Training loss vs. number of distinct labeled samples ever needing loss gradient calculation (left) and number of training batches (right) on CIFAR10 (grey curves represents 10 random trials of SGD).

Figure 13: Test loss vs. number of distinct labeled samples ever needing loss gradient calculation (left) and number of training batches (right) on CIFAR10 (grey curves represents 10 random trials of SGD).

Figure 14: Training error rate (%) vs. number of distinct labeled samples ever needing loss gradient calculation (left) and number of training batches (right) on MNIST (grey curves represents 10 random trials of SGD).

Figure 15: Training error rate (%) vs. number of distinct labeled samples ever needing loss gradient calculation (left) and number of training batches (right) on Fashion-MNIST (grey curves represents 10 random trials of SGD).

Figure 16: Training error rate (%) vs. number of distinct labeled samples ever needing loss gradient calculation (left) and number of training batches (right) on STL10 (grey curves represents 10 random trials of SGD).

Figure 17: Training error rate (%) vs. number of distinct labeled samples ever needing loss gradient calculation (left) and number of training batches (right) on SVHN (grey curves represents 10 random trials of SGD).

Test error (%) for different methods (SGD shows the lowest error out of 10 random trials).

Table content: <table><tr><td>Method</td><td colspan="7">Dataset News20 MNIST CIFAR10 STL10 SVHN Fashion</td></tr><tr><td>SGD(random)</td><td/><td>14.27</td><td>0.88</td><td>18.52</td><td>21.76</td><td>5.20</td><td>7.79</td></tr><tr><td>SPL</td><td/><td>15.43</td><td>1.25</td><td>21.14</td><td>20.63</td><td>5.67</td><td>7.46</td></tr><tr><td>SPLD</td><td/><td>16.23</td><td>1.18</td><td>20.79</td><td>21.25</td><td>5.40</td><td>7.80</td></tr><tr><td colspan="2">MCL(∆ = 0, λ = 0, γ = 0)</td><td>15.99</td><td>1.23</td><td>18.04</td><td>20.50</td><td>5.37</td><td>7.95</td></tr><tr><td colspan="2">MCL(∆ = 0, λ &gt; 0, γ &gt; 0)</td><td>16.54</td><td>0.95</td><td>17.33</td><td>19.70</td><td>4.95</td><td>7.29</td></tr><tr><td colspan="2">MCL(∆ &gt; 0, λ &gt; 0, γ = 0)</td><td>15.45</td><td>0.82</td><td>16.93</td><td>20.40</td><td>5.29</td><td>7.07</td></tr><tr><td>MCL-RAND</td><td/><td>16.23</td><td>0.80</td><td>17.12</td><td>20.42</td><td>5.18</td><td>6.92</td></tr><tr><td colspan="2">MCL(∆ &gt; 0, λ &gt; 0, γ &gt; 0)</td><td>14.12</td><td>0.75</td><td>12.87</td><td>17.83</td><td>4.19</td><td>6.36</td></tr></table>

and where U is a set of features. For a subset A of clusters, Total time (secs.) of MCL(∆ > 0, λ > 0, γ > 0) and time only on WS-SUBMODULARMAX.

Table content: <table><tr><td>Dataset</td><td>News20</td><td colspan="2">MNIST CIFAR10</td><td>STL10</td><td>SVHN</td><td>Fashion</td></tr><tr><td>Total time</td><td colspan="6">2649.19s 3418.97s 3677.73s 2953.47s 34153.81s 2927.18s</td></tr><tr><td>WS-SUBMODULARMAX</td><td>62.44s</td><td>35.33s</td><td>127.36s</td><td>206.70s</td><td>1892.62s</td><td>167.55s</td></tr></table>

Details regarding the datasets. × 10 -6 1 × 10 -6 8 × 10 -7 1 × 10 -7 1 × 10 -6 1 × 10 -6

Table content: <table><tr><td/><td colspan="3">News20 MNIST</td><td>CIFAR10</td><td>STL10</td><td colspan="2">SVHN Fashion</td></tr><tr><td>#Training</td><td/><td>11314</td><td>50000</td><td>50000</td><td>5000</td><td>73257</td><td>50000</td></tr><tr><td>#Test</td><td/><td>7532</td><td>10000</td><td>10000</td><td>8000</td><td>26032</td><td>10000</td></tr><tr><td>#Feature</td><td/><td colspan="6">129791 28 × 32 × 32 × 3 96 × 96 × 3 32 × 32 28 × 28</td></tr><tr><td>#Class</td><td/><td>20</td><td>10</td><td>10</td><td>10</td><td>10</td><td>10</td></tr><tr><td>Dataset</td><td colspan="2">News20</td><td>MNIST</td><td>CIFAR10</td><td>STL10</td><td>SVHN</td><td>Fashion</td></tr><tr><td>p</td><td/><td>50</td><td>50</td><td>20</td><td>20</td><td>20</td><td>50</td></tr><tr><td>#cluster</td><td/><td>200</td><td>1000</td><td>1000</td><td>400</td><td>800</td><td>1000</td></tr><tr><td>γ</td><td/><td>0.05</td><td>0.05</td><td>0.05</td><td>0.2</td><td>0.2</td><td>0.05</td></tr><tr><td>initial k</td><td/><td>4</td><td>4</td><td>4</td><td>20</td><td>30</td><td>10</td></tr><tr><td colspan="2">initial λ 6 initial η</td><td>3.5</td><td>0.02</td><td>0.01</td><td>0.02</td><td>0.01</td><td>0.02</td></tr></table>

Parameters of MCL (Algorithm 1) and its variants for different datasets.

Table content: <table/>

Peer review (iclr2018):
 The main strength of this paper, I think, is the theoretical result in Theorem 1. This result is quite nice. I wish the authors actually concluded with the following minor improvement to the proof that actually strengthens the result further. The authors ended the discussion on thm 1 on page 7 (just above Sec 2.3) by saying what is sufficiently close to w*. If one goes back to (10), it is easy to see that what converges to w* when one of three things happen (assuming beta is fixed once loss L is selected). 1) k goes to infinity 2) alpha goes to 1 3) g(w*) goes to 0 The authors discussed how alpha is close to 1 by virtue of submodular optimization lower bounds there for what is close to w*. In fact this proof shows the situation is much better than that. If we are really concerned about making what converge to w*, and if we are willing to tolerate the increasing computational complexity associated solving submodular problems with larger k, we can schedule k to increase over time which guarantees that both alpha goes to 1 and g(w*) goes to zero. There is also a remark that G(A) tends to be modular when lambda is small which is useful. From the algorithm, it seems clear that the authors recognized these two useful aspects of the objective and scheduled lambda to decrease exponentially and k to increase linearly. It would be really nice to complete the analysis of Thm1 with a formal analysis of convergence speed for ||what-w*|| as lambda and k are scheduled in this fashion. Such an analysis would help practitioners make better choices for the hyper parameters gamma and Delta.