LGFeb 25, 2015
Strongly Adaptive Online Learning
arXiv:1502.07073v3193 citations
AI Analysis
This work addresses the need for more robust online learning algorithms in machine learning, though it appears incremental as it builds on existing low-regret methods.
The paper tackles the problem of making online learning algorithms perform near-optimally on every time interval by introducing a reduction that transforms standard low-regret algorithms into strongly adaptive ones, resulting in efficient algorithms for various problems.
Strongly adaptive algorithms are algorithms whose performance on every time interval is close to optimal. We present a reduction that can transform standard low-regret algorithms to strongly adaptive. As a consequence, we derive simple, yet efficient, strongly adaptive algorithms for a handful of problems.