Subspace optimization for machine learning
department or school: Science, Faculty of
department or school: Computer Science, Department of
data provider: DSpace
degree campus: UBCV
creator: Shea, Betty
issued: 2021-12-07T22:03:26Z
issued: 2021
related degree: Master of Science - MSc
degree grantor: University of British Columbia
description: Many machine learning (ML) problems are solved by iteratively optimizing an objective along a single descent direction. By restricting the search for the next iterate to one direction, per iteration cost is kept low. In many important problem classes, however, it is possible to perform subspace optimization (SO) and search along additional directions nearly "for free". This can lead to finding a better next iterate and result in fewer iterations to reach a solution. In theory and in practice, however, SO is rarely used and existing theory usually assumes an exact SO. In this thesis, we show experimentally that SO could lead to more accurate solutions in less time. We also explore the effect of different SO parameter settings. The experiments are performed through a software package we developed called minFuncLinear which is available for download. On the theory side, we propose a more abstract problem class, multilinear map problems, where SO could be performed efficiently. This encompasses linear composition models, known to allow efficient SO. We give further examples of problems that fall under this framework, such as log-determinant problems. We also provide preliminary convergence analysis of gradient descent (GD) combined with SO, discuss multi-dimensional Wolfe conditions and extend initialization and interpolation methods from linesearches to subspace searches.
aggregated CHO: https://circle.library.ubc.ca/rest/handle/2429/80393
note: Subspace Optimization for Machine LearningbyBetty SheaB. Sc., Carnegie Mellon University, 1999M. Sc., Carnegie Mellon University, 2007A 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)November 2021© Betty Shea, 2021The following individuals certify that they have read, and recommend to the Faculty of Graduateand Postdoctoral Studies for acceptance, the thesis entitled:Subspace Optimization for Machine Learningsubmitted by Betty Shea in partial fulfillment of the requirements for the degree of Master ofScience in Computer Science.Examining Committee:Mark Schmidt, Associate Professor, Computer Science, UBCSupervisorChen Greif, Professor, Computer Science, UBCSupervisory Committee MemberiiAbstractMany machine learning (ML) problems are solved by iteratively optimizing an objective along asingle descent direction. By restricting the search for the next iterate to one direction, per iterationcost is kept low. In many important problem classes, however, it is possible to perform subspaceoptimization (SO) and search along additional directions nearly “for free”. This can lead to findinga better next iterate and result in fewer iterations to reach a solution. In theory and in practice,however, SO is rarely used and existing theory usually assumes an exact SO. In this thesis, we showexperimentally that SO could lead to more accurate solutions in less time. We also explore the ef-fect of different SO parameter settings. The experiments are performed through a software packagewe developed called minFuncLinear which is available for download. On the theory side, wepropose a more abstract problem class, multilinear map problems, where SO could be performedefficiently. This encompasses linear composition models, known to allow efficient SO. We givefurther examples of problems that fall under this framework, such as log-deter…
has type: Thesis/Dissertation
date issued: 2022-05
is shown at: 10.14288/1.0404490
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: Schmidt, Mark
type: Text
identifier URI: http://hdl.handle.net/2429/80393