It is well known that selecting samples with large losses/gradients can
significantly reduce the number of training steps. However, the selection
overhead is often too high to yield any meaningful gains in terms of overall
training time. In this work, we focus on the greedy approach of selecting
samples with large \textit{approximate losses} instead of exact losses in order
to reduce the selection overhead. For smooth convex losses, we show that such a
greedy strategy can converge to a constant factor of the minimum value of the
average loss in fewer iterations than the standard approach of random
selection. We also theoretically quantify the effect of the approximation
level. We then develop SIFT which uses early exiting to obtain approximate
losses with an intermediate layer's representations for sample selection. We
evaluate SIFT on the task of training a 110M parameter 12-layer BERT base model
and show significant gains (in terms of training hours and number of
backpropagation steps) without any optimized implementation over vanilla
training. For e.g., to reach 64% validation accuracy, SIFT with exit at the
first layer takes ~43 hours compared to ~57 hours of vanilla training.

通过选择具有大梯度 / 损失的样本，可以显著减少训练步骤，本文提出了一种基于贪婪法选择具有大近似损失的样本来降低选择开销，并在训练 BERT 模型上展示了显著的训练时间节约和收敛速度提升。

理解采样近似损失的训练加速

Understanding the Training Speedup from Sampling with Approximate Losses

We study the classic cross approximation of matrices based on the maximal
volume submatrices. Our main results consist of an improvement of a classic
estimate for matrix cross approximation and a greedy approach for finding the
maximal volume submatrices. Indeed, we present a new proof of a classic
estimate of the inequality with an improved constant. Also, we present a family
of greedy maximal volume algorithms which improve the error bound of cross
approximation of a matrix in the Chebyshev norm and also improve the
computational efficiency of classic maximal volume algorithm. The proposed
algorithms are shown to have theoretical guarantees of convergence. Finally, we
present two applications: one is image compression and the other is least
squares approximation of continuous functions. Our numerical results in the end
of the paper demonstrate the effective performances of our approach.

基于最大容积子矩阵，本研究改进了矩阵交叉逼近的经典估计并提出了一种贪婪方法来寻找最大容积子矩阵。我们提出了一种改进常数的新证明，以及一族贪婪最大容积算法，这些算法提高了矩阵在 Chebyshev 范数下的交叉逼近误差界，并提高了经典最大容积算法的计算效率。我们的方法具有收敛性的理论保证，最后通过数值实验展示了方法的有效性。

图像压缩和最小二乘解的最大体积矩阵交叉逼近

Maximal Volume Matrix Cross Approximation for Image Compression and  Least Squares Solution

We study a family of combinatorial optimization problems defined by a
parameter $p\in[0,1]$, which involves spectral functions applied to positive
semidefinite matrices, and has some application in the theory of optimal
experimental design. This family of problems tends to a generalization of the
classical maximum coverage problem as $p$ goes to 0, and to a trivial instance
of the knapsack problem as $p$ goes to 1.
In this article, we establish a matrix inequality which shows that the
objective function is submodular for all $p\in[0,1]$, from which it follows
that the greedy approach, which has often been used for this problem, always
gives a design within $1-1/e$ of the optimum. We next study the design found by
rounding the solution of the continuous relaxed problem, an approach which has
been applied by several authors. We prove an inequality which generalizes a
classical result from the theory of optimal designs, and allows us to give a
rounding procedure with an approximation factor which tends to 1 as $p$ goes to
1.

研究一族由参数 p（在 [0,1] 之间）定义的组合优化问题，该问题涉及应用于正半定矩阵的谱函数，并在最优实验设计理论中有一些应用。通过建立矩阵不等式，我们证明了贪心算法总是能够找到近似最优解，而且我们证明了一种舍入程序，其近似系数随着 p 的接近 1 而趋近于 1。