Missing values arise in most real-world data sets due to the aggregation of\nmultiple sources and intrinsically missing information (sensor failure,\nunanswered questions in surveys...). In fact, the very nature of missing values\nusually prevents us from running standard learning algorithms. In this paper,\nwe focus on the extensively-studied linear models, but in presence of missing\nvalues, which turns out to be quite a challenging task. Indeed, the Bayes rule\ncan be decomposed as a sum of predictors corresponding to each missing pattern.\nThis eventually requires to solve a number of learning tasks, exponential in\nthe number of input features, which makes predictions impossible for current\nreal-world datasets. First, we propose a rigorous setting to analyze a\nleast-square type estimator and establish a bound on the excess risk which\nincreases exponentially in the dimension. Consequently, we leverage the missing\ndata distribution to propose a new algorithm, andderive associated adaptive\nrisk bounds that turn out to be minimax optimal. Numerical experiments\nhighlight the benefits of our method compared to state-of-the-art algorithms\nused for predictions with missing values.\n