Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Sample compression schemes for VC classes
Speaker:Shay Moran
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:MPI Audience
Date, Time and Location
Date:Thursday, 9 July 2015
Duration:45 Minutes
Building:E1 4
Sample compression schemes were defined by Littlestone and Warmuth (1986)

as an abstraction of the structure underlying many learning algorithms.
Roughly speaking, a sample compression scheme of size $k$ means that given an arbitrary list of labeled examples, one can retain only $k$ of them in a way that allows to recover the labels of all other examples in the list. They showed that compression implies PAC learnability for binary-labeled classes, and asked whether the other direction holds.
We answer their question and show that every concept class $C$ with VC dimension $d$ has a sample compression scheme of size exponential in $d$.
The proof uses an approximate minimax phenomenon for binary matrices of low VC dimension, which may be of interest in the context of game theory.

Joint work with Amir Yehudayoff

The talk will assume no previous knowledge in machine learning.
The talk will take 45 minutes.

Link to paper:

Name(s):Shay Moran
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):

Created by:Shay Moran, 06/02/2015 09:58 PMLast modified by:Uwe Brahm/MPII/DE, 11/24/2016 04:13 PM
  • Shay Moran, 07/07/2015 02:54 PM
  • Shay Moran, 06/13/2015 12:27 PM
  • Shay Moran, 06/02/2015 10:00 PM
  • Shay Moran, 06/02/2015 09:58 PM -- Created document.