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

By Vivak Patel. 2015

35 citations recorded by the source corpus.

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, Kalman-based stochastic gradient descent (kSGD). Through our analysis, we show kSGD is asymptotically optimal, develop a fast algorithm for very...

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Statistics and Probability

In Optimization & Training

Citations in the corpus

Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation (2019, methodology): “In order to further scale these methods to high-dimensional datasets or models with a large number of parameters, there has been a rich body of research in developing computationally efficient approximations to the Hessian matrix (Becker et al., 1988; Liu and Nocedal, 1989; Martens and Grosse, 2015;”