12 Convex Learning Problems
In this chapter we introduceconvex learning problems. Convex learning comprises
an important family of learning problems, mainly because most of what we can
learn efficiently falls into it. We have already encountered linear regression with
the squared loss and logistic regression, which are convex problems, and indeed
they can be learned efficiently. We have also seen nonconvex problems, such as
halfspaces with the 0-1 loss, which is known to be computationally hard to learn
in the unrealizable case.
In general, a convex learning problem is a problem whose hypothesis class is a
convex set, and whose loss function is a convex function for each example. We be-
gin the chapter with some required definitions of convexity. Besides convexity, we
will define Lipschitzness and smoothness, which are additional properties of the
loss function that facilitate successful learning. We next turn to defining convex
learning problems and demonstrate the necessity for further constraints such as
Boundedness and Lipschitzness or Smoothness. We define these more restricted
families of learning problems and claim that Convex-Smooth/Lipschitz-Bounded
problems are learnable. These claims will be proven in the next two chapters, in
which we will present two learning paradigms that successfully learn all problems
that are either convex-Lipschitz-bounded or convex-smooth-bounded.
Finally, in Section 12.3, we show how one can handle some nonconvex problems
by minimizing “surrogate” loss functions that are convex (instead of the original
nonconvex loss function). Surrogate convex loss functions give rise to efficient
solutions but might increase the risk of the learned predictor.
12.1 Convexity, Lipschitzness, and Smoothness
12.1.1 Convexity
definition12.1 (Convex Set) A setCin a vector space is convex if for any
two vectorsu,vinC, the line segment betweenuandvis contained inC. That
is, for anyα∈[0,1] we have thatαu+ (1−α)v∈C.
Examples of convex and nonconvex sets inR^2 are given in the following. For
the nonconvex sets, we depict two points in the set such that the line between
the two points is not contained in the set.
Understanding Machine Learning,©c2014 by Shai Shalev-Shwartz and Shai Ben-David
Published 2014 by Cambridge University Press.
Personal use only. Not for distribution. Do not post.
Please link tohttp://www.cs.huji.ac.il/~shais/UnderstandingMachineLearning
