UC Santa Cruz

This thesis considers two online matrix learning problems: the problem of online Principle Component Analysis (PCA) and the problem of learning rotations online. Previous papers proposed two online algorithms for these problems, which are the Matrix Exponentiated Gradient (MEG) algorithm and the Gradient Descent (GD) algorithm, respectively. This thesis evaluates these two algorithms by their regret, which is the additional total loss of the online algorithm over the total loss of the best offline comparator (chosen in hindsight).

In Chapter 2, we show that for online PCA, both algorithms achieve essentially the same and optimal (within a constant factor) regret bound when the bound is expressed as a function of the number of trials. However, when considering regret bounds as functions of the loss of the best comparator, MEG remains optimal and strictly outperforms GD. Chapter 3 considers a generalization of online PCA in which we use the combination of the compression gain of PCA and the cosine similarity to measure the closeness between two directions (i.e. unit length vectors). Such a combined measurement involves both the first and second moments of the learner's randomized prediction, and therefore, we propose an online algorithm that maintains both a vector and a matrix as its parameter simultaneously. In particular, in each trial of the game, this algorithm uses a novel iterative procedure to decompose its parameter pair into a mixture of at most $n$ pure directions. Chapter 4 considers the problem of learning rotations online. We show that for this problem, the GD algorithm is optimal (up to a constant) for both the regret bounds that are functions of the number of trials and the regret bounds that are functions of the loss of best comparator.