Understanding the role of averaging in non-smooth stochastic gradient descent
department or school: Science, Faculty of
department or school: Computer Science, Department of
data provider: DSpace
degree campus: UBCV
creator: Randhawa, Sikander
issued: 2020-08-24T15:01:31Z
issued: 2020
related degree: Master of Science - MSc
degree grantor: University of British Columbia
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.…
aggregated CHO: https://circle.library.ubc.ca/rest/handle/2429/75626
note: Understanding the role of averaging in non-smooth stochastic gradient descentbySikander RandhawaB. Sc, University of British Columbia, 2018A THESIS SUBMITTED IN PARTIAL FULFILLMENTOF THE REQUIREMENTS FOR THE DEGREE OFMaster of ScienceinTHE FACULTY OF GRADUATE AND POSTDOCTORAL STUDIES(Computer Science)The University of British Columbia(Vancouver)August 2020c© Sikander Randhawa, 2020The following individuals certify that they have read, and recommend to the Faculty of Graduate and Postdoc-toral Studies for acceptance, the thesis entitled:Understanding the role of averaging in non-smooth stochastic gradient descentsubmitted by Sikander Randhawa in partial fulfillment of the requirements for the degree of Master of Sciencein Computer Science.Examining Committee:Nicholas J. A. Harvey, Computer ScienceSupervisorBruce Shepherd, Computer ScienceSupervisory Committee MemberiiAbstractConsider the problem of minimizing functions that are Lipschitz and strongly convex, but not necessarily dif-ferentiable. We prove that after T steps of stochastic gradient descent (SGD), the error of the final iterate isO(log(T )/T ) with high probability. We also construct a function from this class for which the error of the finaliterate of deterministic gradient descent is Ω(log(T )/T ). This shows that the upper bound is tight and that, inthis 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 [42].We prove analogous results for functions which are Lipschitz and convex, but not necessarily strongly con-vex 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 gradientdescent is Ω(log(T )/√T ).In the strongly-convex setting, several forms of SGD, including suffix averaging, are known …
has type: Thesis/Dissertation
date issued: 2020-11
is shown at: 10.14288/1.0392916
language: eng
degree discipline: Computer Science
provider: Vancouver : University of British Columbia Library
publisher: University of British Columbia
rights: Attribution-NonCommercial-NoDerivatives 4.0 International
rights URI: http://creativecommons.org/licenses/by-nc-nd/4.0/
scholar level: Graduate
type: Text
identifier URI: http://hdl.handle.net/2429/75626