Qing Li, Zhigang Deng, et al.
IEEE T-MI
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 ℓ1-ball in Rd. 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 ℓ1-ball, the input data and the observations. The minimax regret is shown to exhibit a regime transition around the point d=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. © 2013 Elsevier B.V.
Qing Li, Zhigang Deng, et al.
IEEE T-MI
Thomas M. Cover
IEEE Trans. Inf. Theory
Maurice Hanan, Peter K. Wolff, et al.
DAC 1976
Daniel M. Bikel, Vittorio Castelli
ACL 2008