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.