A Stochastic Quasi-Newton Method in the Absence of Common Random Numbers
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913487339388928 |
|---|---|
| author | Menickelly, Matt Wild, Stefan M. Xie, Miaolan |
| author_facet | Menickelly, Matt Wild, Stefan M. Xie, Miaolan |
| contents | We present a quasi-Newton method for unconstrained stochastic optimization. Most existing literature on this topic assumes a setting of stochastic optimization in which a finite sum of component functions is a reasonable approximation of an expectation, and hence one can design a quasi-Newton method to exploit common random numbers. In contrast, and motivated by problems in variational quantum algorithms, we assume that function values and gradients are available only through inexact probabilistic zeroth- and first-order oracles and no common random numbers can be exploited. Our algorithmic framework -- based on prior work on the SASS algorithm -- is general and does not assume common random numbers. We derive a high-probability tail bound on the iteration complexity of the algorithm for nonconvex and strongly convex functions. We present numerical results demonstrating the empirical benefits of augmenting SASS with our quasi-Newton updating scheme, both on synthetic problems and on real problems in quantum chemistry. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2302_09128 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A Stochastic Quasi-Newton Method in the Absence of Common Random Numbers Menickelly, Matt Wild, Stefan M. Xie, Miaolan Optimization and Control 90C15, 90C53, 90C30, 90C26 We present a quasi-Newton method for unconstrained stochastic optimization. Most existing literature on this topic assumes a setting of stochastic optimization in which a finite sum of component functions is a reasonable approximation of an expectation, and hence one can design a quasi-Newton method to exploit common random numbers. In contrast, and motivated by problems in variational quantum algorithms, we assume that function values and gradients are available only through inexact probabilistic zeroth- and first-order oracles and no common random numbers can be exploited. Our algorithmic framework -- based on prior work on the SASS algorithm -- is general and does not assume common random numbers. We derive a high-probability tail bound on the iteration complexity of the algorithm for nonconvex and strongly convex functions. We present numerical results demonstrating the empirical benefits of augmenting SASS with our quasi-Newton updating scheme, both on synthetic problems and on real problems in quantum chemistry. |
| title | A Stochastic Quasi-Newton Method in the Absence of Common Random Numbers |
| topic | Optimization and Control 90C15, 90C53, 90C30, 90C26 |
| url | https://arxiv.org/abs/2302.09128 |