Final ACO Doctoral Examination and Defense of Dissertation
Title: Subset Selection via Spectral Objectives
Adam Brown
ACO PhD student, School of Mathematics
Date: April 11th, 2025
Time: 10am
Location: Groseclose 403
Zoom link: https://gatech.zoom.us/j/94359859040?pwd=xEBQ1Ak6WHvDkRlV0b4vaijBxcK9dO.1
Advisor: Dr. Mohit Singh, School of Industrial and Systems Engineering, Georgia Institute of Technology
Committee:
Dr. Mohit Singh, School of Industrial and Systems Engineering, Georgia Institute of Technology (advisor)
Dr. Greg Blekherman, School of Mathematics, Georgia Institute of Technology
Dr. Santanu Dey, School of Industrial and Systems Engineering, Georgia Institute of Technology
Dr. Lap Chi Lau, School of Computer Science, University of Waterloo
Dr. Sahil Singla, School of Computer Science, Georgia Institute of Technology
Reader:
Dr. Lap Chi Lau, School of Computer Science, University of Waterloo
Link to thesis draft:
https://drive.google.com/file/d/147HZ_htlygASZlOcJ5qKb_jHyZA3yoHr/view?u...
Abstract:
Selecting a small subset of items that captures key properties of a much larger data set is an important problem in a variety of areas, including machine learning, network design, and fair allocation of goods. We use a geometric model for this problem where the items (or their qualities) are represented by d-dimensional vectors. That is, given a large set E, where each element is represented by a real vector, select a small subset S of E with good properties.
There are many different possible goals for subset selection problems, and we will focus on objectives obtained by summing the rank-1 matrices formed by the vectors in S, and considering some function of the eigenvalues of the resulting matrix. For example, we may consider the determinant, trace, or minimum eigenvalue. While we could simply limit the number of selected items, we can also have more elaborate constraints. We may instead restrict our attention to subsets S that are bases of a specific matroid. This will allow us to model a much broader class of problems.
This work focuses on four problems which can be modeled in the spectral subset selection framework. The first, is determinant maximization under matroid constraints. For this problem, in the case that we number of vectors we are selecting is exactly d, we provide a combinatorial O(d^d)-approximation algorithm based on matroid intersection. Next, we consider the special case of the weighted Nash Social Welfare problem. This problem has its own specially-tailored relaxations, which we use to construct a new approximation algorithm. Then, we turn to the minimum eigenvalue problem with general matroid constraints. By modifying the natural convex program, and randomly rounding the optimal solution, we are able to find (1-epsilon)-approximate solution in polynomial time, when the dimension of the vectors is constant. Finally, we turn to a practical problem in electrical network design called the network reconfiguration problem. After analyzing various convex relaxations for the problem we propose a collection of potential upper and lower bound algorithms, and compare them practically.
