Insufficient details to formally understand the guarantees of Algorithm 1 subroutines; additional pseudocode would be helpful

Please refer to the general response where we detail the algorithm.

The subroutine $\text{ComputeImportanceSampling}$ is intentionally abstract, to represent any importance-sampling heuristic. The purpose of this subroutine is to compute the importance of each mini-batch sample and update the memory vector $q$. We will include pseudo-code implementation for our specific importance function.

Algorithm 1: no convergence analysis, when importance sampling probabilities can be quickly approximated

Deriving general convergence properties for the algorithm is not feasible as it depends on the sampling distribution. Faster convergence is expected when the distribution closely aligns with the norm of the true gradient. Figure 7 illustrates that our sampling distribution is the closest to the gradient norm.

The computation of sample importance can introduce overhead. Our importance function adds negligible overhead, especially compared to the state of the art. For categorical cross entropy an analytical expression is avilable (Eq.5). Automatic differentiation can be used for other loss functions; its performance impact is also low, as seen in Figure 10.

Unclear what the framework in Section 4 is proposing

In Section 4 we first analytically derive the importance function for the categorical cross entropy loss. Then we generalize our idea to regression tasks. In particular, we only need to compute the loss gradient w.r.t. the network output to apply our importance sampling strategy to other tasks.

More SGD acceleration methods to compare to

We have compared our method against state-of-the-art importance and adaptive sampling methods like DLIS, LOW and loss-based importance sampling. Our approach, in principle, can be combined with other variance reduction strategies. However, we believe that this would require additional exploration and goes beyond the scope for this work.

How does data-point sampling work, based on the the approximate probabilities?

We first normalize the persistent importance distribution $q$ to obtain a probability distribution $p$ (Algorithm 1, L6) that is then used to select data points (L7). Standard routines can be used to perform the importance sampling given $p$. Our implementation uses numpy.random.choice; another option is torch.multinomial.

Note that when sampling multiple data points simultaneously, it is important to use sampling with replacment, otherwise the prescribed probability distribution $p$ will not be obeyed.

Transformer

We have performed additional experiments on CIFAR-10 using vision transformers (ViT). The results show consistent improvement of ours IS/AS over LOW and DLIS. We will add the plot to the appendix.

DLIS underperformance on Oxford flower 102

The Oxford flower 102 dataset comprises 102 classes across 1020 images, i.e. 10 images/class, which is sparse compared to other datasets. In this example, DLIS has a poor performce as the mini-batch size is small. This, in combination with a resampling-based algorithm with high class count, yields poor gradient estimation, making it hard for the method to converge.

Figure 7

In this figure, we refer to the norm of gradient w.r.t. all parameters as the full gradient norm. We use this term to distinguish it from importance distribution based on subsets of network (DLIS, ours).

Parameter $\alpha$ in Eq.7

We choose $\alpha$ via grid search in $\{0,0.1,0.2,0.3\}$ depending on the task.

Naming convention

The gradient of a network lives in parameter space. The gradient can be seen as a multivariate vector. We generally refer to the different parameters as dimensions in this parameter space. We will clarify.

The error in the parameter-gradient estimation depends on the sampling strategy. A sampling distribution may yield an estimation that is accurate for parameters and poor for others. A good distribution achieves low error across all parameters at the same time. We refer to this as compromise of quality across dimensions.

Imporvement over DLIS

The main distinctions and reasons for improvement lie in the algorithm and the computation of weights. Utilizing the derivative of the loss with respect to the model output is significantly faster than DLIS's importance metric for comparable distributions. Additionally, unlike DLIS, our algorithm does not rely on resampling which avoids the computational cost of forward passes on samples without subsequent backward loops. These two differences account for the superior performance of our approach at equal time comparison.

Figure 1 shows that both DLIS and our approach have similar importance distribution, but ours is computationally efficient.

Figure 7 further compares the weights. Ours and DLIS weights are closer to the optimal weights.

Correction of Eqn. 6

We regret the typo in this equation. We have corrected this equation and it has the following form: $\left\Vert \frac{\partial \mathcal{L}(x_i)}{\partial \theta} \right\Vert = \left\Vert \frac{\partial \mathcal{L}(x_i)}{\partial m(x_i,\theta)} \cdot \frac{\partial m(x_i,\theta)}{\partial \theta} \right\Vert \leq \left\Vert \frac{\partial \mathcal{L}(x_i)}{\partial m(x_i,\theta)} \right\Vert \cdot \left\Vert \frac{\partial m(x_i,\theta)}{\partial \theta} \right\Vert$.

Since the gradient of the loss wrt the parameter $\theta$ is bounded by the gradient wrt the output layer, we chose to importance sample this term: our analytic importance function (shown in eqn. 5). The purpose of this equation 6 is to provide a bound on the derivative with respect to the model parameters, not the input. We will add this clarification in the revised version.

Title choice

We mean "adaptive sampling" and "importance sampling", both of which are standard terms in literature. We are happy fully spell these out in the title, unless reviewers think this would make it overly verbose.

What is meant with the sentence: In this method, as outlined in eq. (3), each data point’s weight, denoted as w(xi), remains constant at N. ?

In adaptive sampling, achieving a proper average estimator requires the weight $w$ to compensate for the factor $1/|\Omega|$ in front of the summation. Hence, we set the weight to the dataset size: $w(x_i) = |\Omega|$.

Limitations/drawbacks beyond weight calculation overhead

Our proposed algorithm relies on a memory of the data importance, with size proportional to the dataset size. In cases where data is streamed and not stored, the algorithm cannot be applied. It can also create outdated importance for data if this memory is not updated often enough. This can happen with a high learning rate and result in a poor sampling distribution. In the worse case, the error in the gradient estimation can be higher than without importance sampling.

Another limitation is related to non-uniform data sampling: The samples that go into a mini-batch are not laid out contiguously in memory, which slows down their loading. We believe that a careful implementation can mitigate this issue.

We will add a paragraph at the end of the result section to discuss the limits and drawbacks of the algorithm and sampling strategy.

Other concerns

From our experiments, the proposed method does not suffer from more overfitting than other methods. In all our presented experiments, we have reported the metric tested on data never seen during training.

Note: The term "Recently" in the reported sentence is a typo and will be corrected.

Link between adaptive sampling and adaptive weighting (LOW)

Adaptive sampling selects samples non-uniformly while weighting them equally. The same sample can be selected multiple times during training, giving it a higher "weight". Adaptive weighting directly assigns higher weight to more important samples, while selecting the samples uniformly. The two strategies are very similar, and our framework can be tailored to perform either. Applying weighting through sampling is known to achieve better performance than explicit weighting.

Additional related work

We will discuss the recommended citations in the related work section.

Figure readability

We will add zoom-ins in Figure 5 to clearly show the differences in convergence behavior near the tails of the plots.