Subhabrata Sen

ICML Conference 2025 Conference Paper

Provable Benefits of Unsupervised Pre-training and Transfer Learning via Single-Index Models

• Taj Jones-McCormick
• Aukosh Jagannath
• Subhabrata Sen

Unsupervised pre-training and transfer learning are commonly used techniques to initialize training algorithms for neural networks, particularly in settings with limited labeled data. In this paper, we study the effects of unsupervised pre-training and transfer learning on the sample complexity of high-dimensional supervised learning. Specifically, we consider the problem of training a single-layer neural network via online stochastic gradient descent. We establish that pre-training and transfer learning (under concept shift) reduce sample complexity by polynomial factors (in the dimension) under very general assumptions. We also uncover some surprising settings where pre-training grants exponential improvement over random initialization in terms of sample complexity.

JMLR Journal 2023 Journal Article

Contextual Stochastic Block Model: Sharp Thresholds and Contiguity

• Chen Lu
• Subhabrata Sen

We study community detection in the “contextual stochastic block model" (Yan and Sarkar (2020), Deshpande et al. (2018)). Deshpande et al. (2018) studied this problem in the setting of sparse graphs with high-dimensional node-covariates. Using the non-rigorous “cavity method" from statistical physics (Mezard and Montanari (2009)), they calculated the sharp limit for community detection in this setting, and verified that the limit matches the information theoretic threshold when the average degree of the observed graph is large. They conjectured that the limit should hold as soon as the average degree exceeds one. We establish this conjecture, and characterize the sharp threshold for detection and weak recovery. [abs] [ pdf ][ bib ] &copy JMLR 2023. ( edit, beta )

JMLR Journal 2022 Journal Article

Variational Inference in high-dimensional linear regression

• Sumit Mukherjee
• Subhabrata Sen

We study high-dimensional bayesian linear regression with product priors. Using the nascent theory of “non-linear large deviations" (Chatterjee and Dembo, 2016), we derive sufficient conditions for the leading-order correctness of the naive mean-field approximation to the log-normalizing constant of the posterior distribution. Subsequently, assuming a true linear model for the observed data, we derive a limiting infinite dimensional variational formula for the log normalizing constant for the posterior. Furthermore, we establish that under an additional “separation" condition, the variational problem has a unique optimizer, and this optimizer governs the probabilistic properties of the posterior distribution. We provide intuitive sufficient conditions for the validity of this “separation" condition. Finally, we illustrate our results on concrete examples with specific design matrices. [abs] [ pdf ][ bib ] &copy JMLR 2022. ( edit, beta )

SODA Conference 2019 Conference Paper

The threshold for SDP-refutation of random regular NAE-3SAT

• Yash Deshpande
• Andrea Montanari
• Ryan O'Donnell
• Tselil Schramm
• Subhabrata Sen

NeurIPS Conference 2018 Conference Paper

Contextual Stochastic Block Models

• Yash Deshpande
• Subhabrata Sen
• Andrea Montanari
• Elchanan Mossel

We provide the first information theoretical tight analysis for inference of latent community structure given a sparse graph along with high dimensional node covariates, correlated with the same latent communities. Our work bridges recent theoretical breakthroughs in detection of latent community structure without nodes covariates and a large body of empirical work using diverse heuristics for combining node covariates with graphs for inference. The tightness of our analysis implies in particular, the information theoretic necessity of combining the different sources of information. Our analysis holds for networks of large degrees as well as for a Gaussian version of the model.

STOC Conference 2016 Conference Paper

Semidefinite programs on sparse random graphs and their application to community detection

• Andrea Montanari
• Subhabrata Sen

Denote by A the adjacency matrix of an Erdos-Renyi graph with bounded average degree. We consider the problem of maximizing over the set of positive semidefinite matrices X with diagonal entries X_ii=1. We prove that for large (bounded) average degree d, the value of this semidefinite program (SDP) is --with high probability-- 2n*sqrt(d) + n, o(sqrt(d))+o(n). For a random regular graph of degree d, we prove that the SDP value is 2n*sqrt(d-1)+o(n), matching a spectral upper bound. Informally, Erdos-Renyi graphs appear to behave similarly to random regular graphs for semidefinite programming. We next consider the sparse, two-groups, symmetric community detection problem (also known as planted partition). We establish that SDP achieves the information-theoretically optimal detection threshold for large (bounded) degree. Namely, under this model, the vertex set is partitioned into subsets of size n/2, with edge probability a/n (within group) and b/n (across). We prove that SDP detects the partition with high probability provided (a-b)^2/(4d)> 1+o_d(1), with d= (a+b)/2. By comparison, the information theoretic threshold for detecting the hidden partition is (a-b)^2/(4d)> 1: SDP is nearly optimal for large bounded average degree. Our proof is based on tools from different research areas: (i) A new 'higher-rank' Grothendieck inequality for symmetric matrices; (ii) An interpolation method inspired from statistical physics; (iii) An analysis of the eigenvectors of deformed Gaussian random matrices.

NeurIPS Conference 2009 Conference Paper

Tracking Dynamic Sources of Malicious Activity at Internet Scale

• Shobha Venkataraman
• Avrim Blum
• Dawn Song
• Subhabrata Sen
• Oliver Spatscheck

We formulate and address the problem of discovering dynamic malicious regions on the Internet. We model this problem as one of adaptively pruning a known decision tree, but with additional challenges: (1) severe space requirements, since the underlying decision tree has over 4 billion leaves, and (2) a changing target function, since malicious activity on the Internet is dynamic. We present a novel algorithm that addresses this problem, by putting together a number of different ``experts algorithms and online paging algorithms. We prove guarantees on our algorithms performance as a function of the best possible pruning of a similar size, and our experiments show that our algorithm achieves high accuracy on large real-world data sets, with significant improvements over existing approaches.