Online Learning Without Prior Information

Abstract

The vast majority of optimization and online learning algorithms today require some prior information about the data (often in the form of bounds on gradients or on the optimal parameter value). When this information is not available, these algorithms require laborious manual tuning of various hyperparameters, motivating the search for algorithms that can adapt to the data with no prior information. We describe a frontier of new lower bounds on the performance of such algorithms, reflecting a tradeoff between a term that depends on the optimal parameter value and a term that depends on the gradients' rate of growth. Further, we construct a family of algorithms whose performance matches any desired point on this frontier, which no previous algorithm reaches.

12 pages main text; 35 pages total; COLT 2017

References in corpus (1)

• No-Regret Algorithms for Unconstrained Online Convex Optimization

Cited by in corpus (8)

• Parameter-free online learning via model selection
• Training Deep Networks without Learning Rates Through Coin Betting
• Online linear optimization with the log-determinant regularizer
• Problem-Complexity Adaptive Model Selection for Stochastic Linear Bandits
• Pareto Optimal Model Selection in Linear Bandits
• Adaptive Online Learning for Gradient-Based Optimizers
• Adaptive Online Learning with Varying Norms
• Approximately Exact Line Search