Back to search

University of Waterloo

Theory and Results on Restarting Schemes for Accelerated First Order Methods

Abstract

dc:description.abstract

Composite convex optimization problems are abundant in industry, and first order methods to solve them are growing in popularity as the size of variables reaches billions. Since the objective function could be possibly non-smooth, proximal gradient methods are one of the main tools for these problems. These methods benefit from acceleration, which uses the memory of past iterates to add momentum to the algorithms. Such methods have a O(1/k^2) convergence rate in terms of function value where k is the iteration number. Restarting algorithms has been seen to help speed up algorithms. O'Donoghue and Candes introduced adaptive restart strategies for accelerated first order methods which rely on easy to compute conditions, and indicate a large performance boost in terms of convergence. The restart works by resetting the momentum gained from acceleration. Their strategies in general are a heuristic, and there is no proof of convergence. In this thesis we show that restarting with the O'Donoghue and Candes condition improves the standard convergence rate in special cases. We consider the case of one-dimensional functions where we prove that the gradient based restart strategy from O'Donoghue and Candes improves the O(1/k^2) bound. We also study the restarting scheme applied to the method of alternating projections (MAP) for two closed, convex, and nonempty sets. It is shown in Chapter 6 that MAP falls into the convex composite paradigm and therefore acceleration can be applied. We study the case of MAP applied to two hyperplanes in arbitrary dimension. Furthermore we make observations as to why the restarts help, what makes a good restart condition, as well as what is needed to make progress in the general case.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2024

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Pavlovic, Viktor
Advisors dc:contributor.advisor
  • Vavasis, Stephen
  • Moursi, Walaa

Subjects

dc:subject × 4

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/10012/20979

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Pavlovic, Viktor. Theory and Results on Restarting Schemes for Accelerated First Order Methods. University of Waterloo, 2024. https://hdl.handle.net/10012/20979