Title
Horizon-Independent Minimax Linear Regression.
Abstract
We consider online linear regression: at each round, an adversary reveals a covariate vector, the learner predicts a real value, the adversary reveals a label, and the learner suffers the squared prediction error. The aim is to minimize the difference between the cumulative loss and that of the linear predictor that is best in hindsight. Previous work demonstrated that the minimax optimal strategy is easy to compute recursively from the end of the game; this requires the entire sequence of covariate vectors in advance. We show that, once provided with a measure of the scale of the problem, we can invert the recursion and play the minimax strategy without knowing the future covariates. Further, we show that this forward recursion remains optimal even against adaptively chosen labels and covariates, provided that the adversary adheres to a set of constraints that prevent misrepresentation of the scale of the problem. This strategy is horizon-independent in that the regret and minimax strategies depend on the size of the constraint set and not on the time-horizon, and hence it incurs no more regret than the optimal strategy that knows in advance the number of rounds of the game. We also provide an interpretation of the minimax algorithm as a follow-the-regularized-leader strategy with a data-dependent regularizer and obtain an explicit expression for the minimax regret.
Year
Venue
Keywords
2018
ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 31 (NIPS 2018)
a set,linear regression,minimax strategy,real value,the aim,minimax regret,minimax algorithm,horizon-independent minimax linear regression
Field
DocType
Volume
Covariate,Mathematical optimization,Minimax,Square (algebra),Regret,Computer science,Linear prediction,Adversary,Recursion,Linear regression
Conference
31
ISSN
Citations 
PageRank 
1049-5258
2
0.49
References 
Authors
0
2
Name
Order
Citations
PageRank
Alan Malek152.29
Peter L. Bartlett254821039.97