Timezone: »
Poster
Learning to Screen
Alon Cohen · Avinatan Hassidim · Haim Kaplan · Yishay Mansour · Shay Moran
Wed Dec 11 10:45 AM -- 12:45 PM (PST) @ East Exhibition Hall B + C #224
Imagine a large firm with multiple departments that plans a large recruitment.
Candidates arrive one-by-one, and for each candidate
the firm decides, based on her data (CV, skills, experience, etc),
whether to summon her for an interview.
The firm wants to recruit the best candidates while minimizing the number of interviews.
We model such scenarios as an assignment problem between items (candidates) and categories (departments):
the items arrive one-by-one in an online manner,
and upon processing each item the algorithm decides,
based on its value and the categories it can be matched with,
whether to retain or discard it (this decision is irrevocable).
The goal is to retain as few items as possible while guaranteeing
that the set of retained items contains an optimal matching.
We consider two variants of this problem:
(i) in the first variant it is assumed that the $n$ items are drawn independently
from an unknown distribution $D$.
(ii) In the second variant it is assumed that before the process starts,
the algorithm has an access to a training set of $n$ items drawn independently
from the same unknown distribution (e.g.\ data of candidates from previous recruitment seasons).
We give tight bounds on the minimum possible number of retained items in each of these variants.
These results demonstrate that one can retain exponentially less items in the second variant (with the training set).
Our algorithms and analysis utilize ideas and techniques from statistical learning theory and from discrete algorithms.
Author Information
Alon Cohen (Google)
Avinatan Hassidim (Google)
Haim Kaplan (TAU, GOOGLE)
Yishay Mansour (Tel Aviv University / Google)
Shay Moran (Google AI Princeton)
More from the Same Authors
-
2020 Poster: Sample Complexity of Uniform Convergence for Multicalibration »
Eliran Shabat · Lee Cohen · Yishay Mansour -
2020 Poster: Prediction with Corrupted Expert Advice »
Idan Amir · Idan Attias · Tomer Koren · Yishay Mansour · Roi Livni -
2020 Spotlight: Prediction with Corrupted Expert Advice »
Idan Amir · Idan Attias · Tomer Koren · Yishay Mansour · Roi Livni -
2020 Poster: Adversarially Robust Streaming Algorithms via Differential Privacy »
Avinatan Hasidim · Haim Kaplan · Yishay Mansour · Yossi Matias · Uri Stemmer -
2020 Poster: Private Learning of Halfspaces: Simplifying the Construction and Reducing the Sample Complexity »
Haim Kaplan · Yishay Mansour · Uri Stemmer · Eliad Tsfadia -
2020 Poster: Synthetic Data Generators -- Sequential and Private »
Olivier Bousquet · Roi Livni · Shay Moran -
2020 Poster: Learning from Mixtures of Private and Public Populations »
Raef Bassily · Shay Moran · Anupama Nandi -
2020 Poster: Online Agnostic Boosting via Regret Minimization »
Nataly Brukhim · Xinyi Chen · Elad Hazan · Shay Moran -
2020 Poster: A Limitation of the PAC-Bayes Framework »
Roi Livni · Shay Moran -
2020 Poster: An Optimal Elimination Algorithm for Learning a Best Arm »
Avinatan Hassidim · Ron Kupfer · Yaron Singer -
2020 Spotlight: An Optimal Elimination Algorithm for Learning a Best Arm »
Avinatan Hassidim · Ron Kupfer · Yaron Singer -
2020 Oral: Adversarially Robust Streaming Algorithms via Differential Privacy »
Avinatan Hasidim · Haim Kaplan · Yishay Mansour · Yossi Matias · Uri Stemmer -
2019 Poster: Online Stochastic Shortest Path with Bandit Feedback and Unknown Transition Function »
Aviv Rosenberg · Yishay Mansour -
2019 Poster: Private Learning Implies Online Learning: An Efficient Reduction »
Alon Gonen · Elad Hazan · Shay Moran -
2019 Spotlight: Private Learning Implies Online Learning: An Efficient Reduction »
Alon Gonen · Elad Hazan · Shay Moran -
2019 Poster: Graph-based Discriminators: Sample Complexity and Expressiveness »
Roi Livni · Yishay Mansour -
2019 Poster: An adaptive nearest neighbor rule for classification »
Akshay Balsubramani · Sanjoy Dasgupta · yoav Freund · Shay Moran -
2019 Spotlight: An adaptive nearest neighbor rule for classification »
Akshay Balsubramani · Sanjoy Dasgupta · yoav Freund · Shay Moran -
2019 Spotlight: Graph-based Discriminators: Sample Complexity and Expressiveness »
Roi Livni · Yishay Mansour -
2019 Poster: Limits of Private Learning with Access to Public Data »
Raef Bassily · Shay Moran · Noga Alon -
2019 Poster: Individual Regret in Cooperative Nonstochastic Multi-Armed Bandits »
Yogev Bar-On · Yishay Mansour -
2017 Poster: Submultiplicative Glivenko-Cantelli and Uniform Convergence of Revenues »
Noga Alon · Moshe Babaioff · Yannai A. Gonczarowski · Yishay Mansour · Shay Moran · Amir Yehudayoff -
2017 Spotlight: Submultiplicative Glivenko-Cantelli and Uniform Convergence of Revenues »
Noga Alon · Moshe Babaioff · Yannai A. Gonczarowski · Yishay Mansour · Shay Moran · Amir Yehudayoff -
2016 Poster: Online Pricing with Strategic and Patient Buyers »
Michal Feldman · Tomer Koren · Roi Livni · Yishay Mansour · Aviv Zohar -
2016 Poster: Supervised learning through the lens of compression »
Ofir David · Shay Moran · Amir Yehudayoff -
2016 Oral: Supervised learning through the lens of compression »
Ofir David · Shay Moran · Amir Yehudayoff -
2013 Poster: From Bandits to Experts: A Tale of Domination and Independence »
Noga Alon · Nicolò Cesa-Bianchi · Claudio Gentile · Yishay Mansour -
2013 Oral: From Bandits to Experts: A Tale of Domination and Independence »
Noga Alon · Nicolò Cesa-Bianchi · Claudio Gentile · Yishay Mansour