High-dimensional least square problems: First order stochastic algorithms

As learning models become ever complex (as shown in Figure 1.1), the importance of efficient optimization algorithms for training these models becomes ever more apparent (illustrated by Figure 1.2).A popular class of these algorithms are the mini-batch gradientbased methods (see Definition 2) which includes stochastic gradient descent [50], Nesterov acceleration [40], and Polyak momentum [49].Despite the popularity and practicality of these algorithms, the theoretical understanding of these algorithms are limited even in the simplest of cases.This thesis aims to bridge the gap between empirical observations and our theoretical understanding of the behaviour of mini-batch gradient-based methods under the setting of quadratic models (See Assumption 6)To motivate further analysis of these algorithms, we re-examine the conventional worstcase complexity bounds of gradient-based methods.In short, these bounds only consider the maximum and minimum eigenvalues of the problem, and fail to capture typical runtime behaviour [48].To overcome this limitation, we adopt a physics-inspired approach from random matrix theory that leverages the universality phenomenon.By placing a distribution on the data, we show that we can incorporate information from the eigenspectrum of the Hessian of the quadratic problem to provide a sharper and more robust analysis.In the high-dimensional setting, we demonstrate through concentration of measure results that the two source of randomness -the sampling mechanism of the algorithm and the data distribution -averages out.Furthermore, we illustrate the deep connection between polynomials and mini-batch gradient-based algorithms -that is, we can write i iterates of the algorithm as a sum of polynomials that depends on the eigenspectrum of AA T for a given design matrix A. These results allow us to state the main theorem of this thesis: Under general quadratic functions, the dynamics of every mini-batch gradientbased algorithm can be exactly captured by a deterministic equation which solves a discrete Volterra equation.In turn, exact dynamics allows us to quantify the behaviour of interesting quadratic statistical models, including training and generalization errors as well as the random features model [6,37].Moreover, we are able to study in order to analyze properties of the celebrated Polyak momentum algorithm under the least-squares setting.Our analysis provides sufficient conditions for convergence, the relationship between convergence rate and batch-size for fixed hyperparmeters, and limiting behaviours.have been instrumental in revealing my passion for mathematical research and imparting the knowledge that I have gained thus far.Courtney and Elliot, thank you for always being available to meet, for patiently answering my questions, encouraging my natural voice in mathematics, and setting an excellent example as mentors and role models in the research community.Needless to say, it is impossible to show my full appreciation to my supervisors in an acknowledgment section.Also, I would like to express my thanks to my undergraduate supervisors Russell Steele and Archer Yang.They exposed me to statistical research which eventually led me to pursuing research in machine learning.More importantly, they have provided continual support and

Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.