Timezone: »
We develop a latent variable model and an efficient spectral algorithm motivated by the recent emergence of very large data sets of chromatin marks from multiple human cell types. A natural model for chromatin data in one cell type is a Hidden Markov Model (HMM); we model the relationship between multiple cell types by connecting their hidden states by a fixed tree of known structure. The main challenge with learning parameters of such models is that iterative methods such as EM are very slow, while naive spectral methods result in time and space complexity exponential in the number of cell types. We exploit properties of the tree structure of the hidden states to provide spectral algorithms that are more computationally efficient for current biological datasets. We provide sample complexity bounds for our algorithm and evaluate it experimentally on biological data from nine human cell types. Finally, we show that beyond our specific model, some of our algorithmic ideas can be applied to other graphical models.
Author Information
Chicheng Zhang (UC San Diego)
Jimin Song (Rutgers)
Kamalika Chaudhuri (UCSD)
Kevin Chen (Rutgers)
More from the Same Authors
-
2022 : The Interpolated MVU Mechanism For Communication-efficient Private Federated Learning »
Chuan Guo · Kamalika Chaudhuri · Pierre STOCK · Mike Rabbat -
2022 : Forgetting Data from Pre-trained GANs »
Zhifeng Kong · Kamalika Chaudhuri -
2023 Workshop: XAI in Action: Past, Present, and Future Applications »
Chhavi Yadav · Michal Moshkovitz · Nave Frost · Suraj Srinivas · Bingqing Chen · Valentyn Boreiko · Himabindu Lakkaraju · J. Zico Kolter · Dotan Di Castro · Kamalika Chaudhuri -
2022 : Panel Discussion »
Kamalika Chaudhuri · Been Kim · Dorsa Sadigh · Huan Zhang · Linyi Li -
2022 : Invited Talk: Kamalika Chaudhuri »
Kamalika Chaudhuri -
2021 Workshop: Privacy in Machine Learning (PriML) 2021 »
Yu-Xiang Wang · Borja Balle · Giovanni Cherubin · Kamalika Chaudhuri · Antti Honkela · Jonathan Lebensold · Casey Meehan · Mi Jung Park · Adrian Weller · Yuqing Zhu -
2021 Poster: Understanding Instance-based Interpretability of Variational Auto-Encoders »
Zhifeng Kong · Kamalika Chaudhuri -
2021 Poster: Consistent Non-Parametric Methods for Maximizing Robustness »
Robi Bhattacharjee · Kamalika Chaudhuri -
2020 Workshop: Privacy Preserving Machine Learning - PriML and PPML Joint Edition »
Borja Balle · James Bell · AurĂ©lien Bellet · Kamalika Chaudhuri · Adria Gascon · Antti Honkela · Antti Koskela · Casey Meehan · Olga Ohrimenko · Mi Jung Park · Mariana Raykova · Mary Anne Smart · Yu-Xiang Wang · Adrian Weller -
2020 Poster: A Closer Look at Accuracy vs. Robustness »
Yao-Yuan Yang · Cyrus Rashtchian · Hongyang Zhang · Russ Salakhutdinov · Kamalika Chaudhuri -
2019 : Audrey Durand, Douwe Kiela, Kamalika Chaudhuri moderated by Yann Dauphin »
Audrey Durand · Kamalika Chaudhuri · Yann Dauphin · Orhan Firat · Dilan Gorur · Douwe Kiela -
2019 : Kamalika Chaudhuri - A Three Sample Test to Detect Data Copying in Generative Models »
Kamalika Chaudhuri -
2019 Workshop: Privacy in Machine Learning (PriML) »
Borja Balle · Kamalika Chaudhuri · Antti Honkela · Antti Koskela · Casey Meehan · Mi Jung Park · Mary Anne Smart · Mary Anne Smart · Adrian Weller -
2019 Poster: The Label Complexity of Active Learning from Observational Data »
Songbai Yan · Kamalika Chaudhuri · Tara Javidi -
2019 Poster: Capacity Bounded Differential Privacy »
Kamalika Chaudhuri · Jacob Imola · Ashwin Machanavajjhala -
2018 : Invited talk 3: Challenges in the Privacy-Preserving Analysis of Structured Data »
Kamalika Chaudhuri -
2018 : Plenary Talk 2 »
Kamalika Chaudhuri -
2018 Workshop: Workshop on Security in Machine Learning »
Nicolas Papernot · Jacob Steinhardt · Matt Fredrikson · Kamalika Chaudhuri · Florian Tramer -
2017 : Analyzing Robustness of Nearest Neighbors to Adversarial Examples »
Kamalika Chaudhuri -
2017 Poster: Renyi Differential Privacy Mechanisms for Posterior Sampling »
Joseph Geumlek · Shuang Song · Kamalika Chaudhuri -
2017 Poster: Approximation and Convergence Properties of Generative Adversarial Learning »
Shuang Liu · Olivier Bousquet · Kamalika Chaudhuri -
2017 Spotlight: Approximation and Convergence Properties of Generative Adversarial Learning »
Shuang Liu · Olivier Bousquet · Kamalika Chaudhuri -
2017 Tutorial: Differentially Private Machine Learning: Theory, Algorithms and Applications »
Kamalika Chaudhuri · Anand D Sarwate -
2016 Poster: Active Learning from Imperfect Labelers »
Songbai Yan · Kamalika Chaudhuri · Tara Javidi -
2015 : Spectral Algorithms for Learning HMMs and Tree HHMs for Epigenetics Data »
Kevin Chen -
2015 : Kamalika Chaudhuri »
Kamalika Chaudhuri -
2015 Workshop: Non-convex Optimization for Machine Learning: Theory and Practice »
Anima Anandkumar · Niranjan Uma Naresh · Kamalika Chaudhuri · Percy Liang · Sewoong Oh -
2015 Poster: Active Learning from Weak and Strong Labelers »
Chicheng Zhang · Kamalika Chaudhuri -
2015 Poster: Convergence Rates of Active Learning for Maximum Likelihood Estimation »
Kamalika Chaudhuri · Sham Kakade · Praneeth Netrapalli · Sujay Sanghavi -
2014 Poster: Beyond Disagreement-Based Agnostic Active Learning »
Chicheng Zhang · Kamalika Chaudhuri -
2014 Poster: Rates of Convergence for Nearest Neighbor Classification »
Kamalika Chaudhuri · Sanjoy Dasgupta -
2014 Spotlight: Beyond Disagreement-Based Agnostic Active Learning »
Chicheng Zhang · Kamalika Chaudhuri -
2014 Spotlight: Rates of Convergence for Nearest Neighbor Classification »
Kamalika Chaudhuri · Sanjoy Dasgupta -
2014 Poster: The Large Margin Mechanism for Differentially Private Maximization »
Kamalika Chaudhuri · Daniel Hsu · Shuang Song -
2013 Poster: A Stability-based Validation Procedure for Differentially Private Machine Learning »
Kamalika Chaudhuri · Staal A Vinterbo -
2012 Poster: Near-optimal Differentially Private Principal Components »
Kamalika Chaudhuri · Anand D Sarwate · Kaushik Sinha -
2011 Poster: Spectral Methods for Learning Multivariate Latent Tree Structure »
Anima Anandkumar · Kamalika Chaudhuri · Daniel Hsu · Sham M Kakade · Le Song · Tong Zhang -
2010 Poster: Rates of convergence for the cluster tree »
Kamalika Chaudhuri · Sanjoy Dasgupta -
2009 Poster: A Parameter-free Hedging Algorithm »
Kamalika Chaudhuri · Yoav Freund · Daniel Hsu -
2008 Poster: Privacy-preserving logistic regression »
Kamalika Chaudhuri · Claire Monteleoni