DATA 609 Meetup 7

George I. Hagstrom

Week Summary

Working on grading….
This week: definition and examples of convex functions
Next week: How to construct convex functions
Reading: Section 3.1, CVX tutorials
Lab 4 available

What is a convex function?

Start with function \(f:\, \mathbb{R}^N\to\mathbb{R}\)
Graph of \(f\) is below line between any two points on graph:

What is a convex function?

\[ f(\theta \mathbf{x}_1 + (1-\theta)\mathbf{x}_2) \leq \theta f(\mathbf{x}_1) + (1-\theta)f(\mathbf{x}_2) \]

Concave

\(f\) is concave if \(-f\) is convex
\(f\) curves down instead of up

Strict Concavity

Equalty only at endpoints, i.e. for \(\theta \neq 0, 1\): \[ f(\theta \mathbf{x}_1 + (1-\theta)\mathbf{x}_2) \leq \theta f(\mathbf{x}_1) + (1-\theta)f(\mathbf{x}_2) \]

Graph in Higher Dimensions

graph of a function \(f: \mathbf{dom}(f)\to\mathbb{R}\): \[G(f) = \{(\mathbf{x},f(\mathbf{x}))\,|\, \mathbf{x}\in\mathbf{dom}(f)\}\]
1D: \((x,y=f(x))\), familiar graph
2D: \((x,y,z=f(x,y))\), 3D surface/landscape
3D+: \(\left(x_1,x_2,x_3,...,x_n,z=f(x_1,x_2,x_3,...,x_n)\right)\)
- Hypersurface

Tangent Lines

Graph lies above tangent lines/planes/hyperplanes

Local to Global Info

Tangent line is a local property

Local to Global Info

But for Convex gives global information!

Local Min is Global Min

Local minimum implies flat tangent

What if there is no single tangent?

Slightly different argument is needed

Local Min is a Global Min

Take \(f:\,\mathbb{R}^2\to\mathbb{R}\)
Assume there is a local min that isn’t the global min

Examples: Affine

Affine \(f(\mathbf{x}) = \mathbf{c}^T\mathbf{x} + \mathbf{d}\)
Both convex and concave

Examples: Power Functions

Power Functions: \(f(x) = x^{\alpha}\)
- Convex for \(\alpha\geq 1\) on \(\mathbb{R}_+\)

Examples: Power Functions

Power Functions: \(f(x) = x^{\alpha}\)
- Concave for \(0<\alpha\leq 1\) on \(\mathbb{R}_+\)

Examples: Power Functions

Power Functions: \(f(x) = x^{\alpha}\)
- Convex for \(\alpha\leq 0\) on \(\mathbb{R}_{++}\)

Examples: \(|x|^{\alpha}\)

\(f(x) = |x|^{\alpha}\) is convex on \(\mathbb{R}\) for \(\alpha\geq 1\)

Examples: \(e^{\alpha x}\)

\(e^{\alpha x}\) is convex for any \(\alpha\)

Examples: Rectified Linear Unit

\(\max(0,x)\) is convex
\(\min(0,x)\) is concave

Examples: `log` and entropy

\(f(x) = \log(x)\) is concave on \(\mathbb{R}_{++}\)
\(f(x) = -x\log(x)\) is concave on \(\mathbb{R}_{+}\)

Examples: Norms

All norms are convex on \(\mathbb{R}^N\to\mathbb{R}\) \[ \|\mathbf{x}\| = \left(\sum_i x_i^2\right)^{1/2} , \|\mathbf{x}\|_p = \left(\sum_i x_i ^p\right)^{1/p} \\ \|\mathbf{x}\|_{\infty} = \max(x_1,x_2,...,x_n) \]
Sum of squares also \(\|\mathbf{x}\|^2 = \mathbf{x}^T\mathbf{x}\)

Lasso and Sparse Regression

Consider Least Squares Problem

\[ \min_{\mathbf{x}} \|A\mathbf{x}-\mathbf{b}\|^2 \]

Suppose \(\mathbf{x}\) has many entries
\(A\) could even be wide
You only want to use a few features
Your data may have outliers

Lasso and Sparse Regression

Apply the following penalty:

\[ \min_{\mathbf{x}} \|A\mathbf{x}-\mathbf{b}\|^2 + \lambda \sum_i |x_i| \]

Equivalent to a norm:

\[ \min_{\mathbf{x}} \|A\mathbf{x}-\mathbf{b}\|^2 + \lambda\|\mathbf{x}\|_1 \]

Lasso and Sparse Regression

We will learn that adding convex functions preserves convexity
Lasso regularization of convex problem also convex
Has a tendency to produce robust solutions with sparse coefficients \(\mathbf{x}\)

Softmax and Geometric Mean

\(\log\left(\sum_{i=1}^n e^{x_i}\right)\) is convex
- This is a smoothed maximum function
\(\left(\Pi_{i=1}^n x_i\right)^{1/n}\)
- Geometric mean

First and Second Order Conditions

First Order Condition: \(f\) is convex if and only if graph lies above all tangent lines
Second Order Condition: \(f\) is convex if and only if the Hessian is positive semi-definite at all points in (convex) domain \[ \left(\nabla^2{f}\right)_{ij} = \frac{\partial^2 f}{\partial x_i \partial x_j} \succeq 0 \]

Second Order Condition

Show that \(f(x) = e^{\alpha x}\) is convex
Take first derivative:
- \(f'(x) = \alpha e^{\alpha x}\)
Take second derivative:
- \(f''(x) = \alpha^2 e^{\alpha x}\)
\(f''(x) \geq 0\), so \(f\) is convex
Also implies sum of convex is convex

Quadratic over Linear

\(f(x,y) = \frac{x^2}{y}\), \(\mathbf{dom}(f) = \mathbb{R}\times\mathbb{R}_{++}\)
Start taking derivatives \[ \nabla f = \begin{bmatrix} \frac{2x}{y} & -\frac{x^2}{y^2} \end{bmatrix}^T \]

\[\nabla^2 f = \begin{bmatrix} \frac{2}{y} & -\frac{2x}{y^2} \\ -\frac{2x}{y^2} & \frac{2x^2}{y^3} \end{bmatrix} \]

Positive semidefinite because \(\mathrm{det}(\nabla^2 f)\geq 0\) and \(Tr(\nabla^2 f) > 0\)

Restriction to Line

\(f:\mathbb{R}^n\to\mathbb{R}\) is convex if and only if it is convex when restricted to every single line in \(\mathbb{R}^n\)
\(g(t) = f(\mathbf{b}+t\mathbf{v})\) is convex for all vectors \(\mathbf{v}\), \(\mathbf{b}\)

Epigraph

\(\mathbf{epi}(f)\) is set of points above the graph of \(f\) \[ \{(\mathbf{x},z)\,| \mathbf{x}\in\mathbf{dom}(f),\, z\geq f(\mathbf{x})\} \]

Epigraph

\(f\) is convex if and only if \(\mathbf{epi}(f)\) is a convex set
Allows for construction of more convex sets
\(f\) is concave if and only if \(\mathbf{sub}(f)\) is a convex set
This is convex: \[ \{(x,y)| \log(x) \leq y \ \leq e^{\alpha x}\} \]

Sub/Super Level Sets

Solution set of inequality defines sub: \[\mathbf{sub}_{\alpha}(f) = \{\mathbf{x}| f(\mathbf{x}\leq \alpha)\}\]
Super-level set has oppositve inequality
\(\alpha\)-sublevel sets of a convex function are convex
\(\alpha\)-superlevel sets of a concave function are convex

Jensen’s Inequality (Project?)

Useful result in probability and statistics:
If \(f\) is a convex function and \(x\) a random variable, then: \[ \mathrm{E}[f(x)]\geq f(\mathrm{E}[x]) \]
Because expectation is \(\sum_i p_i x_i\), convex combination of values of \(x\)

Jensen’s Inequality

wikipedia

Convexity/Concavity important in life

Jensen and Fragility

Suppose something in your life is random
Consider your payoff function \(f(x)\)
If your \(f\) is convex, Jensen says randomness helps you
Your Outcome = \(\mathrm{E}[f(x)]\) better than outcome of average \(f(\mathrm{E}[x])\)
If your payoff is concave, Jensen says randomness hurts you

Car Traffic Example

Few cars, drive speed limit
Cars above threshold, speed drops
Expected Traffic is 30 cars
Expected Time 65 minutes

| Cars | Time       |
|------|------------|
| 1    | 30 minutes |
| 10   | 30 minutes |
| 20   | 30 minutes |
| 30   | 40 minutes |
| 40   | 1 hour     |
| 50   | 1.5 hours  |
| 60   | 3 hours    |

Jensen and Fragility

Convex payouts are called anti-fragile
Concave payouts are called fragile
Many times in life we don’t can’t fully quantify the risks we face
But sometimes we can control the outcome for ourselves should something bad happen
Moral- make your payouts convex if you can

DATA 609 Meetup 7

Week Summary

What is a convex function?

What is a convex function?

Concave

Strict Concavity

Graph in Higher Dimensions

Tangent Lines

Local to Global Info

Local to Global Info

Local Min is Global Min

What if there is no single tangent?

Local Min is a Global Min

Examples: Affine

Examples: Power Functions

Examples: Power Functions

Examples: Power Functions

Examples: \(|x|^{\alpha}\)

Examples: \(e^{\alpha x}\)

Examples: Rectified Linear Unit

Examples: log and entropy

Examples: Norms

Lasso and Sparse Regression

Lasso and Sparse Regression

Lasso and Sparse Regression

Softmax and Geometric Mean

First and Second Order Conditions

Second Order Condition

Quadratic over Linear

Restriction to Line

Epigraph

Epigraph

Sub/Super Level Sets

Jensen’s Inequality (Project?)

Jensen’s Inequality

Convexity/Concavity important in life

Jensen and Fragility

Car Traffic Example

Jensen and Fragility

Thanks!

Examples: `log` and entropy