Adaptive Second Order Coresets for Data-efficient Machine Learning

Omead PooladzandiDavid DaviniBaharan Mirzasoleiman

article2022ICML88 citationsBest Paper Award Runner Up

Proposes ADACORE, a data-selection method that dynamically approximates loss curvature through exponentially averaged Hessian estimates to construct weighted training subsets with provable convergence guarantees and over 2.9x training speedups across convex and deep learning models.

Listen

Training modern machine learning models on massive datasets incurs substantial computational, financial, and environmental costs. While training on smaller subsets of data (coresets) can reduce these overheads, existing data-selection methods lack theoretical convergence guarantees, rely on expensive proxy models, or perform poorly on complex architectures because they fail to capture the loss landscape's geometry.

The article demonstrates ADACORE (Adaptive Second-order Coresets), a data-selection method that leverages loss landscape curvature to extract small, high-quality subsets for efficient model training with proven convergence guarantees.

To scale efficiently without the prohibitive cost of calculating full Hessian second-derivative matrices, the approach approximates the loss curvature using Hessian-free methods and Hutchinson’s diagonal estimation, combined with exponential moving averages to smooth gradient noise. The subset selection is framed as a submodular facility location problem solved via an efficient greedy algorithm. The researchers proved theoretical convergence rates for both convex and non-convex overparameterized models, and evaluated performance across image classification benchmarks (MNIST, CIFAR-10, CIFAR-100, BDD100k) using various neural network architectures and optimization algorithms.

Key findings show that ADACORE achieves substantial computational acceleration, delivering over 2.9-fold speedups compared to training on full datasets and up to 4.5-fold speedups over random data selection. When training neural networks on 1% subsets, it outperformed leading coreset baselines by 6% to 16.8% in test accuracy. Additionally, ADACORE identified more diverse and informative data points, automatically prioritizing uncertain and forgettable examples while discarding redundant samples, which prevented catastrophic forgetting when subset updates were spaced across multiple training epochs.

These results demonstrate that incorporating second-order curvature information significantly improves data-efficient training pipelines. For organizations managing large-scale machine learning workloads, this approach reduces hardware resource consumption, shortens iteration cycles, and lowers energy usage and carbon emissions without sacrificing generalization performance.

Organizations training resource-intensive vision models should consider piloting ADACORE within their existing training workflows to reduce infrastructure compute costs. When deploying the method, teams should favor moderate mini-batch sizes for Hessian estimation and test periodic subset re-selection to balance coreset calculation overhead against optimization speed.

Confidence in these findings is strong across the evaluated standard benchmark vision datasets and residual neural network architectures. However, decision-makers should note that the empirical evaluations focused primarily on image classification tasks, meaning performance across other modalities (such as large language models or tabular data) will require further empirical validation.

University of California, Los Angeles computational efficiency geometry logistic regression Adaptive Second Order Coresets Data-efficient Machine Learning coreset selection

arXiv: 2207.13887 opooladz/AdaCore

Paper: Active Learning for Convolutional Neural Networks: A Core-Set Approach, Ozan Sener et al. (2018). It establishes the foundational geometric core-set and submodular selection framework for deep neural networks that ADACORE adapts and improves using second-order curvature.
Paper: Optimizing Neural Networks with Kronecker-factored Approximate Curvature, James Martens et al. (2015). It provides essential background on practical, scalable approximations of second-order curvature and natural gradient statistics in deep learning optimization.
Paper: Learning to Reweight Examples for Robust Deep Learning, Mengye Ren et al. (2018). It introduces dynamic gradient-based sample evaluation and reweighting to optimize data efficiency and robustness during neural network training.
Paper: Improving Generalization with Active Learning, David Cohn et al. (1994). It establishes classic active learning principles of selectively querying uncertain and informative samples to maximize training efficiency.
Paper: The Tradeoffs of Large Scale Learning, Léon Bottou et al. (2007). It provides the foundational theoretical trade-offs between computation time, sample size, and approximate optimization in large-scale machine learning.

Paper: Minimizing the Accumulated Trajectory Error to Improve Dataset Distillation, Jiawei Du et al. (2023). It extends the concept of loss landscape geometry and trajectory matching to dataset distillation, refining synthetic data generation via flatter loss curvature.
Paper: Adam-mini: Use Fewer Learning Rates To Gain More, Yushun Zhang et al. (2025). It leverages structured second-order Hessian approximations to drastically reduce optimizer memory overhead across large neural architectures.

Cover for Adaptive Second Order Coresets for Data-efficient Machine Learning

Abstract

Training machine learning models on massive datasets incurs substantial computational costs. To alleviate such costs, there has been a sustained effort to develop data-efficient training methods that can carefully select subsets of the training examples that generalize on par with the full training data. However, existing methods are limited in providing theoretical guarantees for the quality of the models trained on the extracted subsets, and may perform poorly in practice. We propose ADACORE, a method that leverages the geometry of the data to extract subsets of the training examples for efficient machine learning. The key idea behind our method is to dynamically approximate the curvature of the loss function via an exponentially-averaged estimate of the Hessian to select weighted subsets (coresets) that provide a close approximation of the full gradient preconditioned with the Hessian. We prove rigorous guarantees for the convergence of various first and second-order methods applied to the subsets chosen by ADACORE. Our extensive experiments show that ADACORE extracts coresets with higher quality compared to baselines and speeds up training of convex and non-convex machine learning models, such as logistic regression and neural networks, by over 2.9x over the full data and 4.5x over random subsets1.

Topics

computational efficiency geometry logistic regression logistics neural networks preconditioners

Keywords

Adaptive Second Order Coresets Data-efficient Machine Learning coreset selection Near-optimal Coresets ADACORE coresets first-order coresets stochastic gradient descent non-convex machine learning non-convex loss functions subset selection algorithms

1. Introduction
2. Related Work
3. Background and Problem Setting
4. ADACORE: Adaptive Second order Coresets
4.1. When First-order Coresets Fail
4.2. Adaptive Second-order Coresets
4.3. Scaling up to Over-parameterized Models
4.4. Extracting Second-order Coresets
4.5. Convergence Analysis
5. Experiments
5.1. Convex Experiments
5.2. Non-Convex Experiments
6. Conclusion
Acknowledgements
References
A. Proofs of Theorems
A.1. Proof of Theorem 4.1
A.2. Proof of Theorem 4.3 and 4.4
A.3. Discussion on Greedy to Extract Near-optimal Coresets
B. Bounding the Norm of Difference Between Preconditioned Gradients
B.1. Convex Loss Functions
B.2. Neural Networks
B.3. Analytic Hessian for Logistic Regression
C. Further Empirical Evidence
C.1. ADACORE estimates full gradient closely, reaching smaller loss
C.2. Class imbalance CIFAR-10
C.3. Class imbalance BDD100k
C.4. CIFAR-100
C.5. When first order coresets fail, continued
C.6. MNIST
C.7. How batch size affects coreset performance
C.8. Potential Social Impacts

Knowls

Knowl 1 — ADACORE Second-Order Coreset Formulation
model/method
ADACORE (ADAptive second-order COREsets) selects weighted subsets of training data that approximate the full dataset gradient preconditioned by the Hessian of the empirical risk loss landscape. Let $V = \{1, \dots, n\}$ index the training dataset, $w \in \mathbb{R}^d$ denote the model parameters, and $\mathcal{L}(w) = \frac{1}{|V|} \sum_{i \in V} l_i(w)$ be the loss function with $g_t = \nabla \mathcal{L}(w_t)$ and Hessian $H_t = \nabla^2 \mathcal{L}(w_t)$ . At training iteration $t$ , ADACORE seeks the smallest subset $S_t^* \subseteq V$ and nonnegative per-element weights $\gamma_{t,j} > 0$ satisfying an error bound $\epsilon > 0$ on the preconditioned gradient:

$S_t^* = \arg\min_{S \subseteq V, \gamma_{t,j} \ge 0 \, \forall j} |S| \quad \text{s.t.} \quad \left\| H_t^{-1} g_t - \sum_{j \in S} \gamma_{t,j} H_{t,j}^{-1} g_{t,j} \right\| \le \epsilon$

Because solving this sparse approximation problem directly is NP-hard, ADACORE upper-bounds the preconditioned gradient approximation error by a facility location function:

$\min_{S \subseteq V} \left\| H_t^{-1} g_t - \sum_{j \in S} \gamma_{t,j} H_{t,j}^{-1} g_{t,j} \right\| \le \sum_{i \in V} \min_{j \in S} \left\| H_{t,i}^{-1} g_{t,i} - H_{t,j}^{-1} g_{t,j} \right\|$

Setting this upper bound to at most $\epsilon$ yields the submodular cover problem:

$S^* \in \arg\min_{S \subseteq V} |S| \quad \text{s.t.} \quad F(S) = C_1 - L(S \cup \{e\}) \ge C_1 - \epsilon$

where $L(S) = \sum_{i \in V} \min_{j \in S} \|H_{t,i}^{-1} g_{t,i} - H_{t,j}^{-1} g_{t,j}\|$ , $e$ is a phantom element, and $C_1 = L(\{e\})$ is a constant upper bound.
Knowl 2 — ADACORE Greedy Algorithm for Coreset Selection and Weighting
algorithm
ADACORE uses a greedy approximation algorithm to solve the submodular cover formulation for coreset extraction per class. The algorithm iteratively selects the element offering the largest marginal gain in the facility location objective until the preconditioned gradient error constraint $\epsilon$ is satisfied, and subsequently assigns weights $\gamma_j$ corresponding to the number of elements closest to medoid $j \in S$ .
Input: Dataset indices $V = \{1, \dots, n\}$ , component loss functions $\{l_i\}_{i \in V}$ , preconditioned gradient vectors $\{H_{t,i}^{-1} g_{t,i}\}_{i \in V}$ , target error $\epsilon > 0$ , constant $C_1 = L(\{e\})$
Output: Coreset $S \subseteq V$ , per-element weights $\{\gamma_j\}_{j \in S}$
$S_0 \leftarrow \emptyset$
$i \leftarrow 0$
while $F(S_i) < C_1 - \epsilon$ do
     $j^* \leftarrow \arg\max_{e \in V \setminus S_i} [F(S_i \cup \{e\}) - F(S_i)]$
     $S_{i+1} \leftarrow S_i \cup \{j^*\}$
     $i \leftarrow i + 1$
end while
$S \leftarrow S_i$
for each $j \in S$ do
     $\gamma_j \leftarrow \sum_{i \in V} \mathbb{I}\left[j = \arg\min_{s \in S} \|H_{t,i}^{-1} g_{t,i} - H_{t,s}^{-1} g_{t,s}\|\right]$
end for
return $S, \{\gamma_j\}_{j \in S}$
The greedy algorithm guarantees a logarithmic approximation ratio $|S| \le (1 + \ln(\max_e F(e \mid \emptyset))) |S^*|$ relative to the optimal subset size $|S^*|$ . The standard computational complexity is $O(n|S|)$ , which can be reduced to $O(|V|)$ using stochastic greedy selection, lazy evaluations, and distributed implementations.
Knowl 3 — Low-Dimensional Gradient and Hessian Diagonal Approximation for Over-Parameterized Models
model/method
To make second-order coreset selection computationally tractable for over-parameterized neural networks, ADACORE approximates gradients and Hessian operators using low-dimensional proxies and exponential moving averages (EMA):
1. Gradient Approximation: The variation in per-example gradient norm is captured by the gradient with respect to the input of the network's final layer. For a softmax layer, this proxy is $\hat{g}_i = p_i - y_i \in \mathbb{R}^C$ , where $p_i$ is the softmax output vector and $y_i$ is the one-hot encoded label for class count $C$ . To mitigate gradient noise, an exponential moving average with parameter $0 < \beta_1 < 1$ is maintained at step $t$ :
$\bar{g}_t = \frac{(1 - \beta_1) \sum_{i=1}^t \beta_1^{t-i} \hat{g}_i}{1 - \beta_1^t}$
1. Hessian Diagonal Preconditioner: Rather than computing the full $d \times d$ Hessian matrix, ADACORE uses an inexact diagonal approximation computed via Hutchinson's stochastic trace estimator. For a random Rademacher vector $z$ , the matrix-vector product $H_t z = \partial (\hat{g}_t^T z) / \partial w_t$ is obtained via backward differentiation. The diagonal is estimated by:
$\text{diag}(H_t) = \mathbb{E}[z \odot (H_t z)]$

over mini-batches of size $b_H$ . To stabilize curvature estimates, an exponential moving average with parameter $0 < \beta_2 < 1$ is applied:

$\bar{H}_t = \sqrt{\frac{(1 - \beta_2) \sum_{i=1}^t \beta_2^{t-i} \text{diag}(H_i) \odot \text{diag}(H_i)}{1 - \beta_2^t}}$
Knowl 4 — Convergence Rate of Newton's Method on ADACORE Coresets
theoretical result
Assume the loss function $\mathcal{L}: \mathbb{R}^d \to \mathbb{R}$ is $\alpha$ -strongly convex and $\beta$ -smooth ( $\|\nabla^2 \mathcal{L}(w)\| \le \beta$ ). Let $S$ be a weighted subset obtained by ADACORE at iteration $t$ that estimates the preconditioned gradient within an error of at most $\epsilon > 0$ , satisfying $\|H_t^{-1} g_t - \sum_{j \in S} \gamma_{t,j} H_{t,j}^{-1} g_{t,j}\| \le \epsilon$ .

Then, under the update rule $w_{t+1} = w_t - \eta H_t^{-1} g_t^S$ with constant learning rate $\eta = \frac{\alpha}{\beta}$ , Newton's method applied to the weighted subset $S$ satisfies:

$\mathcal{L}(w_{t+1}) - \mathcal{L}(w_t) \le -\frac{\alpha^3}{2\beta^4} (\|g_t\| - \beta \epsilon)^2$

where $g_t = \nabla \mathcal{L}(w_t)$ . The iterates converge at an exponential rate to a $\frac{\beta \epsilon}{\alpha}$ -neighborhood of the optimal parameter vector $w^*$ , meaning the algorithm descends until $\|w_t - w^*\| \le \frac{\beta \epsilon}{\alpha}$ .
Knowl 5 — Convergence Rate of AdaHessian on ADACORE Coresets
theoretical result
Assume that the loss function $\mathcal{L}: \mathbb{R}^d \to \mathbb{R}$ is $\alpha$ -strongly convex and $\beta$ -smooth. Let $S$ be a weighted subset selected by ADACORE at iteration $t$ that estimates the preconditioned gradient within an error of at most $\epsilon$ , satisfying $\|H_t^{-1} g_t - \sum_{j \in S} \gamma_{t,j} H_{t,j}^{-1} g_{t,j}\| \le \epsilon$ .

AdaHessian with Hessian power $k \in [0, 1]$ applied to the subset $S$ with step size $\hat{\eta} = \frac{\alpha^k}{\beta}$ exhibits the convergence behavior:

$\mathcal{L}(w_{t+1}) - \mathcal{L}(w_t) \le -\frac{\alpha^{k+2}}{2\beta^{k+3}} (\|g_t\| - \beta \epsilon)^2$

Consequently, the optimization trajectory converges at an exponential rate to a $\frac{\beta \epsilon}{\alpha}$ -neighborhood of the optimal parameter vector $w^*$ .
Knowl 6 — Convergence of Gradient Descent on ADACORE Coresets under PL* Condition
theoretical result
Assume the loss function $\mathcal{L}(w)$ is $\beta$ -smooth and satisfies the $\mu$ -PL $^*$ condition on parameter set $\mathcal{W}$ , defined as $\frac{1}{2}\|\nabla \mathcal{L}(w)\|^2 \ge \mu \mathcal{L}(w)$ for all $w \in \mathcal{W}$ with $\mathcal{L}(w^*) = 0$ . Let $S$ be a weighted subset extracted by ADACORE satisfying $\|H_t^{-1} g_t - \sum_{j \in S} \gamma_{t,j} H_{t,j}^{-1} g_{t,j}\| \le \epsilon$ .

Gradient descent applied to subset $S$ with update rule $w_{t+1} = w_t - \eta \sum_{j \in S} \gamma_{t,j} g_{t,j}$ and constant learning rate $\eta$ achieves the following convergence guarantee at iteration $t$ :

$\mathcal{L}(w_t) \le \left(1 - \frac{\eta \mu \alpha^2}{\beta^2}\right)^t \mathcal{L}(w_0) - \frac{\eta \alpha^2}{2\beta^2} (\beta^2 \epsilon^2 - 2\beta \epsilon \nabla_{\max})$

where $\alpha$ denotes the minimum eigenvalue across all Hessian matrices during training, and $\nabla_{\max}$ is a uniform upper bound on the gradient norm $\|\nabla \mathcal{L}(w)\|$ .
Knowl 7 — Convergence of Mini-batch SGD on ADACORE Coresets under PL* Condition
theoretical result
Let the loss function $\mathcal{L}(w)$ be $\beta$ -smooth and satisfy the $\mu$ -PL $^*$ condition $\frac{1}{2}\|\nabla \mathcal{L}(w)\|^2 \ge \mu \mathcal{L}(w)$ on $\mathcal{W}$ . Let $S$ be an ADACORE coreset satisfying preconditioned gradient approximation error $\epsilon$ . For mini-batch stochastic gradient descent with batch size $m \in \mathbb{N}$ and learning rate $\eta = \frac{m}{\beta(m-1)}$ applied to the coreset $S$ , the expected loss satisfies:

$\mathbb{E}[\mathcal{L}(w_t)] \le \left(1 - \frac{\eta \mu \alpha^2}{2\beta}\right)^t \mathbb{E}[\mathcal{L}(w_0)] - \frac{\alpha^2 \eta}{2\beta} (\beta \epsilon^2 - 2 \epsilon \nabla_{\max})$

where $\alpha$ is the minimum eigenvalue of all Hessian matrices encountered during optimization, $\nabla_{\max}$ bounds the gradient norm, and expectation is taken over the random sampling of mini-batches.
Knowl 8 — Last-Layer Preconditioned Gradient Difference Bound for Deep Networks
theoretical result
For an $L$ -layer neural network with weight matrices $w^{(l)} \in \mathbb{R}^{M_l \times M_{l-1}}$ and Lipschitz continuous activation functions $\sigma^{(l)}(\cdot)$ having bounded derivative $|\sigma'(w)| \le K$ , the normed difference between the full-parameter preconditioned gradients of two data points $i$ and $j$ is upper-bounded by the normed difference between their last-layer preconditioned gradients up to affine constants:

$\|H_i^{-1} g_i - H_j^{-1} g_j\| \le c_1 \left\| \Sigma'_L(z_i^{(L)}) (H_i^{-1} g_i)^{(L)} - \Sigma'_L(z_j^{(L)}) (H_j^{-1} g_j)^{(L)} \right\| + c_2$

where $(H_i^{-1} g_i)^{(L)}$ is the gradient of the loss with respect to the pre-activation outputs $z_i^{(L)}$ of the final layer preconditioned by the inverse Hessian of the final layer, $\Sigma'_L(z_i^{(L)}) = \text{diag}(\sigma'^{(L)}(z_{i,1}^{(L)}), \dots, \sigma'^{(L)}(z_{i,M_L}^{(L)}))$ , and $c_1, c_2$ are positive constants depending on intermediate layer activations and weight bounds.

Knowl 9 — Performance and Ablation of ADACORE on CIFAR-10 with 1% Coresets

data/table

The table below evaluates the test accuracy of ResNet-20 trained on $S=1\%$ subsets selected every $R=1$ epoch from CIFAR-10 over 200 epochs using AdaHessian and SGD with momentum (0.9). Parentheses denote the cumulative percentage of unique dataset points visited throughout training.

Method	AdaHessian	SGD+Momentum
Random	$59.1\% \pm 2.8\, (87\%)$	$45.9\% \pm 2.5\, (87\%)$
CRAIG	$59.5\% \pm 2.8\, (74\%)$	$43.6\% \pm 1.6\, (75\%)$
GRADMATCH	$57.5\% \pm 1.3\, (74\%)$	$49.4\% \pm 1.6\, (74\%)$
GLISTER	$37.5\% \pm 1.3\, (74\%)$	$38.6\% \pm 1.6\, (74\%)$
ADACORE (no avg)	$58.4\% \pm 0.2\, (73\%)$	$51.5\% \pm 1.1\, (74\%)$
ADACORE (avg $g$ )	$59.8\% \pm 0.5\, (73\%)$	$53.2\% \pm 1.1\, (74\%)$
ADACORE (avg $H$ )	$60.2\% \pm 0.5\, (73\%)$	$54.4\% \pm 1.1\, (74\%)$
ADACORE	$60.2\% \pm 0.5\, (73\%)$	$55.4\% \pm 1.1\, (74\%)$
ADACORE ( $b_H = 512$ )	$57.2\% \pm 0.5\, (73\%)$	$52.4\% \pm 1.1\, (74\%)$

ADACORE outperforms first-order subset selection baselines (CRAIG by $11.8\%$ , Random by $9.5\%$ , GRADMATCH by $6.0\%$ , GLISTER by $16.8\%$ under SGD+Momentum) while selecting fewer unique dataset examples overall ( $73\%\text{--}74\%$ vs. $87\%$ for Random). The ablation demonstrates that applying exponential moving average smoothing to both gradient and Hessian diagonal estimates, alongside using a small batch size for Hessian computation ( $b_H = 64$ vs. $512$ ), yields the highest model accuracy.

Knowl 10 — Empirical Training Acceleration on Non-Convex Vision Benchmarks
empirical result
Evaluating ADACORE on non-convex deep learning benchmarks with $S=10\%$ coreset selection every $R=20$ epochs demonstrates substantial training wall-clock speedups over full data training and first-order coreset baselines:
1. BDD100k (ResNet-50, 7 classes, 100k images): ADACORE achieves $74.3\%$ test accuracy in 100 epochs (7,331 seconds), matching full dataset accuracy obtained in 45 epochs (16,093 seconds). This represents a 2.3x speedup over full data training, a 1.8x speedup over Random subsets (which reach $73.3\%$ in 180 epochs / 13,050 s), and outperforms CRAIG ( $73.1\%$ , 150 epochs / 10,996 s) and GRADMATCH ( $72.0\%$ , 200 epochs / 14,040 s).
2. CIFAR-100 (ResNet-18, 100 classes, 32.5k images): ADACORE achieves $58.8\%$ test accuracy in 200 epochs (341 seconds), matching full dataset performance of $59.0\%$ in 40 epochs (960 seconds). This achieves a 2.8x speedup over full dataset training and a 4.3x speedup over Random subsets ( $58.1\%$ , 864 epochs / 1,470 s), while CRAIG ( $57.3\%$ , 250 epochs / 426 s) and GRADMATCH ( $57.0\%$ , 200 epochs / 980 s) fail to reach ADACORE's accuracy.
Knowl 11 — Catastrophic Forgetting Mitigation and Selection Diversity in ADACORE
empirical result
Empirical analysis of example selection dynamics reveals two key properties of ADACORE compared to first-order subset selection methods:
1. Mitigation of Catastrophic Forgetting: When coreset selection occurs infrequently (e.g., $R = 20$ epochs on CIFAR-10 with ResNet-20), first-order methods like CRAIG and GRADMATCH suffer abrupt accuracy drops (catastrophic forgetting) every time a new coreset is recomputed because their selections lack representative diversity across subgroups. ADACORE maintains smooth, monotonic test accuracy progression because preconditioning scales gradient dimensions inversely by curvature, preventing large parameter swings.
2. Targeted Selection of Informative and Uncertain Instances: Ranking training samples by selection frequency shows that ADACORE prioritizes examples with higher forgettability and higher predictive uncertainty over the course of training, while avoiding redundant, easily learned instances without over-indexing on extreme unlearnable outliers.

Coverage note — None was omitted; all principal theoretical convergence theorems (Newton, AdaHessian, GD, SGD), structural upper bounds, algorithmic steps, scalable Hessian/gradient approximation schemes, and empirical benchmark results from the paper and its appendix are fully covered.

References

1.Alain, G., Lamb, A., Sankar, C., Courville, A., and Bengio, Y. Variance reduction in sgd by distributed importance sampling. arXiv preprint arXiv:1511.06481, 2015.
2.Allen-Zhu, Z., Yuan, Y., and Sridharan, K. Exploiting the structure: Stochastic gradient methods using raw clusters. In Advances in Neural Information Processing Systems, pp. 1642–1650, 2016.
3.Asi, H. and Duchi, J. C. The importance of better models in stochastic optimization. arXiv preprint arXiv:1903.08619, 2019.
4.Bekas, C., Kokiopoulou, E., and Saad, Y. An estimator for the diagonal of a matrix. Applied Numerical Mathematics, 57(11):1214–1229, 2007. ISSN 0168-9274. doi: https://doi.org/10.1016/j.apnum.2007.01.003. URL https://www.sciencedirect.com/science/article/pii/S0168927407000244. Numerical Algorithms, Parallelism and Applications (2).
5.Bertsekas, D. P. Projected newton methods for optimization problems with simple constraints. SIAM Journal on control and Optimization, 20(2):221–246, 1982.
6.Birodkar, V., Mobahi, H., and Bengio, S. Semantic redundancies in image-classification datasets: The 10% you don’t need. arXiv preprint arXiv:1901.11409, 2019.
7.Boyd, S. and Vandenberghe, L. Convex Optimization. Cambridge University Press, USA, 2004. ISBN 0521833787.
8.Chen, S. S., Donoho, D. L., and Saunders, M. A. Atomic decomposition by basis pursuit. SIAM review, 43(1): 129–159, 2001.
9.Coleman, C., Yeh, C., Mussmann, S., Mirzasoleiman, B., Bailis, P., Liang, P., Leskovec, J., and Zaharia, M. Selection via proxy: Efficient data selection for deep learning. In International Conference on Learning Representations (ICLR), 2020.
10.Deng, L. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 29(6):141–142, 2012.
11.Donoho, D. L. Compressed sensing. IEEE Transactions on information theory, 52(4):1289–1306, 2006.
12.Elenberg, E. R., Khanna, R., Dimakis, A. G., Negahban, S., et al. Restricted strong convexity implies weak submodularity. Annals of Statistics, 46(6B):3539–3568, 2018.
13.Ghorbani, A. and Zou, J. Data shapley: Equitable valuation of data for machine learning. In International Conference on Machine Learning, pp. 2242–2251. PMLR, 2019.
14.He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770–778, 2016.
15.Hofmann, T., Lucchi, A., Lacoste-Julien, S., and McWilliams, B. Variance reduced stochastic gradient descent with neighbors. In Advances in Neural Information Processing Systems, pp. 2305–2313, 2015.
16.Katharopoulos, A. and Fleuret, F. Not all samples are created equal: Deep learning with importance sampling. In International conference on machine learning, pp. 2525–2534. PMLR, 2018.
17.Killamsetty, K., Sivasubramanian, D., Ramakrishnan, G., and Iyer, R. Glister: Generalization based data subset selection for efficient and robust learning. arXiv preprint arXiv:2012.10630, 2020.
18.Killamsetty, K., Sivasubramanian, D., Mirzasoleiman, B., Ramakrishnan, G., De, A., and Iyer, R. Grad-match: A gradient matching based data subset selection for efficient learning. arXiv preprint arXiv:2103.00123, 2021.
19.Krizhevsky, A., Nair, V., and Hinton, G. Cifar-10 (canadian institute for advanced research). 2009. URL http://www.cs.toronto.edu/~kriz/cifar.html.
20.Kyrillidis, A., Becker, S., Cevher, V., and Koch, C. Sparse projections onto the simplex. In International Conference on Machine Learning, pp. 235–243. PMLR, 2013.
21.Liu, C., Zhu, L., and Belkin, M. Toward a theory of optimization for over-parameterized systems of non-linear equations: the lessons of deep learning. arXiv preprint arXiv:2003.00307, 2020.
22.Loshchilov, I. and Hutter, F. Online batch selection for faster training of neural networks. arXiv preprint arXiv:1511.06343, 2015.
23.Martens, J. and Grosse, R. Optimizing neural networks with kronecker-factored approximate curvature. In International conference on machine learning, pp. 2408–2417. PMLR, 2015.
24.Minoux, M. Accelerated greedy algorithms for maximizing submodular set functions. In Optimization techniques, pp. 234–243. Springer, 1978.
25.Mirzasoleiman, B., Karbasi, A., Sarkar, R., and Krause, A. Distributed submodular maximization: Identifying representative elements in massive data. In Advances in Neural Information Processing Systems, pp. 2049–2057, 2013.
26.Mirzasoleiman, B., Badanidiyuru, A., Karbasi, A., Vondrák, J., and Krause, A. Lazier than lazy greedy. In Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015.
27.Mirzasoleiman, B., Bilmes, J., and Leskovec, J. Coresets for data-efficient training of machine learning models. In International Conference on Machine Learning, pp. 6950–6960. PMLR, 2020.
28.Natarajan, B. K. Sparse approximate solutions to linear systems. SIAM journal on computing, 24(2):227–234, 1995.
29.Nocedal, J. Updating quasi-newton matrices with limited storage. Mathematics of Computation, 35(151):773–782, 1980. ISSN 00255718, 10886842. URL http://www.jstor.org/stable/2006193.
30.Pilanci, M., El Ghaoui, L., and Chandrasekaran, V. Recovery of sparse probability measures via convex programming. 2012.
31.Qian, N. On the momentum term in gradient descent learning algorithms. Neural networks, 12(1):145–151, 1999.
32.Robbins, H. and Monro, S. A stochastic approximation method. The annals of mathematical statistics, pp. 400–407, 1951.
33.Schaul, T., Zhang, S., and LeCun, Y. No more pesky learning rates. In International Conference on Machine Learning, pp. 343–351. PMLR, 2013.
34.Schaul, T., Quan, J., Antonoglou, I., and Silver, D. Prioritized experience replay. arXiv preprint arXiv:1511.05952, 2015.
35.Schwartz, R., Dodge, J., Smith, N. A., and Etzioni, O. Green ai. arXiv preprint arXiv:1907.10597, 2019.
36.Strubell, E., Ganesh, A., and McCallum, A. Energy and policy considerations for deep learning in nlp. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pp. 3645–3650, 2019.
37.Tibshirani, R. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society: Series B (Methodological), 58(1):267–288, 1996.
38.Toneva, M., Sordoni, A., des Combes, R. T., Trischler, A., Bengio, Y., and Gordon, G. J. An empirical study of example forgetting during deep neural network learning. In International Conference on Learning Representations, 2018.
39.Wolsey, L. A. An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica, 2(4): 385–393, 1982.
40.Xu, P., Roosta, F., and Mahoney, M. W. Second-order optimization for non-convex machine learning: An empirical study. In Proceedings of the 2020 SIAM International Conference on Data Mining, pp. 199–207. SIAM, 2020.
41.Yao, Z., Xu, P., Roosta-Khorasani, F., and Mahoney, M. W. Inexact non-convex newton-type methods. arXiv preprint arXiv:1802.06925, 2018.
42.Yao, Z., Gholami, A., Shen, S., Keutzer, K., and Mahoney, M. W. Adahessian: An adaptive second order optimizer for machine learning. arXiv preprint arXiv:2006.00719, 2020.
43.Yu, F., Chen, H., Wang, X., Xian, W., Chen, Y., Liu, F., Madhavan, V., and Darrell, T. Bdd100k: A diverse driving dataset for heterogeneous multitask learning. In IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2020.

Citation

MLA

Pooladzandi, O., et al. “Adaptive Second Order Coresets for Data-efficient Machine Learning”. International Conference on Machine Learning, vol. 162, 2022, pp. 17848–69, https://proceedings.mlr.press/v162/pooladzandi22a.html.

APA

Pooladzandi, O., Davini, D., & Mirzasoleiman, B. (2022). Adaptive Second Order Coresets for Data-efficient Machine Learning. International Conference on Machine Learning, 162, 17848–17869. https://proceedings.mlr.press/v162/pooladzandi22a.html

Chicago

Pooladzandi, O., D. Davini, and B. Mirzasoleiman. 2022. “Adaptive Second Order Coresets for Data-efficient Machine Learning”. International Conference on Machine Learning 162: 17848–69. https://proceedings.mlr.press/v162/pooladzandi22a.html.

Harvard

Pooladzandi, O., Davini, D. and Mirzasoleiman, B. (2022) “Adaptive Second Order Coresets for Data-efficient Machine Learning”, International Conference on Machine Learning. PMLR, pp. 17848–17869. Available at: https://proceedings.mlr.press/v162/pooladzandi22a.html.

Vancouver

1. Pooladzandi O, Davini D, Mirzasoleiman B (2022) Adaptive Second Order Coresets for Data-efficient Machine Learning. In: International Conference on Machine Learning. PMLR, pp 17848–17869

BibTeX

@InProceedings{pmlr-v162-pooladzandi22a,
  title = 	 {Adaptive Second Order Coresets for Data-efficient Machine Learning},
  author =       {Pooladzandi, Omead and Davini, David and Mirzasoleiman, Baharan},
  booktitle = 	 {Proceedings of the 39th International Conference on Machine Learning},
  pages = 	 {17848--17869},
  year = 	 {2022},
  editor = 	 {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan},
  volume = 	 {162},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {17--23 Jul},
  publisher =    {PMLR},
  pdf = 	 {https://proceedings.mlr.press/v162/pooladzandi22a/pooladzandi22a.pdf},
  url = 	 {https://proceedings.mlr.press/v162/pooladzandi22a.html},
  abstract = 	 {Training machine learning models on massive datasets incurs substantial computational costs. To alleviate such costs, there has been a sustained effort to develop data-efficient training methods that can carefully select subsets of the training examples that generalize on par with the full training data. However, existing methods are limited in providing theoretical guarantees for the quality of the models trained on the extracted subsets, and may perform poorly in practice. We propose AdaCore, a method that leverages the geometry of the data to extract subsets of the training examples for efficient machine learning. The key idea behind our method is to dynamically approximate the curvature of the loss function via an exponentially-averaged estimate of the Hessian to select weighted subsets (coresets) that provide a close approximation of the full gradient preconditioned with the Hessian. We prove rigorous guarantees for the convergence of various first and second-order methods applied to the subsets chosen by AdaCore. Our extensive experiments show that AdaCore extracts coresets with higher quality compared to baselines and speeds up training of convex and non-convex machine learning models, such as logistic regression and neural networks, by over 2.9x over the full data and 4.5x over random subsets.}
}

Metadata:DOI registry

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

Adaptive Second Order Coresets for Data-efficient Machine Learning

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — ADACORE Second-Order Coreset Formulation

Knowl 2 — ADACORE Greedy Algorithm for Coreset Selection and Weighting

Knowl 3 — Low-Dimensional Gradient and Hessian Diagonal Approximation for Over-Parameterized Models

Knowl 4 — Convergence Rate of Newton's Method on ADACORE Coresets

Knowl 5 — Convergence Rate of AdaHessian on ADACORE Coresets

Knowl 6 — Convergence of Gradient Descent on ADACORE Coresets under PL* Condition

Knowl 7 — Convergence of Mini-batch SGD on ADACORE Coresets under PL* Condition

Knowl 8 — Last-Layer Preconditioned Gradient Difference Bound for Deep Networks