From Non-Convex to Strongly Convex: Curvature-Adaptive FTPL for Online Optimization

Moses Charikar, Chirag Pabbaraju, Ambuj Tewari

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 con…