Stochastic Variance-Reduced Newton: Accelerating Finite-Sum Minimization with Large Batches
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2022
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910920968503296 |
|---|---|
| author | Dereziński, Michał |
| author_facet | Dereziński, Michał |
| contents | Stochastic variance reduction has proven effective at accelerating first-order algorithms for solving convex finite-sum optimization tasks such as empirical risk minimization. Incorporating second-order information has proven helpful in further improving the performance of these first-order methods. Yet, comparatively little is known about the benefits of using variance reduction to accelerate popular stochastic second-order methods such as Subsampled Newton. To address this, we propose Stochastic Variance-Reduced Newton (SVRN), a finite-sum minimization algorithm that provably accelerates existing stochastic Newton methods from $O(α\log(1/ε))$ to $O\big(\frac{\log(1/ε)}{\log(n)}\big)$ passes over the data, i.e., by a factor of $O(α\log(n))$, where $n$ is the number of sum components and $α$ is the approximation factor in the Hessian estimate. Surprisingly, this acceleration gets more significant the larger the data size $n$, which is a unique property of SVRN. Our algorithm retains the key advantages of Newton-type methods, such as easily parallelizable large-batch operations and a simple unit step size. We use SVRN to accelerate Subsampled Newton and Iterative Hessian Sketch algorithms, and show that it compares favorably to popular first-order methods with variance~reduction. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2206_02702 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Stochastic Variance-Reduced Newton: Accelerating Finite-Sum Minimization with Large Batches Dereziński, Michał Optimization and Control Machine Learning Stochastic variance reduction has proven effective at accelerating first-order algorithms for solving convex finite-sum optimization tasks such as empirical risk minimization. Incorporating second-order information has proven helpful in further improving the performance of these first-order methods. Yet, comparatively little is known about the benefits of using variance reduction to accelerate popular stochastic second-order methods such as Subsampled Newton. To address this, we propose Stochastic Variance-Reduced Newton (SVRN), a finite-sum minimization algorithm that provably accelerates existing stochastic Newton methods from $O(α\log(1/ε))$ to $O\big(\frac{\log(1/ε)}{\log(n)}\big)$ passes over the data, i.e., by a factor of $O(α\log(n))$, where $n$ is the number of sum components and $α$ is the approximation factor in the Hessian estimate. Surprisingly, this acceleration gets more significant the larger the data size $n$, which is a unique property of SVRN. Our algorithm retains the key advantages of Newton-type methods, such as easily parallelizable large-batch operations and a simple unit step size. We use SVRN to accelerate Subsampled Newton and Iterative Hessian Sketch algorithms, and show that it compares favorably to popular first-order methods with variance~reduction. |
| title | Stochastic Variance-Reduced Newton: Accelerating Finite-Sum Minimization with Large Batches |
| topic | Optimization and Control Machine Learning |
| url | https://arxiv.org/abs/2206.02702 |