Understanding Machine Learning: From Theory to Algorithms

12.1 Convexity, Lipschitzness, and Smoothness 161 Intuitively, a Lipschitz function cannot change too fast. Note that iff:R→R is ...

162 Convex Learning Problems 12.1.3 Smoothness The definition of a smooth function relies on the notion ofgradient. Recall that ...

12.2 Convex Learning Problems 163 Proof By the chain rule we have that∇f(w) =g′(〈w,x〉+b)x, whereg′is the derivative ofg. Using t ...

164 Convex Learning Problems Each linear function is parameterized by a vectorw∈Rd. Hence, we can define Hto be the set of all s ...

12.2 Convex Learning Problems 165 homogenous case). LetAbe any deterministic algorithm.^1 Assume, by way of contradiction, thatA ...

166 Convex Learning Problems hypothesis class. It is easy to verify thatHis convex. The argument will be the same as in Example ...

12.3 Surrogate Loss Functions 167 Example 12.11 LetX ={x∈Rd:‖x‖ ≤β/ 2 }andY=R. LetH={w∈ Rd:‖w‖ ≤B}and let the loss function be`( ...

168 Convex Learning Problems y〈w,x〉 `hinge `^0 −^1 1 1 Once we have defined the surrogate convex loss, we can learn the problem ...

12.5 Bibliographic Remarks 169 learning algorithms for these families. We also introduced the notion of convex surrogate loss fu ...

170 Convex Learning Problems the set of all Turing machines. Define the loss function as follows. For every Turing machineT∈Z, l ...

13 Regularization and Stability In the previous chapter we introduced the families of convex-Lipschitz-bounded and convex-smooth ...

172 Regularization and Stability tion, and the algorithm balances between low empirical risk and “simpler,” or “less complex,” h ...

13.2 Stable Rules Do Not Overfit 173 In the next section we formally show how regularization stabilizes the algo- rithm and prev ...

174 Regularization and Stability learning algorithm drastically changes its prediction onziif it observes it in the training set ...

13.3 Tikhonov Regularization as a Stabilizer 175 definition13.4 (Strongly Convex Functions) A functionfisλ-strongly con- vex if ...

176 Regularization and Stability DenotefS(w) =LS(w) +λ‖w‖^2 , and based on Lemma 13.5 we know thatfSis (2λ)-strongly convex. Rel ...

13.3 Tikhonov Regularization as a Stabilizer 177 corollary 13.6 Assume that the loss function is convex andρ-Lipschitz. Then, th ...

178 Regularization and Stability Combining the preceding with Equation (13.14) and again using the assumption β≤λm/2 yield `(A(S ...

13.4 Controlling the Fitting-Stability Tradeoff 179 tradeoff between fitting and overfitting. This tradeoff is quite similar to ...

180 Regularization and Stability corollary13.10 Assume that the loss function is convex,β-smooth, and nonnegative. Then, the RLM ...