Understanding Machine Learning: From Theory to Algorithms

12.1 Convexity, Lipschitzness, and Smoothness 157

non-convex convex

Givenα∈[0,1], the combination,αu+ (1−α)vof the pointsu,vis called a
convex combination.

definition12.2 (Convex Function) LetCbe a convex set. A functionf:
C→Ris convex if for everyu,v∈Candα∈[0,1],

f(αu+ (1−α)v) ≤ αf(u) + (1−α)f(v).

In words,fis convex if for anyu,v, the graph offbetweenuandvlies below
the line segment joiningf(u) andf(v). An illustration of a convex function,
f:R→R, is depicted in the following.

f(u)

f(v)

u

αu+ (1−α)v

v

αf(u) + (1−α)f(v)

f(αu+ (1−α)v)

Theepigraphof a functionfis the set

epigraph(f) ={(x,β) :f(x)≤β}. (12.1)

It is easy to verify that a functionf is convex if and only if its epigraph is a
convex set. An illustration of a nonconvex functionf:R→R, along with its
epigraph, is given in the following.