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?u...
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.
