93 citations · 578 across the 83 of their papers we have counts for
8 papers · 1 filter
Unsupervised Learning through Prediction in a Model of Cortex
Christos H. Papadimitriou, Santosh S. Vempala
We propose a primitive called PJOIN, for "predictive join," which combines and extends the operations JOIN and LINK, which Valiant proposed as the basis of a computational theory o…
Efficient Representations for Life-Long Learning and Autoencoding
Maria-Florina Balcan, Avrim Blum, Santosh Vempala
It has been a long-standing goal in machine learning, as well as in AI more generally, to develop life-long learning systems that learn many different tasks over time, and reuse in…
Max vs Min: Tensor Decomposition and ICA with nearly Linear Sample Complexity
Santosh S. Vempala, Ying Xiao
We present a simple, general technique for reducing the sample complexity of matrix and tensor decomposition algorithms applied to distributions. We use the technique to give a pol…
Query complexity of sampling and small geometric partitions
Navin Goyal, Luis Rademacher, Santosh Vempala
In this paper we study the following problem: Discrete partitioning problem (DPP): Let denote the -dimensional finite projective space over . Fo…
Stochastic billiards for sampling from the boundary of a convex set
A. B. Dieker, Santosh Vempala
Stochastic billiards can be used for approximate sampling from the boundary of a bounded convex set through the Markov Chain Monte Carlo (MCMC) paradigm. This paper studies how man…
Gaussian Cooling and O*(n^3) Algorithms for Volume and Gaussian Volume
Ben Cousins, Santosh Vempala
We present an randomized algorithm for estimating the volume of a well-rounded convex body given by a membership oracle, improving on the previous best complexity of $O^…