mit6
http://dspace.mit.edu:80
The DSpace digital repository system captures, stores, indexes, preserves, and distributes digital research material.
20211203T15:53:20Z

Just interpolate: Kernel “Ridgeless” regression can generalize
https://hdl.handle.net/1721.1/138308
Just interpolate: Kernel “Ridgeless” regression can generalize
Liang, Tengyuan; Rakhlin, Alexander
© Institute of Mathematical Statistics, 2020. In the absence of explicit regularization, Kernel “Ridgeless” Regression with nonlinear kernels has the potential to fit the training data perfectly. It has been observed empirically, however, that such interpolated solutions can still generalize well on test data. We isolate a phenomenon of implicit regularization for minimumnorm interpolated solutions which is due to a combination of high dimensionality of the input data, curvature of the kernel function and favorable geometric properties of the data such as an eigenvalue decay of the empirical covariance and kernel matrices. In addition to deriving a datadependent upper bound on the outofsample error, we present experimental evidence suggesting that the phenomenon occurs in the MNIST dataset.
20200101T00:00:00Z

Does data interpolation contradict statistical optimality?
https://hdl.handle.net/1721.1/138307
Does data interpolation contradict statistical optimality?
Belkin, M; Rakhlin, A; Tsybakov, AB
© 2019 by the author(s). We show that classical learning methods interpolating the training data can achieve optimal rates for the problems of nonparametric regression and prediction with square loss.
20200101T00:00:00Z

Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles
https://hdl.handle.net/1721.1/138306
Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles
Foster, Dylan J; Rakhlin, Alexander
A fundamental challenge in contextual bandits is to develop flexible, generalpurpose algorithms with computational requirements no worse than classical supervised learning tasks such as classification and regression. Algorithms based on regression have shown promising empirical success, but theoretical guarantees have remained elusive except in special cases. We provide the first universal and optimal reduction from contextual bandits to online regression. We show how to transform any oracle for online regression with a given value function class into an algorithm for contextual bandits with the induced policy class, with no overhead in runtime or memory requirements. We characterize the minimax rates for contextual bandits with general, potentially nonparametric function classes, and show that our algorithm is minimax optimal whenever the oracle obtains the optimal rate for regression. Compared to previous results, our algorithm requires no distributional assumptions beyond realizability, and works even when contexts are chosen adversarially.
20200101T00:00:00Z

Near optimal finite time identification of arbitrary linear dynamical systems
https://hdl.handle.net/1721.1/138305
Near optimal finite time identification of arbitrary linear dynamical systems
Sarkar, T; Rakhlin, A
© 2019 International Machine Learning Society (IMLS). Wc derive finite time error bounds for estimating general linear timeinvariant (LTI) systems from a single observed trajectory using the method of least squares. We provide the first analysis of the general case when eigenvalues of the LTI system are arbitrarily distributed in three regimes: stable, marginally stable, and explosive. Our analysis yields sharp upper bounds for each of these cases separately. We observe that although the underlying process behaves quite differently in each of these three regimes, the systematic analysis of a selfnormalized martingale difference term helps bound identification error up to logarithmic factors of the lower bound. On the other hand, we demonstrate that the least squares solution may be statistically inconsistent under certain conditions even when the signaltonoise ratio is high.
20190101T00:00:00Z