IDEAL Annual Meeting 2023

Logistics

• Date: Wednesday, June 7th, 2023
  
• Location: Simpson-Querrey Auditorium, Northwestern Simpson Querrey Biomedical Research Center (303 E Superior St, 1st floor)
• Registration: click here to register

Titles and Abstracts

Speaker: Reza Gheissari (Northwestern University)

Title: High-dimensional limit theorems for stochastic gradient descent

Abstract: Stochastic gradient descent (SGD) is the go-to method for large-scale optimization problems in modern data science. Often, these settings are data constrained, so the sample size and the dimension of the parameter space have to scale together. In this “high-dimensional” scaling, we study pathwise limits of the SGD. Namely, we show limit theorems for trajectories of reasonable summary statistics (finite-dimensional functions of the SGD) as the dimension goes to infinity and the step size simultaneously goes to zero. The limits that arise can be complicated ODE’s or SDE’s, depending on the initialization, step-size and space rescaling. We present these general results, and then discuss their implications for some concrete tasks including classification of XOR Gaussian mixtures via two layer networks. Based on joint work with Gerard Ben Arous and Aukosh Jagannath.

Speaker: Cong Ma (UChicago)

Title: Optimally tackling covariate shift in RKHS-based nonparametric regression

Abstract: We study the covariate shift problem in the context of nonparametric regression over a reproducing kernel Hilbert space (RKHS). We focus on two natural families of covariate shift problems defined using the likelihood ratios between the source and target distributions. When the likelihood ratios are uniformly bounded, we prove that the kernel ridge regression (KRR) estimator with a carefully chosen regularization parameter is minimax rate-optimal (up to a log factor) for a large family of RKHSs with regular kernel eigenvalues. Interestingly, KRR does not require full knowledge of the likelihood ratio apart from an upper bound on it. In striking contrast to the standard statistical setting without covariate shift, we also demonstrate that a naive estimator, which minimizes the empirical risk over the function class, is strictly suboptimal under covariate shift as compared to KRR. We then address the larger class of covariate shift problems where the likelihood ratio is possibly unbounded yet has a finite second moment. Here, we propose a reweighted KRR estimator that weights samples based on a careful truncation of the likelihood ratios. Again, we are able to show that this estimator is minimax optimal, up to logarithmic factors.

Speaker: Yuri Makarychev (TTIC)

Title: Higher-Order Cheeger Inequality for Partitioning with Buffers

Abstract: We prove a new generalization of the higher-order Cheeger inequality for partitioning with buffers. Consider a graph G. The buffered expansion of a set of vertices S with a buffer B is the edge expansion of S after removing all the edges from S to its buffer B. An ε-buffered k-partitioning of graph G is a partitioning of G into disjoint components P_1, …, P_k and buffers B_1, …, B_k in which the size of each buffer B_i is at most ε|P_i|. We prove that there exists an ε-buffered k-partitioning of G, in which the buffered expansion of each P_i with buffer B_i is at most O_𝛿((log k) / ε) λ_{k’}, where where λ_{k’} is the k’-th smallest eigenvalue of the normalized Laplacian of G and k’ = (1 + 𝛿) k.

Our inequality is constructive and avoids the “square-root loss” that is present in the standard Cheeger inequalities (even for k=2). We also provide a complementary lower bound, and a generalization to the setting with arbitrary vertex weights and edge costs. Moreover our result implies and generalizes the standard higher-order Cheeger inequalities and another recent Cheeger-type inequality by Kwok, Lau, and Lee (2017) involving robust vertex expansion.

Joint work with Konstantin Makarychev, Liren Shan, and Aravindan Vijayaraghavan

Poster List

All IDEAL-supported students and postdocs are expected to present a poster during the poster session. Others are welcome to present posters if we have the space. The poster should be able to fit on a 40in x 60in foam board. We will provide foam boards, stands and pins, but you must bring the poster!

Parking

Parking Garages Nearby:

Erie Ontario
321 East Erie Street

Huron Superior
222 East Huron Street