Timezone: »

 
Poster
Multi-Stage Monte Carlo Approximation for Fast Generalized Data Summations
Michael Holmes · Alexander Gray · Charles Isbell

Mon Dec 03 10:30 AM -- 10:40 AM (PST) @
in Poster Session »
In machine learning we often encounter computational bottlenecks in the form of generalized summations over datasets. When the computational cost of these methods is $O(n^2)$ or higher, applicability to large datasets is severely limited. We present a multi-stage Monte Carlo method for approximating such summations with probabilistic relative error control. This method differs from many previous scalability techniques (such as tree-based methods) in that its error is stochastic, but we derive conditions for error control and demonstrate that they work. Further, we give a theoretical sample complexity for the method that is independent of dataset size, and show that this appears to hold in experiments, where speedups reach as high as $10^{14}$ on datasets with points numbering in the millions.
[ PDF] 

Author Information

Michael Holmes (RGM Advisors, LLC)
Alexander Gray (Skytree Inc. and Georgia Tech)
Charles Isbell (Georgia Tech)
Charles Isbell

Dr. Charles Isbell received his bachelor's in Information and Computer Science from Georgia Tech, and his MS and PhD at MIT's AI Lab. Upon graduation, he worked at AT&T Labs/Research until 2002, when he returned to Georgia Tech to join the faculty as an Assistant Professor. He has served many roles since returning and is now The John P. Imlay Jr. Dean of the College of Computing. Charles’s research interests are varied but the unifying theme of his work has been using machine learning to build autonomous agents who engage directly with humans. His work has been featured in the popular press, congressional testimony, and in several technical collections. In parallel, Charles has also pursued reform in computing education. He was a chief architect of Threads, Georgia Tech’s structuring principle for computing curricula. Charles was also an architect for Georgia Tech’s First-of-its’s-kind MOOC-supported MS in Computer Science. Both efforts have received international attention, and been presented in the academic and popular press. In all his roles, he has continued to focus on issues of broadening participation in computing, and is the founding Executive Director for the Constellations Center for Equity in Computing. He is an AAAI Fellow and a Fellow of the ACM. Appropriately, his citation for ACM Fellow reads “for contributions to interactive machine learning; and for contributions to increasing access and diversity in computing”.

More from the Same Authors