Greedy algorithms for prediction

Abstract

In many prediction problems, it is not uncommon that the number of variables used to construct a forecast is of the same order of magnitude as the sample size, if not larger. We then face the problem of constructing a prediction in the presence of potentially large estimation error. Control of the estimation error is either achieved by selecting variables or combining all the variables in some special way. This paper considers greedy algorithms to solve this problem. It is shown that the resulting estimators are consistent under weak conditions. In particular, the derived rates of convergence are either minimax or improve on the ones given in the literature allowing for dependence and unbounded regressors. Some versions of the algorithms provide fast solution to problems such as Lasso.

Published at http://dx.doi.org/10.3150/14-BEJ691 in the Bernoulli (http://isi.cbs.nl/bernoulli/) by the International Statistical Institute/Bernoulli Society (http://isi.cbs.nl/BS/bshome.htm)

References in corpus (11)

• Nearly unbiased variable selection under minimax concave penalty
• Pathwise coordinate optimization
• On the "degrees of freedom" of the lasso
• On asymptotically optimal confidence regions and tests for high-dimensional models
• High-dimensional generalized linear models and the lasso
• Approximation and learning by greedy algorithms
• Sparsity oracle inequalities for the Lasso
• Aggregation for Gaussian regression
• Confidence sets in sparse regression
• Best subset selection, persistence in high-dimensional statistical learning and optimization under $l_1$ constraint
• AdaBoost and Forward Stagewise Regression are First-Order Convex Optimization Methods

Cited by in corpus (1)

• Estimation of an Order Book Dependent Hawkes Process for Large Datasets