0.25
0.5
0.75
1.25
1.5
1.75
2
Learning Halfspaces Under Log-Concave Densities: Polynomial Approximations and Moment Matching
Published on Aug 09, 20133114 Views
We give the first polynomial-time algorithm for agnostically learning any function of a constant number of halfspaces with respect to any log-concave distribution (for any constant accuracy parameter)
Related categories
Chapter list
Learning Intersections of Halfspaces: Smooth Analysis and Log-Concavity00:00
Halfspaces00:03
Two Natural Generalizations00:46
Previous Work - 101:25
Previous Work - 201:39
Previous Work: Hardness - 101:59
Previous Work: Hardness - 202:20
Previous Work: Hardness - 302:42
Previous Work: Hardness - 403:24
Log-Concave Distributions - 103:37
Log-Concave Distributions - 203:58
Log-Concave Distributions - 304:13
Log-Concave Distributions - 404:56
Log-Concave Distributions - 505:10
Smoothed Analysis06:00
Smoothed Analysis for PAC [BD02] - 106:48
Smoothed Analysis for PAC [BD02] - 207:17
Smoothed Analysis for PAC [BD02] - 308:03
Smoothed Analysis for PAC09:38
Outline of Talk - 110:44
Outline of Talk - 211:05
Tools: Polynomial approximation - 111:07
Tools: Polynomial approximation - 211:29
New Methods for Polynomial approximation12:11
Outline of Talk - 312:58
Outline of Talk - 413:02
Approximation by Convolution - 113:06
Approximation by Convolution - 213:22
Approximation by Convolution - 313:47
Approximation by Convolution - 514:04
Approximation by Convolution - 615:27
Approximation by Convolution - 715:47
Approximation by Convolution - 816:05
Approximation by Convolution - 916:30
Approximation by Convolution - 1016:41
Outline of Talk - 517:01
Approximation by Pseudorandomness - 117:06
Approximation by Pseudorandomness - 217:43
Approximation by Pseudorandomness, LP Duality - 117:54
Approximation by Pseudorandomness, LP Duality - 218:05
Approximation by Pseudorandomness, LP Duality - 318:23
Approximation by Pseudorandomness, LP Duality - 418:43
Classical Moment Problem - 119:07
Classical Moment Problem - 219:40
Moment Problem: Robust version - 120:09
Moment Problem: Robust version - 220:20
Moment Problem: Robust version - 320:54
Moment Problem: Robust version - 420:57
Moment Matching Polynomials 21:10
Application 1: Log-Concave - 121:14
Application 1: Log-Concave - 221:36
Application 1: Log-Concave - 321:39
Application 1: Log-Concave - 421:52