Stochastic Online Optimization using Kalman Recursion

2020/02/10 by Joseph de Vilmarest, Olivier Wintenberger, de Vilmarest, Joseph +1 · 1 citation
Decision Sciences · Computer Science · #Advanced Bandit Algorithms Research #Optimization and Search Problems #Data Stream Mining Techniques

paper · pdf · doi:10.48550/arxiv.2002.03636

Abstract

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²) cost per iteration that optimally solves some unconstrained optimization problems.

Citations

• A Stochastic Approximation Method
• Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)

Cited by

• An hybrid stochastic Newton algorithm for logistic regression

Related

• Stochastic models for online optimization
• Stochastic Online Convex Optimization. Application to probabilistic time series forecasting
• Logarithmic Regret for parameter-free Online Logistic Regression
• Online Stochastic Convex Optimization: Wasserstein Distance Variation
• Constrained Online Two-stage Stochastic Optimization: Algorithm with (and without) Predictions