Nishant Mehta | Sample compression schemes for VC classes

Sample compression schemes for VC classes Shay Moran and Amir Yehudayoff (Journal of the ACM, 2016)
  • When Aug 25, 2016 from 11:00 AM to 01:00 PM (Europe/Amsterdam / UTC200)
  • Where CWI, L236
  • Add event to calendar iCal

I'll discuss a recent result that provides the first-ever compression scheme for VC classes that depends only on the VC dimension (although it is exponential in the VC dimension in the worst case). The paper itself is quite elegant and essentially just 10 pages.

Since not everyone may have the requisite background, I will start by giving an ultra-quick summary of VC dimension and VC classes. However, things will go much smoother if you can get familiarity with VC dimension beforehand (there is a multitude of lecture notes available online, in addition to explanations in basically any machine learning textbook; I am happy to provide pointers, just ask).

I'll then explain both boosting and compression schemes (and how they are connected), but only in enough detail for our discussion. Their connection forms a very nice introduction to the proof of the main result of the paper. If you are interested further, take a look at Chapter 4.2 and Chapter 13.1 of Boosting: Foundations and Algorithms (you can ask me for pdf access).

Finally, I'll present some ideas related to the proof of the paper's main result and then sketch the (short!) proof itself.