Adaptive and optimal online linear regression on l(1)-balls

作者：Gerchinovitz Sebastien^*; Yu Jia Yuan

来源：Theoretical Computer Science, 2014, 519: 4-28.

DOI：10.1016/j.tcs.2013.09.024

• Online learning
• Linear regression
• Adaptive algorithms
• Minimax regret

We consider the problem of online linear regression on individual sequences. The goal in this paper is for the forecaster to output sequential predictions which are, after T time rounds, almost as good as the ones output by the best linear predictor in a given l(1)-ball in R-d. We consider both the cases where the dimension d is small and large relative to the time horizon T. We first present regret bounds with optimal dependencies on d. T, and on the sizes U, X and Y of the l(1)-ball, the input data and the observations. The minimax regret is shown to exhibit a regime transition around the point d = root TUX/(2Y). Furthermore, we present efficient algorithms that are adaptive, i.e., that do not require the knowledge of U, X, Y, and T, but still achieve nearly optimal regret bounds.

• 出版日期2014-1-30
• 单位IBM