Stochastic Second-Order Methods Improve Best-Known Sample Complexity of SGD for Gradient-Dominated Function

MaRDI QIDQ6400164arXivFDO

Authors Saeed Masiha, Saber Salehkaleybar, Niao He, Negar Kiyavash, Patrick Thiran

Publication date 25 May 2022

Published in arXiv

arXiv classification

cs.LGmath.OC

Abstract: We study the performance of Stochastic Cubic Regularized Newton (SCRN) on a class of functions satisfying gradient dominance property with $1lealphale2$ which holds in a wide range of applications in machine learning and signal processing. This condition ensures that any first-order stationary point is a global optimum. We prove that the total sample complexity of SCRN in achieving $epsilon$-global optimum is $mathcalO(epsilo{n}^{-7/(2alpha)+1})$ for $1lealpha<3/2$ and $mathcalildeO(epsilo{n}^{-2/(alpha)})$ for $3/2lealphale2$. SCRN improves the best-known sample complexity of stochastic gradient descent. Even under a weak version of gradient dominance property, which is applicable to policy-based reinforcement learning (RL), SCRN achieves the same improvement over stochastic policy gradient methods. Additionally, we show that the average sample complexity of SCRN can be reduced to $mathcalO(epsilo{n}^{-2})$ for $alpha=1$ using a variance reduction method with time-varying batch sizes. Experimental results in various RL settings showcase the remarkable performance of SCRN compared to first-order methods.

Cited in

(1)

• Blockwise Stabilized Adaptive Cubic Regularization with Subsolvers via Recurrence

This page was built for publication: Stochastic Second-Order Methods Improve Best-Known Sample Complexity of SGD for Gradient-Dominated Function

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6400164)