The hypergraph community detection problem asks us to find groups of related or similar entities in hypergraph data. While there are many approaches to this problem, this talk will focus on a spectral method that utilizes information from the eigenvectors of the nonbacktracking or Hashimoto matrix. The Hashimoto operator can be shown to be related to belief-propagation for statistical inference, and using this relationship we obtain a performant hypergraph community detection algorithm with well-understood regions of success and failure for the hypergraph stochastic block model. The talk will additionally pose some conjectures on the fundamental limits of community detection in hypergraphs.

Compressed sensing has been a very successful high-dimensional signal acquisition and recovery technique that relies on linear operations. However, the actual measurements of signals have to be quantized before storing or processing. 1(One)-bit compressed sensing is a heavily quantized version of compressed sensing, where each linear measurement of a signal is reduced to just one bit: the sign of the measurement. Once enough of such measurements are collected, the recovery problem in 1-bit compressed sensing aims to find the original signal with as much accuracy as possible. 

For recovery of sparse vectors, a popular reconstruction method from 1-bit measurements is the binary iterative hard thresholding (BIHT) algorithm. The algorithm is a simple projected sub-gradient descent method, and is known to converge well empirically, despite the nonconvexity of the problem. The convergence property of BIHT was not theoretically justified, except with an exorbitantly large number of measurements (i.e., a number of measurement greater than max{k^10,24^48,k^3.5/ϵ}, where k is the sparsity, ϵ denotes the approximation error, and even this expression hides other factors). In this paper we show that the BIHT algorithm converges with only Õ(k/ϵ) measurements. Note that, this dependence on k and ϵ is optimal for any recovery method in 1-bit compressed sensing. With this result, to the best of our knowledge, BIHT is the only practical and efficient (polynomial time) algorithm that requires the optimal number of measurements in all parameters (both k and ϵ). This is also an example of a gradient descent algorithm converging to the correct solution for a nonconvex problem, under suitable structural conditions.

Joint work with Nami Matsumoto.

The Hypergraph Stochastic Block Model (HSBM) is a complex, many-parameter model generalizing the well-known graph SBM--a paradigm for studying community detection. One of the main uses of the (H)SBM is that it allows us to develop guarantees for community detection algorithms by providing thresholds---parameter conditions that theoretically describe the necessary and sufficient requirements for community detection in the model. These thresholds naturally depend on the type of recovery desired.

I will talk about the most general conditions and thresholds we can develop, under various tweaks in the model, for almost exact and exact recovery in more, or less, general HSBM. This is joint work with Haixiao Wang and Yizhe Zhu. 

Stein's method for distributional approximation has become a valuable tool in probability and statistics by providing finite sample distributional bounds for a wide class of target distributions in a number of metrics. A key step in popular versions of the method involves making couplings constructions, and a family of couplings of Chen and Roellin vastly expanded the range of applications for which Stein's method for normal approximation could be applied. This family subsumes both Stein's classical exchangeable pair, and the size bias coupling. A further simple generalization includes zero bias couplings, and also allows for situations where the coupling is not exact. The zero bias versions result in bounds for which often tedious computations of a variance of a conditional expectation is not required. An example to the Lightbulb process shows that even though the method may be simple to apply, it may yield improvements over previous results that had achieved bounds with optimal rates and small, explicit constants.