Online Learning: Theory, Algorithms, and Applications - Ph.D thesis

Abstract......Page 6
Online Learning......Page 11
Taxonomy of Online Learning Algorithms......Page 12
Main Contributions......Page 14
Outline......Page 16
Notation......Page 17
Bibliographic Notes......Page 19
I Theory......Page 21
Casting Online Learning as Online Convex Programming......Page 22
Regret......Page 24
Non-convex loss functions and relative mistake bounds......Page 25
Bibliographic notes......Page 27
Online Convex Programming by Incremental Dual Ascend......Page 28
Generalized Fenchel Duality......Page 29
A Low Regret Algorithmic Framework for Online Convex Programming......Page 30
Analysis......Page 32
Automatically tuning the complexity tradeoff parameter......Page 36
Tightness of regret bounds......Page 41
Bibliographic notes......Page 42
Generalized Strong Convexity......Page 44
Algorithmic Framework......Page 45
Analysis......Page 47
Bibliographic Notes......Page 49
II Algorithms......Page 50
Quasi-additive Online Classification Algorithms......Page 51
Deriving new online updates based on aggressive dual ascending procedures......Page 59
Complex Prediction Problems......Page 65
Bibliographic Notes......Page 72
A Primal-Dual Perspective of Boosting......Page 74
AdaBoost......Page 77
Bibliographic Notes......Page 79
Projections onto 1 Balls and onto the Probabilistic Simplex......Page 80
Aggressive Updates for the Hinge-loss......Page 86
Aggressive Updates for Label Ranking......Page 88
Aggressive Updates for the Max-of-Hinge loss function......Page 97
Bibliographic Notes......Page 99
III Applications......Page 100
Label Ranking......Page 101
Algorithms......Page 102
Experiments......Page 104
Bibliographic Notes......Page 105
The Alignment Problem......Page 106
Hypothesis Class and a Learning Algorithm for Alignment......Page 108
Efficient evaluation of the alignment function......Page 110
Speech-to-phoneme alignment......Page 111
Music-to-score alignment......Page 114
Bibliographic Notes......Page 117
Bibliography......Page 118
Appendices......Page 120
Gradients, Subgradients, and Differential Sets......Page 130
Fenchel Conjugate......Page 131
Strongly Convex Functions......Page 134
Technical lemmas......Page 142
Brief Overview of PAC Learning......Page 150
Online-to-Batch Conversions......Page 152
Bibliographic Notes......Page 161