Title: Randomized Kernel Rounding Methods for Routing, Scheduling, and Machine Learning

Date: Wednesday, April 20, 2022

Time: 09:30am EST

Location: https://bluejeans.com/601031659 (online)

Majid Farhadi

Ph.D. Candidate

Algorithms, Combinatorics, and Optimization School of Computer Science Georgia Institute of Technology

Committee:

Dr. Swati Gupta, School of Industrial and Systems Engineering, Georgia Institute of Technology Dr. Renato D. C. Monteiro, School of Industrial and Systems Engineering, Georgia Institute of Technology Dr. Mohit Singh, School of Industrial and Systems Engineering, Georgia Institute of Technology Dr. Santosh Vempala, College of Computing, Georgia Institute of Technology

Advisor: Dr. Prasad Tetali, Department of Mathematical Sciences, Carnegie Mellon University

Reader: Dr. Swati Gupta, School of Industrial and Systems Engineering, Georgia Institute of Technology

Thesis will be available at:

https://drive.google.com/file/d/11e6s2-KEYVaNtrLa1hL4GUyEsm20XQQ5/view?usp=sharing

Summary:

 From Computer Science, Machine Learning, Communications, and Control Systems to Supply Chain, Finance, and Policy Making we make a sequence of choices, optimality of which can be decisive to maximize revenue or critical to ensure robustness, security, and reliability. In numerous cases, solving the exact problem is not feasible, e.g., due to limited computational and storage resources, missing key data, or intrinsic hardness barriers. Therefore, researchers develop algorithms to guarantee solutions that are approximately correct/optimal.

We study classical problems from combinatorial optimization and machine learning and develop near optimal approximation algorithms and computational complexity results. We introduce new randomized techniques, notably the kernel alpha-point rounding, for efficiently converting solutions of tractable convex/linear relaxations of these problems. The problems under study have immediate applications in machine learning, Ads/search systems, routing, scheduling, non-convex optimization, mathematical programming, Markov chains, and non-linear dimension reduction; to name but a few. We employ techniques from convex optimization, machine learning, linear algebra, graph theory, high dimensional geometry, combinatorics, and probability theory; and further contribute to such theories, e.g., by providing a new inequality on the lower tail of a sum of Bernoulli random variables.