[Theory] 1/9 Talks at TTIC: Sumegha Garg, Princeton University

[Mary Marre]

*When:*      Thursday, January 9th at 11:00 am



*Where:*     TTIC, 6045 S. Kenwood Avenue, 5th Floor, Room 526



*Who: *       Sumegha Garg, Princeton University


*Title*: Understanding the Limits of Space-Bounded and Fair Learning
Algorithms

*Abstract*: Machine learning has been a growing field since the 1960s with
a wide variety of applications. With the increasing scale of problems, it
has become both practically and philosophically important to study the
feasibility of learning under memory constraints. Secondarily, as machine
learning algorithms are increasingly being deployed for making decisions on
humans, for example, in healthcare, hiring, loan decisions or policing,
fears that these systems may inadvertently discriminate against members of
underrepresented populations have grown. This necessitates the development
of a theory of algorithmic fairness that studies the feasibility of fair
learning and gives theoretical guarantees for limiting the harm caused by
automated decision making on humans.

A recent line of works has focused on the following question: Can one prove
strong lower bounds on the number of samples needed for learning under
memory constraints? In the first part of the talk, we develop an
extractor-based approach to prove memory-sample tradeoffs for a large class
of learning problems and extend it to even when the learner is allowed a
second pass over the stream of samples.

In the second part of the talk, we will investigate the role of information
in fair prediction algorithms. We prove that at times, the cost associated
with requiring fairness should be blamed on a lack of information about
important subpopulations, not on the fairness desideratum itself.


Host: Yury Makarychev <yury at ttic.edu>



Mary C. Marre
Administrative Assistant
*Toyota Technological Institute*
*6045 S. Kenwood Avenue*
*Room 517*
*Chicago, IL  60637*
*p:(773) 834-1757*
*f: (773) 357-6970*
*mmarre at ttic.edu <mmarre at ttic.edu>*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20200102/74ef7aa2/attachment-0001.html>