[Theory Lunch 04/23] Tyler LaBonte: The Distance Oracle for Convex Optimization

[Haoming Li]

USC CS Theory Lunch:

The Distance Oracle for Convex Optimization

Speaker: Tyler LaBonte (USC)
Time: 04/23/21 11:45am PST
Location: https://usc.zoom.us/j/94386654763

Abstract:

Convex optimization and linear programming are fundamental, powerful techniques in mathematical optimization. Under certain conditions, including the presence of a separation oracle for the feasible region, the Ellipsoid Method is a polynomial-time algorithm for solving convex optimization problems. Decades of work on cutting-plane methods have resulted in Ellipsoid-like algorithms which achieve optimal oracle complexity in this setting. However, obtaining an efficient separation oracle is not always possible or natural. Recent work has studied membership, approximation, index, and quantum oracles as alternatives to separation. While each is theoretically insightful, only quantum oracles have improved upon the oracle complexity of cutting-plane methods.

We propose a classical alternative oracle, the distance oracle, which returns the minimum Euclidean distance from the query point to the feasible region. We present progress on an algorithm for solving the linear feasibility problem with a distance oracle in O(n log(n)) queries, a logarithmic improvement in oracle complexity over the best separation oracle-based method. For problems where distance oracles are natural, such as interactive learning, this enables an efficient algorithm for optimization.

Bio:

Tyler LaBonte is a graduating senior at the University of Southern California with a B.S. in Applied and Computational Mathematics, where he was fortunate to be advised by Shaddin Dughmi, Jason D. Lee, and David Kempe. He will be attending the Georgia Institute of Technology for his Ph.D. in Machine Learning, where he will be advised by Tuo Zhao. He is the recipient of the DoD National Defense Science and Engineering Graduate Fellowship, the NSF Graduate Research Fellowship, and the USC Trustee Scholarship.