Stochastic Online Optimization using Kalman Recursion

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. The unconstrained challenge is tackled through 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 O(d^2) online algorithm that optimally solves some unconstrained optimization problems.

• Publication year

  2020

• Venue

  Journal of machine learning research

• Publication date

  2020-02-07

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 2002.03636
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• An Efficient Stochastic Newton Algorithm for Parameter Estimation in Logistic Regressions

  2019influential reference
• Finite-sample Analysis of M-estimators using Self-concordance

  2018cited by this paper
• Online natural gradient as a Kalman filter

  2017cited by this paper
• Lower and Upper Bounds on the Generalization of Stochastic Exponentially Concave Optimization

  2015influential reference
• High-Dimensional Statistics

  2014cited by this paper
• Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regression

  2013influential reference
• Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)

  2013cited by this paper
• Open Problem: Fast Stochastic Exp-Concave Optimization

  2013cited by this paper
• User-Friendly Tail Bounds for Sums of Random Matrices

  2010cited by this paper
• Exponential inequalities for self-normalized martingales with applications

  2007cited by this paper
• Logarithmic regret algorithms for online convex optimization

  2006cited by this paper
• Prediction, learning, and games

  2006influential reference
• Online Bounds for Bayesian Algorithms

  2004cited by this paper
• Online Convex Programming and Generalized Infinitesimal Gradient Ascent

  2003cited by this paper
• Time Series Analysis by State Space Methods

  2001cited by this paper
• Statistical analysis of learning dynamics

  1999cited by this paper
• Comparative accuracies of artificial neural networks and discriminant analysis in predicting forest cover types from cartographic variables

  1999cited by this paper
• Natural Gradient Works Efficiently in Learning

  1998cited by this paper
• Scaling Up the Accuracy of Naive-Bayes Classifiers: A Decision-Tree Hybrid

  1996cited by this paper
• Posterior Mode Estimation by Extended Kalman Filtering for Multivariate Dynamic Generalized Linear Models

  1992cited by this paper
• Acceleration of stochastic approximation by averaging

  1992cited by this paper
• Efficient Estimations from a Slowly Convergent Robbins-Monro Process

  1988cited by this paper
• The Kalman Filter from the Perspective of Goldberger—Theil Estimators

  1985cited by this paper
• Generalized Linear Models

  1984cited by this paper
• On Tail Probabilities for Martingales

  1975cited by this paper
• New Results in Linear Filtering and Prediction Theory

  1961cited by this paper
• A Stochastic Approximation Method

  1951cited by this paper

• An hybrid stochastic Newton algorithm for logistic regression

  2025influential citation
• Adaptive time series forecasting with markovian variance switching

  2024cites this paper
• MODL: Multilearner Online Deep Learning

  2024cites this paper
• Non asymptotic analysis of Adaptive stochastic gradient algorithms and applications

  2023cites this paper
• Adaptive Probabilistic Forecasting of Electricity (Net-)Load

  2023cites this paper
• KOALA: A Kalman Optimization Algorithm with Loss Adaptivity

  2021cites this paper
• KaFiStO: A Kalman Filtering Framework for Stochastic Optimization

  2021cites this paper
• Kalman recursions Aggregated Online

  2020influential citation