Author name cluster

Ioana Dumitriu

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers

2 author rows

ICLR Conference 2024 Conference Paper

Faithful and Efficient Explanations for Neural Networks via Neural Tangent Kernel Surrogate Models

Andrew Engel
Zhichao Wang
Natalie Frank
Ioana Dumitriu
Sutanay Choudhury
Anand D. Sarwate
Tony Chiang

A recent trend in explainable AI research has focused on surrogate modeling, where neural networks are approximated as simpler ML algorithms such as kernel machines. A second trend has been to utilize kernel functions in various explain-by-example or data attribution tasks. In this work, we combine these two trends to analyze approximate empirical neural tangent kernels (eNTK) for data attribution. Approximation is critical for eNTK analysis due to the high computational cost to compute the eNTK. We define new approximate eNTK and perform novel analysis on how well the resulting kernel machine surrogate models correlate with the underlying neural network. We introduce two new random projection variants of approximate eNTK which allow users to tune the time and memory complexity of their calculation. We conclude that kernel machines using approximate neural tangent kernel as the kernel function are effective surrogate models, with the introduced trace NTK the most consistent performer.

Details

NeurIPS Conference 2023 Conference Paper

Spectral Evolution and Invariance in Linear-width Neural Networks

Zhichao Wang
Andrew Engel
Anand D Sarwate
Ioana Dumitriu
Tony Chiang

We investigate the spectral properties of linear-width feed-forward neural networks, where the sample size is asymptotically proportional to network width. Empirically, we show that the spectra of weight in this high dimensional regime are invariant when trained by gradient descent for small constant learning rates; we provide a theoretical justification for this observation and prove the invariance of the bulk spectra for both conjugate and neural tangent kernels. We demonstrate similar characteristics when training with stochastic gradient descent with small learning rates. When the learning rate is large, we exhibit the emergence of an outlier whose corresponding eigenvector is aligned with the training data structure. We also show that after adaptive gradient training, where a lower test error and feature learning emerge, both weight and kernel matrices exhibit heavy tail behavior. Simple examples are provided to explain when heavy tails can have better generalizations. We exhibit different spectral properties such as invariant bulk, spike, and heavy-tailed distribution from a two-layer neural network using different training strategies, and then correlate them to the feature learning. Analogous phenomena also appear when we train conventional neural networks with real-world data. We conclude that monitoring the evolution of the spectra during training is an essential step toward understanding the training dynamics and feature learning.

PDF Details

NeurIPS Conference 2016 Conference Paper

Exploiting Tradeoffs for Exact Recovery in Heterogeneous Stochastic Block Models

Amin Jalali
Qiyang Han
Ioana Dumitriu
Maryam Fazel

The Stochastic Block Model (SBM) is a widely used random graph model for networks with communities. Despite the recent burst of interest in community detection under the SBM from statistical and computational points of view, there are still gaps in understanding the fundamental limits of recovery. In this paper, we consider the SBM in its full generality, where there is no restriction on the number and sizes of communities or how they grow with the number of nodes, as well as on the connectivity probabilities inside or across communities. For such stochastic block models, we provide guarantees for exact recovery via a semidefinite program as well as upper and lower bounds on SBM parameters for exact recoverability. Our results exploit the tradeoffs among the various parameters of heterogenous SBM and provide recovery guarantees for many new interesting SBM configurations.

PDF Details

SODA Conference 2016 Conference Paper

Recovery and Rigidity in a Regular Stochastic Block Model

Gerandy Brito
Ioana Dumitriu
Shirshendu Ganguly
Christopher Hoffman
Linh V. Tran

The stochastic block model is a natural model for studying community detection in random networks. Its clustering properties have been extensively studied in the statistics, physics and computer science literature. Recently this area has experienced major mathematical breakthroughs, particularly for the binary (two-community) version, see [24, 25, 20]. In this paper, we introduce a variant of the binary model which we call the regular stochastic block model (RSBM). We prove rigidity of this model by showing that with high probability an exact recovery of the community structure is possible. Spectral methods exhibit a regime where this can be done efficiently. Moreover we also prove that, in this setting, any suitably good partial recovery can be bootstrapped to obtain a full recovery of the communities.

Details

TCS Journal 2004 Journal Article

A Halfliar's game

Ioana Dumitriu
Joel Spencer

In Ulam's game Paul tries to find one of n possibilities with q yes–no questions, while responder Carole is allowed to lie a fixed number k of times. We consider an asymmetric variant in which Carole must say yes when that is the correct answer (whence the halflie). We show that this variation allows Paul to distinguish between roughly 2 k as many possibilities as in Ulam's game.

Details DOI