Online optimization for machine learning: parallelism, adaptivity, and model selection

• Author / Creator

  Joulani, Pooria

• We study three problems in the application, design, and analysis of online optimization algorithms for machine learning.
  First, we consider speeding-up the common task of k-fold cross-validation of online algorithms, and provide TreeCV, an algorithm that reduces the time penalty of k-fold cross-validation from k to log(k), and is easily adoptable to parallel and distributed computing environments.
  Second, we consider algorithms for online delayed-feedback distributed optimization, and provide SOLID, a meta-algorithm for deriving delay-tolerant versions of standard online optimization algorithms and their analysis. We further apply SOLID to obtain algorithms that adapt to the delay pattern observed during optimization, solving an open problem from the literature. Third, we study asynchronous online and stochastic optimization. We start by providing a unifying analysis of standard serial online optimization algorithms. Then, we build on this analysis to design and analyze two new asynchronous online optimization algorithms. The first algorithm, AsynCADA, features the ability to handle generic convex constraints, proximal updates and adaptive step-sizes. The second algorithm, HedgeHog, is the first asynchronous variant of the Hedge algorithm. Both algorithms enjoy linear speed-up if the data is sufficiently sparse, extending the scope of problem settings and algorithmic techniques adoptable to asynchronous optimization. Underlying the analysis of AsynCADA and HedgeHog is a generic framework for studying online optimization algorithms with perturbed state, which is of independent interest.

• Subjects / Keywords

  • Cross-Validation
  • Delay-Tolerant Optimization
  • Asynchronous Optimization
  • Stochastic Optimization
  • Adaptive Optimization
  • Online Learning

• Graduation date

  Fall 2019

• Type of Item

  Thesis

• Degree

  Doctor of Philosophy

• DOI

  https://doi.org/10.7939/r3-bfqk-1193

• License

  Permission is hereby granted to the University of Alberta Libraries to reproduce single copies of this thesis and to lend or sell such copies for private, scholarly or scientific research purposes only. Where the thesis is converted to, or otherwise made available in digital form, the University of Alberta will advise potential users of the thesis of these terms. The author reserves all other publication and other rights in association with the copyright in the thesis and, except as herein before provided, neither the thesis nor any substantial portion thereof may be printed or otherwise reproduced in any material form whatsoever without the author's prior written permission.