Compressed Least Squares Regression

2009, Discussing articles

[see  Linear regression with random projections, 2012 for corrections]

Odalric-Ambrym Maillard, Rémi Munos.
In NIPS ’09, pages 1213–1221, 2009.

[Download]

Abstract:

We consider the problem of learning, from K data, a regression function in a linear space of high dimension N using projections onto a random subspace of lower dimension M. From any algorithm minimizing the (possibly penalized) empirical risk, we provide bounds on the excess risk of the estimate computed in the projected subspace (compressed domain) in terms of the excess risk of the estimate built in the high-dimensional space (initial domain). We show that solving the problem in the compressed domain instead of the initial domain reduces the estimation error at the price of an increased (but controlled) approximation error. We apply the analysis to Least-Squares (LS) regression and discuss the excess risk and numerical complexity of the resulting “Compressed Least Squares Regression” (CLSR) in terms of N, K, and M. When we choose M=O(\sqrt{K}),  we show that CLSR has estimation error of order O(\log K / \sqrt{K}) and provides an interesting alternative to usual penalization techniques where one first selects a random subspace of lower dimension and then performs an empirical risk minimizer in this subspace.

You can dowload the paper from the NIPS Website (here) or from the HAL online open depository* (here).

Bibtex:
@incollection{MaillardM09,
title = {Compressed Least-Squares Regression},
author = {Odalric Maillard and R\'{e}mi Munos},
booktitle = {Advances in Neural Information Processing Systems 22},
editor = {Y. Bengio and D. Schuurmans and J.D. Lafferty and C.K.I. Williams and A. Culotta},
pages = {1213–1221},
year = {2009},
publisher = {Curran Associates, Inc.},
url = {http://papers.nips.cc/paper/3698-compressed-least-squares-regression.pdf}
}

Complexity versus Agreement for Many Views

2009, Discussing articles

Odalric-Ambrym Maillard, Nicolas Vayatis.
In ALT 2009, pages 232–246, 2009.

[Download]

Abstract:

The paper considers the problem of semi-supervised multi-view classification, where each view corresponds to a Reproducing Kernel Hilbert Space. An algorithm based on co-regularization methods with extra penalty terms reflecting smoothness and general agreement properties is proposed. We first provide explicit tight control on the Rademacher (L1 ) complexity of the corresponding class of learners for arbitrary many views, then give the asymptotic behavior of the bounds when the co-regularization term increases, making explicit the relation between consistency of the views and reduction of the search space. Third we provide an illustration through simulations on toy examples. With many views, a parameter selection procedure is based on the stability approach with clustering and localization arguments. The last new result is an explicit bound on the L2 -diameter of the class of functions.

You can dowload the paper from the ALT website (here) or from the HAL online open depository* (here).

Bibtex:
@inproceedings{MaillardV09,
author = {{Odalric-Ambrym} Maillard and Nicolas Vayatis},
title = {Complexity versus Agreement for Many Views.},
booktitle = {Algorithmic Learning Theory, 20th International Conference, {ALT} 2009, Porto, Portugal, October 3-5, 2009.},
year = {2009},
pages = {232–246},
editor = {Ricard Gavald\`{a} and G\`{a}bor Lugosi and Thomas Zeugmann and Sandra Zilles},
series = {Lecture Notes in Computer Science},
year = {2009}, volume = {5809},
publisher = {Springer}
}