Timezone: »

 
Stochastic Adaptive Regularization Method with Cubics: A High Probability Complexity Bound
Katya Scheinberg · Miaolan Xie
Event URL: https://openreview.net/forum?id=2BdnlBkgVkWN »

We present a high probability complexity bound for a stochastic adaptive regularization method with cubics, also known as regularized Newton method. The method makes use of stochastic zeroth, first and second-order oracles that satisfy certain accuracy and reliability assumptions. Such oracles have been used in the literature by other adaptive stochastic methods, such as trust region and line search. These oracles capture many settings, such as expected risk minimization, stochastic zeroth order optimization, and others. In this paper, we give the first high-probability iteration bound for stochastic cubic regularization and show that just as in the deterministic case, it is superior to other adaptive methods.

Author Information

Katya Scheinberg (Cornell)
Miaolan Xie (Cornell University)

More from the Same Authors

  • 2021 : High Probability Step Size Lower Bound for Adaptive Stochastic Optimization »
    Katya Scheinberg · Miaolan Xie
  • 2022 : Poster Session 1 »
    Andrew Lowy · Thomas Bonnier · Yiling Xie · Guy Kornowski · Simon Schug · Seungyub Han · Nicolas Loizou · xinwei zhang · Laurent Condat · Tabea E. Röber · Si Yi Meng · Marco Mondelli · Runlong Zhou · Eshaan Nichani · Adrian Goldwaser · Rudrajit Das · Kayhan Behdin · Atish Agarwala · Mukul Gagrani · Gary Cheng · Tian Li · Haoran Sun · Hossein Taheri · Allen Liu · Siqi Zhang · Dmitrii Avdiukhin · Bradley Brown · Miaolan Xie · Junhyung Lyle Kim · Sharan Vaswani · Xinmeng Huang · Ganesh Ramachandra Kini · Angela Yuan · Weiqiang Zheng · Jiajin Li
  • 2022 : Katya Scheinberg, Stochastic Oracles and Where to Find Them »
    Katya Scheinberg
  • 2021 : Poster Session 2 (gather.town) »
    Wenjie Li · Akhilesh Soni · Jinwuk Seok · Jianhao Ma · Jeffery Kline · Mathieu Tuli · Miaolan Xie · Robert Gower · Quanqi Hu · Matteo Cacciola · Yuanlu Bai · Boyue Li · Wenhao Zhan · Shentong Mo · Junhyung Lyle Kim · Sajad Fathi Hafshejani · Chris Junchi Li · Zhishuai Guo · Harshvardhan Harshvardhan · Neha Wadia · Tatjana Chavdarova · Difan Zou · Zixiang Chen · Aman Gupta · Jacques Chen · Betty Shea · Benoit Dherin · Aleksandr Beznosikov
  • 2021 Workshop: OPT 2021: Optimization for Machine Learning »
    Courtney Paquette · Quanquan Gu · Oliver Hinder · Katya Scheinberg · Sebastian Stich · Martin Takac
  • 2021 Poster: High Probability Complexity Bounds for Line Search Based on Stochastic Oracles »
    Billy Jin · Katya Scheinberg · Miaolan Xie