Back to search

Boston University

Formal guarantees for heuristic optimization algorithms used in machine learning

Abstract

dc:description.abstract

Recently, Stochastic Gradient Descent (SGD) and its variants have become the dominant methods in the large-scale optimization of machine learning problems. A variety of strategies have been proposed for tuning the step sizes, ranging from adaptive step sizes (e.g., AdaGrad) to heuristic methods to change the step size in each iteration. Also, momentum has been widely employed in machine learning tasks to accelerate the training process. Yet, there is a gap in our theoretical understanding of them. In this work, we start to close this gap by providing formal guarantees to a few heuristic optimization methods and proposing improved algorithms if the theoretical results are suboptimal. First, we analyze a generalized version of the AdaGrad (Delayed AdaGrad) step sizes in both convex and non-convex settings, showing that these step sizes allow the algorithms to automatically adapt to the level of noise of the stochastic gradients. We show sufficient conditions for Delayed AdaGrad to achieve almost sure convergence of the gradients to zero, which is the first guarantee for Delayed AdaGrad in the non-convex setting. Moreover, we present a high probability analysis for Delayed AdaGrad and its momentum variant in the non-convex setting. Second, we present an analysis of SGD with exponential and cosine step sizes, which are simple-to-use, empirically successful but lack of theoretical support. We provide the very first convergence guarantees for them in the smooth and non-convex setting, with and without the Polyak-Łojasiewicz (PL) condition. We show that these two strategies also have the good property of adaptivity to noise under PL condition. Third, we study the last iterate of momentum methods. We prove the first lower bound in the general convex setting for the last iterate of SGD with constant momentum. Based on the fact that the lower bound is suboptimal, we investigate a class of (both adaptive and non-adaptive) Follow-The-Regularized-Leader-based momentum algorithms (FTRL-based SGDM) with increasing momentum and shrinking updates. We show that their last iterate has optimal convergence for unconstrained convex stochastic optimization problems without projections onto bounded domains nor knowledge of the number of iterations.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy
Level thesis:degree_level
doctoral
Discipline thesis:degree_discipline
Systems Engineering
Grantor
Boston University
Year dc:date.issued
2022

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Li, Xiaoyu
Advisor dc:contributor.advisor
  • Orabona, Francesco
ORCID dc:identifier.orcid

Subjects

dc:subject × 1

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/2144/45053

Chain of custody

source
Harvested from
Boston University
Base URL
open.bu.edu/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Li, Xiaoyu. Formal guarantees for heuristic optimization algorithms used in machine learning. doctoral thesis, Boston University, 2022. https://hdl.handle.net/2144/45053