Optimization#
Some notes on convex optimization following Boyd & Vandenberghe, plus basic optimization algorithms.
About this chapter
Most of this chapter follows Boyd and Vandenberghe. Convex sets and convex functions come first, then the standard problem classes (linear, quadratic, geometric and semidefinite programs). Duality follows: the Lagrangian gives a lower bound on the optimal value, and when strong duality holds the KKT conditions characterize the solution. Then come approximation and fitting problems such as regularized least squares, and unconstrained minimization by gradient descent and Newton’s method.
The second half is more practical: gradient descent, SGD and Newton’s method as used on data, the expectation maximization algorithm (EM) for models with hidden variables, why neural network losses are hard to optimize and how Adam adapts its step size, and branch-and-bound for mixed integer programs.
Chapter outline: 7 sections
- Convex optimizationA convex set contains the segment between any two of its points, and a convex function lies below its chords.
- Duality (boyd 5)1 interactiveAdd the constraints to the objective with weights \lambda and \nu.
- Approx + fitting (boyd 6)Fitting problems built on \vert\vert Ax - b \vert\vert.
- Unconstrained minimization (boyd 9)1 interactiveThe bounds mI \preceq \nabla^2 f \preceq MI come up again and again below: their ratio \kappa = M/m bounds the condition number, and it controls how fast gradient descent converges.
- Basic algorithmsThe same methods from the data side.
- Expectation maximization - Jordan ch 11Maximizing \log p(x|\theta) directly is hard because it sums over the hidden z.
- Misc1 interactive
Convex optimization#
A convex set contains the segment between any two of its points, and a convex function lies below its chords. The lists of operations that preserve convexity are the practical part: they let you check convexity without going back to the definition.
Convex sets (boyd 2)#
Affine, convex and conical sets differ only in which combinations \(\theta x_1 + (1-\theta) x_2\) they must contain. The separating and supporting hyperplane theorems are the geometric facts that duality rests on later.
affine set: \(x_1, x_2 \in C, \theta \in \mathbb{R} \implies \theta x_1 + (1 - \theta) x_2 \in C\)
affine hull: aff C = {\(\sum \theta_i x_i \vert x_i \in C, \sum \theta_i =1\)}
convex set: \(x_1, x_2 \in C, 0 \leq \theta \leq 1 \implies \theta x_1 + (1 - \theta) x_2 \)
convex hull: conv C = {\(\sum \theta_i x_i \: \vert x_i \in C, \theta_i \geq 0, \sum \theta_i = 1\)}
cone: \(\theta \geq 0 \implies \theta x \in C\)
operations that preserve convexity
intersection (finite intersection of half-spaces)
pointwise max of affine funcs
composition
affine
perspective
linar fractional = projective
generalized inequalities:
proper cone K: convex, closed, pointed, solid
\(x \preceq_K y \iff y-x \in K\)
separating hyperplane thm: C, D convex \(C \cap D =\emptyset \implies \exists a \neq 0, b \: s.t. \\ a^Tx \leq b \forall x \in C, \\a^Tx \geq b \forall x \in D\)
supporting hyperplane thm: {\(x\vert a^tx = a^t x_0\)} where \(x_0\) on boundary of convex C
dual cone \(K^*\) = {\(y\vert x^Ty \geq 0 \: \forall x \in K\)}
\(\preceq_{K^*}\) is dual of \(\preceq_K\)
\(x \preceq_K y \iff \lambda^T x \leq \lambda^T y \quad \forall \: \lambda \succeq_{K^*} 0\)
Geometry#
The standard convex sets that problems are built from: ellipsoids, hyperplanes and halfspaces, norm cones, polyhedra and simplices.
ellipsoid: {\(x \in \mathbb{R}^n \vert (x-x_c)^T P^{-1} (x-x_c) \leq 1\)} where P symmetric, PSD
{\(x_c + Au \vert \vert \vert u\vert \vert _2 \leq 1\)}
hyperplane: {\(x\vert a^Tx = b\)} ~ creates a halfspace
norm cone: {\((x, t)\vert \: \vert \vert x\vert \vert \leq t\)}
polyhedron: {x | Ax=b, Cx=d} = \(\{ \sum_i^k \theta_i v_i \; \vert \sum_i^m \theta_i = 1, \theta_i \geq 0 \} \: m \leq k\)
simplex: conv{\(v_{0:k}\)}
Convex funcs (boyd 3)#
Four equivalent ways to check convexity: Jensen’s inequality, a PSD Hessian, the function lying above its tangent planes, or a convex epigraph. The conjugate \(f^*\) reappears in duality, where the dual function of a simple problem is \(-f^*\).
definitions
Jensen’s inequality \(0 \leq \theta \leq 1\)
\(f(\theta x_1 + (1 - \theta) x_2) \leq \theta f(x_1) + (1 - \theta) f(x_2)\)
\(f(E[X]) \leq E[f(X)]\)
\(\nabla^2 f(x) \succeq 0\)
\(f(x_2) \geq f(x_1) + \nabla f(x_1)^T (x_2 - x_1)\)
can show this by restricting to an arbitrary line
consider epi f - also use things that preseve convexity
concepts
epigraph epi f = \(\{ (x, t) \; \vert \: x \in dom f, f(x) \leq t \}\)
extended value extension: \(\tilde{f}(x) = f(x)\) if \(x \in dom f\) else \(\infty\)
wide sense function - can take on values \(\pm \infty\)
= dom f = {\(x \vert f(x) < \infty\)}
wide sense convex func: \(f(x) = \inf \{ t \in \mathbb{R} \vert (x, t) \in F\}\) where \(F \subseteq \mathbb{R}^{n+1}\)
\(F(x) = \inf \{ t \in \mathbb{R} \vert (x, t) \in F \}\)
\(\alpha\)-sublevel set of convex func is convex
operations that preserve convexity
nonnegative weighted sums ~ multiplies for logs
affine map
pointwise max of convex
composition
perspective
minimization ~ sometimes
conjugate of f
\(f^*(y) = \underset{x \in dom f}{\sup} \: y^T x - f(x)\)
dom \(f^*\) = {\(y\vert f^*(y)\) is finite}
called Legendre transform when f differentiable
fenchel’s inequality: \(f(x) + f^*(y) \geq x^ty\)
\(f^{**} = f\) iff convex, closed
ex. \(f(S) = \log \: \det X^{-1}\)
\(f^*(Y) = \underset{X}{\sup} [\operatorname{tr}(YX) + \log \: \det X]\)
\(= -n - \log \: \det(-Y)\) if \(-Y \in S^n_{++}\)
can use conj. to go other way: \(f(y) = \underset{x}{\sup}(y^Tx - f^*(x))\)
Optimization problems (boyd 4)#
Standard form writes every problem as minimizing \(f_0\) subject to inequalities \(f_i(x) \leq 0\) and equalities \(h_i(x) = 0\). Many transformations (slack variables, epigraph form, eliminating equalities) give equivalent problems. The subsections then list the main convex problem classes, from linear programs up to semidefinite programs.
Optimization#
Two problems are equivalent when a solution of one gives a solution of the other. The epigraph form, for example, moves the objective into a constraint \(f_0 \leq t\) and minimizes \(t\).
standard form: \(p^* = \min \: f_0(x)\\s.t. \: f_i(x) \leq 0 \\ h_i(x) = 0\)
equivalent problems
change of vars
constraint transformations
slack vars
eliminating equalities
eliminating linear equalities
introducing equalities
optimizing over some vars ~ ex. quadratic
epigraph form: \(\min \: t \: s.t. \: f_0 \leq t\)
implicit + explicit constraints
Convex optimization#
standard form: \(p^* = \min \: f_0(x)\\s.t. \: f_i(x) \leq 0 \\ a_i^Tx = b_i\) where all f are convex
optimality criteria (special cases of KKT)
x optimal if
x is feasible
\(\nabla f_0 (x)^T(y-x) \geq 0 \: \forall y\) feasible
if unconstrained \(\nabla f_0 (x) = 0\)
if equality only Ax=b, \(\nabla f_0 (x) \perp N(A)\)
\(x \succeq 0\), \(\nabla f_0 (x) \succeq 0; x_i (\nabla f_0 (x))_i = 0\)
equivalent convex problems
eliminating equality constraints
introducing equality constraints
slack vars ~ for linear inequalities
epigraph form
minimizing over some vars
Linear optimization#
- \[\begin{split}p^* = \min \: c^T x + d\\s.t. \: Gx \succeq h \\ Ax=b\end{split}\]
standard form \(x \succeq 0\) is the only inequality
standard dual: max \(-b^T \nu\) s.t. \(A^T \nu + c \geq 0\)
linear-fractional program
\(\min \: \frac{c^Tx + d}{e^tx+f} \\ s.t \: Gx \succeq h \\ Ax = b\) ~ can be converted to LP
Quadratic optimization#
\(\min \: 1/2 x^TPx + q^Txr \\s.t. \: Gx \succeq h\) where \(P \in S_+^n\)
QCQP - inequality constraints also convex
ex. \(\min \: \vert \vert Ax-b\vert \vert _2^2\)
SOCP - \(\min f^Tx \\ s.t. \: \vert \vert A_ix+b_i\vert \vert _2 \leq c_i^T + d_i \\ Fx=g\)
Geometric program#
Not convex as written, but the change of variables \(y_i = \log x_i\) turns posynomials into convex functions.
\(\min \: f_0(x) \\ s.t. \: f_i(x) \leq 1 \: i = 1:m \\ h_i(x) = 1 \: i = 1:p\) where \(f_{0:m}\) posynomials, \(h_i\) monomials
monomial \(f(x) = c x_1^{a_1} \cdot x_n^{a_n}, c>0\)
posynomial ~ sum of monomials ~ can transform into convex w/ \(y_i = \log x_i\)
Generalized inequality#
Inequalities with respect to a proper cone \(K\) instead of componentwise. Taking \(K\) to be the cone of PSD matrices gives semidefinite programs.
- \[\begin{split}\min \: f_0(x)\\s.t. \: f_i(x) \preceq_{K_i} 0, i=1:m\\Ax=b\end{split}\]
conic form problem: \(\min \: c^Tx \\ s.t. \: Fx +g \preceq_K 0\\Ax=b\) ~ set \(K=S_+^K\)
SDP = semi-definite program: \(\min \: c^T x\\s.t. \: x_1F_1+...+x_nF_n+G \preceq 0\\Ax=b\) ~ where \(F_1, ..., F_n \in S^k\)
standard form: \(\min \: \operatorname{tr}(CX) \\ s.to \: \operatorname{tr}(A_iX)=b_i \\ X \succeq 0\)
Duality (boyd 5)#
Add the constraints to the objective with weights \(\lambda\) and \(\nu\). Minimizing over \(x\) gives the dual function \(g\), which is a lower bound on \(p^*\) for every \(\lambda \succeq 0\). The dual problem looks for the best such bound.
consider \(\min \: \cblue{f_0 (x)} \\ s.t. \: \corange{f_i(x) \leq 0} \\ \cgreen{h_i(x) = 0}\)
lagrangian \(L(x, \lambda, \nu) = \cblue{f_0(x)} + \corange{\sum \lambda_i f_i(x)} + \cgreen{\sum \nu_i h_i(x)}\)
objective + weighted inequality constraints + weighted equality constraints
dual function \(g(\lambda, \nu) = \underset{x \in D}{\inf} L(x, \lambda, \nu)\) ~ g always concave
\(\lambda \succeq 0 \implies g(\lambda, \nu) \leq p^*\)
\((\lambda, \nu)\) dual feasible if
\(\lambda \succeq 0\)
\((\lambda, \nu) \in dom \: g\)
when \(p^* = - \infty\), dual infeasible
when \(d^*=\infty\), primal infeasible
dual related to to conjugate func
ex. min f(x) s.t. \(x = 0 \implies g(\nu) = -f^*(-\nu)\)
lagrange dual problem: \(\max \: g(\lambda, \nu)\\s.t. \: \lambda \succeq 0\)
weak duality: \(d^* \leq p^*\)
optimal duality gap: \(p^* - d^*\)
strong duality: \(d^* = p^*\) ~ requires more than convexity
slater’s condition ~ if problem convex \(\implies\) strong duality + \(\exists\) dual optimal point
\(\exists x \in relint \: D\\f_i(x) < 0\\Ax = b\) ~ point is strictly feasible
to weaken this, affine \(f_i\) can be \(\leq 0\)
sion’s minimax thm: \(x \to f(x, y)\) ~ conditions
\(\implies \underset{x}{\min} \: \underset{y}{\sup} \: f(x,y) = \underset{y}{\sup} \: \underset{x}{\min} \: f(x,y)\)
Optimality conditions#
The duality gap \(f_0(x) - g(\lambda, \nu)\) certifies how far a feasible \(x\) is from optimal, so it works as a stopping rule. Under strong duality the optimum satisfies the KKT conditions, including complementary slackness: a constraint that is not tight gets \(\lambda_i = 0\).
duality gap: \(f_0(x) - g(\lambda, \nu)\)
can use stopping condition duality gap \(\leq \epsilon_{abs}\) to be \(\epsilon_{abs}\) - suboptimal
strong duality yields complementary slackness
\(\lambda_i f_i(x^*)=0\)
KKT optimality conditions ~ assume \(f_0, f_i, h_i\) differentiable, strong duality
\(f_i(x^*) \leq 0\)
\(h_i(x^*) = 0\)
\(\lambda_i^* \geq 0\)
\(\lambda_i^*f(x_i^*) = 0\)
\(\nabla f_0 (x^*) + \sum \lambda_i^* \nabla f_i (x_i^*) + \sum \nu_i^* \nabla h_i (x^*) = 0\)
Thms of alternatives#
Pairs of systems where at most one (weak) or exactly one (strong) is solvable. Farkas’s lemma is the standard example, and a solution of one system certifies that the other is infeasible.
weak alternative - at most one of 2 is true
strong alternative - exactly one is true
ex. Fredholm alternative
ex. Farkas’s lamma
\(\exists x \: Ax \leq 0, c^Tx < 0\)
\(\exists y \: y \geq 0, A^Ty + c = 0\)
Approx + fitting (boyd 6)#
Fitting problems built on \(\vert\vert Ax - b \vert\vert\). The choice of norm or penalty decides which residuals matter, a regularizer trades fit for small \(x\), and robust versions account for uncertainty in \(A\).
Norm approx problem#
Least squares, weighted least squares, Chebyshev (minimize the largest residual) and penalty function approximation are the same problem with different norms or penalties on \(r = Ax - b\).
minimize \(\vert \vert Ax-b\vert \vert\)
ex. weighted norm approx. min||W(Ax-b)||
ex. least squares min ||Ax-b||\(_2^2\)
ex. chebyshev approx norm min||Ax-b||\(_\infty\)
ex. penalty function approx problem: \(\min \: \phi(r_1) + ... + \phi(r_m)\\s.t. \: r=Ax-b\)
Least norm problem#
min \(\vert \vert x\vert \vert \\s.t. \: Ax=b\) ~ min \(\vert \vert x_0+ Zu\vert \vert\), Z cols basis for N(A)
Regularized approximation#
Two goals at once: a small residual and a small regularizer, traded off by \(\gamma\). Tikhonov uses squared \(\ell_2\) norms for both; lasso and total variation use other penalties.
residual + regularizer
min \(\cblue{\vert \vert Ax-b\vert \vert} + \corange{\gamma \vert \vert x\vert \vert}\)
min \(\cblue{\vert \vert Ax-b\vert \vert ^2} + \corange{\gamma \vert \vert x\vert \vert ^2}\)
Tikhonov: \(\min \: \cblue{\vert \vert Ax-b\vert \vert _2^2} + \corange{\gamma \vert \vert x\vert \vert _2^2}\)
examples
ex. regularize w/ ||Dx||
ex. lasso
ex. quadratic smoothing
ex. total variation
Robust approximation#
When \(A\) is uncertain, either minimize the expected error over a random \(A\) or the worst-case error over a set \(\mathcal A\).
\(A = \bar{A} + U\) ~ random w/ mean 0
stochastic robust approx problem: \(\min \: E\vert \vert Ax-b\vert \vert\)
(worst-case) robust approx prob: \(\min \: \sup \vert \vert Ax-b\vert \vert \: \vert A \in \mathcal{A}\)
Function fitting#
\(f(u) = x_1 f_1 (u) + .... + x_n f_n (u)\) ~ \(f_i\) are basis funcs, \(x_i\) are coefficients
sparse descriptions + basis pursuit
interpolation
Unconstrained minimization (boyd 9)#
The bounds \(mI \preceq \nabla^2 f \preceq MI\) come up again and again below: their ratio \(\kappa = M/m\) bounds the condition number, and it controls how fast gradient descent converges.
Unconstrained problems#
Without constraints, the optimum of a differentiable convex \(f\) is where \(\nabla f = 0\). Strong convexity (\(mI\)) and smoothness (\(MI\)) bound \(f\) between two quadratics, which gives a stopping rule: a small gradient means \(f(x)\) is close to \(p^*\).
\(x^* = \text{argmin} \: f(x) \implies \nabla f(x^*) = 0\)
examples
ex. quadratic: \(\min \: 1/2 x^TPX + q^Tx + r\)
solved w/ \(Px^* + q = 0\), if \(P \succeq 0\), unique soln \(-P^{-1}q\)
ex. unconstrained geometric program
ex. analytic center of linear inequalities
\(\min \: f(x) = -\sum \: \log (b_i - a_i^Tx)\)\( where dom f = \)\(\{x\vert a_i^Tx< b_i, i = 1:m\}\)
3 definitions of convexity
\(0 \leq \theta \leq 1\)
\(f(\theta x_1 + (1 - \theta) x_2) \leq \theta f(x_1) + (1 - \theta) f(x_2)\)
\(\nabla^2 f(x) \succeq 0\)
\(f(x_2) \geq f(x_1) + \nabla f(x_1)^T (x_2 - x_1)\)
\(0 \preceq \cgreen{\underset{\text{strong convexity}}{mI}} \preceq \nabla^2 f(x) \preceq \corange{\underset{\text{smoothness}}{MI}}\)
\(\kappa = M/m\) bounds condition number of \(\nabla^2 f = \frac{\lambda_{\max}(\nabla^2 f)}{\lambda_{\min}(\nabla^2 f)}\)
strongly convex: \(\nabla^2 f(x) \succeq \cgreen{mI}\)
\(\implies f(x_2) \geq f(x_1) + \nabla f(x_1)^T(x_2-x_1) + \cgreen{m/2 \vert \vert x_2-x_1\vert \vert _2^2}\)
minimizing yields \(p^* \geq f(x) - 1/(2m) \vert \vert \nabla f(x)\vert \vert _2^2\)
if the gradient of f at x is small enough, then the difference between f(x) and p⋆ is small
smooth: \(\exists \: M, \: \nabla^2f(x) \preceq \corange{MI}\)
\(\implies f(y) \leq f(x) + \nabla f(x)^T(y-x) + \corange{M/2 \vert \vert y-x\vert \vert _2^2}\)
cond(C) = \(W_{\max}^2 / W_{\min}^2\)
width of convex set \(C \subset \mathbb{R}^n\) in direction q with \(\vert \vert q\vert \vert _2=1\)
\(W(C, q) = \underset{z \in C}{\sup} \: q^Tz - \underset{z \in C}{\inf} \: q^Tz\)
alpha-level subset: \(C_\alpha = \{x\vert f(x) \leq \alpha\}\)
Descent methods#
Every method below picks a descent direction \(\Delta x\) and a step size \(t\). Backtracking line search starts at \(t = 1\) and shrinks it by \(\beta\) until the step decreases \(f\) by enough.
update rule \(x = x + t \Delta x\)
exact line search: \(t = \underset{s \geq 0}{\text{argmin}} \:f(x+s \Delta x)\)
backtracking line search
given a descent direction \(\Delta x \text{ for } f, x \in dom \: f, \alpha \in (0, 0.5), \beta \in (0, 1)\)
t:=1, \(\alpha \in (0, 0.5), \beta \in (0, 1)\)
while \(f(x + t \Delta x) > f(x) + \alpha t \nabla f(x)^T \Delta x\)
\(t *= \beta\)
Gd method#
Gradient descent is the descent method with \(\Delta x = -\nabla f(x)\). Its speed depends on the condition number of the Hessian.
convergence
can bound number of iterations required to be less than \(\epsilon\)
examples
a quadratic problem in \(R^2\)
non-quadratic problem in \(R^2\)
a problem in \(R^{100}\)
gradient method and condition number
conclusions
gd often exhibits approximately linear convergence
convergence rate depends greatly on \(cond (\nabla^2 f(x))\) or sublevel sets
Steepest descent method#
Steepest descent depends on the norm used to measure the step. The Euclidean norm gives gradient descent, a quadratic norm \(\vert\vert \cdot \vert\vert_P\) gives \(-P^{-1}\nabla f\), and \(\ell_1\) moves one coordinate at a time.
examples
euclidean norm: \(\Delta x_{sd} = - \nabla f(x)\)
quadratic norm \(\vert \vert z\vert \vert _P = (z^TPz)^{1/2} = \vert \vert P^{1/2}z\vert \vert _2\) where \(P \in S_{++}^n\)
\(\Delta x_{sd} = -P^{-1} \nabla f(x)\)
\(\ell_1\) norm: \(\Delta_{sd} = -\frac{\partial f(x)}{\partial x_i} e_i\)
Newton’s method#
The Newton step rescales the gradient by the inverse Hessian. The Newton decrement \(\lambda^2\) gives the stopping criterion \(\lambda^2 / 2 \leq \epsilon\), and backtracking line search picks the step size.
Newton step \(\Delta x_{nt} = - \nabla^2 f(x)^{-1} \nabla f(x)\)
PSD \(\implies \nabla f(x)^T \Delta x_{nt} = - \nabla f(x)^T \nabla^2 f(x)^{-1} \nabla f(x) < 0\)
Newton’s method
compute the newton step \(\Delta x_{nt}\) and decrement \(\lambda^2 = \nabla f(x)^T \nabla^2 f(x)^{-1} \nabla f(x)\)
stopping criterion: quit if \(\lambda^2 / 2 \leq \epsilon\)
line search: choose step size t w/ backtracking line search
update: \(x += t \Delta x_{nt}\)
Basic algorithms#
The same methods from the data side. For least squares, the gradient is a sum over examples of the example times its residual, and SGD estimates that sum from one example or a mini-batch.
types: batch (have full data) vs online
gradient descent = batch gradient descent
gradient - vector that points to direction of maximum increase
at every step, subtract gradient multiplied by learning rate: \(x_k = x_{k-1} - \corange{\alpha} \cblue{\nabla_x F(x_{k-1})}\)
alpha = 0.05 seems to work
\(J(\theta) = 1/2 (\theta ^T X^T X \theta - 2 \theta^T X^T y + y^T y)\)
\(\nabla_\theta J(\theta) = X^T X \theta - X^T Y\)
= \(\sum_i \cblue{x_i} \corange{(x_i^T - y_i)}\)
this represents residuals * examples
stochastic gradient descent
don’t use all training examples - approximates gradient
single-sample
mini-batch (usually better in offline case)
coordinate-descent algorithm
online algorithm - update theta while training data is changing
when to stop?
predetermined number of iterations
stop when improvement drops below a threshold
each pass of the whole data = 1 epoch
benefits
less prone to getting stuck to shallow local minima
don’t need huge ram
faster
newton’s method for optimization
second-order optimization - requires 1st & 2nd derivatives
\(\theta_{k+1} = \theta_k - \corange{H_K^{-1}} \cblue{g_k}\)
update with inverse of Hessian as alpha - this is an approximation to a taylor series
finding inverse of Hessian can be hard / expensive
ADMM - alternating direction method of multipliers (ADMM) is an algorithm that solves convex optimization problems by breaking them into smaller pieces, each of which are then easier to handle
Expectation maximization - Jordan ch 11#
Maximizing \(\log p(x|\theta)\) directly is hard because it sums over the hidden \(z\). Jensen’s inequality gives a lower bound \(\mathcal L\) that EM raises in turns: the E step fits the distribution over \(z\), the M step fits \(\theta\).
from Michael Jordan’s “An Introduction to Probabilistic Graphical Models”
method to maximize likelihood on model with observed X and hidden Z
expectation step - values of unobserved latent variables are filled in
calculates prob of latent variables given observed variables and current param values
maximization step - parameters are adjusted based on filled-in variables
goal: maximize complete log-likelihood, but don’t know z
expected complete log-likelihood \(E_{p'}[l(\theta; x,z)] = \sum_z p'(z\vert x,\theta) \cdot \log \: p(x,z\vert \theta)\)
p’ distribution is assignment to z vars
deriving auxilary function \(\mathcal L(q, \theta, x) = \sum_z p'(z\vert x) \log \frac{p(x,z\vert \theta)}{p'(z\vert x)}\) - lower bound for the log likelihood
- \[\begin{split}\begin{align} l(\theta; x) &= \log \: p(x\vert \theta) & \text{incomplete log-likelihood} \\&= \log \sum_z p(x,z\vert \theta) &\text{complete log-likelihood}\\&= \log\sum_z p'(z\vert x) \frac{p(x,z\vert \theta)}{p'(z\vert x)} &\text{multiplying by 1} \\ &\geq \sum_z p'(z\vert x) \log \frac{p(x,z\vert \theta)}{p'(z\vert x)} &\text{Jensen's inequality}\\&\triangleq \mathcal L (p', \theta) \end{align}\end{split}\]
this removes dependence on z
steps
E: \(p'(z\vert x, \theta) = \underset{p'}{\text{argmax}}\: \mathcal L(p',\theta, x)\)
M: \(\theta = \underset{\theta}{\text{argmax}} \: \mathcal L(p', \theta, x)\)
equivalent to maximizing expected complete log-likelihood
stochastically converges to local minimum
alternatively, can look at kl-divergences
Misc#
Nn optimization#
Why is it hard?#
The shapes listed below are what make neural network losses hard to minimize. The widget shows one of them, a winding canyon, and what momentum does about it.
plateaus
winding canyons
cliffs
local maxima to dodge
saddle points (local max and local min)
most popular
sgd
sgd + nesterov momentum
adam
adagrad - maintains a per-parameter learning rate that improves performance on problems with sparse gradients
rmsprop - (ignore) per-parameter learning rates that are adapted based on the average of recent magnitudes of the gradients for the weight (e.g. how quickly it is changing)
adam - “adaptive moment estimation” (kingma_2015)
\(\cblue{m_t}=\beta_1 \cblue{m_{t-1}}+\left(1-\beta_1\right) g_t\) (1st moment) \(\corange{v_t}=\beta_2 \corange{v_{t-1}}+\left(1-\beta_2\right) g_t^2\) (2nd moment) \(\cblue{\widehat{m}_t}=\frac{\cblue{m_t}}{1-\beta_1^t}\) (bias correction) \(\corange{\hat{v}_t}=\frac{\corange{v_t}}{1-\beta_2^t}\) (bias correction) \(\theta_t=\theta_{t-1}-\alpha \frac{\cblue{\widehat{m}_t}}{\sqrt{\corange{\hat{v}_t}}+\epsilon}\)
Hyperparameters: \(\beta_1=0.9, \beta_2=0.999, \epsilon= 10^{-8}\)
Intuition: \(m_t\) is an EMA of gradients (momentum), and \(v_t\) is an EMA of squared gradients (adaptive per-parameter scaling, like RMSProp). Dividing by \(\sqrt{\hat{v}_t}\) gives each parameter its own effective learning rate - large-gradient directions get damped, small-gradient directions get amplified. The bias-correction terms fix the fact that \(m_t\) and \(v_t\) are biased toward zero in early steps (since they’re initialized at zero) with \(m_0=v_0=0\).
keep track of per-parameter learning rate (based on first moment of gradients tracked) and per-parameter second moment (based on variance of gradients tracked)
alpha - learning rate
beta1 - exponential decay rate for first moment estimate
default 0.9
beta2 - exponential decay rate for 2nd moment estimates (should be higher when gradients sparser)
default 0.999
epsilon - small number to prevent division by zero
requires low dims
goodfellow 2015 “Qualitatively characterizing neural network optimization problems” plots loss on line from starting point to ending point
could do PCA on params
Complicated is simpler#
ex. \(x^3 \sin(x)\) is simpler than just \(x\) on the domain [−0.01, 0.01]
dropout is like ridge
Mixed integer programming (mip)#
A linear program where some variables must be integers. Branch-and-bound solves the relaxation without integer constraints, then splits on a variable with a fractional value into two subproblems and repeats.
Notes from this overview
ex: minimize \(c^{\top} x\) s.t.
\(\mathrm{A} \mathrm{x}=\mathrm{b}\) (linear constraints)
\(l\leq x \leq u\) (bound constraints)
some or all \(x_j\) must take integer values (integrality constraints)
solving: branch-and-bound
integer constraints make this difficult so start by solving the relaxation without integer constraints
pick one of the variables \(x_b\) that was not integer to be our branching variable
say it’s value was 5.7, now solve 2 MIPS, one with constraint \(x_b \leq 5\) an \(x_b \geq 6\)
return better solution of these two
iterate by solving relaxation and then adding more branching constraints
Key ideas
Convexity can be checked from the definition, the Hessian, tangent planes or the epigraph, but usually it is easier to build a function from operations that preserve convexity.
The Lagrange dual function is a lower bound on \(p^*\) for every \(\lambda \succeq 0\); under strong duality (for example Slater’s condition) the bound is tight and the KKT conditions characterize the optimum.
The duality gap \(f_0(x) - g(\lambda, \nu)\) bounds how suboptimal a feasible point is.
Gradient descent converges roughly linearly at a rate set by the condition number of the Hessian; Newton’s method rescales by the inverse Hessian at a higher cost per step.
EM maximizes a lower bound on the log-likelihood from Jensen’s inequality, alternating between the hidden variables and the parameters.
Neural network losses are hard because of plateaus, canyons, cliffs and saddle points; momentum and per-parameter step sizes as in Adam help.