Integrating Functions via Distance Sensitive Hashing
summary
Claims a data structure that estimates partition-like sums z(y)=sum_x exp(phi(<x,y>)) faster than naive sampling: random sampling needs ~1/mu probes but this method takes ~1/sqrt(mu) probes, with preprocessing/space roughly N^{3/2} in the worst parametrization and extra factors exponential in the Lipschitz constant (roughly exp(O(L^{2/3}))). Construction combines importance sampling corrections with distance-sensitive hashing and a bank of multi-resolution hash tables; estimator is unbiased and variance-bounded so the scheme provably works (experiments left for future work).
AI-written summary · about
chapters (10)
- 0:00Problem introduction
- 1:44Applications and motivation
- 5:53Computational challenges
- 8:38Machine learning context
- 12:43Theoretical setup and bounds
- 17:24Prior work overview
- 20:55Presented solution
- 26:29Hashing-based estimation
- 29:49Proof intuition
- 38:45Conclusion and summary
related talks
01h 10mSketching High-Dimensional Data
26mUsing Random Projections to Make Sense of High-Dimensional ...
01h 24mStreaming, Sketching and Sufficient Statistics I
01h 04mSampling Big Ideas in Sublinear Algorithms
01h 26mStreaming, Sketching and Sufficient Statistics II
35mSampling for Subset Selection and Applications
40mMonotone Estimation Framework and its Applications for Scalable Analytics of Large Data Sets
41mScalable Spatial Scan Statistics with Coresets