Dissertation
First-order methods for constrained optimization with new iteration complexity and applications in machine learning
University of Iowa
Doctor of Philosophy (PhD), University of Iowa
Summer 2021
DOI: 10.17077/etd.005823
Abstract
In recent years, there has been a surge of interest in the topic of machine learning with a large collection of statistical models being developed and analyzed. There has also been substantial research on optimization algorithms applied to machine learning problems. Despite the existence of data-driven constraints in many statistical models, such as Neyman-Pearson classification and constrained lasso, the focus of most new developments on optimization for machine learning has been either on unconstrained problems or simply constrained problems in which the projection mapping onto the feasible set has a closed-form solution. This thesis seeks to fill in the gap by studying first-order methods for optimization problems with data-driven nonlinear constraints. A number of first-order algorithms are proposed, and the corresponding computational complexity results are established. In this thesis, we investigate provable first-order methods for optimization problems with functional constraints under different assumptions. The level-set method, presented in Chapter 2, is used to solve a convex constrained optimization where the objective function and the constraints are defined as summation of finitely many loss functions. We propose a new variant of the feasible level-set method, which can generate a feasible solution path. To construct an efficient oracle used in the level-set method, a novel saddle-point reformulation of the level-set function using convex conjugate and perspective of the loss functions is analyzed. In Chapter 3, we examine a class of convex constrained optimization problems where an error bound condition holds. Different from the existing works where growth parameters in the error bound condition are either known or estimated in advance, our methods do not require knowing those growth parameters and any other problem-dependent parameters. In Chapter 4, we investigate the non-convex non-smooth constrained optimization where the objective function and the constraint functions are weakly convex. Quadratically regularized subgradient methods are proposed. The computational complexity of our methods for finding a nearly stationary point is established under a uniform Slater’s condition. In Chapter 5, we propose inexact proximal-point penalty methods for solving smooth constrained optimization where the objective function is non-convex, and the constraint functions can also be either convex or non-convex. The uniform Slater’s condition assumption discussed in Chapter 4 is relaxed and the computational complexity of the proposed method for finding an ε-stationary point is established.
Details
- Title: Subtitle
- First-order methods for constrained optimization with new iteration complexity and applications in machine learning
- Creators
- Runchao Ma
- Contributors
- Qihang Lin (Advisor)Kurt Anstreicher (Committee Member)Samuel Burer (Committee Member)Weiyu Xu (Committee Member)Tianbao Yang (Committee Member)
- Resource Type
- Dissertation
- Degree Awarded
- Doctor of Philosophy (PhD), University of Iowa
- Degree in
- Business Administration
- Date degree season
- Summer 2021
- DOI
- 10.17077/etd.005823
- Publisher
- University of Iowa
- Number of pages
- xi, 191 pages
- Copyright
- Copyright 2021 Runchao Ma
- Language
- English
- Description illustrations
- color illustrations
- Description bibliographic
- Includes bibliographical references (pages 176-191).
- Public Abstract (ETD)
In recent years, there has been a surge of interest in the topic of machine learning with a large collection of statistical models being developed and analyzed. There has also been substantial research on optimization algorithms applied to machine learning problems. Despite the existence of data-driven constraints in many statistical models, such as Neyman-Pearson classification and constrained lasso, the focus of most new developments on optimization for machine learning has been either on unconstrained problems or simply constrained problems in which the projection mapping onto the feasible set has a closed-form solution. This thesis seeks to fill in the gap by studying first-order methods for optimization problems with data-driven nonlinear constraints. A number of first-order algorithms are proposed for constrained optimization, and the corresponding computational complexity results are established.
- Academic Unit
- Tippie College of Business
- Record Identifier
- 9984124172302771
Metrics
90 File views/ downloads
259 Record Views