Back to search

University of British Columbia

Understanding the role of averaging in non-smooth stochastic gradient descent

Abstract

dc:description

Consider the problem of minimizing functions that are Lipschitz and strongly convex, but not necessarily differentiable. We prove that after T steps of stochastic gradient descent (SGD), the error of the final iterate is O(log⁡T⁄T) with high probability. We also construct a function from this class for which the error of the final iterate of deterministic gradient descent is Ω(log⁡T⁄T). This shows that the upper bound is tight and that, in this setting, the last iterate of stochastic gradient descent has the same general error rate (with high probability) as deterministic gradient descent. This resolves both open questions posed by Shamir (2012). We prove analogous results for functions which are Lipschitz and convex, but not necessarily strongly convex or differentiable. After T steps of stochastic gradient descent, the error of the final iterate is O(log⁡T⁄√T) with high probability, and there exists a function for which the error of the final iterate of deterministic gradient descent is Ω(log⁡T⁄√T). In the strongly-convex setting, several forms of SGD, including suffix averaging, are known to achieve the optimal O(1⁄T) convergence rate in expectation. An intermediate step of our high probability analysis for the error of the final iterate proves that the suffix averaging method achieves error O(1⁄T) with high probability, which is optimal (for any first-order optimization method). This improves results of Rakhlin et al. (2012) and Hazan and Kale (2014), both of which achieved error O(1⁄T), but only in expectation, and achieved a high probability error bound of O(log⁡log⁡T ⁄T), which is suboptimal. This is the first known high-probability result which attains the optimal O(1⁄T) rate. We also consider a simple, non-uniform averaging strategy of Lacoste-Julien et al. (2012) and prove that it too achieves the optimal O(1⁄T) convergence rate with high probability. This provides a second algorithm which achieves the optimal O(1⁄T) convergence rate with high-probability. Our high-probability results are proven using a generalization of Freedman's Inequality which we develop.

Degree

thesis:*
Name thesis:degree_name
Master of Science - MSc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
2020

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Randhawa, Sikander

Rights

dc:rights
Statement dc:rights
  • Attribution-NonCommercial-NoDerivatives 4.0 International
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/75626

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Randhawa, Sikander. Understanding the role of averaging in non-smooth stochastic gradient descent. master's thesis, University of British Columbia, 2020. http://hdl.handle.net/2429/75626