Kalman-based stochastic gradient method with stop condition and insensitivity to conditioning
From MaRDI portal
Abstract: Modern proximal and stochastic gradient descent (SGD) methods are believed to efficiently minimize large composite objective functions, but such methods have two algorithmic challenges: (1) a lack of fast or justified stop conditions, and (2) sensitivity to the objective function's conditioning. In response to the first challenge, modern proximal and SGD methods guarantee convergence only after multiple epochs, but such a guarantee renders proximal and SGD methods infeasible when the number of component functions is very large or infinite. In response to the second challenge, second order SGD methods have been developed, but they are marred by the complexity of their analysis. In this work, we address these challenges on the limited, but important, linear regression problem by introducing and analyzing a second order proximal/SGD method based on Kalman Filtering (kSGD). Through our analysis, we show kSGD is asymptotically optimal, develop a fast algorithm for very large, infinite or streaming data sources with a justified stop condition, prove that kSGD is insensitive to the problem's conditioning, and develop a unique approach for analyzing the complex second order dynamics. Our theoretical results are supported by numerical experiments on three regression problems (linear, nonparametric wavelet, and logistic) using three large publicly available datasets. Moreover, our analysis and experiments lay a foundation for embedding kSGD in multiple epoch algorithms, extending kSGD to other problem classes, and developing parallel and low memory kSGD implementations.
Recommendations
- On the regularizing property of stochastic gradient descent
- Large-scale machine learning with stochastic gradient descent
- A proximal stochastic gradient method with progressive variance reduction
- Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm
- A line search based proximal stochastic gradient algorithm with dynamical variance reduction
Cites work
- A proximal stochastic gradient method with progressive variance reduction
- A Stochastic Approximation Method
- A stochastic quasi-Newton method for large-scale optimization
- Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization
- Accelerated, parallel, and proximal coordinate descent
- All of Nonparametric Statistics
- Asymptotic equivalence of density estimation and Gaussian white noise
- Asymptotic Statistics
- Asymptotics in statistics. Some basic concepts.
- Gravitational-wave data analysis. Formalism and sample applications: the Gaussian Case
- scientific article; zbMATH DE number 1818892 (Why is no real title available?)
- scientific article; zbMATH DE number 3458075 (Why is no real title available?)
- scientific article; zbMATH DE number 1569104 (Why is no real title available?)
- scientific article; zbMATH DE number 3084450 (Why is no real title available?)
- Large-scale linear regression: development of high-performance routines
- Numerical Optimization
- Probability. Theory and examples.
- Proximal splitting methods in signal processing
- SGD-QN: careful quasi-Newton stochastic gradient descent
- Solving sequences of generalized least-squares problems on multi-threaded architectures
Cited in
(3)
This page was built for publication: Kalman-based stochastic gradient method with stop condition and insensitivity to conditioning
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5506688)
