Kalman-based Stochastic Gradient Method with Stop Condition and Insensitivity to Conditioning

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.

References in corpus (5)

• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting
• A Linearly-Convergent Stochastic L-BFGS Algorithm
• Accelerated, Parallel and Proximal Coordinate Descent
• Large-scale linear regression: Development of high-performance routines

Cited by in corpus (10)

• Kalman Gradient Descent: Adaptive Variance Reduction in Stochastic Optimization
• The Extended Kalman Filter is a Natural Gradient Descent in Trajectory Space
• The Impact of Local Geometry and Batch Size on Stochastic Gradient Descent for Nonconvex Problems
• Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation
• Informative Neural Ensemble Kalman Learning
• Self-Tuning Stochastic Optimization with Curvature-Aware Gradient Filtering
• Particle Filtering Methods for Stochastic Optimization with Application to Large-Scale Empirical Risk Minimization
• Stochastic Approximation for High-frequency Observations in Data Assimilation
• CSG: A stochastic gradient method for a wide class of optimization problems appearing in a machine learning or data-driven context
• On stochastic optimization methods for Monte Carlo least-squares problems