In this thesis we study the following basic machine learning task: Given a fixed set of n input points in a d-dimensional linear regression problem, we wish to predict a hidden response value for each of the points. We can only afford to attain the responses for a small subset of the points that are then used to construct linear predictions for all points in the dataset. The performance of the predictions is evaluated by the total square loss on all responses. We show that a good approximate solution to this least squares problem can be obtained from just dimension d many responses by using a joint sampling technique called volume sampling. Moreover, the least squares solution obtained for the volume sampled subproblem is an unbiased estimator of optimal solution based on all n responses. This unbiasedness is a desirable property that is not shared by standard subset selection techniques.

Motivated by these basic properties, we develop a theoretical framework for studying volume sampling, which leads to a number of new expectation formulas and statistical guarantees which are of importance not only to least squares regression but also numerical linear algebra in general. Our methods lead to several novel extensions of volume sampling, including a regularized variant, and we propose the first efficient algorithms which make this technique a practical tool in the machine learning toolbox. Finally, we provide experimental evidence which confirms our theoretical findings.

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.

Personalized health-care is trending and individuals tend to wear sensors in order to record their own health data. As a part of this trend, any redundancy in the data captured by wearable sensors must be exploited to reduce the number of devices one may wear. In this thesis, we work with a device which senses breathing and pulse through pressure tube and pulse oximetry, respectively. Extracting the dependency between these two measurements, we approximately predict the breathing rate by first reconstructing the breathing signal using the data coming from the finger-tip sensor, and then detecting the peaks in the reconstructed signal. For breathing signal reconstruction, two different techniques are used: (1) applying low- and high-pass filters on the pulse signal (2) training a neural network on a prepared dataset. Our experiments show that neural networks have a better performance comparing to filters in reconstructing the breathing signal, and consequently, predicting the breathing rate.

Exponentiated Gradient +/- (abbr. EG+-) is a gradient update algorithm

drawn from work by Manfred Warmuth (Kivinen and Warmuth, 1997) in the

online learning setting. This thesis ports the algorithm into the context of deep

neural networks and analyses its fitness in that context compared to the current

state of the art gradient update methods. Existing methods employ an additive

update scheme whereby some fraction of the gradient is added to the weight

values to update them at each iteration in the gradient descent algorithm. EG+-

provides a multiplicative update scheme whereby a proportion of the gradient

is multiplied into the original weight value, and then normalized to update the

weight. EG+- is motivated by using a relative entropy regularization. This thesis

analyzes various properties and experimental results of the algorithm in comparison

to other update methods, and analyzes EG+- in the context of state of the

art residual networks and challenging vision problems. Three published implementations

are experimented with, and demonstrate that EG+- performs better

than SGD when there are many noisy features, and that it compares well with

commonly used state-of-the art gradient descent optimization methods. EG+-

also performs better than most SGD based optimizers on black-box adversarial

attacks, with the exception of non momentum based SGD with which it performs

similarly.

This thesis develops algorithms for learning combinatorial objects. A combinatorial object is a structured concept composed of components. Examples are permutations, Huffman trees, binary search trees and paths in a directed graph. Learning combinatorial objects is a challenging problem: First, the number of combinatorial objects is typically exponential in terms of number of components. Second, the convex hull of these objects is a polytope whose characterization in the original space may have exponentially many facets or a description of the polytope in terms of facets/inequalities may not be even known. Finally, the loss of each object could be a complicated function of its component and may not be simply additive as a function of the components. In this thesis, we explore a wide variety of combinatorial objects and address the challenges above. For each combinatorial object, we go beyond the original space of the problem and introduce auxiliary spaces and representations. The representation of the objects in these auxiliary spaces admits additive losses and polytopes with polynomially many facets. This allows us to extend well-known algorithms like Expanded Hedge and Component Hedge to these combinatorial objects for the first time.