We consider the problem of learning an unknown function f from given data about f. The learning problem is to give an approximation fˆ to f that predicts the values of f away from the data. There are numerous settings for this learning problem depending on:
(i) the model class assumption, i.e., what additional information we have about f;
(ii) how we measure the accuracy of how well fˆ predicts f;
(iii) what is known about the data and data sites;
(iv) whether and how the data observations are polluted by noise.
Under standard model class assumptions, we show that a near-optimal fˆ can be found by solving a certain discrete over-parameterized optimization problem with a penalty term.
Copyright. All Rights Reserved.