Stochastic Online Optimization using Kalman Recursion
This work addresses unconstrained optimization problems for machine learning practitioners, offering incremental improvements in analysis and bounds for specific regression tasks.
The paper tackles stochastic online optimization by applying the Extended Kalman Filter in constant dynamics, providing a parameter-free algorithm with O(d^2) cost per iteration. It achieves high probability bounds on cumulative excess risk for linear, logistic, and generalized linear regressions, improving existing analyses in bounded stochastic optimization.
We study the Extended Kalman Filter in constant dynamics, offering a bayesian perspective of stochastic optimization. We obtain high probability bounds on the cumulative excess risk in an unconstrained setting. In order to avoid any projection step we propose a two-phase analysis. First, for linear and logistic regressions, we prove that the algorithm enters a local phase where the estimate stays in a small region around the optimum. We provide explicit bounds with high probability on this convergence time. Second, for generalized linear regressions, we provide a martingale analysis of the excess risk in the local phase, improving existing ones in bounded stochastic optimization. The EKF appears as a parameter-free online algorithm with O(d^2) cost per iteration that optimally solves some unconstrained optimization problems.