Title: Differential Privacy in the Streaming Model
| Speaker: | Jalaj Upadhyay |
| Affiliation: | University of Waterloo |
| Room: | MC 6486 |
Abstract:
In
this
talk,
we
will
explore
differentially
private
algorithms
when
the
private
data
is
streamed
online.
In
the
first
part
of
the
talk,
we
present
almost
optimal
space
data-structures
that
can
be
used
to
compute
low
rank
approximation
and
linear
regression
on
streamed
data
while
preserving
differential
privacy.
Notably,
we
match
the
best
known
space
bound
in
the
non-private
setting
by
Kane
and
Nelson
(JACM:
61(1)).
At
the
core
of
all
our
private
algorithms
is
an
algorithm
for
private-sketch
generation
(PSG).
In
the
second
part
of
our
talk,
we
discuss
a
new
distribution
of
random
matrices
that
satisfies
the
Johnson-Lindenstrauss
transform
and
also
preserves
differential
privacy.
We
then
show
how
to
use
a
random
matrix
picked
from
this
distribution
in
PSG
to
get
update
time
efficiency
without
increasing
the
space
requirements
of
our
data-structures
and
without
effecting
the
privacy
guarantee.
Time
permitting,
we
will
also
explore
the
application
of
PSG
in
differentially
private
manifold
learning.
The
presentation
will
be
based
on
the
following
manuscripts:
http://arxiv.org/abs/1409.5414
http://arxiv.org/abs/1410.2470