# Haim Kaplan

I work on data structures, algorithms, computational geometry and machine learning. Right now my main focus is on online learning, reinforcement learning, and clustering. Typically my research is theoretical. I am also a faculty at the school of computer science of Tel Aviv University.

Authored Publications

Google Publications

Other Publications

Sort By

Differentially-Private Bayes Consistency

Aryeh Kontorovich

Shay Moran

Menachem Sadigurschi

Archive, Archive, Archive

Preview abstract
We construct a universally Bayes consistent learning rule
which satisfies differential privacy (DP).
We first handle the setting of binary classification
and then extend our rule to the more
general setting of density estimation (with respect to the total variation metric).
The existence of a universally consistent DP learner
reveals a stark difference with the distribution-free PAC model.
Indeed, in the latter DP learning is extremely limited:
even one-dimensional linear classifiers
are not privately learnable in this stringent model.
Our result thus demonstrates that by allowing
the learning rate to depend on the target distribution,
one can circumvent the above-mentioned impossibility result
and in fact learn \emph{arbitrary} distributions by a single DP algorithm.
As an application, we prove that any VC class can be privately learned in a semi-supervised
setting with a near-optimal \emph{labelled} sample complexity of $\tilde O(d/\eps)$ labeled examples
(and with an unlabeled sample complexity that can depend on the target distribution).
View details

Adversarially Robust Streaming Algorithms via Differential Privacy

Journal of the ACM, vol. 69(6) (2022), pp. 1-14

Preview abstract
A streaming algorithm is said to be adversarially robust if its accuracy guarantees are maintained even when the data stream is chosen maliciously, by an adaptive adversary. We establish a connection between adversarial robustness of streaming algorithms and the notion of differential privacy. This connection allows us to design new adversarially robust streaming algorithms that outperform the current state-of-the-art constructions for many interesting regimes of parameters.
View details

Near-optimal Regret Bounds for Stochastic Shortest Path

Aviv Rosenberg

International Conference on Machine Learning (ICML) 2020 (2020)

Preview abstract
Stochastic shortest path (SSP) is a well-known problem in planning and control, in which an agent has to reach a goal state in minimum total expected cost.
In the learning formulation of the problem, the agent is unaware of the environment dynamics (i.e., the transition function) and has to repeatedly play for a given number of episodes while learning the problem’s optimal solution.
Unlike other well-studied models in reinforcement learning (RL), the length of an episode is not predetermined (or bounded) and is influenced by the agent’s actions.
Recently, Tarbouriech et al. (2019) studied this problem in the context of regret minimization, and provided an algorithm whose regret bound is inversely proportional to the square root of the minimum instantaneous cost.
In this work we remove this dependence on the minimum cost—we give an algorithm that guarantees a regret bound of $O(B S \sqrt{A K})$ , where B is an upper bound on the expected cost of the optimal policy, S is the number of states, A is the number of actions and K is the total number of episodes.
We additionally show that any learning algorithm must have at least $\Omega(B \sqrt{S A K})$ regret in the worst case.
View details

Output sensitive algorithms for approximate incidences and their applications

Micha Sharir

Computational Geometry Theory and Applications, vol. 91 (2019), pp. 101666

Preview abstract
An ε-approximate incidence between a point and some geometric object (line, circle,
plane, sphere) occurs when the point and the object lie at distance at most ε from
each other. Given a set of points and a set of objects, computing the approximate
incidences between them is a major step in many database and web-based applications
in computer vision and graphics, including robust model fitting, approximate point
pattern matching, and estimating the fundamental matrix in epipolar (stereo) geometry.
In a typical approximate incidence problem of this sort, we are given a set P of m
points in two or three dimensions, a set S of n objects (lines, circles, planes, spheres),
and an error parameter ε > 0, and our goal is to report all pairs (p, s) ∈ P × S
that lie at distance at most ε from one another. We present efficient output-sensitive
approximation algorithms for quite a few cases, including points and lines or circles in
the plane, and points and planes, spheres, lines, or circles in three dimensions. Several
of these cases arise in the applications mentioned above. Our algorithms report all pairs
at distance ≤ ε, but may also report additional pairs, all of which are guaranteed to be
at distance at most αε, for some problem-dependent constant α > 1. Our algorithms
are based on simple primal and dual grid decompositions and are easy to implement.
We note that (a) the use of duality, which leads to significant improvements in the
overhead cost of the algorithms, appears to be novel for this kind of problems; (b) the
correct choice of duality in some of these problems is fairly intricate and requires some
care; and (c) the correctness and performance analysis of the algorithms (especially in
the more advanced versions) is fairly non-trivial. We analyze our algorithms and prove
guaranteed upper bounds on their running time and on the “distortion” parameter α.
View details

General techniques for approximate incidences and their application to the camera posing problem

Micha Sharir

Bernhard Zeisl

The 35th International Symposium on Computational Geometry (2019)

Preview abstract
We consider the classical camera pose estimation problem that arises in many computer vision
applications, in which we are given n 2D-3D correspondences between points in the scene and
points in the camera image (some of which are incorrect associations), and where we aim to
determine the camera pose (the position and orientation of the camera in the scene) from this
data. We demonstrate that this posing problem can be reduced to the problem of computing
ε-approximate incidences between two-dimensional surfaces (derived from the input correspondences) and points (on a grid) in a four-dimensional pose space. Similar reductions can be applied
to other camera pose problems, as well as to similar problems in related application areas.
We describe and analyze three techniques for solving the resulting ε-approximate incidences
problem in the context of our camera posing application. The first is a straightforward assignment
of surfaces to the cells of a grid (of side-length ε) that they intersect. The second is a variant
of a primal-dual technique, recently introduced by a subset of the authors [2] for different (and
simpler) applications. The third is a non-trivial generalization of a data structure Fonseca and
Mount [3], originally designed for the case of hyperplanes. We present and analyze this technique
in full generality, and then apply it to the camera posing problem at hand.
We compare our methods experimentally on real and synthetic data. Our experiments show
that for the typical values of n and ε, the primal-dual method is the fastest, also in practice.
View details

Upward Max Min Fairness

Preview
Emilie Danna

Yishay Mansour

INFOCOM (2012)

Joint Cache Partition and Job Assignment on Multi-Core Processors

WADS'13: Proceedings of the 13th international conference on Algorithms and Data Structures (2012)

No Results Found