Rejection Sampling for Weighted Jaccard Similarity Revisited

02/02/2021

Rejection Sampling for Weighted Jaccard Similarity Revisited

Xiaoyun Li, Ping Li

Keywords:

Abstract Paper Similar Papers

Abstract: Efficiently computing the weighted Jaccard similarity has become an active research topic in machine learning and theory. For sparse data, the standard technique is based on the consistent weighed sampling (CWS). For dense data, however, methods based on rejection sampling (RS) can be much more efficient. Nevertheless, existing RS methods are still slow for practical purposes. In this paper, we propose to improve RS by a strategy, which we call efficient rejection sampling (ERS), based on ``early stopping + densification''. We analyze the statistical property of ERS and provide experimental results to compare ERS with RS and other algorithms for hashing weighted Jaccard. The results demonstrate that ERS significantly improves the existing methods for estimating the weighted Jaccard similarity in relatively dense data.

The video of this talk cannot be embedded. You can watch it here:

https://slideslive.com/38949128

(Link will open in new window)

0

0

0

0

Share

This is an embedded video. Talk and the respective paper are published at AAAI 2021 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment

no comments yet

Similar Papers

12/07/2020

StochasticRank: Global Optimization of Scale-Free Discrete Functions

Aleksei Ustimenko, Liudmila Prokhorenkova

Keywords Paper

Supervised Learning

0

0

0

0

13:06

12/07/2020

Efficiently sampling functions from Gaussian process posteriors

James Wilson, Viacheslav Borovitskiy, Alexander Terenin and
Peter Mostowsky, Marc Deisenroth

Keywords Paper

Gaussian Processes

0

0

0

0

14:40

06/12/2020

Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimization

Sam Hopkins, Jerry Li, Fred Zhang

Keywords Paper

0

0

0

0

3:34

19/08/2021

Thompson Sampling for Bandits with Clustered Arms

Emil Carlsson, Devdatt Dubhashi, Fredrik D. Johansson

Keywords Paper

Machine Learning, Online Learning, Learning Theory, Reinforcement Learning

0

0

0

0

14:27

06/12/2021

Identity testing for Mallows model

Róbert Busa-Fekete, Dimitris Fotakis, Balazs Szorenyi, Emmanouil Zampetakis

Keywords Paper

0

0

0

0

14:51

26/04/2020

Understanding l4-based Dictionary Learning: Interpretation, Stability, and Robustness

Yuexiang Zhai, Hermish Mehta, Zhengyuan Zhou, Yi Ma

Keywords Paper

L4-norm Maximization, Robust Dictionary Learning

0

0

0

0

5:05

18/07/2021

Wasserstein Distributional Normalization For Robust Distributional Certification of Noisy Labeled Data

Sung Woo Park, Junseok Kwon

Keywords Paper

Deep Learning, Generative Models, Algorithms, Representation Learning; Optimization, Submodular Optimization, Probabilistic Methods, Robust statistics

0

0

0

0

5:20

12/07/2020

Doubly robust off-policy evaluation with shrinkage

Yi Su, Maria Dimakopoulou, Akshay Krishnamurthy, Miroslav Dudik

Keywords Paper

Online Learning, Active Learning, and Bandits

0

0

0

0

15:08

06/12/2021

Shared Independent Component Analysis for Multi-Subject Neuroimaging

Hugo Richard, Pierre Ablin, Bertrand Thirion and
Alexandre Gramfort, Aapo Hyvarinen

Keywords Paper

representation learning

0

0

0

0

14:21

26/08/2020

Distributionally Robust Formulation and Model Selection for the Graphical Lasso

Pedro Cisneros, Alexander Petersen, Sang-Yun Oh

Keywords Paper

0

0

0

0

14:08

06/12/2020

Random Reshuffling: Simple Analysis with Vast Improvements

Konstantin Mishchenko, Ahmed Khaled Ragab Bayoumi, Peter Richtarik

Keywords Paper

Reinforcement Learning and Planning -> Planning; Reinforcement Learning and Planning -> Reinforcement Learning, Reinforcement Learning and Planning

0

0

0

0

3:08

14/09/2020

Fast greedy C-Bound minimization with guarantees

B. Bauvin, C. Capponi, J.F. Roy, F. Laviolett

Keywords Paper

0

0

0

0

15:14

26/08/2020

Naive Feature Selection: Sparsity in Naive Bayes

Armin Askari, Alexandre d'Aspremont, Laurent El Ghaoui

Keywords Paper

0

0

0

0

14:32

06/12/2021

Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination

Dylan J Foster, Akshay Krishnamurthy

Keywords Paper

theory, reinforcement learning and planning, bandits, online learning

0

0

0

0

19:34

02/02/2021

A Sharp Leap from Quantified Boolean Formula to Stochastic Boolean Satisfiability Solving

Pei-Wei Chen, Yu-Ching Huang, Jie-Hong R. Jiang

Keywords Paper

0

0

0

0

18:58

06/12/2021

Robust Regression Revisited: Acceleration and Improved Estimation Rates

Arun Jambulapati, Jerry Li, Tselil Schramm, Kevin Tian

Keywords Paper

theory, optimization

0

0

0

0

14:22

18/07/2021

Run-Sort-ReRun: Escaping Batch Size Limitations in Sliced Wasserstein Generative Models

José Lezama, Wei Chen, Qiang Qiu

Keywords Paper

Deep Learning

0

0

0

0

5:13

12/07/2020

Stochastic Regret Minimization in Extensive-Form Games

Gabriele Farina, Christian Kroer, Tuomas Sandholm

Keywords Paper

Learning Theory

0

0

0

0

12:01

22/06/2020

The power of factorization mechanisms in local and central differential privacy

Alexander Edmonds, Aleksandar Nikolov, Jonathan Ullman

Keywords Paper

statistical queries, local differential privacy, matrix mechanism, matrix factorization, factorization mechanism, PAC learning, Differential privacy

0

0

0

0

18:36

14/06/2020

A Graduated Filter Method for Large Scale Robust Estimation

Huu Le, Christopher Zach

Keywords Paper

robust fitting, bundle adjustment, non-convex, poor local minima, non-linear least squares, graduated non-convexity.

0

0

0

0

1:01

18/07/2021

Stochastic Sign Descent Methods: New Algorithms and Better Theory

Mher Safaryan, Peter Richtarik

Keywords Paper

Optimization, Distributed and Parallel Optimization

0

0

0

0

5:12

06/12/2020

AI Feynman 2.0: Pareto-optimal symbolic regression exploiting graph modularity

Silviu-Marian Udrescu, Andrew Tan, Jiahai Feng and
Orisvaldo Neto, Tailin Wu, Max Tegmark

Keywords Paper

0

0

0

0

3:13

14/09/2020

Model-based Clustering with HDBSCAN*

Michael Strobl, Joerg Sander, Ricardo Campello, Osmar Zaiane

Keywords Paper

hierarchical clustering, expectation maximization, model selection

0

0

0

0

15:31

14/06/2020

ABCNet: Real-Time Scene Text Spotting With Adaptive Bezier-Curve Network

Yuliang Liu, Hao Chen, Chunhua Shen and
Tong He, Lianwen Jin, Liangwei Wang

Keywords Paper

bezier curve, scene text, end-to-end, detection, recognition, arbitrarily shaped, one stage, align, sampling, deep neural network

0

0

0

0

5:01

03/05/2021

Mixed-Features Vectors and Subspace Splitting

Alejandro Pimentel-Alarcón, Daniel L Pimentel-Alarcón

Keywords Paper

0

0

0

0

13:27

02/02/2021

Robust Model Compression Using Deep Hypotheses

Omri Armstrong, Ran Gilad-Bachrach

Keywords Paper

0

0

0

0

17:26

18/07/2021

Risk Bounds and Rademacher Complexity in Batch Reinforcement Learning

Yaqi Duan, Chi Jin, Zhiyuan Li

Keywords Paper

Theory, RL, Decisions and Control Theory

0

0

0

0

5:18

18/07/2021

On the price of explainability for some clustering problems

Eduardo Laber, Lucas Murtinho

Keywords Paper

Optimization, Combinatorial Optimization

0

0

0

0

16:52

12/07/2020

A Unified Theory of Decentralized SGD with Changing Topology and Local Updates

Anastasiia Koloskova, Nicolas Loizou, Sadra Boreiri and
Martin Jaggi, Sebastian Stich

Keywords Paper

Optimization - Large Scale, Parallel and Distributed

0

0

0

0

13:46

13/04/2021

Transforming gaussian processes with normalizing flows

Juan Maroñas, Oliver Hamelijnck, Jeremias Knoblauch, Theodoros Damoulas

Keywords Paper

0

0

0

0

3:05

06/12/2020

GCN meets GPU: Decoupling “When to Sample” from “How to Sample”

Morteza Ramezani, Weilin Cong, Mehrdad Mahdavi and
Anand Sivasubramaniam, Mahmut Kandemir

Keywords Paper

0

0

0

0

3:24

12/07/2020

The continuous categorical: a novel simplex-valued exponential family

Elliott Gordon-Rodriguez, Gabriel Loaiza-Ganem, John Cunningham

Keywords Paper

Probabilistic Inference - Models and Probabilistic Programming

0

0

0

0

14:59

09/07/2020

A Fast Spectral Algorithm for Mean Estimation with Sub-Gaussian Rates

Zhixian Lei, Kyle Luh, Prayaag Venkat, Fred Zhang

Keywords Paper

High-dimensional statistics, Adversarial learning and robustness

0

0

0

0

15:00

02/02/2021

Fast and Compact Bilinear Pooling by Shifted Random Maclaurin

Tan Yu, Xiaoyun Li, Ping Li

Keywords Paper

0

0

0

0

14:24

06/12/2020

Distributed Training with Heterogeneous Data: Bridging Median- and Mean-Based Algorithms

Xiangyi Chen, Tiancong Chen, Haoran Sun and
Steven Wu, Mingyi Hong

Keywords Paper

0

0

0

0

3:19

03/05/2021

Randomized Ensembled Double Q-Learning: Learning Fast Without a Model

Xinyue Chen, Che Wang, Zijian Zhou, Keith Ross

Keywords Paper

Machine Learning, Artificial Integlligence, Deep Reinforcement Learning

0

0

0

0

5:05

06/12/2020

A Contour Stochastic Gradient Langevin Dynamics Algorithm for Simulations of Multi-modal Distributions

Wei Deng, Guang Lin, Faming Liang

Keywords Paper

0

0

0

0

3:26

06/12/2021

Stochastic Online Linear Regression: the Forward Algorithm to Replace Ridge

Reda Ouhamma, Odalric-Ambrym Maillard, Vianney Perchet

Keywords Paper

robustness, bandits

0

0

0

0

11:30

18/07/2021

More Powerful and General Selective Inference for Stepwise Feature Selection using Homotopy Method

Kazuya Sugiyama, Vo Nguyen Le Duy, Ichiro Takeuchi

Keywords Paper

Algorithms, Sparsity and Compressed Sensing

0

0

0

0

5:15

18/07/2021

ConvexVST: A Convex Optimization Approach to Variance-stabilizing Transformation

Mengfan Wang, Boyu Lyu, Guoqiang Yu

Keywords Paper

Optimization, Convex Optimization

0

0

0

0

4:59