Timezone: »

 
Poster
Online A-Optimal Design and Active Linear Regression
Xavier Fontaine · Pierre Perrault · Michal Valko · Vianney Perchet

Wed Jul 21 09:00 AM -- 11:00 AM (PDT) @ None #None
in Poster Session 3 »
We consider in this paper the problem of optimal experiment design where a decision maker can choose which points to sample to obtain an estimate $\hat{\beta}$ of the hidden parameter $\beta^{\star}$ of an underlying linear model. The key challenge of this work lies in the heteroscedasticity assumption that we make, meaning that each covariate has a different and unknown variance. The goal of the decision maker is then to figure out on the fly the optimal way to allocate the total budget of $T$ samples between covariates, as sampling several times a specific one will reduce the variance of the estimated model around it (but at the cost of a possible higher variance elsewhere). By trying to minimize the $\ell^2$-loss $\mathbb{E} [\lVert\hat{\beta}-\beta^{\star}\rVert^2]$ the decision maker is actually minimizing the trace of the covariance matrix of the problem, which corresponds then to online A-optimal design. Combining techniques from bandit and convex optimization we propose a new active sampling algorithm and we compare it with existing ones. We provide theoretical guarantees of this algorithm in different settings, including a $\mathcal{O}(T^{-2})$ regret bound in the case where the covariates form a basis of the feature space, generalizing and improving existing results. Numerical experiments validate our theoretical findings.
Keywords: Algorithms · Online Learning Algorithms

Author Information

Xavier Fontaine (ENS Paris-Saclay)
Pierre Perrault (ENS Paris Saclay & Inria)
Michal Valko (DeepMind / Inria / ENS Paris-Saclay)
Vianney Perchet (ENSAE & Criteo AI Lab)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors