ACO Defense of Research Proposal of Jai Moondra, January 17, 2024

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:

Jai Moondra, ACO Ph.D. Student, School of Computer Science

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.