v2.11.0 (5518)

PA - C8 - DS-ENSAE-6 : Online learning and aggregation


Course description: The aim of online learning is to provide efficient recursive algorithms of prediction when the data are arriving sequentially in a streaming way rather than as an array given once and for all. Whereas statistical learning is dealing

with independent identically distributed data, the emphasis in online learning

is on adversarial setting where the data are of arbitrary nature satisfying mild conditions. In this setting, one of the key ideas is to use, at each time instance, a suitable randomized choice from the given set of candidate predictors. Analogous techniques can be applied to solve the problem of aggregation, that is, to obtain procedures that predict almost as good as the best estimator in a given set. This course provides an introduction to online learning and aggregation focusing on theoretical aspects.


Topics covered:

-- Online classification in realizable case, halving.

-- Online gradient descent for convex and strongly convex loss. Online-

to-batch conversion. Online linear regression.

-- Randomization by exponential weighting. Prediction with expert ad-


-- Adversarial multi-armed bandit problem.

-- Aggregation of estimators.

-- Gradient-free online learning. Continuum bandit problem.



Shalev-Schwartz, S. (2011) Online learning and online convex optimi-

sation. Foundations and Trends in Machine Learning, vol. 4, pages


Tsybakov, A. (2020) Online learning and aggregation. Lecture Notes.


Evaluation: Final exam.

effectifs minimal / maximal:


Diplôme(s) concerné(s)

Format des notes

Numérique sur 20

Littérale/grade réduit

Pour les étudiants du diplôme Data Sciences

Le rattrapage est autorisé (Max entre les deux notes)
    L'UE est acquise si Note finale >= 10
    • Crédits ECTS acquis : 2.5 ECTS
    Veuillez patienter