Online Non-Convex Learning: Following the Perturbed Leader is Optimal
We study the problem of online learning with non-convex losses, where the learner has access to an offline optimization oracle. We show that the classical Follow the Perturbed Leader (FTPL) algorithm achieves optimal regret rate of $O(T^{-1/2})$ in this setting. This improves upon the previous best-known regret rate of $O(T^{-1/3})$ for FTPL. We further show that an optimistic variant of FTPL achieves better regret bounds when the sequence of losses encountered by the learner is `predictable'.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Follow the Perturbed Leader: Optimism and Fast Parallel Algorithms for Smooth Minimax Games
We consider the problem of online learning and its application to solving minimax games. For the online learning problem, Follow the Perturbed Leader (FTPL) is a widely studied algorithm which enjoys the optimal $O(T^{1/…
From Non-Convex to Strongly Convex: Curvature-Adaptive FTPL for Online Optimization
Curvature adaptivity is a classical theme in online optimization: for convex Lipschitz losses, adaptive methods interpolate between the optimal $O(\sqrt{T})$ regret for general convex losses and $O(\log T)$ regret under …
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 conv…
Leader-Following Consensus of High-Order Perturbed Multi-agent Systems under Multiple Time-Varying Delays
Solving an output consensus problem in multi-agent systems is often hindered by multiple time-variant delays. To address such fundamental problems over time, we present a new optimal time-variant distributed control for …
Online Non-convex Optimization with Long-term Non-convex Constraints
A novel Follow-the-Perturbed-Leader type algorithm is proposed and analyzed for solving general long-term constrained optimization problems in online manner, where the objective and constraints are arbitrarily generated …