This thesis is dedicated to the study of online learning algorithms. In particular, after reviewing fundamental concepts in the theory of convex and online linear optimization, we provide a refined analysis of Implicit updates in the framework of Online Mirror Descent. We design a new adaptive algorithm based on it and carefully study its regret bound in the static case, linking it to the variability of the sequence of loss functions. Furthermore, we extend its application to the dynamic setting, studying its dynamic regret. In particular, we show that it achieves the optimal dynamic regret bound, when the quantities of interest are observable or known beforehand. On the other hand, in order to have a fully adaptive algorithm we show how to combine strongly adaptive algorithms with a simple greedy strategy. Finally, we focus on the well known problem of learning with expert advice. We review existing algorithm and describe an existing open problem. We provide some recent results and partial progress on how this problem could be addressed.

ADAPTIVE AND IMPLICIT ONLINE LEARNING / N. Campolongo ; supervisor: N. Cesa-Bianchi ; coordinator: P. Boldi. - : . Dipartimento di Informatica Giovanni Degli Antoni, 2021 Mar 22. ((33. ciclo, Anno Accademico 2020. [10.13130/campolongo-nicolo-_phd2021-03-22].

ADAPTIVE AND IMPLICIT ONLINE LEARNING

N. Campolongo
2021

Abstract

This thesis is dedicated to the study of online learning algorithms. In particular, after reviewing fundamental concepts in the theory of convex and online linear optimization, we provide a refined analysis of Implicit updates in the framework of Online Mirror Descent. We design a new adaptive algorithm based on it and carefully study its regret bound in the static case, linking it to the variability of the sequence of loss functions. Furthermore, we extend its application to the dynamic setting, studying its dynamic regret. In particular, we show that it achieves the optimal dynamic regret bound, when the quantities of interest are observable or known beforehand. On the other hand, in order to have a fully adaptive algorithm we show how to combine strongly adaptive algorithms with a simple greedy strategy. Finally, we focus on the well known problem of learning with expert advice. We review existing algorithm and describe an existing open problem. We provide some recent results and partial progress on how this problem could be addressed.
CESA BIANCHI, NICOLO' ANTONIO
BOLDI, PAOLO
Settore INF/01 - Informatica
ADAPTIVE AND IMPLICIT ONLINE LEARNING / N. Campolongo ; supervisor: N. Cesa-Bianchi ; coordinator: P. Boldi. - : . Dipartimento di Informatica Giovanni Degli Antoni, 2021 Mar 22. ((33. ciclo, Anno Accademico 2020. [10.13130/campolongo-nicolo-_phd2021-03-22].
Doctoral Thesis
File in questo prodotto:
File Dimensione Formato  
phd_unimi_R12065.pdf

accesso aperto

Descrizione: Articolo principale
Tipologia: Tesi di dottorato completa
Dimensione 1.56 MB
Formato Adobe PDF
1.56 MB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/823932
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact