We study multi-user contextual bandits where users are related by a graph and their reward functions exhibit both non-linear behavior and graph homophily. We introduce a principled joint penalty for the collection of user reward functions, combining a graph smoothness term based on RKHS distances with an individual roughness penalty. Our central contribution is proving that this penalty is equivalent to the squared norm within a single, unified multi-user RKHS. We explicitly derive its reproducing kernel, which fuses the graph Laplacian with the base arm kernel. This unification allows us to reframe the problem as learning a single lifted function, enabling the design of principled algorithms, LK-GP-UCB and LK-GP-TS, that leverage Gaussian Process posteriors over this new kernel for exploration. We provide high-probability regret bounds that scale with an effective dimension of the multi-user kernel, replacing dependencies on user count or ambient dimension.
@inproceedings{wu2026laplacian,
title = {Laplacian Kernelized Bandit},
author = {Shuang Wu and Arash A. Amini},
booktitle = {The Fourteenth International Conference on Learning Representations},
year = {2026},
doi = {10.48550/arXiv.2601.00461},
url = {https://openreview.net/forum?id=5majEbTAZa},
eprint = {2601.00461},
archiveprefix = {arXiv},
primaryclass = {cs.LG}
}
Trajectory Seriation via Spectral Tangent Alignment and Global Embedding
Zhixin Zhou, Navin Souda, Arash A. Amini · ICMLlink
This paper addresses the problem of linear seriation: recovering the intrinsic order of noisy samples drawn from an unknown one-dimensional manifold embedded in a higher-dimensional space. We propose a multi-stage approach that first robustly estimates local tangent directions using Principal Component Analysis on neighborhoods, establishing theoretical consistency for these local estimates. Global orientation consistency of these tangents is then achieved through a spectral relaxation of a pairwise alignment objective. Finally, a globally consistent 1D embedding is computed by solving a carefully formulated linear system that aligns the embedding with the oriented local projections. This method effectively leverages local geometric information while ensuring global coherence, producing an ordering robust to noise, curvature, and initial data rotation.
@inproceedings{zhou2026trajectory,
title = {Trajectory Seriation via Spectral Tangent Alignment and Global Embedding},
author = {Zhixin Zhou and Navin Souda and Arash A. Amini},
booktitle = {Forty-third International Conference on Machine Learning},
year = {2026},
url = {https://icml.cc/virtual/2026/poster/65481}
}
Community-Size Biases in Statistical Inference of Communities in Temporal Networks
Theodore Y. Faust, Arash A. Amini, Mason A. Porter · PreprintarXivdoicode
In the study of time-dependent networks, researchers often examine the evolution of communities, which are sets of densely connected sets of nodes that are connected sparsely to other nodes. An increasingly prominent approach to studying community structure in temporal networks is statistical inference. In the present paper, we study the performance of a class of statistical-inference methods for community detection in temporal networks. We represent temporal networks as multilayer networks, with each layer encoding a time step, and we illustrate that statistical-inference models that generate community assignments via either a uniform distribution on community assignments or discrete-time Markov processes are biased against generating communities with large or small numbers of nodes. In particular, we demonstrate that statistical-inference methods that use such generative models tend to poorly identify community structure in networks with large or small communities. To rectify this issue, we introduce a novel statistical model that generates the community assignments of the nodes in given layer using all of the community assignments in the previous layer. We prove results that guarantee that our approach greatly mitigates the bias against large and small communities, so using our generative model is beneficial for studying community structure in networks with large or small communities.
@article{faust2026community,
title = {Community-Size Biases in Statistical Inference of Communities in Temporal Networks},
author = {Theodore Y. Faust and Arash A. Amini and Mason A. Porter},
journal = {arXiv preprint arXiv:2601.15635},
year = {2026},
doi = {10.48550/arXiv.2601.15635},
url = {https://arxiv.org/abs/2601.15635},
eprint = {2601.15635},
archiveprefix = {arXiv},
primaryclass = {cs.SI}
}
Wasserstein Concentration of Empirical Measures for Dependent Data via the Method of Moments
We establish a general concentration result for the 1-Wasserstein distance between the empirical measure of a sequence of random variables and its expectation. Unlike standard results that rely on independence or specific mixing conditions, our result requires only two conditions: control over the variance of the empirical moments, and a flexible tail condition we term $\Psi_{r_n}$-sub-Gaussianity. This approach allows for significant dependencies between variables, provided their algebraic moments behave predictably. The proof uses the method of moments combined with a polynomial approximation of Lipschitz functions via Jackson kernels, allowing us to translate moment concentration into topological concentration.
@article{amini2026wasserstein,
title = {Wasserstein Concentration of Empirical Measures for Dependent Data via the Method of Moments},
author = {Arash A. Amini and Luciano Vinas},
journal = {arXiv preprint arXiv:2601.07228},
year = {2026},
doi = {10.48550/arXiv.2601.07228},
url = {https://arxiv.org/abs/2601.07228},
eprint = {2601.07228},
archiveprefix = {arXiv},
primaryclass = {math.ST}
}
Learning general conditional independence structures via the neighbourhood lattice
Arash A. Amini, Bryon Aragam, Qing Zhou · JMLRpdflinkcode
@article{nb-lat-graphoid,
title = {Learning general conditional independence structures via the neighbourhood lattice},
author = {Arash A. Amini and Bryon Aragam and Qing Zhou},
journal = {Journal of Machine Learning Research},
volume = {27},
number = {117},
pages = {1--42},
year = {2026},
url = {http://jmlr.org/papers/v27/25-1595.html}
}
2025
Network two-sample test for block models
Chung Kyong Nguen, Oscar Hernan Madrid Padilla, Arash A. Amini · NeurIPSarXivpdfdoi
We consider the two-sample testing problem for networks, where the goal is to determine whether two sets of networks originated from the same stochastic model. Assuming no vertex correspondence and allowing for different numbers of nodes, we address a fundamental network testing problem that goes beyond simple adjacency matrix comparisons. We adopt the stochastic block model (SBM) for network distributions, due to their interpretability and the potential to approximate more general models. The lack of meaningful node labels and vertex correspondence translate to a graph matching challenge when developing a test for SBMs. We introduce an efficient algorithm to match estimated network parameters, allowing us to properly combine and contrast information within and across samples, leading to a powerful test. We show that the matching algorithm, and the overall test are consistent, under mild conditions on the sparsity of the networks and the sample sizes, and derive a chi-squared asymptotic null distribution for the test. Through a mixture of theoretical insights and empirical validations, including experiments with both synthetic and real-world data, this study advances robust statistical inference for complex network data.
@inproceedings{nguen2025network,
title = {Network two-sample test for block models},
author = {Chung Kyong Nguen and Oscar Hernan Madrid Padilla and Arash A. Amini},
editor = {D. Belgrave and C. Zhang and H. Lin and R. Pascanu and P. Koniusz and M. Ghassemi and N. Chen},
booktitle = {Advances in Neural Information Processing Systems},
volume = {38},
pages = {166537--166581},
year = {2025},
publisher = {Curran Associates, Inc.},
doi = {10.48550/arXiv.2406.06014},
url = {https://proceedings.neurips.cc/paper_files/paper/2025/hash/f3766dc99a12e017c50b320fe06c213f-Abstract-Conference.html},
eprint = {2406.06014},
archiveprefix = {arXiv},
primaryclass = {math.ST}
}
A CLT for Polynomial GNNs on Community-Based Graphs
We consider the empirical distribution of the embeddings of a $k$-layer polynomial GNN on a semi-supervised node classification task and prove a central limit theorem for them. Assuming a community based model for the underlying graph, with growing average degree $\nu_n\to\infty$, we show that the empirical distribution of the centered features, when scaled by $\nu_{n}^{k-1/2}$ converge in 1-Wasserstein distance to a centered stable mixture of multivariate normal distributions. In addition, the joint empirical distribution of uncentered features and labels when normalized by $\nu_n^k$ approach that of mixture of multivariate normal distributions, with stable means and covariance matrices vanishing as $\nu_n^{-1}$. We explicitly identify the asymptotic means and covariances, showing that the mixture collapses towards a 1-D version as $k$ is increased. Our results provides a precise and nuanced lens on how oversmoothing presents itself in the large graph limit, in the sparse regime. In particular, we show that training with cross-entropy on these embeddings is asymptotically equivalent to training on these nearly collapsed Gaussian mixtures.
@inproceedings{vinas2025clt,
title = {A CLT for Polynomial GNNs on Community-Based Graphs},
author = {Vinas, Luciano and Amini, Arash A.},
editor = {D. Belgrave and C. Zhang and H. Lin and R. Pascanu and P. Koniusz and M. Ghassemi and N. Chen},
booktitle = {Advances in Neural Information Processing Systems},
volume = {38},
pages = {154190--154225},
year = {2025},
publisher = {Curran Associates, Inc.},
url = {https://proceedings.neurips.cc/paper_files/paper/2025/hash/e2ed71839b2e1d34569198cf634ea802-Abstract-Conference.html}
}
Bayesian Community Detection for Networks with Covariates
Luyi Shen, Arash Amini, Nathaniel Josephs, Lizhen Lin · BAdoi
@article{shen2025bayesian,
title = {{Bayesian Community Detection for Networks with Covariates}},
author = {Luyi Shen and Arash Amini and Nathaniel Josephs and Lizhen Lin},
journal = {Bayesian Analysis},
volume = {20},
number = {3},
pages = {735 -- 762},
year = {2025},
publisher = {International Society for Bayesian Analysis},
doi = {10.1214/24-BA1415},
url = {https://doi.org/10.1214/24-BA1415}
}
Simple GNNs With Low Rank Non-Parametric Aggregators
We revisit recent spectral GNN approaches to semi-supervised node classification (SSNC). We posit that state-of-the-art (SOTA) GNN architectures may be over-engineered for common SSNC benchmark datasets (citation networks, page-page networks, etc.). By replacing feature aggregation with a non-parametric learner we are able to streamline the GNN design process and avoid many of the engineering complexities associated with SOTA hyperparameter selection (GNN depth, non-linearity choice, feature dropout probability, etc.). Our empirical experiments suggest conventional methods such as non-parametric regression are well suited for semi-supervised learning on sparse, directed networks and a variety of other graph types commonly found in SSNC benchmarks. Additionally, we bring attention to recent changes in evaluation conventions for SSNC benchmarking and how this may have partially contributed to rising performances over time.
@inproceedings{vinas2025simple,
title = {Simple GNNs With Low Rank Non-Parametric Aggregators},
author = {Vinas, Luciano and Amini, Arash A.},
editor = {Wolf, Guy and Krishnaswamy, Smita},
booktitle = {Proceedings of the Third Learning on Graphs Conference},
volume = {269},
pages = {10:1--10:11},
year = {2025},
month = {26--29 Nov},
publisher = {PMLR},
series = {Proceedings of Machine Learning Research},
url = {https://proceedings.mlr.press/v269/vinas25a.html}
}
Step and Smooth Decompositions as Topological Clustering
We investigate the classification performance of graph neural networks with graph-polynomial features, poly-GNNs, on the problem of semi-supervised node classification. We analyze poly-GNNs under a general contextual stochastic block model (CSBM) by providing a sharp characterization of the rate of separation between classes in their output node representations. A question of interest is whether this rate depends on the depth of the network k, i.e., whether deeper networks can achieve a faster separation? We provide a negative answer to this question: for a sufficiently large graph, a depth k>1 poly-GNN exhibits the same rate of separation as a depth k=1 counterpart. Our analysis highlights and quantifies the impact of “graph noise” in deep GNNs and shows how noise in the graph structure can dominate other sources of signal in the graph, negating any benefit further aggregation provides. Our analysis also reveals subtle differences between even and odd-layered GNNs in how the feature noise propagates.
@article{vinas2024sharp,
title = {Sharp Bounds for Poly-{GNN}s and the Effect of Graph Noise},
author = {Vinas, Luciano and Amini, Arash A.},
journal = {arXiv preprint arXiv:2407.19567},
year = {2024}
}
@article{ye2024federated,
title = {Federated Learning of Generalized Linear Causal Networks},
author = {Ye, Qiaoling and Amini, Arash A. and Zhou, Qing},
journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence},
volume = {46},
number = {10},
pages = {6623-6636},
year = {2024},
doi = {10.1109/TPAMI.2024.3381860}
}
Hierarchical Stochastic Block Model for Community Detection in Multiplex Networks
Arash Amini, Marina Paez, Lizhen Lin · BAarXivdoicode
@article{AminiPaezLin2024,
title = {{Hierarchical Stochastic Block Model for Community Detection in Multiplex Networks}},
author = {Arash Amini and Marina Paez and Lizhen Lin},
journal = {Bayesian Analysis},
volume = {19},
number = {1},
pages = {319 -- 345},
year = {2024},
publisher = {International Society for Bayesian Analysis},
doi = {10.1214/22-BA1355},
url = {https://doi.org/10.1214/22-BA1355}
}
2023
Nested stochastic block model for simultaneously clustering networks and nodes
Nathaniel Josephs, Arash A. Amini, Marina Paez, Lizhen Lin · PreprintarXiv
@article{josephs2023nested,
title = {Nested stochastic block model for simultaneously clustering networks and nodes},
author = {Josephs, Nathaniel and Amini, Arash A. and Paez, Marina and Lin, Lizhen},
journal = {arXiv preprint},
year = {2023},
url = {https://arxiv.org/abs/2307.09210},
eprint = {2307.09210},
archiveprefix = {arXiv},
note = {Accepted for publication at {JMLR} subject to minor revisions}
}
Statistical Guarantees for Consensus Clustering
Zhixin Zhou, Gautam Dudeja, Arash A Amini · ICLRlink
@inproceedings{zhou2023statistical,
title = {Statistical Guarantees for Consensus Clustering},
author = {Zhixin Zhou and Gautam Dudeja and Arash A Amini},
booktitle = {The Eleventh International Conference on Learning Representations (ICLR)},
year = {2023},
url = {https://openreview.net/forum?id=kQxry8Z6Fd9}
}
Adjusted Chi-Square Test for Degree-Corrected Block Models
@article{ZhangAmini2023,
title = {Adjusted Chi-Square Test for Degree-Corrected Block Models},
author = {Zhang, Linfan and Amini, Arash A.},
journal = {The Annals of Statistics},
volume = {51},
number = {6},
pages = {2366--2385},
year = {2023},
doi = {10.1214/23-AOS2329},
url = {https://doi.org/10.1214/23-AOS2329}
}
Performance evaluation of automotive dealerships using grouped mixture of regressions
Haidar Almohri, Ratna Babu Chinnam, Arash A. Amini · ESAdoi
@article{almohri2023performance,
title = {Performance evaluation of automotive dealerships using grouped mixture of regressions},
author = {Almohri, Haidar and Chinnam, Ratna Babu and Amini, Arash A.},
journal = {Expert Systems with Applications},
volume = {213},
number = {Part C},
pages = {119266},
year = {2023},
doi = {10.1016/j.eswa.2022.119266}
}
2022
Finding quadruply imaged quasars with machine learning – I. Methods
A Akhazhanov, A More, A Amini, C Hazlett, T Treu, S Birrer, A Shajib, K Liao, C Lemon, A Agnello, B Nord, M Aguena, …, et al. · MNRASarXivpdfdoi
@article{akhazhanov2022finding,
title = {{Finding quadruply imaged quasars with machine learning – I. Methods}},
author = {Akhazhanov, A and More, A and Amini, A and Hazlett, C and Treu, T and Birrer, S and Shajib, A and Liao, K and Lemon, C and Agnello, A and Nord, B and Aguena, M and Allam, S and Andrade-Oliveira, F and Annis, J and Brooks, D and Buckley-Geer, E and Burke, D L and Carnero Rosell, A and Carrasco Kind, M and Carretero, J and Choi, A and Conselice, C and Costanzi, M and da Costa, L N and Pereira, M E S and De Vicente, J and Desai, S and Dietrich, J P and Doel, P and Everett, S and Ferrero, I and Finley, D A and Flaugher, B and Frieman, J and García-Bellido, J and Gerdes, D W and Gruen, D and Gruendl, R A and Gschwend, J and Gutierrez, G and Hinton, S R and Hollowood, D L and Honscheid, K and James, D J and Kim, A G and Kuehn, K and Kuropatkin, N and Lahav, O and Lima, M and Lin, H and Maia, M A G and March, M and Menanteau, F and Miquel, R and Morgan, R and Palmese, A and Paz-Chinchón, F and Pieres, A and Plazas Malagón, A A and Sanchez, E and Scarpine, V and Serrano, S and Sevilla-Noarbe, I and Smith, M and Soares-Santos, M and Suchyta, E and Swanson, M E C and Tarle, G and To, C and Varga, T N and Weller, J and {{DES Collaboration}}},
journal = {Monthly Notices of the Royal Astronomical Society},
volume = {513},
number = {2},
pages = {2407-2421},
year = {2022},
month = {04},
doi = {10.1093/mnras/stac925},
url = {https://doi.org/10.1093/mnras/stac925},
issn = {0035-8711}
}
@inproceedings{amini2022perfectness,
title = {On perfectness in Gaussian graphical models},
author = {Amini, Arash and Aragam, Bryon and Zhou, Qing},
booktitle = {International Conference on Artificial Intelligence and Statistics},
pages = {7505--7517},
year = {2022},
organization = {PMLR}
}
Target alignment in truncated kernel ridge regression
Arash A. Amini, Richard Baumgartner, Dai Feng · NeurIPSarXivcode
@inproceedings{amini2022target,
title = {Target alignment in truncated kernel ridge regression},
author = {Arash A. Amini and Richard Baumgartner and Dai Feng},
editor = {Alice H. Oh and Alekh Agarwal and Danielle Belgrave and Kyunghyun Cho},
booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
year = {2022},
url = {https://openreview.net/forum?id=SPiQQu2NmO9}
}
A non-graphical representation of conditional independence via the neighbourhood lattice
Arash A Amini, Bryon Aragam, Qing Zhou · PreprintarXiv
@article{amini2022non,
title = {A non-graphical representation of conditional independence via the neighbourhood lattice},
author = {Amini, Arash A and Aragam, Bryon and Zhou, Qing},
journal = {Preprint},
year = {2022},
eprint = {2206.05829}
}
2021
Spectrally-truncated kernel ridge regression and its free lunch
@article{amini2021spectrally,
title = {Spectrally-truncated kernel ridge regression and its free lunch},
author = {Arash A. Amini},
journal = {Electron. J. Statist.},
volume = {15},
number = {2},
pages = {3743-3761},
year = {2021},
doi = {10.1214/21-EJS1873},
issn = {1935-7524}
}
Concentration of kernel matrices with application to kernel spectral clustering
@article{kernelconcen:annals,
title = {{Concentration of kernel matrices with application to kernel spectral clustering}},
author = {Arash A. Amini and Zahra S. Razaee},
journal = {The Annals of Statistics},
volume = {49},
number = {1},
pages = {531 -- 556},
year = {2021},
publisher = {Institute of Mathematical Statistics},
doi = {10.1214/20-AOS1967},
url = {https://doi.org/10.1214/20-AOS1967}
}
Label consistency in overfitted generalized k-means
@article{zhang2021label,
title = {Label consistency in overfitted generalized k-means},
author = {Zhang, Linfan and Amini, Arash A},
journal = {Neural Information Processing Systems (NeurIPS)},
year = {2021}
}
On the properties of the toxicity index and its statistical efficiency
Zahra S. Razaee, Arash A. Amini, Márcio A. Diniz, Mourad Tighiouart, Greg Yothers, André Rogatko · Stat Medpdfdoi
@article{razaee2020properties,
title = {On the properties of the toxicity index and its statistical efficiency},
author = {Razaee, Zahra S. and Amini, Arash A. and Diniz, Márcio A. and Tighiouart, Mourad and Yothers, Greg and Rogatko, André},
journal = {Statistics in Medicine},
volume = {40},
number = {6},
pages = {1535-1552},
year = {2021},
doi = {https://doi.org/10.1002/sim.8858},
url = {https://onlinelibrary.wiley.com/doi/abs/10.1002/sim.8858}
}
2020
Approximate Identification of the Optimal Epidemic Source in Complex Networks
We consider the problem of identifying the source of a network epidemic from a complete snapshot of the infected nodes. We take a fully statistical approach and derive novel recursions to compute the Bayes optimal solution, under a heterogeneous susceptible-infected (SI) epidemic model. Our analysis is time and rate independent, and holds for general network topologies. We then provide two highly scalable algorithms for solving these recursions, a mean-field approximation and a greedy approach, and evaluate their performance on real and synthetic networks. Previous work on the problem has mostly focused on tree-like network topologies. Real networks are far from tree-like and an emphasis will be given to networks with high transitivity, such as social networks and those with communities. We show that on such networks, our approaches significantly outperform popular geometric and spectral centrality measures, most of which perform no better than random guessing.
@inproceedings{approx-epidem,
title = {Approximate Identification of the Optimal Epidemic Source in Complex Networks},
author = {Kazemitabar, S. Jalil and Amini, Arash A.},
editor = {Masuda, Naoki and Goh, Kwang-Il and Jia, Tao and Yamanoi, Junichi and Sayama, Hiroki},
booktitle = {Proceedings of NetSci-X 2020: Sixth International Winter School and Conference on Network Science},
pages = {107--125},
year = {2020},
publisher = {Springer International Publishing},
address = {Cham},
isbn = {978-3-030-38965-9}
}
@article{zhou2020optimal,
title = {Optimal bipartite network clustering},
author = {Zhou, Zhixin and Amini, Arash A},
journal = {Journal of Machine Learning Research},
volume = {21},
number = {40},
pages = {1--68},
year = {2020}
}
Optimizing regularized Cholesky score for order-based learning of Bayesian networks
Qiaoling Ye, Arash A. Amini, Qing Zhou · TPAMIarXivlink
@article{dagarcs:IEEE,
title = {Optimizing regularized Cholesky score for order-based learning of Bayesian networks},
author = {Qiaoling Ye and Arash A. Amini and Qing Zhou},
journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence},
year = {2020},
publisher = {IEEE}
}
The Potts-Ising model for discrete multivariate data
@article{razaee2020potts,
title = {The Potts-Ising model for discrete multivariate data},
author = {Razaee, Zahra and Amini, Arash},
journal = {Advances in Neural Information Processing Systems},
volume = {33},
year = {2020}
}
Generalized Autoregressive Linear Models for Discrete High-Dimensional Data
Parthe Pandit, Mojtaba Sahraee-Ardakan, Arash A. Amini, Sundeep Rangan, Alyson K. Fletcher · JSAITdoi
@article{pandit2020generalized,
title = {Generalized Autoregressive Linear Models for Discrete High-Dimensional Data},
author = {Pandit, Parthe and Sahraee-Ardakan, Mojtaba and Amini, Arash A. and Rangan, Sundeep and Fletcher, Alyson K.},
journal = {IEEE Journal on Selected Areas in Information Theory},
volume = {1},
number = {3},
pages = {884-896},
year = {2020},
doi = {10.1109/JSAIT.2020.3041714}
}
2019
Globally optimal score-based learning of directed acyclic graphs in high-dimensions
@inproceedings{aragam2019globally,
title = {Globally optimal score-based learning of directed acyclic graphs in high-dimensions},
author = {Aragam, Bryon and Amini, Arash and Zhou, Qing},
booktitle = {Advances in Neural Information Processing Systems},
pages = {4452--4464},
year = {2019}
}
Matched Bipartite Block Model with Covariates.
Zahra S Razaee, Arash A Amini, Jingyi Jessica Li · JMLRarXivpdflinkcode
@article{Razaee2017,
title = {Matched Bipartite Block Model with Covariates.},
author = {Razaee, Zahra S and Amini, Arash A and Li, Jingyi Jessica},
journal = {Journal of Machine Learning Research},
volume = {20},
number = {34},
pages = {1--44},
year = {2019}
}
Analysis of spectral clustering algorithms for community detection: the general bipartite setting
@article{sc-review,
title = {Analysis of spectral clustering algorithms for community detection: the general bipartite setting},
author = {Zhou, Zhixin and Amini, Arash A},
journal = {Journal of Machine Learning Research},
volume = {20},
number = {47},
pages = {1--47},
year = {2019}
}
Efficient Network Epidemic Inference with Application to Source Identification
S. Jalil Kazemitabar, Arash A. Amini · Working paper
@article{is-epidem,
title = {Efficient Network Epidemic Inference with Application to Source Identification},
author = {S. Jalil Kazemitabar and Arash A. Amini},
journal = {Working paper},
year = {2019-}
}
Exact slice sampler for Hierarchical Dirichlet Processes
Arash A. Amini, Marina Paez, Lizhen Lin, Zahra S. Razaee · Tech ReportarXivcode
We propose an exact slice sampler for Hierarchical Dirichlet process (HDP) and its associated mixture models (Teh et al., 2006). Although there are existing MCMC algorithms for sampling from the HDP, a slice sampler has been missing from the literature. Slice sampling is well-known for its desirable properties including its fast mixing and its natural potential for parallelization. On the other hand, the hierarchical nature of HDPs poses challenges to adopting a full-fledged slice sampler that automatically truncates all the infinite measures involved without ad-hoc modifications. In this work, we adopt the powerful idea of Bayesian variable augmentation to address this challenge. By introducing new latent variables, we obtain a full factorization of the joint distribution that is suitable for slice sampling. Our algorithm has several appealing features such as (1) fast mixing; (2) remaining exact while allowing natural truncation of the underlying infinite-dimensional measures, as in (Kalli et al., 2011), resulting in updates of only a finite number of necessary atoms and weights in each iteration; and (3) being naturally suited to parallel implementations. The underlying principle for joint factorization of the full likelihood is simple and can be applied to many other settings, such as designing sampling algorithms for general dependent Dirichlet process (DDP) models.
@article{hdp:slice,
title = {Exact slice sampler for Hierarchical Dirichlet Processes},
author = {Arash A. Amini and Marina Paez and Lizhen Lin and Zahra S. Razaee},
eprint = {1903.08829v1}
}
Sparse Multivariate Bernoulli Processes in High Dimensions
We consider the problem of estimating the parameters of a multivariate Bernoulli process with auto-regressive feedback in the high-dimensional setting where the number of samples available is much less than the number of parameters. This problem arises in learning interconnections of networks of dynamical systems with spiking or binary valued data. We also allow the process to depend on its past up to a lag p, for a general $p \geq 1$, allowing for more realistic modeling in many applications. We propose and analyze an $\ell_1$-regularized maximum likelihood (ML) estimator under the assumption that the parameter tensor is approximately sparse. Rigorous analysis of such estimators is made challenging by the dependent and non-Gaussian nature of the process as well as the presence of the nonlinearities and multi-level feedback. We derive precise upper bounds on the mean-squared estimation error in terms of the number of samples, dimensions of the process, the lag $p$ and other key statistical properties of the model. The ideas presented can be used in the rigorous high-dimensional analysis of regularized $M$-estimators for other sparse nonlinear and non-Gaussian processes with long-range dependence.
@inproceedings{mbp:ar,
title = {Sparse Multivariate Bernoulli Processes in High Dimensions},
author = {Pandit, Parthe and Sahraee-Ardakan, Mojtaba and Amini, Arash and Rangan, Sundeep and Fletcher, Alyson K.},
editor = {Chaudhuri, Kamalika and Sugiyama, Masashi},
booktitle = {Proceedings of Machine Learning Research},
volume = {89},
pages = {457--466},
year = {2019},
month = {16--18 Apr},
publisher = {PMLR},
series = {Proceedings of Machine Learning Research},
url = {http://proceedings.mlr.press/v89/pandit19a.html}
}
On the support recovery of marginal regression
S. Jalil Kazemitabar, Arash A. Amini, Ameet Talwalkar · Tech ReportarXiv
Leading methods for support recovery in high-dimensional regression, such as Lasso, have been well-studied and their limitations in the context of correlated design have been characterized with precise incoherence conditions. In this work, we present a similar treatment of selection consistency for marginal regression (MR), a computationally efficient family of methods with connections to decision trees. Selection based on marginal regression is also referred to as covariate screening or independence screening and is a popular approach in applied work, especially in ultra high-dimensional settings. We identify the underlying factors—which we denote as \emph{MR incoherence}—affecting MR's support recovery performance. Our near complete characterization provides a much more nuanced and optimistic view of MR in comparison to previous works. To ground our results, we provide a broad taxonomy of results for leading feature selection methods, relating the behavior of Lasso, OMP, SIS, and MR. We also lay the foundation for interesting generalizations of our analysis, e.g., to non-linear feature selection methods and to more general regression frameworks such as a general additive models.
@article{mr:supp,
title = {On the support recovery of marginal regression},
author = {S. Jalil Kazemitabar and Arash A. Amini and Ameet Talwalkar},
eprint = {1903.09488v1}
}
The neighborhood lattice for encoding partial correlations in a Hilbert space
Arash A. Amini, Bryon Aragam, Qing Zhou · Tech ReportarXiv
Neighborhood regression has been a successful approach in graphical and structural equation modeling, with applications to learning undirected and directed graphical models. We extend these ideas by defining and studying an algebraic structure called the neighborhood lattice based on a generalized notion of neighborhood regression. We show that this algebraic structure has the potential to provide an economic encoding of all conditional independence statements in a Gaussian distribution (or conditional uncorrelatedness in general), even in the cases where no graphical model exists that could "perfectly" encode all such statements. We study the computational complexity of computing these structures and show that under a sparsity assumption, they can be computed in polynomial time, even in the absence of the assumption of perfectness to a graph. On the other hand, assuming perfectness, we show how these neighborhood lattices may be "graphically" computed using the separation properties of the so-called partial correlation graph. We also draw connections with directed acyclic graphical models and Bayesian networks. We derive these results using an abstract generalization of partial uncorrelatedness, called partial orthogonality, which allows us to use algebraic properties of projection operators on Hilbert spaces to significantly simplify and extend existing ideas and arguments. Consequently, our results apply to a wide range of random objects and data structures, such as random vectors, data matrices, and functions.
@article{lattice:hilbert,
title = {The neighborhood lattice for encoding partial correlations in a Hilbert space},
author = {Arash A. Amini and Bryon Aragam and Qing Zhou},
eprint = {1711.00991v2}
}
@article{sdp:sbm:aos,
title = {{On semidefinite relaxations for the block model}},
author = {A. A. Amini and E. Levina},
journal = {The Annals of Statistics},
volume = {46},
number = {1},
pages = {149-179},
year = {2018},
archiveprefix = {arXiv}
}
Conditional chi-square test for degree-corrected block models
Linfan Zhang, Arash A. Amini · Working paper
@article{cctest,
title = {Conditional chi-square test for degree-corrected block models},
author = {Linfan Zhang and Arash A. Amini},
journal = {Working paper},
year = {2018-}
}
2017
Partial correlation graphs and the neighborhood lattice
A. A. Amini, B. Aragam, Q. Zhou · Working paper
@article{pcg:working,
title = {Partial correlation graphs and the neighborhood lattice},
author = {A. A. Amini and B. Aragam and Q. Zhou},
journal = {Working paper},
year = {2017-}
}
Efficient community detection via low rank semidefinite programming
Bowei Yan, Purna Sarkar, Arash A. Amini · Working paper
@article{sdp:lowrank,
title = {Efficient community detection via low rank semidefinite programming},
author = {Bowei Yan and Purna Sarkar and Arash A. Amini},
journal = {Working paper},
year = {2017-}
}
Learning Directed Acyclic Graphs with Penalized Neighbourhood Regression
Bryon Aragam, Arash A. Amini, Qing Zhou · Tech ReportarXiv
We study a family of regularized score-based estimators for learning the structure of a directed acyclic graph (DAG) for a multivariate normal distribution from high-dimensional data with $p\gg n$. Our main results establish support recovery guarantees and deviation bounds for a family of penalized least-squares estimators under concave regularization without assuming prior knowledge of a variable ordering. These results apply to a variety of practical situations that allow for arbitrary nondegenerate covariance structures as well as many popular regularizers including the MCP, SCAD, $\ell_{0}$ and $\ell_{1}$. The proof relies on interpreting a DAG as a recursive linear structural equation model, which reduces the estimation problem to a series of neighbourhood regressions. We provide a novel statistical analysis of these neighbourhood problems, establishing uniform control over the superexponential family of neighbourhoods associated with a Gaussian distribution. We then apply these results to study the statistical properties of score-based DAG estimators, learning causal DAGs, and inferring conditional independence relations via graphical models. Our results yield—for the first time—finite-sample guarantees for structure learning of Gaussian DAGs in high-dimensions via score-based estimation.
@article{dag:highd,
title = {Learning Directed Acyclic Graphs with Penalized Neighbourhood Regression},
author = {Bryon Aragam and Arash A. Amini and Qing Zhou},
year = {2017},
eprint = {1511.08963v3}
}
Variable Importance using Decision Trees
Jalil Kazemitabar, Arash Amini, Adam Bloniarz, Ameet S Talwalkar · NeurIPSpdflinksupplement
@inproceedings{kazemitabar2017variable,
title = {Variable Importance using Decision Trees},
author = {Kazemitabar, Jalil and Amini, Arash and Bloniarz, Adam and Talwalkar, Ameet S},
booktitle = {Advances in Neural Information Processing Systems},
pages = {425--434},
year = {2017}
}
Structured regression models for high-dimensional spatial spectroscopy data
Arash A. Amini, Elizaveta Levina, Kerby A. Shedden · EJSarXivdoi
@article{AmLeSh2017,
title = {Structured regression models for high-dimensional spatial spectroscopy data},
author = {Arash A. Amini and Elizaveta Levina and Kerby A. Shedden},
journal = {Electron. J. Statist.},
volume = {11},
number = {2},
pages = {4151-4178},
year = {2017},
doi = {10.1214/17-EJS1301},
issn = {1935-7524}
}
Partial correlation graphs and the neighborhood lattice
Arash A. Amini, Bryon Aragam, Qing Zhou · Tech ReportarXiv
We define and study partial correlation graphs (PCGs) with variables in a general Hilbert space and their connections to generalized neighborhood regression, without making any distributional assumptions. Using operator-theoretic arguments, and especially the properties of projection operators on Hilbert spaces, we show that these neighborhood regressions have the algebraic structure of a lattice, which we call a neighborhood lattice. This lattice property significantly reduces the number of conditions one has to check when testing all partial correlation relations among a collection of variables. In addition, we generalize the notion of perfectness in graphical models for a general PCG to this Hilbert space setting, and establish that almost all Gram matrices are perfect. Under this perfectness assumption, we show how these neighborhood lattices may be "graphically" computed using separation properties of PCGs. We also discuss extensions of these ideas to directed models, which present unique challenges compared to their undirected counterparts. Our results have implications for multivariate statistical learning in general, including structural equation models, subspace clustering, and dimension reduction. For example, we discuss how to compute neighborhood lattices efficiently and furthermore how they can be used to reduce the sample complexity of learning directed acyclic graphs. Our work demonstrates that this abstract viewpoint via projection operators significantly simplifies existing ideas and arguments from the graphical modeling literature, and furthermore can be used to extend these ideas to more general nonparametric settings.
@article{pcg,
title = {Partial correlation graphs and the neighborhood lattice},
author = {Arash A. Amini and Bryon Aragam and Qing Zhou},
eprint = {1711.00991v1}
}
2016
Soft-label M-estimators in community detection
Arash A. Amini · Working paper
@article{soft:label,
title = {Soft-label M-estimators in community detection},
author = {Arash A. Amini},
journal = {Working paper},
year = {2016-}
}
Attribute-efficient online sparse regression
Ehsan Ebrahimzadeh, Arash A. Amini · Working paper
@article{online:sp:reg,
title = {Attribute-efficient online sparse regression},
author = {Ehsan Ebrahimzadeh and Arash A. Amini},
journal = {Working paper},
year = {2016-}
}
2015
Identifiability of Gaussian DAGs in the equal-variance case: A linear-algebraic proof
A. A. Amini · Tech Report
@unpublished{dag:ident,
title = {{Identifiability of Gaussian DAGs in the equal-variance case: A linear-algebraic proof}},
author = {A. A. Amini},
year = {2015}
}
2013
Bayesian inference as iterated random functions with applications to sequential inference in graphical models
@article{irf:arxiv,
title = {{Bayesian inference as iterated random functions with applications to sequential inference in graphical models}},
author = {Amini, A. A. and Nguyen, X.},
journal = {Preprint},
year = {2013},
eprint = {1311.0072}
}
Bayesian inference as iterated random functions with applications to sequential inference in graphical models
@inproceedings{irf:nips,
title = {{Bayesian inference as iterated random functions with applications to sequential inference in graphical models}},
author = {Amini, A. A. and Nguyen, X.},
booktitle = {Neural Information Processing Systems (NIPS)},
year = {2013}
}
Pseudo-likelihood methods for community detection in large sparse networks
A. A. Amini, A. Chen, P. J. Bickel, E. Levina · AOSarXivdoicode
@article{pl:aos,
title = {{Pseudo-likelihood methods for community detection in large sparse networks}},
author = {Amini, A. A. and Chen, A. and Bickel, P. J. and Levina, E.},
journal = {The Annals of Statistics},
volume = {41},
number = {4},
pages = {2097--2122},
year = {2013},
doi = {10.1214/13-AOS1138},
url = {http://adsabs.harvard.edu/abs/2012arXiv1207.2340A http://projecteuclid.org/euclid.aos/1382547514},
issn = {0090-5364}
}
Sequential Detection of Multiple Change Points in Networks: A Graphical Model Approach
@article{mcp:it,
title = {{Sequential Detection of Multiple Change Points in Networks: A Graphical Model Approach}},
author = {Amini, A. A. and Nguyen, X.},
journal = {IEEE Transactions on Information Theory},
volume = {59},
number = {9},
pages = {5824--5841},
year = {2013},
doi = {10.1109/TIT.2013.2264716},
url = {http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=6518132},
issn = {0018-9448}
}
2012
Message-passing sequential detection of multiple change points in networks
@inproceedings{mcp:isit,
title = {{Message-passing sequential detection of multiple change points in networks}},
author = {Nguyen, X. and Amini, A. A. and Rajagopal, R.},
booktitle = {IEEE International Symposium on Information Theory (ISIT)},
pages = {2007--2011},
year = {2012},
doi = {10.1109/ISIT.2012.6283653},
url = {http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=6283653},
isbn = {978-1-4673-2579-0}
}
Approximation properties of certain operator-induced norms on Hilbert spaces
@article{approx12,
title = {{Approximation properties of certain operator-induced norms on Hilbert spaces}},
author = {Amini, A. A. and Wainwright, M. J.},
journal = {Journal of Approximation Theory},
volume = {164},
number = {2},
pages = {320--345},
year = {2012},
doi = {10.1016/j.jat.2011.11.002},
url = {http://linkinghub.elsevier.com/retrieve/pii/S0021904511001821},
issn = {00219045}
}
Sampled forms of functional PCA in reproducing kernel Hilbert spaces
@article{fpca:aos,
title = {{Sampled forms of functional PCA in reproducing kernel Hilbert spaces}},
author = {Amini, A. A. and Wainwright, M. J.},
journal = {The Annals of Statistics},
volume = {40},
number = {5},
pages = {2483--2510},
year = {2012},
doi = {10.1214/12-AOS1033},
url = {http://projecteuclid.org/euclid.aos/1359987528},
issn = {0090-5364}
}
2009
High-dimensional analysis of semidefinite relaxations for sparse principal components
@article{sdp:aos,
title = {{High-dimensional analysis of semidefinite relaxations for sparse principal components}},
author = {Amini, A. A. and Wainwright, M. J.},
journal = {The Annals of Statistics},
volume = {37},
number = {5B},
pages = {2877--2921},
year = {2009},
doi = {10.1214/08-AOS664},
url = {http://projecteuclid.org/euclid.aos/1247836672},
issn = {0090-5364}
}
2008
High-dimensional analysis of semidefinite relaxations for sparse principal components
@inproceedings{sdp:isit,
title = {{High-dimensional analysis of semidefinite relaxations for sparse principal components}},
author = {Amini, A. A. and Wainwright, M. J.},
booktitle = {IEEE International Symposium on Information Theory (ISIT)},
pages = {2454--2458},
year = {2008},
url = {http://ieeexplore.ieee.org/xpls/abs\_all.jsp?arnumber=4595432},
isbn = {9781424425716}
}
2006
A fast method for sparse component analysis based on iterative detection-projection
A. A. Amini, M. Babai-Zadeh, C. Jutten · MaxEnt
@inproceedings{Amini2006a,
title = {{A fast method for sparse component analysis based on iterative detection-projection}},
author = {Amini, A. A. and Babai-Zadeh, M. and Jutten, C.},
booktitle = {Bayesian Inference and Maximum Entropy Methods in Science and Engineering (MaxEnt)},
year = {2006}
}
A new approach for sparse decomposition and sparse source separation
A. A. Amini, M. Babaie-Zadeh, C. Jutten · EUSIPCOlink
@inproceedings{Amini2006,
title = {{A new approach for sparse decomposition and sparse source separation}},
author = {Amini, A. A. and Babaie-Zadeh, M. and Jutten, C.},
booktitle = {European Signal Processing Conference (EUSIPCO)},
pages = {2--6},
year = {2006},
url = {http://sharif.edu/~mbzadeh/PublicOfficial/2006/EUSIPCO2006.pdf}
}