ACO Defense of Research Proposal of Jai Moondra, January 17, 2024
Title: New Directions in Multi-objective Optimization with Applications
Date: Wednesday, January 17, 2024
Time: 10:00 to 11:30 AM
Location (hybrid): Klaus 2108; Zoom link: https://gatech.zoom.us/j/93859090283
Jai Moondra, ACO Ph.D. Student, School of Computer Science
Committee:
Dr. Swati Gupta (advisor) | Sloan School of Management, Massachusetts Institute of Technology
Dr. Mohit Singh (advisor) | H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology
Dr. Sahil Singla | School of Computer Science, Georgia Institute of Technology
Dr. Santosh Vempala | School of Computer Science, Georgia Institute of Technology
Abstract: Multi-objective optimization is the study of optimizing more than one objective function on a fixed domain set. Competing objectives often arise from fairness considerations in optimization problems with direct social impact – such as facility location and machine learning model training – where traditional objectives can be unfair to certain individuals or groups.
We study the notion of solution portfolio that generalizes the classical notion of simultaneous approximations. Given a domain and a class of objectives over the domain, a portfolio is a subset of the domain such that for each objective, its optimal value in the subset is within a given multiplicative factor of its optimum value in the domain. A portfolio of size one is a simultaneous approximation, and larger portfolios have stronger approximation factor guarantees. We study this trade-off between size and approximation factor for various combinatorial domains and different classes of objectives. We improve previous results on simultaneous approximations and develop new techniques and results for portfolios of size more than one. I will discuss extensions of portfolios to other settings including stochastic combinatorial optimization and potential applications in machine learning. I will also discuss a multi-objective view of online learning problems and the trade-off between the dual objectives of regret and runtime, including an application to recommendation systems using submodular base polytopes.
