BEGIN:VCALENDAR VERSION:2.0 PRODID:-//128.220.13.64//NONSGML kigkonsult.se iCalcreator 2.20// CALSCALE:GREGORIAN METHOD:PUBLISH X-FROM-URL:https://www.cs.jhu.edu/~mdinitz/theory X-WR-TIMEZONE:America/New_York BEGIN:VTIMEZONE TZID:America/New_York X-LIC-LOCATION:America/New_York BEGIN:STANDARD DTSTART:20231105T020000 TZOFFSETFROM:-0400 TZOFFSETTO:-0500 TZNAME:EST END:STANDARD BEGIN:DAYLIGHT DTSTART:20240310T020000 TZOFFSETFROM:-0500 TZOFFSETTO:-0400 TZNAME:EDT END:DAYLIGHT END:VTIMEZONE BEGIN:VEVENT UID:ai1ec-353@www.cs.jhu.edu/~mdinitz/theory DTSTAMP:20240319T084359Z CATEGORIES: CONTACT: DESCRIPTION:
Speaker: Audra McMillan
\nAffiliation: Apple
Ti tle: Hiding among the clones: a simple and nearly optimal analysis of priv acy amplification by shuffling
\nAbstract:
\nDifferential priva
cy (DP) is a model of privacy-preserving machine learning that has garnere
d significant interest in recent years due to its rigorous privacy guarant
ees. An algorithm differentially private if the output is stable under sma
ll changes in the input database. While DP has been adopted in a variety o
f applications\, most applications of DP in industry actually satisfy a st
ronger notion called local differential privacy. In local differential pri
vacy data subjects perturb their data before it reaches the data analyst.
While this requires less trust\, it comes a substantial cost to accuracy.
Recent work of Erlingsson\, Feldman\, Mironov\, Raghunathan\, Talwar\, and
Thakurta [EFMRTT19] demonstrated that random shuffling amplifies differen
tial privacy guarantees of locally randomized data. Such amplification imp
lies substantially stronger privacy guarantees for systems in which data i
s contributed anonymously [BEMMRLRKTS17] and has led to significant intere
st in the shuffle model of privacy [CSUZZ19\, EFMRTT19]. In this talk\, we
will discuss a new result on privacy amplification by shuffling\, which a
chieves the asymptotically optimal dependence in the local privacy paramet
er. Our result is based on a new proof strategy which is simpler than prev
ious approaches\, and extends to a lightly weaker notion known as approxim
ate differential privacy with nearly the same guarantees. Based on joint w
ork with Vitaly Feldman and Kunal Talwar (https://arxiv.org/abs/2012.12803
)
Speaker: Maryam Negahbani
\nAffiliation: Dartmouth Univ
ersity
Title: “Revisiting Priority k-Center: Fairness and Outliers
\nAbstract:
\nClustering is a fundamental unsupervised learnin
g and facility location problem extensively studied in the literature. I w
ill talk about a clustering problem called “priority k-center” introduced
by Plesnik (in Disc. Appl. Math. 1987). Given a metric space on n points
X\, with distance function d\, an integer k\, and radius r_v for each poin
t v in X\, the goal is to choose k points S as “centers” to minimize the m
aximum distance of a point v to S divided by r_v. For uniform r_v’s this i
s precisely the “k-center” problem where the objective is to minimize the
maximum distance of any point to S. In the priority version\, points with
smaller r_v are prioritized to be closer to S. Recently\, a special case o
f this problem was studied in the context of “individually fair clustering
” by Jung et al.\, FORC 2020. This notion of fairness forces S to open a
center in every “densely populated area” by setting r_v to be v’s distance
to its closest (n/k)-th neighbor.
In this talk\, I show how to ap proximate priority k-center with outliers: When for a given integer z\, yo u are allowed to throw away z points as outliers and minimize the objectiv e over the rest of the points. We show there is 9-approximation\, which is morally a 5\, if you have constant many types of radii or if your radii a re powers of 2. This is via an LP-aware reduction to min-cost max-flow and is general enough that could handle Matroid constraints on facilities (wh ere instead of asking to pick at most k facilities\, you are asked to pick facilities that are independent in a given matroid). Things become quite interesting for priority knapsack-center with outliers: where opening each center costs something and you have a limited budget to spend on your sol ution S. In this case\, we do not know how to solve the corresponding flow problem\, so we alter our reduction to reduce to a simpler problem we do know how to solve taking a hit of +5 in the approximation ratio. There are still many open problems in this work\, in addition to solving the flow p roblem in the knapsack case\, the best LP integrality gap we know for prio rity k-center with outliers is 3.
DTSTART;TZID=America/New_York:20210331T120000 DTEND;TZID=America/New_York:20210331T130000 LOCATION:https://wse.zoom.us/j/91450299380 SEQUENCE:0 SUMMARY:[Theory Seminar] Maryam Negahbani URL:https://www.cs.jhu.edu/~mdinitz/theory/event/theory-seminar-maryam-nega hbani/ X-COST-TYPE:free END:VEVENT BEGIN:VEVENT UID:ai1ec-346@www.cs.jhu.edu/~mdinitz/theory DTSTAMP:20240319T084359Z CATEGORIES: CONTACT: DESCRIPTION:Speaker: Leonidas Tsepenekas
\nAffiliation: University
of Maryland
Title: Approximating Two-Stage Stochastic Supplier Pro blems
\nAbstract:
\nThe main focus of this talk will be radius-
based (supplier) clustering in the two-stage stochastic setting with recou
rse\, where the inherent stochasticity of the model comes in the form of a
budget constraint. Our eventual goal is to provide results in the most ge
neral distributional setting\, where there is only black-box access to the
underlying distribution. To that end\, we follow a two-step approach. Fir
st\, we develop algorithms for a restricted version of the problem\, in wh
ich all possible scenarios are explicitly provided\; second\, we employ a
novel scenario-discarding variant of the standard Sample Average Approxima
tion (SAA) method\, in which we also crucially exploit structural properti
es of the algorithms developed for the first step of the framework. In thi
s way\, we manage to generalize the results of the latter to the black-box
model. Finally\, we note that the scenario-discarding modification to the
SAA method is necessary in order to optimize over the radius.
Pap er: https://arxiv.org/abs/2008.03325
DTSTART;TZID=America/New_York:20210407T120000 DTEND;TZID=America/New_York:20210407T130000 LOCATION:https://wse.zoom.us/j/91450299380 SEQUENCE:0 SUMMARY:[Theory Seminar] Leonidas Tsepenekas URL:https://www.cs.jhu.edu/~mdinitz/theory/event/theory-seminar-leonidas-ts epenekas/ X-COST-TYPE:free END:VEVENT BEGIN:VEVENT UID:ai1ec-358@www.cs.jhu.edu/~mdinitz/theory DTSTAMP:20240319T084359Z CATEGORIES: CONTACT: DESCRIPTION:Speaker: Samson Zhou
\nAffiliation: Carnegie Mellon Uni
versity
Title: Tight Bounds for Adversarially Robust Streams and S liding Windows via Difference Estimators
\nAbstract:
\nWe intro
duce difference estimators for data stream computation\, which pr
ovide approximations to F(v)-F(u) for frequency vectors v\,u and a given f
unction F. We show how to use such estimators to carefully trade error for
memory in an iterative manner. The function F is generally non-linear\, a
nd we give the first difference estimators for the frequency moments F_p f
or p between 0 and 2\, as well as for integers p>2. Using these\, we resol
ve a number of central open questions in adversarial robust streaming and
sliding window models.
For both models\, we obtain algorithms for norm estimation whose dependence on epsilon is 1/epsilon^2\, which shows\, up to logarithmic factors\, that there is no overhead over the standard i nsertion-only data stream model for these problems.
DTSTART;TZID=America/New_York:20210414T120000 DTEND;TZID=America/New_York:20210414T130000 SEQUENCE:0 SUMMARY:[Theory Seminar] Samson Zhou URL:https://www.cs.jhu.edu/~mdinitz/theory/event/theory-seminar-samson-zhou -3/ X-COST-TYPE:free END:VEVENT BEGIN:VEVENT UID:ai1ec-376@www.cs.jhu.edu/~mdinitz/theory DTSTAMP:20240319T084359Z CATEGORIES: CONTACT: DESCRIPTION: DTSTART;TZID=America/New_York:20230906T120000 DTEND;TZID=America/New_York:20230906T130000 SEQUENCE:0 SUMMARY:[Theory Seminar] Welcome Back / Introductions URL:https://www.cs.jhu.edu/~mdinitz/theory/event/theory-seminar-welcome-bac k-introductions/ X-COST-TYPE:free END:VEVENT BEGIN:VEVENT UID:ai1ec-372@www.cs.jhu.edu/~mdinitz/theory DTSTAMP:20240319T084359Z CATEGORIES: CONTACT: DESCRIPTION:Speaker: Zeyu Guo
\nAffiliation: Ohio State University<
/p>\n
Title: TBD
\nAbstract: TBD
DTSTART;TZID=America/New_York:20231025T120000 DTEND;TZID=America/New_York:20231025T130000 SEQUENCE:0 SUMMARY:[Theory Seminar] Zeyu Guo URL:https://www.cs.jhu.edu/~mdinitz/theory/event/theory-seminar-zeyu-guo/ X-COST-TYPE:free END:VEVENT END:VCALENDAR