# Second-Order Stochastic Optimization for Machine Learning in Linear Time

arXiv: https://arxiv.org/abs/1602.03943 · HTML: https://mlsanity.com/paper/1602.03943/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Feb 2016.

## Built on by (most cited first, 14 of 14)

- [If Influence Functions are the Answer, Then What is the Question?](https://mlsanity.com/paper/2209.05364/) (2022)
- [Dataset Pruning: Reducing Training Data by Examining Generalization Influence](https://mlsanity.com/paper/2205.09329/) (2022)
- [Influence Selection for Active Learning](https://mlsanity.com/paper/2108.09331/) (2021)
- [Unleashing the Power of Data Tsunami: A Comprehensive Survey on Data Assessment and Selection for Instruction Tuning of Language Models](https://mlsanity.com/paper/2408.02085/) (2024)
- [Repairing Neural Networks by Leaving the Right Past Behind](https://mlsanity.com/paper/2207.04806/) (2022)
- [Unified Parameter-Efficient Unlearning for LLMs](https://mlsanity.com/paper/2412.00383/) (2024)
- [Membership Inference Attack Using Self Influence Functions](https://mlsanity.com/paper/2205.13680/) (2022)
- [FairIF: Boosting Fairness in Deep Learning via Influence Functions with Validation Set Sensitive Attributes](https://mlsanity.com/paper/2201.05759/) (2022)
- [Large-Scale Deep Learning Optimizations: A Comprehensive Survey](https://mlsanity.com/paper/2111.00856/) (2021)
- [Sample based Explanations via Generalized Representers](https://mlsanity.com/paper/2310.18526/) (2023)
- [Understanding Programmatic Weak Supervision via Source-aware Influence Function](https://mlsanity.com/paper/2205.12879/) (2022)
- [A Novel Stochastic Gradient Descent Algorithm for Learning Principal Subspaces](https://mlsanity.com/paper/2212.04025/) (2022)
- [Peering Beyond the Gradient Veil with Distributed Auto Differentiation](https://mlsanity.com/paper/2102.09631/) (2021)
- [Accelerating Stochastic Probabilistic Inference](https://mlsanity.com/paper/2203.07585/) (2022)

## Abstract (arXiv)

First-order stochastic methods are the state-of-the-art in large-scale machine learning optimization owing to efficient per-iteration complexity. Second-order methods, while able to provide faster convergence, have been much less explored due to the high cost of computing the second-order information. In this paper we develop second-order stochastic methods for optimization problems in machine learning that match the per-iteration cost of gradient based methods, and in certain settings improve upon the overall running time over popular first-order methods. Furthermore, our algorithm has the desirable property of being implementable in time linear in the sparsity of the input data.