Speaker: Leonidas Tsepenekas
Affiliation: University of Maryland

Title: Approximating Two-Stage Stochastic Supplier Problems

Abstract:
The main focus of this talk will be radius-based (supplier) clustering in the two-stage stochastic setting with recourse, where the inherent stochasticity of the model comes in the form of a budget constraint. Our eventual goal is to provide results in the most general distributional setting, where there is only black-box access to the underlying distribution. To that end, we follow a two-step approach. First, we develop algorithms for a restricted version of the problem, in which all possible scenarios are explicitly provided; second, we employ a novel scenario-discarding variant of the standard Sample Average Approximation (SAA) method, in which we also crucially exploit structural properties of the algorithms developed for the first step of the framework. In this way, we manage to generalize the results of the latter to the black-box model. Finally, we note that the scenario-discarding modification to the SAA method is necessary in order to optimize over the radius.

Paper: https://arxiv.org/abs/2008.03325

Speaker: Samson Zhou
Affiliation: Carnegie Mellon University

Title: Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators

Abstract:
We introduce difference estimators for data stream computation, which provide approximations to F(v)-F(u) for frequency vectors v,u and a given function F. We show how to use such estimators to carefully trade error for memory in an iterative manner. The function F is generally non-linear, and we give the first difference estimators for the frequency moments F_p for p between 0 and 2, as well as for integers p>2. Using these, we resolve a number of central open questions in adversarial robust streaming and sliding window models.

For both models, we obtain algorithms for norm estimation whose dependence on epsilon is 1/epsilon^2, which shows, up to logarithmic factors, that there is no overhead over the standard insertion-only data stream model for these problems.

Speaker: Zeyu Guo
Affiliation: Ohio State University

Title: TBD

Abstract: TBD

Speaker: Yuzhou Gu

Affiliation:NYU Center for Data Science & Courant Institute

Title: Community detection in the hypergraph stochastic block model

Abstract:

Community detection is a fundamental problem in network
science, and its theoretical study has received significant attention
over the last decade. In this talk I will present some recent advances
on the community detection problem in sparse hypergraphs. In
particular, we determine the weak recovery threshold for the
hypergraph stochastic block model for a wide range of parameters. This
resolves conjectures made by physicists in the corresponding regimes
and has implications to phase transitions of random constraint
satisfaction problems. A key component in this study is to analyze the
behavior of information channels under repeated applications of the
belief propagation operator. We introduce a framework for performing
this analysis based on information-theoretical methods for channel
comparison. Along the way, we formulate a rigorous version of the
population dynamics algorithm, an approach commonly used in practice
but lacks theoretical guarantees.