Georgia Institute of Technology
Sparse and Low-rank Constrained Optimization: Formulations, Theory, and Algorithms
Abstract
dc:description.abstractSparsity and low rank are fundamental concepts in data reduction. Sparse and low-rank constrained optimization has benefited various application areas by effectively managing the rapid growth of big data, including machine learning, finance, cloud computing, and healthcare. Despite its versatility, sparse and low-rank constrained optimization is known to be NP-hard. This thesis aims to mitigate this challenge by developing novel formulations, theory, and algorithms. This thesis's first part focuses on two classic sparse constrained optimization problems within the domains of optimization and interpretable machine learning. Both problems involve selecting a fixed-size subset of matrix rows and/or columns to maximize metrics like entropy or accuracy, aiming to minimize the gap relative to their non-sparse counterparts. The submatrix selection problem can be naturally formulated as discrete optimization since whether to select each candidate element corresponds to a binary variable. This motivates us to explore discrete algorithms and methods. First, we derive equivalent mixed-integer convex programming formulations for both sparse constrained optimization problems, which pave the way for designing efficient branch-and-cut algorithms to achieve optimality. In addition, we develop scalable approximation algorithms, analyze their first-known theoretical guarantees, and provide their efficient implementations for approximately solving sparse constrained optimization problems. In the second part of this thesis, we propose a general low-rank optimization framework. We show that various problems in optimization and machine learning fall into our framework, including quadratically constrained quadratic program, fair machine learning, and recommendation systems. The low-rank constrained optimization is generally NP-hard and not even mixed-integer convex representable. Hence, we leverage partial convexification to obtain a tractable convex relaxation of low-rank constrained optimization. While partial convexification is often practical, its solution quality lacks theoretical guarantees. We fill this gap by developing a new theory in convex geometry, which offers a geometric perspective to analyze the performance of partial convexification. Specifically, (i) we establish the necessary and sufficient condition under which partial convexification matches the original low-rank constrained optimization, and (ii) we derive an upper bound on the minimum rank among all the optimal solutions of partial convexification and prove its tightness. To efficiently solve partial convexification, we develop a column generation algorithm combined with a rank-reduction algorithm. This combination ensures that the output solution satisfies the theoretical guarantees.
Degree
thesis:*- Level thesis:degree_level
- Doctoral
- Department dc:contributor.department
- Industrial and Systems Engineering
- Grantor dc:publisher
- Georgia Institute of Technology
- Year dc:date.issued
- 2024
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Li, Yongchun
- Advisor dc:contributor.advisor
-
- Xie, Weijun
- Committee members dc:contributor.committeemember
-
- Cifuentes, Diego
- Dey, Santanu
- Singh, Mohit
- Hildebrand, Robert
Subjects
dc:subject × 6Rights
- Language dc:language.iso
- en_US
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- https://hdl.handle.net/1853/75236