Odalric-Ambrym Maillard

This page is dedicated to start discussions about the article "Sparse Recovery with Brownian Sensing". Feel free to post any comment, sugggestion, question, correction, extension... I will enjoy discussing this with you.

• Abstract:

" We consider the problem of recovering the parameter α ∈ R^K of a sparse function f (i.e. the number of non-zero entries of α is small compared to the number K of features) given noisy evaluations of f at a set of well-chosen sampling points. We introduce an additional randomization process, called Brownian sensing, based on the computation of stochastic integrals, which produces a Gaussian sensing matrix, for which good recovery properties are proven, independently on the number of sampling points N , even when the features are arbitrarily non-orthogonal. Under the assumption that f is Hölder continuous with exponent at least 1/2, we provide an estimate â of the parameter such that ||α − â||_2 = O( ||η||_2/ sqrt(N)), where η is the observation noise. The method uses a set of sampling points uniformly distributed along a one-dimensional curve selected according to the features. We report numerical experiments illustrating our method."

• Future work:

Find a systematic way to choose an appropriate curve to sample along.

This page is dedicated to start discussions about the article "Adaptive bandits: Towards the best history-dependent strategy". Feel free to post any comment, sugggestion, question, correction, extension... I will enjoy discussing this with you.

• Abstract:

"We consider multi-armed bandit games with possibly adaptive opponents.
We introduce models  \Theta of constraints based on equivalence classes on the common history (information shared by the player and the opponent) which define two learning scenarios:
(1) The opponent is constrained, i.e.~he provides rewards that are stochastic functions of equivalence classes defined by some model  \theta^*\in\Theta . The regret is measured with respect to (w.r.t.) the best history-dependent strategy.
(2) The opponent is arbitrary and we measure the regret w.r.t.~the best strategy among all mappings from classes to actions (i.e.~the best history-class-based strategy) for the best model in  \Theta .
This allows to model opponents (case 1) or strategies (case 2) which handles finite memory, periodicity, standard stochastic bandits and other situations.

When  \Theta=\{\theta\} , i.e.~only one model is considered, we derive \textit{tractable} algorithms achieving a \textit{tight} regret (at time T) bounded by  \tilde O(\sqrt{TAC}) , where  C is the number of classes of  \theta . Now, when many models are available, all known algorithms achieving a nice regret  O(\sqrt{T}) are unfortunately \textit{not tractable} and scale poorly with the number of models  |\Theta| . Our contribution here is to provide {\em tractable} algorithms with regret bounded by  T^{2/3}C^{1/3}\log(|\Theta|)^{1/2} ."

• Discussion:

We do not know whether in the case of a pool of models \Phi_\Theta, there exist tractable algorithms with \Phi_\Theta-regret better that T^{2/3} with log dependency w.r.t. |\Theta|.

• Future work:

Extend this setting to Reinforcement Learning.

This page is dedicated to start discussions about the article "Scrambled Objects for Least-Squares Regression".
Feel free to post any comment, sugggestion, question, correction, extension... I will enjoy discussing this with you.

• Abstract:

"We consider least-squares regression using a randomly generated subspace G_P \subset F of finite dimension P,  where F is a function space of infinite dimension, e.g. L2([0, 1]^d). G_P is defined as the span of P random features that are linear combinations of the basis functions of F weighted by random Gaussian i.i.d. coefficients. In particular, we consider multi-resolution random combinations at all scales of a given mother function, such as a hat function or a wavelet. In this latter case, the resulting Gaussian objects are called scrambled wavelets and we show that they enable to approximate functions in Sobolev spaces H_s([0, 1]^d). As a result, given N data, the least-squares estimate \hat g built from P scrambled wavelets has excess risk ||f^* − \hat g||2 P = O(||f^*||2_{H_s([0,1]^d)}(logN)/P + P(logN)/N) for target functions f^* \in H_s([0, 1]^d) of smoothness order s > d/2. An interesting aspect of the resulting bounds is that they do not depend on the distribution P from which the data are generated, which is important in a statistical regression setting considered here. Randomization enables to adapt to any possible distribution. We conclude by describing an efficient numerical implementation using lazy expansions with numerical complexity \tilde O (2dN^3/2 logN + N^2), where d is the dimension of the input space."

• Discussion:

It appears that similar methods using random generation of features seem to have been used in practice for years, beginning with the perceptron. Thus a natural question is what light this work sheds on such practical ideas.

The proof here is not satisfactory here for it makes appear big, not optimal constants. The main reason is that we used techniques from "A distribution Free Theory of Nonparametric Regression" in order to control the concentration of the quadratic process that appears. But using more recent techniques would definitely yield to tighter bounds.

• Future work:

In the case the initial set of features comes from Carleman operators, there is a deep connection with RKHS. Thus we would like to use proof techniques from kernel methods to derive alternate bounds with improved constants and improve further our understanding of this concept.

This page is dedicated to start discussions about the article "Online Learning in Adversarial Lipschitz Environments".
Feel free to post any comment, sugggestion, question, correction, extension... I will enjoy discussing this with you.

• Abstract:

"We consider the problem of online learning in an adversarial environment when the reward functions chosen by the adversary are assumed to be Lipschitz. This setting extends previous works on linear and convex online learning. We  provide a class of algorithms with cumulative regret upper bounded by O(\sqrt{dT ln(\lambda)}) where d is the dimension of the search space, T the time horizon, and \lambda the Lipschitz constant. Efficient numerical implementations using particle methods are discussed. Applications include online supervised learning problems for both full and partial (bandit) information settings, for a large class of non-linear regressors/classifiers, such as neural networks."

• Discussion:

It would be interesting to analyse general PMC methods and get full understanding of the speed of convergence towards the distribution targetted by the method. This involves working for instance on further developing the nice results of the book (Feynman-Kac Formulae, Pierre Del Moral,2004) as well as (Sequential Monte Carlo Methods in Practice, A.Doucet , N. de Freitas, N. Gordon, 2001).

• Future work: 

Developping a deeper analysis of the PMC methods, that can be applied to this paper, or any other else.

This page is dedicated to start discussions about the article "Complexity versus Agreement for Many Views".
Feel free to post any comment, sugggestion, question, correction, extension... I will enjoy discussing this with you.

• 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."

• Future work:

It would be interesting to compare the selection method proposed here that uses a data-driven penalty  with standard model selection methods (P.Massart, S.Arlot...etc)