First-order methods for structured optimization
department or school: Science, Faculty of
department or school: Computer Science, Department of
data provider: DSpace
degree campus: UBCV
creator: Fang, Huang
issued: 2021-10-20T19:01:02Z
issued: 2021
related degree: Doctor of Philosophy - PhD
degree grantor: University of British Columbia
description: First-order methods are gaining substantial interest in the past two decades because of their superior performance in solving today's large-scale problems. In this thesis, we study some widely used first-order methods for problems that satisfy certain structures. Specifically, in the first part, we contribute to coordinate optimization and show that greedy coordinate descent (GCD) has an implicit screening ability that usually selects coordinates that are nonzero at the solution, which explains why GCD works exceptionally well for problems that admit sparse solutions. We also extend the elegant safe-screening rule that depends on duality gap to atomic-norm regularized problems. In the second part, we study online mirror descent (OMD) with unknown time horizon and unbounded domain, which is known to suffer from linear regret. We provide a stabilization technique and show that the stabilized-OMD can achieve sublinear regret. We also build the connection between stabilized-OMD and dual averaging. In the third part, we derive improved iteration complexity of the stochastic subgradient method for over-parameterized models that satisfy an interpolation condition. The obtained iteration complexity matches the rate of the stochastic gradient method applied to smooth problems that also satisfy an interpolation condition. Our analysis partially explains the empirical observation that nonsmoothness in modern machine learning models sometimes does not slow down the training process.
aggregated CHO: https://circle.library.ubc.ca/rest/handle/2429/80005
note: First-order methods for structured optimizationbyHuang FangB.Sc, The Central University of Finance and Economics, China, 2011M.Sc, The University of California, Davis, US, 2015A THESIS SUBMITTED IN PARTIAL FULFILLMENTOF THE REQUIREMENTS FOR THE DEGREE OFDoctor of PhilosophyinTHE FACULTY OF GRADUATE AND POSTDOCTORALSTUDIES(Computer Science)The University of British Columbia(Vancouver)October 2021© Huang Fang, 2021The following individuals certify that they have read, and recommend to the Facultyof Graduate and Postdoctoral Studies for acceptance, the thesis entitled:First-order methods for structured optimizationsubmitted by Huang Fang in partial fulfillment of the requirements for the degreeof Doctor of Philosophy in Computer Science.Examining Committee:Michael P. Friedlander, Computer ScienceSupervisorNicolas J.A. Harvey, Computer ScienceSupervisory Committee MemberMark Schmidt, Computer ScienceSupervisory Committee MemberBrian Wetton, MathematicsUniversity ExaminerBruce Shepherd, Computer ScienceUniversity ExaminerChih-Jen Lin, Computer Science, National Taiwan UniversityExternal ExamineriiAbstractFirst-order methods are gaining substantial interest in the past two decades becauseof their superior performance in solving today’s large-scale problems. In this thesis,we study some widely used first-order methods for problems that satisfy certainstructures. Specifically, in the first part, we contribute to coordinate optimizationand show that greedy coordinate descent (GCD) has an implicit screening abilitythat usually selects coordinates that are nonzero at the solution, which explainswhy GCD works exceptionally well for problems that admit sparse solutions. Wealso extend the elegant safe-screening rule that depends on duality gap to atomic-norm regularized problems. In the second part, we study online mirror descent(OMD) with unknown time horizon and unbounded domain, which is known tosuffer from linear regret. We provide a stabilization technique and show that thes…
has type: Thesis/Dissertation
date issued: 2021-11
is shown at: 10.14288/1.0402562
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
contributor: Friedlander, Michael P.
type: Text
identifier URI: http://hdl.handle.net/2429/80005