Publications related to Kernel Density Estimation through Density Constrained Near Neighbor Search

Cluster-and-Conquer: When Randomness Meets Graph Locality

K-Nearest-Neighbors (KNN) graphs are central to many emblematic data mining and machine-learning applications. Some of the most efficient KNN graph algorithms are incremental and local: they start from a random graph, which they incrementally improve by tr ...

IEEE COMPUTER SOC2021

Oblivious Sketching of High-Degree Polynomial Kernels

Mikhail Kapralov, Amir Zandieh

Kernel methods are fundamental tools in machine learning that allow detection of non-linear dependencies between data without explicitly constructing feature vectors in high dimensional spaces. A major disadvantage of kernel methods is their poor scalabili ...

ASSOC COMPUTING MACHINERY2020

Scaling up Kernel Ridge Regression via Locality Sensitive Hashing

Mikhail Kapralov, Amir Zandieh, Navid Nouri

Random binning features, introduced in the seminal paper of Rahimi and Recht '07, are an efficient method for approximating a kernel matrix using locality sensitive hashing. Random binning features provide a very simple and efficient way to approximate the ...

ADDISON-WESLEY PUBL CO2020

Robust discrete choice models with t-distributed kernel errors

Michel Bierlaire, Thomas Gasos, Prateek Bansal

Models that are robust to aberrant choice behaviour have received limited attention in discrete choice analysis. In this paper, we analyse two robust alternatives to the multinomial probit (MNP) model. Both alternative models belong to the family of robit ...

EPFL2020

Particle number control for direct simulation Monte-Carlo methodology using kernel estimates

The efficiency of stochastic particle schemes for large scale simulations relies on the ability to preserve a uniform distribution of particles in the whole physical domain. While simple particle split and merge algorithms have been considered previously, ...

2019

Kernel Regression for Graph Signal Prediction in Presence of Sparse Noise

Pascal Frossard, Arun Venkitaraman

In presence of sparse noise we propose kernel regression for predicting output vectors which are smooth over a given graph. Sparse noise models the training outputs being corrupted either with missing samples or large perturbations. The presence of sparse ...

IEEE2019

Testing Graph Clusterability: Algorithms and Lower Bounds

Mikhail Kapralov, Aidasadat Mousavifar, Ashish Hari Chiplunkar

We consider the problem of testing graph cluster structure: given access to a graph G = (V, E), can we quickly determine whether the graph can be partitioned into a few clusters with good inner conductance, or is far from any such graph? This is a generali ...

IEEE COMPUTER SOC2018

A Sampling Theory for Non-Decaying Signals

Michaël Unser, Quy Ha Nguyen

The classical assumption in sampling and spline theories is that the input signal is square-integrable, which prevents us from applying such techniques to signals that do not decay or even grow at infinity. In this paper, we develop a sampling theory for m ...

2017

Validation of likelihood ratio methods for forensic evidence evaluation handling multimodal score distributions

Rudolf Haraksim

This study presents a method for computing likelihood ratios (LRs) from multimodal score distributions, as the ones produced by some commercial off-the-shelf automated fingerprint identification systems (AFISs). The AFIS algorithms used to compare fingerma ...

Inst Engineering Technology-IET2017

Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization

Volkan Cevher, Jonathan Mark Scarlett, Ilija Bogunovic

In this paper, we consider the problem of sequentially optimizing a black-box function

f

based on noisy samples and bandit feedback. We assume that

f

is smooth in the sense of having a bounded norm in some reproducing kernel Hilbert space (RKHS), yield ...

2017

Kernel Density Estimation through Density Constrained Near Neighbor Search

Graph Chatbot

Chat with Graph Search

Cluster-and-Conquer: When Randomness Meets Graph Locality

Oblivious Sketching of High-Degree Polynomial Kernels

Scaling up Kernel Ridge Regression via Locality Sensitive Hashing

Robust discrete choice models with t-distributed kernel errors

Particle number control for direct simulation Monte-Carlo methodology using kernel estimates

Kernel Regression for Graph Signal Prediction in Presence of Sparse Noise

Testing Graph Clusterability: Algorithms and Lower Bounds

A Sampling Theory for Non-Decaying Signals

Validation of likelihood ratio methods for forensic evidence evaluation handling multimodal score distributions

Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization

Cluster-and-Conquer: When Randomness Meets Graph Locality

Oblivious Sketching of High-Degree Polynomial Kernels

Robust discrete choice models with t-distributed kernel errors

Testing Graph Clusterability: Algorithms and Lower Bounds

Particle number control for direct simulation Monte-Carlo methodology using kernel estimates

A Sampling Theory for Non-Decaying Signals

Kernel Regression for Graph Signal Prediction in Presence of Sparse Noise

Scaling up Kernel Ridge Regression via Locality Sensitive Hashing

Validation of likelihood ratio methods for forensic evidence evaluation handling multimodal score distributions

Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization