Timezone: »
Poster
Learning Mixtures of Graphs from Epidemic Cascades
Jessica Hoffmann · Soumya Basu · Surbhi Goel · Constantine Caramanis
Thu Jul 16 08:00 AM -- 08:45 AM & Thu Jul 16 07:00 PM -- 07:45 PM (PDT) @
We consider the problem of learning the weighted edges of a balanced mixture of two undirected graphs from epidemic cascades. While mixture models are popular modeling tools, algorithmic development with rigorous guarantees has lagged. Graph mixtures are apparently no exception: until now, very little is known about whether this problem is solvable.
To the best of our knowledge, we establish the first necessary and sufficient conditions for this problem to be solvable in polynomial time on edge-separated graphs. When the conditions are met, i.e., when the graphs are connected with at least three edges, we give an efficient algorithm for learning the weights of both graphs with optimal sample complexity (up to log factors).
We give complementary results and provide sample-optimal (up to log factors) algorithms for mixtures of directed graphs of out-degree at least three, and for mixture of undirected graphs of unbalanced and/or unknown priors.
Author Information
Jessica Hoffmann (University of Texas at Austin)
Soumya Basu (University of Texas at Austin)
Surbhi Goel (University of Texas at Austin)
Constantine Caramanis (University of Texas)
More from the Same Authors
-
2023 : Exposing Attention Glitches with Flip-Flop Language Modeling »
Bingbin Liu · Jordan Ash · Surbhi Goel · Akshay Krishnamurthy · Cyril Zhang -
2023 : Exposing Attention Glitches with Flip-Flop Language Modeling »
Bingbin Liu · Jordan Ash · Surbhi Goel · Akshay Krishnamurthy · Cyril Zhang -
2023 Poster: Reward-Mixing MDPs with Few Latent Contexts are Learnable »
Jeongyeol Kwon · Yonathan Efroni · Constantine Caramanis · Shie Mannor -
2022 Poster: Asymptotically-Optimal Gaussian Bandits with Side Observations »
Alexia Atsidakou · Orestis Papadigenopoulos · Constantine Caramanis · Sujay Sanghavi · Sanjay Shakkottai -
2022 Spotlight: Asymptotically-Optimal Gaussian Bandits with Side Observations »
Alexia Atsidakou · Orestis Papadigenopoulos · Constantine Caramanis · Sujay Sanghavi · Sanjay Shakkottai -
2022 Poster: Understanding Contrastive Learning Requires Incorporating Inductive Biases »
Nikunj Umesh Saunshi · Jordan Ash · Surbhi Goel · Dipendra Kumar Misra · Cyril Zhang · Sanjeev Arora · Sham Kakade · Akshay Krishnamurthy -
2022 Spotlight: Understanding Contrastive Learning Requires Incorporating Inductive Biases »
Nikunj Umesh Saunshi · Jordan Ash · Surbhi Goel · Dipendra Kumar Misra · Cyril Zhang · Sanjeev Arora · Sham Kakade · Akshay Krishnamurthy -
2022 Poster: Coordinated Attacks against Contextual Bandits: Fundamental Limits and Defense Mechanisms »
Jeongyeol Kwon · Yonathan Efroni · Constantine Caramanis · Shie Mannor -
2022 Poster: Inductive Biases and Variable Creation in Self-Attention Mechanisms »
Benjamin Edelman · Surbhi Goel · Sham Kakade · Cyril Zhang -
2022 Spotlight: Inductive Biases and Variable Creation in Self-Attention Mechanisms »
Benjamin Edelman · Surbhi Goel · Sham Kakade · Cyril Zhang -
2022 Spotlight: Coordinated Attacks against Contextual Bandits: Fundamental Limits and Defense Mechanisms »
Jeongyeol Kwon · Yonathan Efroni · Constantine Caramanis · Shie Mannor -
2021 Poster: Statistical Estimation from Dependent Data »
Vardis Kandiros · Yuval Dagan · Nishanth Dikkala · Surbhi Goel · Constantinos Daskalakis -
2021 Spotlight: Statistical Estimation from Dependent Data »
Vardis Kandiros · Yuval Dagan · Nishanth Dikkala · Surbhi Goel · Constantinos Daskalakis -
2021 Poster: Fairness for Image Generation with Uncertain Sensitive Attributes »
Ajil Jalal · Sushrut Karmalkar · Jessica Hoffmann · Alexandros Dimakis · Eric Price -
2021 Spotlight: Fairness for Image Generation with Uncertain Sensitive Attributes »
Ajil Jalal · Sushrut Karmalkar · Jessica Hoffmann · Alexandros Dimakis · Eric Price -
2021 Poster: Combinatorial Blocking Bandits with Stochastic Delays »
Alexia Atsidakou · Orestis Papadigenopoulos · Soumya Basu · Constantine Caramanis · Sanjay Shakkottai -
2021 Spotlight: Combinatorial Blocking Bandits with Stochastic Delays »
Alexia Atsidakou · Orestis Papadigenopoulos · Soumya Basu · Constantine Caramanis · Sanjay Shakkottai -
2021 Poster: Acceleration via Fractal Learning Rate Schedules »
Naman Agarwal · Surbhi Goel · Cyril Zhang -
2021 Spotlight: Acceleration via Fractal Learning Rate Schedules »
Naman Agarwal · Surbhi Goel · Cyril Zhang -
2020 Poster: Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descent »
Surbhi Goel · Aravind Gollakota · Zhihan Jin · Sushrut Karmalkar · Adam Klivans -
2020 Poster: Efficiently Learning Adversarially Robust Halfspaces with Noise »
Omar Montasser · Surbhi Goel · Ilias Diakonikolas · Nati Srebro -
2019 Poster: Robust Estimation of Tree Structured Gaussian Graphical Models »
Ashish Katiyar · Jessica Hoffmann · Constantine Caramanis -
2019 Poster: Pareto Optimal Streaming Unsupervised Classification »
Soumya Basu · Steven Gutstein · Brent Lance · Sanjay Shakkottai -
2019 Oral: Pareto Optimal Streaming Unsupervised Classification »
Soumya Basu · Steven Gutstein · Brent Lance · Sanjay Shakkottai -
2019 Oral: Robust Estimation of Tree Structured Gaussian Graphical Models »
Ashish Katiyar · Jessica Hoffmann · Constantine Caramanis -
2018 Poster: Learning One Convolutional Layer with Overlapping Patches »
Surbhi Goel · Adam Klivans · Raghu Meka -
2018 Oral: Learning One Convolutional Layer with Overlapping Patches »
Surbhi Goel · Adam Klivans · Raghu Meka