Online Non-Convex Learning: Following the Perturbed Leader is Optimal

2019/03/19 by Suggala, Arun Sai, Netrapalli, Praneeth · 3 citations
#FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.1903.08110

Abstract

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'.

Cited by

• Conformal Online Learning of Deep Koopman Linear Embeddings
• Online Learning for Approximately-Convex Functions with Long-term Adversarial Constraints
• Online Ensemble Transformer for Accurate Cloud Workload Forecasting in Predictive Auto-Scaling

Related

• Best-Case Lower Bounds in Online Learning
• No-Regret Learnability for Piecewise Linear Losses
• Online non-convex optimization with imperfect feedback
• Online Learning: A Modern Introduction Using Convex Optimization
• Follow the Perturbed Leader: Optimism and Fast Parallel Algorithms for\n Smooth Minimax Games