Title: Point Location and Active Learning - Learning Halfspaces Almost Optimally
| Speaker: | Shachar Lovett |
| Affiliation: | UC San Diego |
| Zoom: | Please email Emma Watson |
Abstract:
The
point
location
problem
is
a
central
problem
in
computational
geometry.
It
asks,
given
a
known
partition
of
R^d
by
n
hyperplanes,
and
an
unknown
input
point,
to
find
the
cell
in
the
partition
to
which
the
input
point
belongs.
The
access
to
the
input
is
via
linear
queries.
A
linear
query
is
specified
by
an
hyperplane,
and
the
result
of
the
query
is
which
side
of
the
hyperplane
the
input
point
lies
in.
A
dual
problem
is
active
learning
of
half-spaces,
a
well-studied
problem
in
machine
learning.
Here,
there
are
n
known
points
in
R^d,
and
an
unknown
input
hyperplane.
Each
point
is
labeled
by
the
side
of
the
input
hyperplane
it
lies
in.
The
goal
is
to
find
the
labels
of
all
n
given
points,
by
making
a
few
linear
queries,
where
a
linear
query
amounts
to
querying
the
label
of
an
arbitrary
point.
There
is
a
simple
lower
bound
that
shows
that
Omega(d
log
n)
queries
may
be
needed.
In
a
series
of
works
spanning
the
last
40
years,
the
best
upper
bound
has
been
O(d^2
log
d
log
n),
leaving
a
quadratic
gap
between
the
lower
and
upper
bounds
dependence
on
the
dimension
d.
In
this
work,
we
improve
this
to
a
near-linear
dependency.
The
proof
combines
previous
geometric
and
combinatorial
techniques
combined
with
a
new
structural
decomposition.
Joint
work
with
Max
Hopkins,
Daniel
Kane
and
Gaurav
Mahajan.