PhD Seminar • Algorithms and Complexity — VC Dimension and Distribution-Free Sample-Based TestingExport this event to calendar

Wednesday, April 21, 2021 — 1:00 PM EDT

Please note: This PhD seminar will be given online.

Nathan Harms, PhD candidate
David R. Cheriton School of Computer Science

Supervisor: Professor Eric Blais

We consider the problem of determining which classes of functions can be tested more efficiently than they can be learned, in the distribution-free sample-based model that corresponds to the standard PAC learning setting. Our main result shows that while VC dimension by itself does not always provide tight bounds on the number of samples required to test a class of functions in this model, it can be combined with a closely-related variant that we call “lower VC” (or LVC) dimension to obtain strong lower bounds on this sample complexity.

We use this result to obtain strong and in many cases nearly optimal bounds on the sample complexity for testing unions of intervals, halfspaces, intersections of halfspaces, polynomial threshold functions, and decision trees. Conversely, we show that two natural classes of functions, juntas and monotone functions, can be tested with a number of samples that is polynomially smaller than the number of samples required for PAC learning.

Finally, we also use the connection between VC dimension and property testing to establish new lower bounds for testing radius clusterability and testing feasibility of linear constraint systems.


To join this PhD seminar on Zoom, please go to https://zoom.us/j/95246898752?pwd=Q040ZC90Tjc0NWxXc3JRc0plcE8zdz09.

Location 
Online PhD seminar
200 University Avenue West

Waterloo, ON N2L 3G1
Canada
Event tags 

S M T W T F S
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
3
  1. 2021 (114)
    1. July (8)
    2. June (11)
    3. May (16)
    4. April (27)
    5. March (20)
    6. February (13)
    7. January (19)
  2. 2020 (217)
    1. December (18)
    2. November (12)
    3. October (7)
    4. September (21)
    5. August (28)
    6. July (14)
    7. June (18)
    8. May (16)
    9. April (20)
    10. March (16)
    11. February (25)
    12. January (22)
  3. 2019 (255)
  4. 2018 (217)
  5. 2017 (36)
  6. 2016 (21)
  7. 2015 (36)
  8. 2014 (33)
  9. 2013 (23)
  10. 2012 (4)
  11. 2011 (1)
  12. 2010 (1)
  13. 2009 (1)
  14. 2008 (1)