IFML Seminar: 11/5/24 - Online Convex Optimization with a Separation Oracle

Speaker Bio: Zak Mhammedi is a Research Scientist at Google Research, focusing on reinforcement learning and optimization. He completed his PhD in Computer Science at the Australian National University and previously held a postdoctoral position at MIT. Zak’s work bridges the gap between theoretical and practical machine learning, particularly in developing efficient optimization and reinforcement learning algorithms. He has presented at top conferences such as COLT, NeurIPS, and ICML, with several papers receiving oral and spotlight recognition. 

Abstract: This talk explores recent advancements in efficient online convex optimization, presenting a new class of projection-free algorithms designed for scalable online and stochastic optimization with convex constraints. Departing from traditional Frank-Wolfe-style algorithms, which depend on linear optimization oracles and can be computationally costly, these methods instead leverage membership and separation oracles. This shift enables the algorithms to achieve state-of-the-art regret bounds and convergence rates among projection-free methods while significantly improving computational efficiency compared to projection-based approaches like online gradient descent. Built on a simple reduction to optimization over a Euclidean ball, where projections are inexpensive, this modular approach provides a foundation for developing more efficient algorithms in diverse settings, advancing solutions for large-scale optimization problems.