Online Linear Optimization via Smoothing
We present a new optimization-theoretic approach to analyzing Follow-the-Leader style algorithms, particularly in the setting where perturbations are used as a tool for regularization. We show that adding a strongly convex penalty function to the decision rule and adding stochastic perturbations to data correspond to deterministic and stochastic smoothing operations, respectively. We establish an equivalence between "Follow the Regularized Leader" and "Follow the Perturbed Leader" up to the smoothness properties. This intuition leads to a new generic analysis framework that recovers and improves the previous known regret bounds of the class of algorithms commonly known as Follow the Perturbed Leader.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Nonlinear Model Predictive Control Based on Constraint-Aware Particle Filtering/Smoothing
Nonlinear model predictive control (NMPC) has gained widespread use in many applications. Its formulation traditionally involves repetitively solving a nonlinear constrained optimization problem online. In this paper, we…
Model Predictive ControlOptimization-Induced Graph Implicit Nonlinear Diffusion
Due to the over-smoothing issue, most existing graph neural networks can only capture limited dependencies with their inherently finite aggregation layers. To overcome this limitation, we propose a new kind of graph conv…
A Recursive Newton Method for Smoothing in Nonlinear State Space Models
In this paper, we use the optimization formulation of nonlinear Kalman filtering and smoothing problems to develop second-order variants of iterated Kalman smoother (IKS) methods. We show that Newton's method corresponds…
State Space ModelsAdaptive Matrix Online Learning through Smoothing with Guarantees for Nonsmooth Nonconvex Optimization
We study online linear optimization with matrix variables constrained by the operator norm, a setting where the geometry renders designing data-dependent and efficient adaptive algorithms challenging. The best-known adap…
Proximal Point Imitation Learning
This work develops new algorithms with rigorous efficiency guarantees for infinite horizon imitation learning (IL) with linear function approximation without restrictive coherence assumptions. We begin with the minimax f…
Imitation Learning