Professor of Computer Science at University of Milan

Online learning is an abstract mathematical framework for the study of sequential decision problems. In this course, we consider online algorithms that construct predictive models (for classification or regression) by going through the data points sequentially, using each new data point to adjust the current model. Typically, this adjustment is "local", as it only involves the current model and the new data point. This has two main advantages: first, online algorithms typically scale well with the number of data points; second, they easily adapt to the properties of the data sequence on which they are run. As a consequence, popular stochastic optimization methods for large-scale learning applications, such as stochastic gradient descent, are often built on online learning algorithms. In this course, we introduce the framework of online convex optimization, the standard model for the design and analysis of online learning algorithms. After defining the notions of regret and regularization, we describe and analyze some of the most important online algorithms, including Mirror Descent, AdaGrad, and Online Newton Step. The last part of the course is concerned with models of online learning with partial feedback. In particular, we describe and analyze algorithms for the multiarmed bandit model.

Professor of Computer Science at University of California, Merced

Learning a model from data is usually defined by an optimisation problem, where a loss function (such as the classification error) is minimised over the parameters of the model on a training set. The optimisation is usually carried out using gradient-based algorithms. However, some models of interest involve objective functions or constraints that are non-differentiable or involve discrete parameters, such as autoencoders using binary codes, decision trees, or neural nets whose parameters are quantised. We will describe a generic approach to solve this type of problems, based on introducing auxiliary variables and constraints so the optimisation involves an augmented space but is simpler. Applying to this a penalty method and alternating optimisation results in steps that often exhibit high parallelism and take the form of known problems which can be solved by existing algorithms. We will describe three cases where this is applicable: 1) in "nested systems", involving mathematically nested functions, such as deep nets; 2) in compressing machine learning models, in particular deep nets, so they optimise a given loss while satisfying constraints on memory, execution time or energy; and 3) in learning decision trees and their combination with neural nets.

Slides