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 continuous-discrete 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 while achieving the same performance. 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. Inspired by the human interaction between teacher and student, recent studies BID28 BID2 BID56 ) 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) BID6 , 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) BID31 BID58 BID57 BID59 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: DISPLAYFORM0 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 BID27 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) BID26 , 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 BID1 ) 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 BID7 BID5 . 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 BID28 BID59 BID2 ) 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) BID53 and experimental design BID43 , 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 BID62 . 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 BID51 BID19 , 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 BID13 BID52 BID14 BID15 selects samples that are most uncertain, while query by committee BID54 BID14 BID0 selects the ones that multiple models most disagree on. With machine teaching BID28 BID66 BID49 BID65 , 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 BID8 BID35 BID39 BID29 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 BID10 BID38 ).
Minimax Curriculum Learning is a machine teaching method involving increasing desirable hardness and scheduled reducing diversity.  A curriculum learning approach using a submodular set function that captures the diversity of examples chosen during training.  The paper introduces MiniMax Curriculum learning as an approach for adaptively training models by providing it different subsets of data. 