On Adaptive Stochastic Optimization for Streaming Data: A Newton's Method with O(dN) Operations

Abstract

Stochastic optimization methods encounter new challenges in the realm of streaming, characterized by a continuous flow of large, high-dimensional data. While first-order methods, like stochastic gradient descent, are the natural choice, they often struggle with ill-conditioned problems. In contrast, second-order methods, such as Newton's methods, offer a potential solution, but their computational demands render them impractical. This paper introduces adaptive stochastic optimization methods that bridge the gap between addressing ill-conditioned problems while functioning in a streaming context. Notably, we present an adaptive inversion-free Newton's method with a computational complexity matching that of first-order methods, $\mathcal{O}(dN)$, where $d$ represents the number of dimensions/features, and $N$ the number of data. Theoretical analysis confirms their asymptotic efficiency, and empirical evidence demonstrates their effectiveness, especially in scenarios involving complex covariance structures and challenging initializations. In particular, our adaptive Newton's methods outperform existing methods, while maintaining favorable computational efficiency.

References in corpus (6)

• ADADELTA: An Adaptive Learning Rate Method
• On the Convergence of Adam and Beyond
• A simpler approach to obtaining an O(1/t) convergence rate for the projected stochastic subgradient method
• An efficient Averaged Stochastic Gauss-Newton algorithm for estimating parameters of non linear regressions models
• Non-Asymptotic Analysis of Stochastic Approximation Algorithms for Streaming Data
• Non asymptotic analysis of Adaptive stochastic gradient algorithms and applications