Learning Theory of Online Mirror Descent Algorithms

Abstract

Gradient descent is a classical powerful method for minimizing functions over Euclidean spaces or infinite dimensional Hilbert spaces. It has been widely used in machine learning applications and deeply studied in learning theory. Mirror descent is an extension of the gradient descent method by relaxing the Hilbert space structure and allowing a Banach space norm on R^d where the subgradient is viewed as an element in the dual space. In the online or stochastic setting, accordingly, online mirror descent algorithms are extended from stochastic gradient descent algorithms by the same approach. There are many variants of online mirror descent algorithms which are considered to be potentially powerful, some of them are not well understood with very few theoretical results under mild conditions. In this thesis we mainly focus on the online regularized dual averaging algorithm, which is a variant of online mirror descent algorithms, for pointwise learning, and online mirror descent algorithm for pairwise learning.

Online regularized dual averaging (online RDA) is an efficient method to solve regularized learning schemes involving a data-fitting term and a regularizer possibly inducing sparsity. Existing studies of online RDA impose boundedness assumptions on the subgradients for the iterates encountered in the learning process. We present novel error analysis by avoiding these boundedness assumptions and provide optimal convergence rates (subject to a logarithmic factor) for general convex and strongly convex objective functions.

Apart from pointwise learning scheme, pairwise learning has attracted growing interest in both practical and theoretical machine learning. Unlike traditional learning tasks with the associated loss function depending only on a single example, pairwise learning refers to learning tasks for which the associated loss function involves a pair of examples. For pairwise learning, we first give convergence analysis of general unregularized online learning algorithms associated with a reproducing kernel Hilbert space with general convex loss functions, then we study in particular the online mirror descent algorithm including a regularization term for pairwise learning. Refined upper bounds are obtained with relaxed assumptions on the domain and the loss function.

Date of Award	29 Jan 2018
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Dingxuan ZHOU (Supervisor)