  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.
