论文标题
使用Kalman递归的随机在线优化
Stochastic Online Optimization using Kalman Recursion
论文作者
论文摘要
我们以恒定动力学研究了扩展的卡尔曼滤波器，提供了随机优化的贝叶斯观点。在不受约束的环境中，我们获得了累积过量风险的高概率界限。为了避免任何投影步骤，我们提出了两阶段分析。首先，对于线性和逻辑回归，我们证明该算法进入了一个本地阶段，在该阶段中，估计值留在最佳距离周围的小区域。我们在此收敛时间内提供具有很高可能性的明确界限。其次，对于广义线性回归，我们提供了对当地阶段中过量风险的Martingale分析，从而改善了有界随机优化的现有风险。 EKF作为无参数的在线算法，每次迭代的O（d^2）成本最佳地解决了一些不受约束的优化问题。
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.
