Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: The paper proposes a theoretically founded method to generate subsets of a dataset, together with corresponding sample weights in a way that the average gradient of the subset is at most epsilon far from the average gradient of the full dataset. Given such a subset, the authors provide theoretical guarantees for convergence to an epsilon neighborhood of the optimum for strongly convex functions. The proposed algorithm to create such a subset is a greedy algorithm that relies on parameter independent similarities between samples, namely similarity scores that are true regardless of the current value of the function parameters.

Although I find the approach interesting, I have three main concerns with the proposed method.
1. The experimental setup is lacking significant information, baselines and baseline tuning (see below for more in depth comments).
2. The proposed upper bound which has been used for a similar purpose by [1] becomes nonsensical in high dimensions and although for [1] this would mean sampling with a non optimal sampling distribution for CRAIG it means converging very far from the optimum. What are the values of epsilon that you observe in practice?
3. I do not see how CRAIG would be applied to deep learning. The argument in section 3.4 is that the variance of the gradient norm is captured by the gradient of the last layer or last few layers, however this is true given the parameters of the neural network. The gradients can change arbitrarily after a very small number of parameter updates as shown by [2].

Experimental setup
----------------------------

For the case of the convex problems, the learning rate is not tuned independently for each method. Even more importantly the stepsizes of CRAIG are all numbers larger than 1 so the expected learning rate is multiplied by the average step size. This makes it difficult to understand whether the speedup is due to a larger learning rate or due to CRAIG. Similarly for figure 3 the result could be due to a non decreasing step size because of \gamma_j while for CRAIG \gamma_j are ordered in decreasing order.

In addition, there is no experimental analysis of the epsilon bound and the actual difference of the gradients for the subset and the full dataset. There are also no baselines that use a subset to train. A comparison with a baseline that uses 1. random subset or 2. a subset selected via importance sampling from [1] would contribute towards understanding the particular benefits of CRAIG.

Regarding the neural network experiments:
1. There is no explicit definition of the similarity function used for the case of neural networks. If we assume based on 3.4 that the algorithm requires an extra forward pass in the beginning of every epoch there should be visible steps in Figure 3 where time passes but the loss doesn't move.
2. 2000 seconds and 80% accuracy on MNIST points towards a mistake on the implementation of the training. On a laptop CPU it takes ~15s per epoch and achieves ~95% test accuracy from the first epoch for the neural network described.
3. Similarly 80% accuracy on CIFAR10 is sufficiently low for Resnet-56 to be alarming.

[1] Zhao, Peilin, and Tong Zhang. "Stochastic optimization with importance sampling for regularized loss minimization." international conference on machine learning. 2015.
[2] Defazio, Aaron, and Léon Bottou. "On the ineffectiveness of variance reduced optimization for deep learning." arXiv preprint arXiv:1812.04529 (2018).
review_title: Official Blind Review #4

final_score: rating: 3: Weak Reject
review_content: This paper proposes a novel extension to SGD/incremental gradient methods called CRAIG. The algorithm selects a subset of datapoints to approximate the training loss at the beginning of each epoch in order to reduce the total amount of time necessary to solve the empirical risk minimization problem. In particular, the algorithm formulates a submodular optimization problem based on the intuition that the gradient of the problem on the selected subset approximates the gradient of the true training loss up to some tolerance. Each datapoint in the subset is a medoid and assigned a weight corresponding to the number of datapoints in the full set that are assigned to that particular datapoint. A greedy algorithm is employed to approximately solve the subproblem. Theory is proven based on based on an incremental subgradient method with errors. Experiments demonstrate significant savings in time for training both logistic regression and small neural networks.

Strengths:

The proposed idea is novel and intriguing, utilizing tools from combinatorial optimization to select an appropriate subset for approximating the training loss. Based on the experiments provided in the paper, it does appear to yield a significant speedup in training time. It is interesting to observe how the order of the datapoints matter significantly for training, and that CRAIG is also able to naturally define a good ordering of the datapoints for SG training. This is strong algorithmic work.

Weaknesses:

Some questions I had about the work:

- How well does one have to approximate $d_{ij}$ in order for the method to be effective? The authors provide an approach to approximate this for both logistic regression and neural networks. How does one guarantee that one is obtaining the maximum over $x in \mathcal{X}$ for neural networks via backpropagating only on the last layer? Does taking this maximum matter?
- How does one choose $\epsilon$? Is this related to how $d_{ij}$’s are approximated?
- If one were to consider an algorithm that samples points from this new distribution over the data given by CRAIG, if one were to include the weight $\gamma_j$ into the algorithm, would the sample gradient be unbiased? What if one were to simply use $\gamma_j$ to weight that particular sample in the new distribution?
- In machine learning, the empirical risk (finite-sum) minimization problem is an approximation to the true expected risk minimization problem. What is the effect of CRAIG on the expected risk? Is there any deterioration in generalization performance?
- In page 4, what does the $\min_{S \subseteq V}$ refer to? Should the equation be interpreted as with the set $S$ fixed or not?
- Theorems 1 and 2 are stated a bit non-rigorously. Are these theorems for fixed $k$? What does it mean for these bounds that $k \rightarrow \infty$?
- In Theorems 1 and 2, what is the bound on the steplength in order to obtain the convergence result for $\tau = 0$?
- In Theorem 1 for $0 < \tau < 1$, why does one obtain a result where $\|x_k – x_*\|^2 \leq 2 \epsilon R / \mu$, why is the distance to the solution bounded by a constant? What if one were to initialize $x_0$ to be such that $\|x_0 – x_*\|^2 > 2 \epsilon R / \mu$? (Similar for Theorem 2.)
- In the experiments, how is the steplength and other hyperparameters tuned? Are multiple trials run? 
- Is $\epsilon$ used to determine the subset or is it based on a predetermined subset size?
- How do the final test losses compare between CRAIG and the original algorithms?
- How do the relative distances (rather than the absolute distance) to the solution behave?
- How does CRAIG perform over multiple epochs? How does the algorithm transition when the subset is changed (as in neural networks)?
- Why does CovType appear more stable with the shuffled version over the other datasets? Is the stability related to the distribution of the weights $\gamma_j$?

Some grammatical errors/typos/formatting issues:

- Equation (9) needs more space between the $\forall x, i, j$ and the rest of the equation.
- What is $\Delta$ on page 5? Is it supposed to be $F$?
- On page 8, And should not be capitalized.
- Page 14, prove not proof
- Page 14, subtracting not subtracking
- Page 16, cycle not cycke

Overall, although I like the ideas in the paper, the paper still needs some significant amount of refining in terms of both writing and theory, as well as some additional experiments to be convincing. If the comments I made above were addressed, I would be open to changing my decision. 
review_title: Official Blind Review #1

final_score: rating: 8: Accept
review_content: This paper presents a method for subselecting training data 
in order to speed up incremental gradient (IG) methods (in terms of computation time). 
The idea is to train a model on a representative subset of the data such 
that the computation time is significantly decreased without 
significantly degrading performance. Given a dataset D and 
subset S selected by the proposed method, it is shown that 
training on subset S achieves nearly the same loss as training on the full 
dataset D would, while achieving significant computational speedups.

This paper is a clear accept. The approach is novel and has well-developed 
theory supporting it. The empirical evaluation of the method shows 
large speedups in training time without degradation in performance 
for reasonably large subsets (e.g. 20% of the data). The paper is 
very clear, well-written, and was a genuinely fun read.

Clarifying questions:
  - In results reporting speedups, does the reported training time for CRAIG 
  include the preprocessing time? Or only the time spent running IG on the resulting 
  subset?
  - How many runs are the experiments averaged over? There don't seem to be 
  error bars, which makes it difficult to assess whether the speedups are 
  statistically significant
  - I imagine that an approach like this would be desirable when working with  very large datasets. Has 
  CRAIG been evaluated in settings with millions of datapoints? Or does it become impractical? I think 
  that the paper stands on its own without such a demonstration, but it would go a long way towards 
  encouraging mainstream adoption of your method.
  - Figure 3, left: What could be happening at around 40s? It looks like 
  all three of the random permutations have a spike in loss at around the same time, despite being 
  different permutations of the sub-selected data
  - How were hyperparameters, such as the regularization parameter, step-size etc. chosen? One of the 
  main claims of the paper is that using the subset selected by CRAIG doesn't significantly 
  effect the optimization performance. But if the baselines weren't thoroughly tuned, it could be the case 
  that IG on the CRAIG subset performs similarly to IG on the full training data, but that neither 
  is actually reaching satisfactory performance in a given domain.
  - Figure 4: isn't 2000s \approx 30min really slow for MNIST? From what I remember, reasonable test accuracy 
  on MNIST with a feed-forward network with a single layer takes only a few minutes? Though admittedly, I could 
  be misremembering this.
  
Somewhat open-ended questions:
  - To what extent are the results hardware dependent? Do you see similar results on 
  different hardware? I'm wondering how much of the speedup could be attributed to 
  something like better memory locality when using the smaller subset selected using CRAIG.
  - Section 3.4 mentions that the O(|V||S|) complexity can be reduced 
  to O(|V|) using a stochastic greedy algorithm. Has the performance 
  when training on a subset selected via the stochastic algorithm 
  been compared to the performance when training on a subset selected by the 
  deterministic version? 

I have only minor suggestions:
  - The CRAIG Algorithm 
    - When F is introduced, I had trouble conceptualizing what kind of object it was. I think 
      mentioning what spaces it's mapping between could increase readability.
    - Mirzasoluiman et al. (2015a) looks like it is supposed to be a parenthetical citation
  - Figure 4: The caption labels appear to be swapped. In the figure, (a) is MNIST, but in the 
    caption, (b) is MNIST
  - 5.1: There is a vertical space issue between the introduction of section 5 and section 5.1. 
  I suspect this was necessary to make the max page requirements. If space is an issue, my suggestion would 
  be to move Algorithm 1 to the appendix. It's nice to have a concrete algorithm specification, but I personally 
  did not find that it aided my understanding of your paper.
review_title: Official Blind Review #3

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

The reviewers were quite split on the paper. 

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

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

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