Learning Theory from First Principles

Preface ix I Preliminaries 1 1 Mathematical preliminaries 3 1.1 Linear algebra and differentiable calculus.................. 3 1.1.1 Minimization of quadratic forms................... 3 1.1.2 Inverting a 2 × 2 matrix........................ 4 1.1.3 Inverting matrices defined by blocks, matrix inversion lemma... 4 1.1.4 Eigenvalue and singular value decomposition............ 6 1.1.5 Differential calculus.......................... 7 1.2 Concentration inequalities........................... 7 1.2.1 Hoeffding’s inequality......................... 9 1.2.2 McDiarmid’s inequality........................ 12 1.2.3 Bernstein’s inequality (_x0007_)....................... 14 1.2.4 Expectation of the maximum..................... 16 1.2.5 Estimation of expectations through quadrature (_x0007_)......... 17 1.2.6 Concentration inequalities for matrices (_x0007__x0007_)............. 18 2 Introduction to supervised learning 21 2.1 From training data to predictions....................... 22 2.2 Decision theory................................. 25 2.2.1 Loss functions............................. 25 2.2.2 Risks................................... 26 2.2.3 Bayes risk and Bayes predictor.................... 27 2.3 Learning from data............................... 30 2.3.1 Local averaging............................. 30 2.3.2 Empirical risk minimization...................... 31 2.4 Statistical learning theory........................... 33 2.4.1 Measures of performance....................... 35 2.4.2 Notions of consistency over classes of problems........... 35 2.5 No free lunch theorems (_x0007_).......................... 36 2.6 Quest for adaptivity.............................. 38 2.7 Beyond supervised learning.......................... 39 2.8 Summary - book outline............................ 40 3 Linear least-squares regression 43 3.1 Introduction................................... 43 3.2 Least-squares framework............................ 44 3.3 Ordinary least-squares (OLS) estimator................... 45 3.3.1 Closed-form solution.......................... 45 3.3.2 Geometric interpretation........................ 46 3.3.3 Numerical resolution.......................... 47 3.4 Statistical analysis of OLS........................... 47 3.5 Fixed design setting.............................. 48 3.5.1 Statistical properties of the OLS estimator............. 50 3.5.2 Experiments.............................. 52 3.6 Ridge least-squares regression......................... 53 3.7 Lower-bound (_x0007_)................................ 57 3.8 Random design analysis............................ 59 3.8.1 Gaussian designs............................ 61 3.8.2 General designs (_x0007__x0007_)......................... 61 3.9 Principal component analysis (_x0007_)....................... 63 3.10 Conclusion................................... 65 II Generalization bounds for learning algorithms 67 4 Empirical risk minimization 69 4.1 Convexification of the risk........................... 70 4.1.1 Convex surrogates........................... 71 4.1.2 Geometric interpretation of the support vector machine (_x0007_).... 72 4.1.3 Conditional Φ-risk and classification calibration (_x0007_)........ 74 4.1.4 Relationship between risk and Φ-risk (_x0007__x0007_).............. 76 4.2 Risk minimization decomposition....................... 80 4.3 Approximation error.............................. 80 4.4 Estimation error................................ 81 4.4.1 Application of McDiarmid’s inequality................ 82 4.4.2 Easy case I: quadratic functions.................... 83 4.4.3 Easy case II: Finite number of models................ 84 4.4.4 Beyond finitely many models through covering numbers (_x0007_)... 84 4.5 Rademacher complexity............................ 86 4.5.1 Symmetrization............................. 87 4.5.2 Lipschitz-continuous losses...................... 89 4.5.3 Ball-constrained linear predictions.................. 91 4.5.4 Putting things together (linear predictions)............. 92 4.5.5 From constrained to regularized estimation (_x0007_)........... 93 4.5.6 Extensions and improvements..................... 96 4.6 Model selection (_x0007_)............................... 98 4.6.1 Structural risk minimization...................... 98 4.6.2 Selection based on validation set................... 99 4.7 Relationship with asymptotic statistics (_x0007_)................. 99 4.8 Summary.................................... 101 5 Optimization for machine learning 103 5.1 Optimization in machine learning....................... 103 5.2 Gradient descent................................ 105 5.2.1 Simplest analysis: ordinary least-squares............... 106 5.2.2 Convex functions and their properties................ 110 5.2.3 Analysis of GD for strongly convex and smooth functions..... 112 5.2.4 Analysis of GD for convex and smooth functions (_x0007_)....... 117 5.2.5 Beyond gradient descent (_x0007_)..................... 120 5.2.6 Non-convex objective functions (_x0007_)................. 122 5.3 Gradient methods on non-smooth problems................. 123 5.4 Convergence rate of stochastic gradient descent (SGD)........... 127 5.4.1 Strongly convex problems (_x0007_).................... 132 5.4.2 Adaptive methods (_x0007_)......................... 134 5.4.3 Bias-variance trade-offs for least-squares (_x0007_)............. 135 5.4.4 Variance reduction (_x0007_)........................ 138 5.5 Conclusion................................... 143 6 Local averaging methods 145 6.1 Introduction................................... 145 6.2 Local averaging methods............................ 147 6.2.1 Linear estimators............................ 147 6.2.2 Partition estimators.......................... 148 6.2.3 Nearest-neighbors........................... 150 6.2.4 Nadaraya-Watson estimator a.k.a. kernel regression (_x0007_)...... 151 6.3 Generic “simplest” consistency analysis................... 153 6.3.1 Fixed partition............................. 155 6.3.2 k-nearest neighbor........................... 158 6.3.3 Kernel regression (Nadaraya-Watson) (_x0007_).............. 160 6.4 Universal consistency (_x0007_)........................... 163 6.5 Adaptivity (_x0007__x0007_)................................ 166 6.6 Conclusion................................... 167 7 Kernel methods 169 7.1 Introduction................................... 170 7.2 Representer theorem.............................. 170 7.3 Kernels..................................... 173 7.3.1 Linear and polynomial kernels.................... 175 7.3.2 Translation-invariant kernels on [0, 1]................. 176 7.3.3 Translation-invariant kernels on Rd.................. 179 7.3.4 Beyond vectorial input spaces (_x0007_).................. 182 7.4 Algorithms................................... 184 7.4.1 Representer theorem.......................... 184 7.4.2 Column sampling............................ 185 7.4.3 Random features............................ 185 7.4.4 Dual algorithms (_x0007_).......................... 186 7.4.5 Stochastic gradient descent (_x0007_).................... 187 7.4.6 “Kernelization” of linear algorithms................. 188 7.5 Generalization guarantees - Lipschitz-continuous losses........... 189 7.5.1 Risk decomposition........................... 190 7.5.2 Approximation error for translation-invariant kernels on Rd.... 191 7.6 Theoretical analysis of ridge regression (_x0007_)................. 194 7.6.1 Kernel ridge regression as a “linear” estimator........... 194 7.6.2 Bias and variance decomposition (_x0007_)................ 195 7.6.3 Relating empirical and population covariance operators...... 198 7.6.4 Analysis for well-specified problems (_x0007_)............... 200 7.6.5 Analysis beyond well-specified problems (_x0007_)............. 201 7.6.6 Balancing bias and variance (_x0007_)................... 202 7.7 Experiments................................... 203 7.8 Conclusion................................... 205 8 Sparse methods 207 8.1 Introduction................................... 207 8.1.1 Dedicated proof technique for constrained least-squares...... 209 8.1.2 Probabilistic and combinatorial lemmas............... 210 8.2 Variable selection by the ℓ0-penalty...................... 212 8.2.1 Assuming k is known.......................... 212 8.2.2 Estimating k (_x0007_)............................ 214 8.3 Variable selection by ℓ1-regularization.................... 216 8.3.1 Intuition and algorithms........................ 217 8.3.2 Slow rates - random design...................... 221 8.3.3 Slow rates - fixed design........................ 221 8.3.4 Fast rates (_x0007_).............................. 224 8.3.5 Zoo of conditions (_x0007__x0007_)......................... 225 8.3.6 Random design (_x0007_)........................... 227 8.4 Experiments................................... 228 8.5 Extensions.................................... 229 8.6 Conclusion................................... 230 9 Neural networks 233 9.1 Introduction................................... 233 9.2 Single hidden layer neural network...................... 235 9.2.1 Optimization.............................. 236 9.2.2 Rectified linear units and homogeneity................ 237 9.2.3 Estimation error............................ 239 9.3 Approximation properties........................... 241 9.3.1 Universal approximation property in one dimension........ 242 9.3.2 Infinitely many neurons and variation norm............. 243 9.3.3 Variation norm in one dimension................... 244 9.3.4 Variation norm in arbitrary dimension................ 248 9.3.5 Precise approximation properties................... 249 9.3.6 From the variation norm to a finite number of neurons (_x0007_).... 250 9.4 Generalization performance for neural networks............... 253 9.5 Relationship with kernel methods (_x0007_).................... 255 9.5.1 From a Banach space F1 to a Hilbert space F2 (_x0007_)......... 255 9.5.2 Kernel function (_x0007__x0007_).......................... 257 9.5.3 Upper-bound on RKHS norm (_x0007__x0007_).................. 258 9.6 Experiments................................... 259 9.7 Extensions.................................... 260 9.8 Conclusion................................... 261 III Special topics 263 10 Ensemble learning 265 10.1 Averaging / bagging.............................. 266 10.1.1 Independent datasets.......................... 266 10.1.2 Bagging................................. 268 10.2 Random projections and averaging...................... 269 10.2.1 Gaussian sketching........................... 271 10.2.2 Random projections.......................... 273 10.3 Boosting..................................... 278 10.3.1 Problem set-up............................. 279 10.3.2 Incremental learning.......................... 281 10.3.3 Matching pursuit............................ 282 10.3.4 Adaboost................................ 283 10.3.5 Greedy algorithm based on gradient boosting............ 284 10.3.6 Convergence of expected risk..................... 287 10.3.7 Experiments.............................. 290 10.4 Conclusion................................... 290 11 From online learning to bandits 291 11.1 First-order online convex optimization.................... 292 11.1.1 Convex case............................... 293 11.1.2 Strongly-convex case (_x0007_)....................... 295 11.1.3 Online mirror descent (_x0007_)....................... 295 11.1.4 Lower bounds (_x0007__x0007_)........................... 297 11.2 Zero-th order convex optimization...................... 299 11.2.1 Smooth stochastic gradient descent.................. 301 11.2.2 Stochastic smoothing (_x0007_)....................... 303 11.2.3 Extensions............................... 307 11.3 Multi-armed bandits.............................. 307 11.3.1 Need for an exploration-exploitation trade-off............ 308 11.3.2 “Explore-then-commit”........................ 308 11.3.3 Optimism in the face of uncertainty (_x0007_)............... 310 11.3.4 Adversarial bandits (_x0007_)........................ 312 11.4 Conclusion................................... 314 12 Over-parameterized models 315 12.1 Implicit bias of gradient descent........................ 316 12.1.1 Least-squares.............................. 316 12.1.2 Separable classification......................... 318 12.1.3 Beyond convex problems (_x0007_)..................... 323 12.2 Double descent................................. 325 12.2.1 The double descent phenomenon................... 325 12.2.2 Empirical evidence........................... 326 12.2.3 Linear regression with Gaussian projections (_x0007_)........... 327 12.3 Global convergence of gradient descent.................... 332 12.3.1 Mean field limits............................ 333 12.3.2 From linear networks to positive definite matrices.......... 337 12.3.3 Global convergence for positive definite matrices.......... 338 12.3.4 Special case of Oja flow........................ 340 12.4 Lazy regime and neural tangent kernels (_x0007_)................. 341 12.5 Conclusion................................... 343 13 Structured prediction 345 13.1 Multi-category classification.......................... 346 13.1.1 Extension of classical convex surrogates............... 346 13.1.2 Generalization bound I: stochastic gradient descent......... 348 13.1.3 Generalization bound II: Rademacher complexities (_x0007_)....... 350 13.2 General set-up and examples......................... 352 13.2.1 Examples................................ 352 13.2.2 Structure encoding loss functions................... 354 13.3 Surrogate methods............................... 356 13.3.1 Score functions and decoding step.................. 356 13.3.2 Fisher consistency and calibration functions............. 357 13.3.3 Main surrogate frameworks...................... 357 13.4 Smooth/quadratic surrogates......................... 358 13.4.1 Quadratic surrogate.......................... 358 13.4.2 Theoretical guarantees......................... 358 13.4.3 Linear estimators and decoding steps................. 359 13.4.4 Smooth surrogates (_x0007_)......................... 360 13.5 Max-margin formulations........................... 362 13.5.1 Structured SVM............................ 362 13.5.2 Max-min formulations (_x0007__x0007_)...................... 363 13.6 Generalization bounds (_x0007_)........................... 365 13.7 Experiments................................... 366 13.7.1 Robust regression............................ 366 13.7.2 Ranking................................. 366 13.8 Conclusion................................... 369 14 Probabilistic methods 371 14.1 From empirical risks to log-likelihoods.................... 371 14.1.1 Conditional likelihoods......................... 373 14.1.2 Classical priors............................. 373 14.1.3 Sparse priors.............................. 374 14.1.4 On the relationship between MAP and MMSE (_x0007_)......... 375 14.2 Discriminative vs. generative models..................... 378 14.2.1 Linear discriminant analysis and softmax regression........ 379 14.2.2 Naive Bayes............................... 379 14.2.3 Maximum likelihood estimations................... 380 14.3 Bayesian inference............................... 381 14.3.1 Computational handling of posterior distributions......... 382 14.3.2 Model selection through marginal likelihood............. 383 14.4 PAC-Bayesian analysis............................. 384 14.4.1 Set-up.................................. 384 14.4.2 Uniformly bounded loss functions................... 385 14.5 Conclusion................................... 387 15 Lower bounds on performance 389 15.1 Statistical lower bounds............................ 390 15.1.1 Minimax lower bounds......................... 390 15.1.2 Reduction to a hypothesis test.................... 391 15.1.3 Review of information theory..................... 393 15.1.4 Lower-bound on hypothesis testing based on information theory. 395 15.1.5 Examples................................ 398 15.1.6 Minimax lower bounds through Bayesian analysis.......... 399 15.2 Optimization lower bounds.......................... 402 15.2.1 Convex optimization.......................... 402 15.2.2 Non-convex optimization (_x0007_)..................... 404 15.3 Lower bounds for stochastic gradient descent (_x0007_).............. 407 15.4 Conclusion................................... 409