Mark Schmidt

Optimization and inference are essential ingredients of machine learning (ML). Many optimization and inference problems can be formulated from a probabilistic perspective to exploit the Fisher-Rao geometric structure of a probability family. By leveraging the structure, optimization and inference methods can improve their performance. A classic approach to exploiting the Fisher-Rao structure is natural-gradient descent (NGD). However, implementing NGD remains computationally intensive. When a parameter space is constrained, it can also be non-trivial to perform NGD while taking the constraint into consideration. It is even more challenging to perform NGD in structured parameter spaces. This work pushes the boundary of the theory and practice of NGD. We first establish a connection among NGD, mirror descent (MD), and Riemannian gradient descent (RGD). Thanks to this connection, we consider various approaches to better exploit underlying geometric and algebraic structures of NGD resulting in computationally efficient and practically useful methods for inference and optimization problems in ML. In the first part of this work, we reduce the computational cost of NGD for exponential family approximations in variational inference. To do so, we exploit a convex duality in MD by viewing NGD as a MD update.Secondly, we extend the scope of NGD and develop efficient methods by exploiting a similar duality for mixtures of exponential family approximations. Mixtures are more powerful than the exponential family to model complex distributions. We introduce a new Fisher-Rao metric for a mixture since the original Fisher-Rao metric becomes singular in mixture cases. The third part of this work addresses the constraint issue in NGD by proposing a new efficient update scheme inspired by RGD. We focus on performing NGD updates in positive-definite constrained parameter spaces as these spaces appear in exponential family distributions and their mixtures. Finally, we enable a practical usage of NGD methods in structured and constrained parameter spaces by using tools from Riemannian geometry. We propose a structure-preserving NGD update scheme by using matrix Lie groups and moving coordinates. Thanks to our approach, we alsodevelop novel structured second-order methods for unconstrained optimization and adaptive gradient-based methods for deep learning.

View record

Algorithm designers are regularly faced with the tedious task of finding suitabledefault values for the parameters that impact the performance of algorithms. Thoroughlyevaluating even a single parameter configuration typically requires runningthe algorithm on a large number of problem instances, which can make the processvery slow. To address this problem, many automated algorithm configurationprocedures have been proposed. The vast majority of these are based on powerfulmeta-heuristics with strong diversification mechanisms, thereby ensuring that theysufficiently explore the parameter configuration space.However, despite the prominence of automated algorithm configuration, relativelylittle is known about the algorithm configuration landscapes searched bythese procedures, which relate parameter values to algorithm performance. As aresult, while these strong diversification mechanisms make existing configuratorsrobust, it is unclear whether or not they are actually required or simply increase therunning time of the configurators.One particularly notable early work in the field showed evidence suggestingthat the algorithm configuration landscapes of two optimization algorithms are, infact, close to uni-modal. However, existing fitness landscape analysis techniquesare unable to account for the stochasticity in the performance measurements ofalgorithms in a statistically principled way, which is a major barrier to their applicationto studying algorithm configuration scenarios. We address this gap bydeveloping the first statistically principled method for detecting significant deviationsfrom uni-modality in a stochastic landscape.We apply this method, along with other (new and existing) landscape analysistechniques, to a variety of algorithm configuration scenarios arising in automated machine learning (AutoML) and the minimization of the running time ofalgorithms for solving NP-hard problems. We show that algorithm configurationlandscapes are most often highly structured and relatively simple.Using the intuition from this analysis, we develop two prototype algorithmconfiguration procedures designed for AutoML. We show that the methods makeassumptions that are too strong, leading to mixed results. However, we build onthis intuition and develop another procedure for the configuration of NP-hard algorithms.Compared to state-of-the-art baselines, we show that our new methodoften finds similar or better configurations in the same or less time.

View record

Nucleic acid molecules are vital constituents of living beings. These molecules arealso utilized for building autonomous nanoscale devices with biological and technologicalapplications, such as toehold switches, algorithmic structures, robots,and logic gates. Predicting the kinetics (non-equilibrium dynamics) of interactingnucleic acid strands, such as hairpin opening and strand displacement reactions,would assist with understanding the functionality of nucleic acids in the cell andwith building nucleic-acid based devices.Continuous-time Markov chains (CTMC) are commonly used to predict thekinetics of these reactions. However, predicting kinetics with CTMC models ischallenging. Because, first, the CTMCs should be defined with accurate and biophysicallyrealistic kinetic models. Second, the state space of the CTMCs may belarge, making predictions time-consuming, particularly for reactions that happenon a long time scale (rare events), such as strand displacement at room temperature.We introduce an Arrhenius kinetic model of interacting nucleic acid strandsthat relates the activation energy of a state transition with the immediate local environmentof the affected base pair. Our model can be used in stochastic simulationsto estimate kinetic properties and is consistent with existing thermodynamic modelsthat make equilibrium predictions. We infer the model’s parameters on a widerange of reactions by using mean first passage time (MFPT) estimates. We estimateMFPTs using exact computations on simplified state spaces. We show thatour new model surpasses the performance of the previously established Metropoliskinetic model.We further address MFPT estimation and the rapid evaluation of perturbed parameters for parameter inference in the full state space of reactions’ CTMCs.We show how to use a reduced variance stochastic simulation algorithm (RVSSA)to estimate MFPTs. We also introduce a fixed path ensemble inference (FPEI)approach for the rapid evaluation of perturbed parameters. These methods arepromising, but they are not suitable for rare events. Thus, we introduce the pathwayelaboration method, a time-efficient and probabilistic truncated-based approach foraddressing both mentioned tasks. We demonstrate the effectiveness of our methodsby conducting computational experiments on nucleic acid kinetics measurementsthat cover a wide range of rates for different type of reactions.

View record

Deep neural networks have dominated performance benchmarks on numerous machine learning tasks. These models now power the core technology of a growing list of products such as Google Search, Google Translate, Apple Siri, and even Snapchat, to mention a few. We first address two challenges in the real-world applications of deep neural networks in computer vision: data scarcity and prediction reliability. We present a new approach to data collection through synthetic data via video games that is cost-effective and can produce high-quality labelled training data on a large scale. We validate the effectiveness of synthetic data on multiple problems through cross-dataset evaluation and simple adaptive techniques. We also examine the reliability of neural network predictions in computer vision problems and show that these models are fragile on out-of-distribution test data. Motivated by statistical learning theory, we argue that it is necessary to detect out-of-distribution samples before relying on the predictions. To facilitate the development of reliable out-of-distribution sample detectors, we present a less biased evaluation framework. Using our framework, we thoroughly evaluate over ten methods from data mining, deep learning, and Bayesian methods. We show that on real-world problems, none of the evaluated methods can reliably certify a prediction. Finally, we explore the applications of deep neural networks on high-resolution portrait production pipelines. We introduce AutoPortrait, a pipeline that performs professional-grade colour-correction, portrait cropping, and portrait retouching in under two seconds. We release the first large scale professional retouching dataset.

View record

This work considers optimization methods for large-scale machine learning (ML).Optimization in ML is a crucial ingredient in the training stage of ML models.Optimization methods in this setting need to have cheap iteration cost. First-ordermethods are known to have reasonably low iteration costs. A notable recent classof stochastic first-order methods leverage variance reduction techniques to improvetheir convergence speed. This group includes stochastic average gradient(SAG), stochastic variance reduced gradient (SVRG), and stochastic average gradientam´elior´e (SAGA). The SAG and SAGA approach to variance reduction useadditional memory in their algorithm. SVRG, on the other hand, does not needadditional memory but requires occasional full-gradient evaluation. We first introducevariants of SVRG that require fewer gradient evaluations. We then presentthe first linearly convergent stochastic gradient method to train conditional randomfields (CRFs) using SAG. Our method addresses the memory issues requiredfor SAG and proposes a better non-uniform sampling (NUS) technique. The thirdpart of this work extends the applicability of SAGA to Riemannian manifolds.We modify SAGA with operations existing in the manifold to improve the convergencespeed of SAGA in these new spaces. Finally, we consider the convergence ofclassic stochastic gradient methods, based on mirror descent (MD), in non-convexsetting. We analyse the MD with more general divergence function and show itsapplication for variational inference models.

View record

In 2012, deep learning made a major comeback. Deep learning started breaking records in many machine learning benchmarks, especially those in the field of computer vision. By integrating deep learning, machine learning methods have became more practical for many applications like object counting, detection, or segmentation. Unfortunately, in the typical supervised learning setting, deep learning methods might require a lot of labeled data that are costly to acquire. For instance, in the case of acquiring segmentation labels, the annotator has to label each pixel in order to draw a mask over each object and get the background regions. In fact, each image in the CityScapes dataset took around 1.5 hours to label. Further, to achieve high accuracy, we might need millions of such images. In this work, we propose four weakly supervised methods. They only require labels that are cheap to collect, yet they perform well in practice. We devised an experimental setup for each proposed method. In the first setup, the model needs to learn to count objects from point annotations. In the second setup, the model needs to learn to segment objects from point annotations. In the third setup, the model needs to segment objects from image level annotations. In the final setup, the model needs to learn to detect objects using counts only. For each of these setups the proposed method achieves state-of-the-art results in its respective benchmark. Interestingly, our methods are not much worse than fully supervised methods. This is despite their training labels being significantly cheaper to acquire than for the fully supervised case. In fact, in fixing the time budget for collecting annotations, our models performed much better than fully supervised methods. This suggests that carefully designed models can effectively learn from data labeled with low human effort.

View record

Recent years have witnessed huge advances in machine learning (ML) and its applications, especially in image, speech, and language applications. Optimization in ML is a key ingredient in both the training and hyperparameter tuning steps, and it also influences the test phase. In this thesis, we make improvements to optimization of all of these three problems. The first part of the thesis considers the training problem. We present the first linearly-convergent stochastic gradient method to train conditional random fields (CRFs) using the stochastic average gradient (SAG) method. Our method addresses the memory issues required for SAG and proposes a better non-uniform sampling (NUS) technique. The second part of the thesis deals with memory-free linearly-convergent stochastic gradient method for training ML models. We consider the stochastic variance reduced gradient (SVRG) algorithm, which normally requires occasional full-gradient evaluations. We show that we can decrease the number of gradient evaluations using growing batches (which improves performance in the early iterations) and support vectors (which improves performance in the later iterations). The third part of this thesis switches to the problem of hyper-parameter tuning. Although it is a lower dimensional problem, it can be more difficult as it is a non-convex global optimization problem. First, we propose a harmless global optimization algorithm to ensure that the performance is not worse than using random search. Moreover, we explore the use of gradient-based Bayesian optimization (BO) to improve the performance. We propose the use of directional derivatives to address the memory issues of BO. Finally, in the fourth part of this thesis, we propose a novel optimization method that combines the advantages of BO and Lipschitz optimization (LO).

View record

We study the problem of decision-making under uncertainty in the bandit setting. This thesis goes beyond the well-studied multi-armed bandit model to consider structured bandit settings and their applications. In particular, we learn to make better decisions by leveraging the application-specific problem-structure in the form of features or graph information. We investigate the use of structured bandits in two practical applications: online recommender systems with an available network of users and viral marketing in social networks. For each of these applications, we design efficient bandit algorithms and theoretically characterize their performance. We experimentally evaluate the efficiency and effectiveness of these algorithms on real-world datasets. For applications that require modelling complex non-linear feature-reward relationships, we propose a bootstrapping approach and establish theoretical regret bounds for it. Furthermore, we consider the application of multi-class classification with bandit feedback as a test-bed for evaluating our bootstrapping approach.

View record

This work looks at large-scale machine learning, with a particular focus on greedy methods. A recent trend caused by big datasets is to use optimization methods that have a cheap iteration cost. In this category are (block) coordinate descent and Kaczmarz methods, as the updates of these methods only rely on a reduced subspace of the problem at each iteration. Prior to our work, the literature cast greedy variations of these methods as computationally expensive with comparable convergence rates to randomized versions. In this dissertation, we show that greed is good. Specifically, we show that greedy coordinate descent and Kaczmarz methods have efficient implementations and can be faster than their randomized counterparts for certain common problem structures in machine learning. We show linear convergence for greedy (block) coordinate descent methods under a revived relaxation of strong convexity from 1963, which we call the Polyak-Lojasiewicz (PL) inequality. Of the proposed relaxations of strong convexity in the recent literature, we show that the PL inequality is the weakest condition that still ensures a global minimum. Further, we highlight the exploitable flexibility in block coordinate descent methods, not only in the different types of selection rules possible, but also in the types of updates we can use. We show that using second-order or exact updates with greedy block coordinate descent methods can lead to superlinear or finite convergence (respectively) for popular machine learning problems. Finally, we introduce the notion of “active-set complexity”, which we define as the number of iterations required before an algorithm is guaranteed to reach the optimal active manifold, and show explicit bounds for two common problem instances when using the proximal gradient or the proximal coordinate descent method.

View record