## ML-Opt: Romain Camilleri and Swati Padmanabhan

### June 4, 2021 @ 1:30 pm - 2:30 pm PDT

The final talks of the ML-OPT seminar of the spring quarter will be given **Friday (6/4)** at **1:30pm** **PST** by **Romain Camilleri** and **Swati Padmanabhan**.

**Title:** High-Dimensional Experimental Design and Kernel Bandits

**Abstract:** I will talk about high-dimensional bandits. First I want to review how the classical approach to solving linear bandits motivates an experimental design problem. Then I plan to justify why common rounding techniques cannot be applied in a potentially infinite-dimensional space. Lastly, I will show that one can avoid relying on rounding techniques by using a Catoni estimator.

**Bio:** Romain Camilleri is a 3rd year Ph.D. student at the Paul G. Allen School of Computer Science and Engineering at the University of Washington, where he is advised by Kevin Jamieson.

—————————————-

**Title:** Computing Lewis Weights to High Precision

**Abstract:** We present an algorithm for computing high-precision approximate L_p Lewis weights for p > 2. Given an m x n real full-rank matrix A and p>=3, our algorithm computes epsilon-approximate L_p-Lewis weights using O(p^3 \log (m p / epsilon)) iterations, where each iteration takes time linear in the sparsity of the input matrix plus the time to compute the leverage scores of a diagonal rescaling of A. Previously, such iteration complexities were known only for 0< p < 4 [CohenPeng2015]. Consequently, our result helps complete the picture on near-optimal reduction from leverage scores to L_p-Lewis weights for all p>0.

[Joint work with Maryam Fazel, Yin Tat Lee, and Aaron Sidford]

**Bio:** Swati is a graduate student working on problems in convex optimization, advised by Yin Tat Lee.