BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Himanshu Tyagi (IISc Bangalore)
DTSTART:20201120T180000Z
DTEND:20201120T190000Z
DTSTAMP:20260404T110643Z
UID:DataScienceFoundations/1
DESCRIPTION:Title: General lower bounds for estimation under informatio
n constraints\nby Himanshu Tyagi (IISc Bangalore) as part of Foundatio
ns of Data Science\n\n\nAbstract\nWe present very general lower bounds for
parametric estimation when only limited information per sample is allowed
. These limitations can arise\, for example\, in form of communication con
straints\, privacy constraints\, or linear measurements. Our lower bounds
hold for discrete distributions with large alphabet as well as continuous
distributions with high-dimensional parameters\, apply for any information
constraint\, and are valid for any $\\ell_p$ loss function. Our bounds re
cover both strong data processing inequality based bounds and Cramér-Rao
based bound as special cases.\n\nThis talk is based on joint work with Jay
adev Acharya and Clément Canonne.\n\nRegister to attend at https://docs.g
oogle.com/forms/d/e/1FAIpQLScoh-JZpgqveACNvFepKEtBObo6WEqUrjWVNSs_yt5EnO2p
Hw/viewform\n
LOCATION:https://stable.researchseminars.org/talk/DataScienceFoundations/1
/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Adam Smith (Boston University)
DTSTART:20201204T180000Z
DTEND:20201204T190000Z
DTSTAMP:20260404T110643Z
UID:DataScienceFoundations/2
DESCRIPTION:Title: When is Memorization of Irrelevant Training Data Nec
essary for High-Accuracy Learning?\nby Adam Smith (Boston University)
as part of Foundations of Data Science\n\n\nAbstract\nModern machine learn
ing models are complex\, and frequently encode surprising amounts of infor
mation about individual inputs. In extreme cases\, complex models appear t
o memorize entire input examples\, including seemingly irrelevant informat
ion (social security numbers from text\, for example). In this paper\, we
aim to understand whether this sort of memorization is necessary for accur
ate learning. We describe natural prediction problems in which every suffi
ciently accurate training algorithm must encode\, in the prediction model\
, essentially all the information about a large subset of its training exa
mples. This remains true even when the examples are high-dimensional and h
ave entropy much higher than the sample size\, and even when most of that
information is ultimately irrelevant to the task at hand. Further\, our re
sults do not depend on the training algorithm or the class of models used
for learning.\n\nOur problems are simple and fairly natural variants of th
e next-symbol prediction and the cluster labeling tasks. These tasks can b
e seen as abstractions of image- and text-related prediction problems. To
establish our results\, we reduce from a family of one-way communication p
roblems for which we prove new information complexity lower bounds.\n\nJoi
nt work with Gavin Brown\, Mark Bun\, Vitaly Feldman\, and Kunal Talwar.\n
LOCATION:https://stable.researchseminars.org/talk/DataScienceFoundations/2
/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Tim Roughgarden (Columbia University)
DTSTART:20210318T180000Z
DTEND:20210318T190000Z
DTSTAMP:20260404T110643Z
UID:DataScienceFoundations/3
DESCRIPTION:Title: Data-Driven Algorithm Design\nby Tim Roughgarden
(Columbia University) as part of Foundations of Data Science\n\n\nAbstrac
t\nThe best algorithm for a computational problem generally depends on the
“relevant inputs”\, a concept that depends on the application domain
and often defies formal articulation. While there is a large literature on
empirical approaches to selecting the best algorithm for a given applicat
ion domain\, there has been surprisingly little theoretical analysis of th
e problem.\n\n\nWe adapt concepts from statistical and online learning the
ory to reason about application-specific algorithm selection. Our models a
re straightforward to understand\, but also expressive enough to capture s
everal existing approaches in the theoretical computer science and AI comm
unities\, ranging from self-improving algorithms to empirical performance
models. We present one framework that models algorithm selection as a stat
istical learning problem\, and our work here shows that dimension notions
from statistical learning theory\, historically used to measure the comple
xity of classes of binary- and real-valued functions\, are relevant in a m
uch broader algorithmic context. We also study the online version of the a
lgorithm selection problem\, and give possibility and impossibility result
s for the existence of no-regret learning algorithms.\n\n\nJoint work with
Rishi Gupta.\n
LOCATION:https://stable.researchseminars.org/talk/DataScienceFoundations/3
/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Ingrid Daubechies (Duke University)
DTSTART:20210401T170000Z
DTEND:20210401T190000Z
DTSTAMP:20260404T110643Z
UID:DataScienceFoundations/4
DESCRIPTION:Title: Discovering low-dimensional manifolds in high-dimens
ional data sets\nby Ingrid Daubechies (Duke University) as part of Fou
ndations of Data Science\n\n\nAbstract\nThis talk reviews diffusion method
s to identify low-dimensional manifolds underlying high-dimensional datase
ts\, and illustrates that by pinpointing additional mathematical structure
\, improved results can be obtained. Much of the talk draws on a case stud
y from a collaboration with biological morphologists\, who compare differe
nt phenotypical structures to study relationships of living or extinct ani
mals with their surroundings and each other. This is typically done from c
arefully defined anatomical correspondence points (landmarks) on e.g. bone
s\; such landmarking draws on highly specialized knowledge. To make possib
le more extensive use of large (and growing) databases\, algorithms are re
quired for automatic morphological correspondence maps\, without any preli
minary marking of special features or landmarks by the user.\n\nMore infor
mation on https://sites.google.com/view/dstheory/home (abstract and speake
r biography).\n
LOCATION:https://stable.researchseminars.org/talk/DataScienceFoundations/4
/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Hamed Hassani (University of Pennsylvania)
DTSTART:20210506T180000Z
DTEND:20210506T190000Z
DTSTAMP:20260404T110643Z
UID:DataScienceFoundations/5
DESCRIPTION:Title: Learning Robust Models: How does the Geometry of Per
turbations Play a Role?\nby Hamed Hassani (University of Pennsylvania)
as part of Foundations of Data Science\n\n\nAbstract\nIn this talk\, we w
ill focus on the emerging field of (adversarially) robust machine learning
. The talk will be self-contained and no particular background on robust l
earning will be needed. Recent progress in this field has been accelerated
by the observation that despite unprecedented performance on clean data\,
modern learning models remain fragile to seemingly innocuous changes such
as small\, norm-bounded additive perturbations. Moreover\, recent work in
this field has looked beyond norm-bounded perturbations and has revealed
that various other types of distributional shifts in the data can signific
antly degrade performance. However\, in general our understanding of such
shifts is in its infancy and several key questions remain unaddressed.\n\n
\nThe goal of this talk is to explain why robust learning paradigms have t
o be designed — and sometimes rethought — based on the geometry of the
input perturbations. We will cover a wide range of perturbation geometrie
s from simple norm-bounded perturbations\, to sparse\, natural\, and more
general distribution shifts. As we will show\, the geometry of the perturb
ations necessitates fundamental modifications to the learning procedure as
well as the architecture in order to ensure robustness. In the first part
of the talk\, we will discuss our recent theoretical results on robust le
arning with respect to various geometries\, along with fundamental tradeof
fs between robustness and accuracy\, phase transitions\, etc. The remainin
g portion of the talk will be about developing practical robust training a
lgorithms and evaluating the resulting (robust) deep networks against stat
e-of-the-art methods on naturally-varying\, real-world datasets.\n
LOCATION:https://stable.researchseminars.org/talk/DataScienceFoundations/5
/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Christos Papadimitrious (Columbia University)
DTSTART:20210923T170000Z
DTEND:20210923T180000Z
DTSTAMP:20260404T110643Z
UID:DataScienceFoundations/6
DESCRIPTION:Title: How does the brain beget the mind?\nby Christos
Papadimitrious (Columbia University) as part of Foundations of Data Scienc
e\n\n\nAbstract\nHow do molecules\, cells and synapses effect reasoning\,
intelligence\, planning\, language? Despite dazzling progress in experim
ental neuroscience\, as well as in cognitive science at the other extreme
of scale\, we do not seem to be making progress in the overarching questio
n: the gap is huge and a completely new approach seems to be required. As
Richard Axel recently put it: "We don't have a logic for the transformat
ion of neural activity into thought [...]." \n\nWhat kind of formal syste
m would qualify as this "logic"? \n\nI will introduce the Assembly Calculu
s (AC)\, a computational system which appears to be a promising bridge bet
ween neurons and cognition. Through this programming framework\, a Parser
was recently implemented which (a) can handle reasonably complex sentence
s of English and other languages\, and (b) works exclusively through the s
piking of neurons.\n
LOCATION:https://stable.researchseminars.org/talk/DataScienceFoundations/6
/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Maxim Raginsky (University of Illinois at Urbana-Champaign)
DTSTART:20211021T170000Z
DTEND:20211021T180000Z
DTSTAMP:20260404T110643Z
UID:DataScienceFoundations/7
DESCRIPTION:by Maxim Raginsky (University of Illinois at Urbana-Champaign)
as part of Foundations of Data Science\n\nAbstract: TBA\n
LOCATION:https://stable.researchseminars.org/talk/DataScienceFoundations/7
/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Nicole Immorlica (Microsoft Research New England)
DTSTART:20211118T180000Z
DTEND:20211118T190000Z
DTSTAMP:20260404T110643Z
UID:DataScienceFoundations/8
DESCRIPTION:Title: Communicating with Anecdotes\nby Nicole Immorlic
a (Microsoft Research New England) as part of Foundations of Data Science\
n\n\nAbstract\nClassic models of communication in economics typically assu
me agents can communicate any message. However\, many important communicat
ions\, such as those in newspapers or politicians' speeches\, use data to
convey information. In this talk\, we explore how the reliance on data imp
acts communication. In our model\, there are two Bayesian agents (a sender
and a receiver) who wish to communicate. The receiver must take an action
whose payoff depends on their personal preferences and an unknown state o
f the world. The sender has access to a collection of data points correlat
ed with the state of the world and can send exactly one of these to the re
ceiver in order to influence her choice of action. Importantly\, the sende
r's personal preferences may differ from the receiver's\, which affects th
e sender's strategic choice of what to send. We show that in a Nash equili
brium even a small difference in preferences can lead to a significant bia
s in the communicated datum. This can significantly reduce informativeness
of the communication\, leading to substantial utility loss for both sides
. One implication is informational homophily: a receiver can rationally pr
efer to obtain data from a poorly-informed sender with aligned preferences
\, rather than a knowledgeable expert whose preferences may differ from he
r own.\n\n\nJoint work with Nika Haghtalab\, Brendan Lucier\, Markus Mobiu
s and Divya Mohan.\n
LOCATION:https://stable.researchseminars.org/talk/DataScienceFoundations/8
/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Eric Tchetgen Tchetgen (The Wharton School\, University of Pennsyl
vania)
DTSTART:20220316T200000Z
DTEND:20220316T210000Z
DTSTAMP:20260404T110643Z
UID:DataScienceFoundations/9
DESCRIPTION:Title: An Introduction to Proximal Causal Learning\nby
Eric Tchetgen Tchetgen (The Wharton School\, University of Pennsylvania) a
s part of Foundations of Data Science\n\n\nAbstract\nA standard assumption
for causal inference from observational data is that one has measured a s
ufficiently rich set of covariates to ensure that within covariates strata
\, subjects are exchangeable across observed treatment values. Skepticism
about the exchangeability assumption in observational studies is often war
ranted because it hinges on one’s ability to accurately measure covariat
es capturing all potential sources of confounding. Realistically\, confoun
ding mechanisms can rarely if ever\, be learned with certainty from measur
ed covariates. One can therefore only ever hope that covariate measurement
s are at best proxies of true underlying confounding mechanisms operating
in an observational study\, thus invalidating causal claims made on basis
of standard exchangeability conditions.\n\nCausal learning from proxies is
a challenging inverse problem which has to date remained unresolved. In t
his paper\, we introduce a formal potential outcome framework for proximal
causal learning\, which while explicitly acknowledging covariate measurem
ents as imperfect proxies of confounding mechanisms\, offers an opportunit
y to learn about causal effects in settings where exchangeability based on
measured covariates fails. Sufficient conditions for nonparametric identi
fication are given\, leading to the proximal g-formula and corresponding p
roximal g-computation algorithm for estimation\, both generalizations of R
obins’ foundational g-formula and g-computation algorithm\, which accoun
t explicitly for bias due to unmeasured confounding. Both point treatment
and time-varying treatment settings are considered\, and an application of
proximal g-computation of causal effects is given for illustration.\n
LOCATION:https://stable.researchseminars.org/talk/DataScienceFoundations/9
/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Gabriel Peyré (CNRS and Ecole Normale Supérieure)
DTSTART:20220420T190000Z
DTEND:20220420T200000Z
DTSTAMP:20260404T110643Z
UID:DataScienceFoundations/10
DESCRIPTION:Title: Scaling Optimal Transport for High dimensional Lear
ning\nby Gabriel Peyré (CNRS and Ecole Normale Supérieure) as part o
f Foundations of Data Science\n\n\nAbstract\nOptimal transport (OT) has re
cently gained lot of interest in machine learning. It is a natural tool to
compare in a geometrically faithful way probability distributions. It fin
ds applications in both supervised learning (using geometric loss function
s) and unsupervised learning (to perform generative model fitting). OT is
however plagued by the curse of dimensionality\, since it might require a
number of samples which grows exponentially with the dimension. In this ta
lk\, I will explain how to leverage entropic regularization methods to def
ine computationally efficient loss functions\, approximating OT with a bet
ter sample complexity. More information and references can be found on the
website of our book "Computational Optimal Transport" https://optimaltran
sport.github.io/\n
LOCATION:https://stable.researchseminars.org/talk/DataScienceFoundations/1
0/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Sébastien Bubeck (Microsoft Research)
DTSTART:20220511T200000Z
DTEND:20220511T210000Z
DTSTAMP:20260404T110643Z
UID:DataScienceFoundations/11
DESCRIPTION:Title: Set Chasing\, with an application to online shortes
t path\nby Sébastien Bubeck (Microsoft Research) as part of Foundatio
ns of Data Science\n\n\nAbstract\nSince the late 19th century\, mathematic
ians have realized the importance and generality of selection problems: gi
ven a collection of sets\, select an element in each set\, possibly in a "
nice" way. Of particular importance in computer science is the scenario wh
ere the ground set is a metric space\, in which case it is natural to ask
for *Lipschitz* selection. In this talk I will describe a far-reaching ext
ension of this classical Lipschitz selection problem to an *online* settin
g\, where sets are streaming to the selector. I will show how Riemannian g
radient descent (aka mirror descent) can be used to approach this type of
problems. I will illustrate the power of the framework by solving a long-s
tanding problem in online shortest path known as layered graph traversal (
introduced by Papadimitriou and Yannakakis in 1989).\n
LOCATION:https://stable.researchseminars.org/talk/DataScienceFoundations/1
1/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Shuchi Chawla (UT Austin)
DTSTART:20220406T200000Z
DTEND:20220406T210000Z
DTSTAMP:20260404T110643Z
UID:DataScienceFoundations/12
DESCRIPTION:Title: Pandora's Box with Correlations: Learning and Appro
ximation\nby Shuchi Chawla (UT Austin) as part of Foundations of Data
Science\n\n\nAbstract\nIn the Pandora's Box problem\, the algorithm is pro
vided with a number of boxes with unknown (stochastic) rewards contained i
nside them. The algorithm can open any box at some cost\, discover the rew
ard inside\, and based on these observations can choose one box and keep t
he reward contained in it. Given the distributions from which the rewards
are drawn\, the algorithm must determine an order in which to open the box
es as well as when to stop and accept the best reward found so far. In gen
eral\, an optimal algorithm may make both decisions adaptively based on in
stantiations observed previously. The Pandora's Box problem and its extens
ions capture many kinds of optimization problems with stochastic input whe
re the algorithm can obtain instantiations of input random variables at so
me cost. Previous work on these problems assumes that different random var
iables in the input are distributed independently. As such it does not cap
ture many real-world settings. In this work\, we provide the first algorit
hms for Pandora's Box-type problems with correlations. In the independent
setting\, optimal algorithms are non-adaptive and based on the notion of t
he Gittins index. These techniques fail to extend to the correlated case.
We assume that the algorithm has access to samples drawn from the joint di
stribution on input and provide solutions that require few samples\; are c
omputationally efficient\; and guarantee approximate optimality. This is j
oint work with Evangelia Gergatsouli\, Yifeng Teng\, Christos Tzamos\, and
Ruimin Zhang and appeared in FOCS'20.\n
LOCATION:https://stable.researchseminars.org/talk/DataScienceFoundations/1
2/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Ravi Kumar (Google)
DTSTART:20220615T200000Z
DTEND:20220615T210000Z
DTSTAMP:20260404T110643Z
UID:DataScienceFoundations/13
DESCRIPTION:Title: (Date to be confirmed)\nby Ravi Kumar (Google)
as part of Foundations of Data Science\n\nAbstract: TBA\n
LOCATION:https://stable.researchseminars.org/talk/DataScienceFoundations/1
3/
END:VEVENT
END:VCALENDAR