WIXLIB

expected risk Lempirical risk L̂h ĥERMFigure 2: We want to minimize the expected risk L to get h , but we can only minimizethe empirical risk L̂ to get ĥ.minimizer (ERM), which minimizes the training error:ĥERM arg min L̂(h).h H(1)Now what can we say about the relationship between L̂(ĥERM ) and L(ĥERM )? The keypoint is that ĥERM depends on L̂, so L̂(ĥERM ) is no longer an average of i.i.d. randomvariables; in fact, it’s quite a narly beast. Intuitively, the training error should besmaller than the test error and hence less reliable, but how do we formalize this?Using uniform convergence, we will show that:!rComplexity(H)L(ĥERM ) L̂(ĥERM ) Op.(2) {z } {z}ntest errortraining error The rate of convergence is governed by the complexity of H. We will devote a gooddeal of time computing the complexity of various function classes H. VC dimension,covering numbers, and Rademacher complexity are different ways of measuring how biga set of functions is. For example, we will see that if H contains d-dimensional linearclassifiers that are s-sparse, then Complexity(H) O(s log d), which means we cantolerate exponentially more irrelevant features! All of these results are distributionfree, makes no assumptions on the underlying data-generating distribution! These generalization bounds are in some sense the heart of statistical learning theory.But along the way, we will develop generally useful concentration inequalities whoseapplicability extends beyond machine learning (e.g., showing convergence of eigenvaluesin random matrix theory).7

1.4Kernel methods (Lecture 1) Let us take a detour away from analyzing the error of learning algorithms and thinkingmore about what models we should be learning. Real-world data is complex, so weneed expressive models. Kernels provide a rigorous mathematical framework to buildcomplex, non-linear models based on the machinery of linear models. For concreteness, suppose we’re trying to solve a regression task: predicting y Rfrom x X . The usual way of approaching machine learning is to define functions via a linearcombination of features: f (x) w · φ(x). Richer features yield richer functions:– φ(x) [1, x] yields linear functions– φ(x) [1, x, x2 ] yields quadratic functions Kernels provide another way to define functions. We define a positive semidefinite0kernel k(x, x0 ), which captures the “similarity” betweenPnx and x , and the define afunction by comparing with a set of exemplars: f (x) i 1 αi k(xi , x).– Kernels allow us to construct complex non-linear functions (e.g., Gaussian kernel0 k2)) that are universal, in that it can approximate anyk(x, x0 ) exp( kx x2σ 2continuous function.– For strings, trees, graphs, etc., can define kernels that exploit dynamic programming for efficient computation. Finally, we operate on the functions themselves, which is at the end of the day all thatmatters. We will define a space of functions called an reproducing kernel Hilbertspace (RKHS), which allows us to treat the functions like vectors and perform linearalgebra. It turns out that all three perspectives are getting at the same thing:Feature map φ(x)uniqueKernel k(x, x0 )Figure 3:uniqueRKHS H with k · kHThe three key mathematical concepts in kernel methods.8

There are in fact many feature maps that yield the same kernel (and thus RKHS), soone can choose the one based on computational convenience. Kernel methods generallyrequire O(n2 ) time (n is the number of training points) to even compute the kernelmatrix. Approximations based on sampling offer efficient solutions. For example, bygenerating lots of random features of the form cos(ω · x b), we can approximate anyshift-invariant kernel. Random features also provides some intuition into why neuralnetworks work.1.5Online learning (Lecture 1) The world is a dynamic place, something that’s not captured well by our earlier analysesbased on asymptotics and uniform convergence. Online learning tries to do addressthis in two ways:– So far, in order to analyze the error of a learning algorithm, we had to assumethat the training examples were i.i.d. However in practice, data points mightbe dependent, and worse, they might be generated by an adversary (think spamclassification).– In addition, we have so far considered the batch learning setting, where we geta training set, learn a model, and then deploy that model. But in practice, datamight be arriving in a stream, and we might want to interleave learning andprediction. The online learning setting is a game between a learner and nature:x1p1y1Learner.NaturexTpTyTFigure 4: Online learning game.– Iterate t 1, . . . , T : Learner receives input xt X (e.g., system gets email)Learner outputs prediction pt Y (e.g., system labels email)Learner receives true label yt Y (e.g., user relabels email if necessary)(Learner updates model parameters)9

How do we evaluate?– Loss function: (yt , pt ) R (e.g., 1 if wrong, 0 if correct)– Let H be a set of fixed expert predictors (e.g., heuristic rules)– Regret: cumulative difference between learner’s loss and best fixed expert’s loss:in other words, how well did the learner do compared to if we had seen all thedata and chose the best single expert in advance? Our primary aim is to upper bound the regret. For example, for finite H, we will show:p(3)Regret O( T log H ).Things to note:– The average regretbest fixed expert).RegretTgoes to zero (in the long run, we’re doing as well as the– The bound only depends logarithmically on the number of experts, which meansthat the number of experts H can be exponentially larger than the number ofdata points T .– There is no probability here; the data is generated adversarially. What we relyon is the (possibly hidden) convexity in the problem. Online learning naturally leads to the multi-armed bandit setting, where the learneronly receives partial feedback. Suppose you’re trying to assign treatments pt to patientsxt . In this case, you only observe the outcome associated with treatment pt , not theother treatments you could have chosen (in the standard online learning setting, youreceive the true label and hence feedback about every possible output). Online learningtechniques can be adapted to work in the multi-armed bandit setting. Overall, online learning has many things going for it: it leads to many simple algorithms(online gradient descent) which are used heavily in practice. At the same time, thetheory is remarkably clean and results are quite tight.2Asymptotics2.1Overview (Lecture 1) Here’s the basic question: Suppose we have data points drawn from an unknowndistribution with parameters θ :x(1) , . . . , x(n) pθ .(4)Can we come up with an estimate θ̂ (some function of the data) that gets close to θ ?10

We begin with perhaps the simplest statistical problem: estimating the mean of a Gaussian distribution (Section 2.2). This allows us to introduce the concept of parametererror, and provides intuition for how this error scales with dimensionality and number of examples. We then consider estimating multinomial distributions (Section 2.3),where we get our first taste of asymptotics in order to cope with the non-Gaussianity,appealing to the central limit theorem and the continuous mapping theorem. Finally,we generalize to exponential families (Section 2.4), a hugely important class of models.Here, our parameter estimate is no longer an empirical average, so we lean on the deltamethod. We then introduce the method of moments, and show an equivalence with exponentialfamilies via the maximum entropy principle (Section 2.5). But the real benefit ofmethod of moments is in latent-variable models (Section 2.6). Here, we show thatwe can obtain an efficient estimator for three-view mixture models when maximumlikelihood would otherwise require non-convex optimization. Next, we turn from parameter estimation to prediction, starting with fixed design linearregression (Section 2.7). The analysis is largely similar to mean estimation, and we getexact closed form expressions. For the random design setting and general loss functions(to handle logistic regression), we need to again appeal to asymptotics (Section 2.8). So far, we’ve only considered unregularized estimators, which make sense when thenumber of data points is large relative to the model complexity. Otherwise, regularization is necessary to prevent overfitting. As a first attempt to study regularization,we analyze the regularized least squares estimator (ridge regression) for fixed designlinear regression, and show how to tune the regularization strength to balance thebias-variance tradeoff (Section 2.9).2.2Gaussian mean estimation (Lecture 1) We warmup with a simple classic example from statistics. The goal is to estimate themean of a Gaussian distribution. Suppose we have n i.i.d. samples from a Gaussiandistribution with unknown mean θ Rd and known variance σ 2 I (so that each of thed components are independent):x(1) , . . . , x(n) N (θ , σ 2 I)(5) Define θ̂ to be parameter estimate equal to the sample mean:nθ̂ 1 X (i)x .n i 1(6) Let us study how this estimate θ̂ deviates from the true parameter θ:θ̂ θ Rd .11(7)

This deviation is a random vector which should depend on the number of points n andthe variance σ 2 . What do you think the dependence will be? Lemma 1 (parameter deviation for Gaussian mean)– The sample mean estimate θ̂ deviates from the true parameter θ according to aGaussian: σ2I .(8)θ̂ θ N 0,n– FIGURE: [θ̂ in a ball around θ for d 2] Proof of Lemma 1– We need the following basic properties of Gaussians: Fact 1 (sums of independent Gaussians): if v1 N (0, Σ1 ) and v2 N (0, Σ2 )are independent, then v1 v2 N (0, Σ1 Σ2 ). Fact 2 (constant times Gaussian): if v N (0, Σ), then Av N (0, AΣA )for any matrix A.– The rest is just algebra: First, note that x(i) θ N (0, σ 2 I).def P Next, we have that Sn ni 1 x(i) N (0, nσ 2 I) by Fact 1. 2 Finally, we have θ̂ θ Snn N 0, σnI by Fact 2. Lemma 1 tells us how the entire estimated vector behaves, but sometimes it’s convenient to just get one number that tells us how we’re doing. Let’s define the meansquared parameter error, which is the squared distance between the estimate θ̂ andthe true parameter θ :kθ̂ θ k22 .(9)How do you think the parameter error behaves? Lemma 2 (parameter error for Gaussian mean)– The mean-squared parameter error is:kθ̂ θ k22 σ2 2χ ,n d(10)and has expected value:hi dσ 2E kθ̂ θk22 .n12(11)

Proof of Lemma 2– Standard properties of chi-squared distributions:P If v1 , . . . , vd N (0, 1), then dj 1 vj2 χ2d . If z χ2d , then E[z] d and Var[z] 2d.p– By Lemma 1, we know that v σn2 (θ̂ θ ) N (0, I).P– The squared 2-norm of this vector (kvk22 dj 1 vj2 ) is therefore distributed asχ2d .– Multiplying both sides byσ2nyields (10).– Taking expectations on both sides yields (11). A Gaussian random vector has fluctuations on the orderqof its standard deviation, we2can think of θ̂ having typical deviations on the order of dσn . FIGURE: [relate to previous figure, density of a chi-squared for kθ̂ θ k22 ] Takeaways– Life is easy when everything’s Gaussian, since we can compute things in closedform.– Think geometrically about shrinking balls around θ .2.3Multinomial estimation (Lecture 1) In the above, things worked out nicely because everything was Gaussian. What if aredata are not Gaussian? Suppose we have an unknown multinomialPd distribution over d choices: θ d (that is,θ [θ1 , . . . , θd ], θj 0 for each j and j 1 θj 1). Suppose we have n i.i.d. samplesfrom this unknown multinomial distributionx(1) , . . . , x(n) Multinomial(θ ),(12)where each x(i) {e1 , . . . , ed } and ej {0, 1}d is an indicator vector that is 1 atposition j and 0 elsewhere. Consider the empirical distribution as the estimator (same form as the sample mean):n1 X (i)θ̂ x .n i 1 Example:13(13)

– θ [0.2, 0.5, 0.3]– x(1) [0, 1, 0], x(2) [1, 0, 0], x(3) [0, 1, 0]– θ̂ [ 31 , 23 , 0] We can now ask the same question as we did for Gaussian estimation: what is theparameter error kθ̂ θ k22 ? Before we had gotten a chi-squared distribution becausewe had Gaussians and could work out everything in closed form. But now, we havemultinomial distributions, which makes things more difficult to analyze. How do youthink the parameter error will behave? Fortunately, not all hope is lost. Our strategy will be to study the asymptotic behavior of the estimators. By the central limit theorem, we have dn(θ̂ θ ) N (0, V ),(14)defwhere V diag(θ ) θ (θ ) is the the asymptotic variance of a single multinomialdraw. Written out, the elements of V are:(θj (1 θj ) if j k(15)Vjk if j 6 k. θj θk It is easy to check this by noticing that E[xj ] E[x2j ] θj , E[xj xk ] 0 for j 6 k.Further sanity check:– For a single component j, when θj is close to 0 or 1, the variance is small.– The covariance between components j and k is negative since the probabilitiessum to 1 (there is competition among components). Next, we can apply the continuous mapping theorem on the function k · k22 (seeAppendix), which lets us transfer convergence results through continuous functions:dnkθ̂ θ k22 tr(W(V, 1)),(16)where W(V, k) is the Wishart distribution (multivariate generalization of the chisquared) with mean matrix V and k degrees of freedom. This follows because z N (0, V ), then zz W(V, 1), and kzk22 tr(zz ).14

Taking expectations1 and dividing by n on both sides yields:! dhiX11 2 oE kθ̂ θ k2 θj (1 θj )nnj 1 11 o.nn(17)(18) Note that the n1 term is independent of d, unlike in the Gaussian case, where the result2was dσn . The difference is that in the Gaussian case, each dimension had standardq1deviation σ, whereas in the multinomial case here, it is aboutfor the uniformddistribution.d1This step actually requires additional justification. In particular, if we have Yn Y , in order toconclude E[Yn ] E[Y ], we need (Yn ) to be uniformly integrable. A sufficient condition is that Yn has finitesecond-order moments, which means that a data point needs to have finite fourth-order moments. This isclearly the case for the multinomial distribution (which is bounded), and will be true for exponential families(for which all moments exist), discussed in the next section. Showing this result formally is non-trivial andis out of the scope of this class.15

[begin lecture 2]2.4(2)Exponential families (Lecture 2) So far, we’ve analyzed the Gaussian and the multinomial. Now let us delve intoexponential families, a much more general family of distributions which include theGaussian, multinomial, gamma, beta, etc., but not things like the uniform distributionor mixture models. Exponential families are also the basis of undirected graphical models. You probablyfirst saw exponential families in a univariate continuous setting, but we will introducethem here in the multivariable discrete setting in order to build some different intuitions(and to simply the math). Definition 1 (exponential family)– Let X be a discrete set. Example: X { 1, 1}3– Let φ : X Rd be a feature function. Example (unary and binary factors):φ(x) [x1 , x2 , x3 , x1 x2 , x2 x3 ] R5 .(19)– Define a family of distributions P, where each pθ P assigns each x X aprobability that depends on x only through φ(x):defdefP {pθ : θ Rd },pθ (x) exp{θ · φ(x) A(θ)},(20)where the log-partition functiondefA(θ) logXexp{θ · φ(x)}(21)x Xensures the distribution is normalized.– Example: if θ [0, 0, 0, 0, 0], then pθ is the uniform distribution.– Example: if θ [0, 0, 0, log 2, 0] (which favors x1 and x2 having the same sign),then pθ assigns probability:16

x1 1 1 1 1 1 1 1 1x2 x3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1exp{θ · φ(x)}220.50.50.50.522pθ (x)0.20.20.050.050.050.050.20.2– Note that unlike multinomial distributions, P does not contain all possible distributions. Varying one parameter θj has the effect of moving all points x with thesame feature φ(x)j the same way.– FIGURE: [Venn diagram over outcome x, indicator features correspond to regions] A very useful property of exponential families is that derivatives of the log-partitionfunction correspond to moments of the distribution (a short algebra calculation thatyou should do once, but we’re going to skip):– The mean is the gradient of the log-partition function:Xdef A(θ) Eθ [φ(x)] pθ (x)φ(x).(22)x X– The covariance is the Hessian of the log-partition function:def 2 A(θ) Covθ [φ(x)] Eθ [(φ(x) Eθ [φ(x)])(φ(x) Eθ [φ(x)]) ].(23)– Note that since 2 A(θ) is a covariance matrix, it is necessarily positive semidefinite, which means that A is convex.– If 2 A(θ) 0, then A is strongly convex, and A is invertible (for intuition,consider the 1D case where A would be an increasing function). In this case,the exponential family is said to be minimal. For simplicity, we will assume weare working

Apr 20, 2016 · There is obviously a large gap between theory and practice; theory relies on assump-tions can be simultaneously too strong (e.g., data are i.i.d.) and too weak (e.g., any distribution). The philosophy of this class is that the the purpose of theory here not to churn out formulas that you simply plug nu