4 papers
Optimal estimation of Gaussian (poly)trees
Yuhao Wang, Ming Gao, Wai Ming Tai +2
We develop optimal algorithms for learning undirected Gaussian trees and directed Gaussian polytrees from data. We consider both problems of distribution learning (i.e. in KL dista…
On Mergable Coresets for Polytope Distance
Benwei Shi, Aditya Bhaskara, Wai Ming Tai +1
We show that a constant-size constant-error coreset for polytope distance is simple to maintain under merges of coresets. However, increasing the size cannot improve the error boun…
Optimal estimation of Gaussian DAG models
Ming Gao, Wai Ming Tai, Bryon Aragam
We study the optimal sample complexity of learning a Gaussian directed acyclic graph (DAG) from observational data. Our main results establish the minimax optimal sample complexity…
Tracking the Frequency Moments at All Times
Zengfeng Huang, Wai Ming Tai, Ke Yi
The traditional requirement for a randomized streaming algorithm is just {\em one-shot}, i.e., algorithm should be correct (within the stated $\eps$-error bound) at the end of the…