Optimization and Learning via Stochastic Gradient Search

\begin{align*} \theta_{n+1} = \theta_n - [\nabla^2 J(\theta) ]^{-1} \nabla J(\theta_n) \end{align*}

• Step size is adaptive: \(\epsilon_n = [\nabla^2 J(\theta) ]\)

• In neighbourhood of local minima, the Hessian \(\nabla^2 J(\theta)\) is positive definite and thus:

  1. Hessian is invertible
  2. Multiplying the negative gradient direction by hessian still gives a descent

  direction [Lemma 1.1]

Benefits:

• Quadratic convergence

Problems:

• Hessian may not be invertible at every point
• Zeros can be inflection point
• Computation at each step is expensive (compute gradients, hessian, inversion of hessian)

Quasi-newton methods attempt to solve those problems. E.g. Barzilai-Borwein method used in Gradient Projection for Sparse Reconstruction paper.

At each step move along the gradient direction until you reach minima on that line.

\begin{align*} \epsilon_n = \arg \min_{\epsilon > 0} J(\theta_n - \epsilon \nabla J(\theta)) \end{align*}

Non-adaptive step size means step size is independent of the current parameter \(\theta\). The step size is either constant or decreasing.

There are theorems for convergence of the gradient descent algorithm. In the proof of these theorems (Theorem 1.3, Theorem 1.4) on crucial relation (lets call Descent Lemma) is used:

\begin{align*} J(\theta_{i+1}) < J(\theta_i) - \epsilon_i \left( 1 - \frac 1 2 L \epsilon_i \right) ||\nabla J (\theta_i)||^2 \end{align*}

So, when the step size is small \(\epsilon_i < 2 / L\) then the cost function decreases with each step.

• For decreasing step size, after sufficiently large \(n\) the step size will satisfy the relation and the algorithm converges.
• For fixed step size, we explicity require this relation to be satisfied.

If the descent direction \(d(\theta)\) is bounded then we need following for our algorithm to be able to explore all of the parameter space:

\begin{align*} \sum_{n=1}^\infty \epsilon_n = \infty \end{align*}

Theorem 1.4 [# 30] If the step size if fixed, just like Theorem 1.3 gradient descent converges to a stationary point or leads to a monotone decreasing sequence, when the following conditions are met:

1. The gradient is Lipschitz continuous with Lipschitz constant \(L\)
2. The step size satisfies \(0 < \epsilon < 2/L\)

Theorem 1.4 has extensions similar to Lemma 1.3. When the gradient is biased the algorithm converges to solution of \(\nabla J(\theta) + \beta = 0\) i.e. solution of adjusted objective \(J(\theta) + \beta \theta\)

(where \(\beta\) is the limit of the bias \(\lim \beta_n \to \beta\)).

The Lagrangian associated to this NLP is

\begin{align*} \mathcal L(\theta, \lambda, \eta) = J(\theta) + \lambda g(\theta) + \eta h(\theta) \end{align*}

Interpretaion of Lagrange multipliers:

The lagrange multipliers can be viewed as the rate of change of the optimal cost as the level of constraint changes. See Theorem 1.7. Practically, in economics they are called shadow prices, in physics they can represent concrete physical quantities.

Constraint qualification conditions:

For lagrangian formulation to be useful with gradient based methods, some "constraint qualification" conditions must be satisfied. These conditions ensure that lagrange multipliers satisfying KKT conditions exist at the satitionary point. In other words, without constraint qualification conditions, there can be stationary points (and local minimas) that don't satisfy KKT condition. The constraint qualificationc conditions are:

1. The gradients of constraints \(\{ \nabla h_i (\theta); \nabla q_i(\theta)\}\) must be linear independent,
2. And there must exist a direction where we can move without invalidating the constraints. i.e. \(v\) exists such that
   • \(\nabla h_i(\theta) v = 0\)
   • \(\nabla g_i(\theta) v < 0\) for all \(g_i\) that are active.

Karush Kuhn Tucker (KKT) condition:

If constraint qualification conditions hold at a local minima then the KKT conditions is satisfied. Those statitionary points which also satisfy KKT condition are called KKT points.

1. The first order optimality condition for the original NLP:

   \begin{align*} \nabla_\theta \mathcal L(\theta, \lambda, \eta) = 0 \end{align*}

2. The inequality constraint:

   \begin{align*} \nabla_\lambda \mathcal L(\theta, \lambda, \eta) = g(\theta) < 0 \end{align*}

   And complimentary slackness condition for inequality constraint:

   \begin{align*} \lambda_i g_i(\theta) = 0 \end{align*}

   Which means either the constraint \(g_i(\theta) < 0\) is inactive (requiring \(\lambda_i = 0\)) or the constraint itself is active \(g_i(\theta) = 0\).

3. The equality constraint:

   \begin{align*} \nabla_\eta \mathcal L(\theta, \lambda, \eta) = h(\theta) = 0 \end{align*}

Second order condition:

The KKT condition provide the first order condition. For the KKT point of be a local minima there is a second order condition that must be satisfied. It states, that the Hessian of \(\mathcal L\) must be positive definite for those directions that don't violate the constraints. i.e. for directions \(v \in C(\theta^*, \lambda^*)\), we need

\begin{align*} v^T \nabla^2_\theta \mathcal L(\theta, \lambda, \eta) v > 0 \end{align*}

where, the set of direction \(C\) is defined as set of directions \(v\) that satisfy:

1. \(\nabla h v = 0\)
2. \(\nabla g v = 0\) if \(g\) is active, and \(\nabla g v < 0\) if \(g\) is inactive.

This is given in Theorem 1.6 [# 34]

We solve the unconstrainted problem:

\begin{align*} J_\alpha (\theta) = J(\theta) + \frac {\alpha} 2 \left( || g(\theta)_+ ||^2 + ||h(\theta)||^2 \right) \end{align*}

where \(g_i(\theta)_+ = max(0, g_i(\theta))\)

Increase \(\alpha\) to get better solutions:

Theorem 1.8 [# 36] If we increase \(\alpha\) such that \(\alpha_n \to \infty\), then the limit of the optimal points \(\theta_n(\alpha_n)\) (if it exists) is a stationary point of the original constrained optimization problem.

And the lagrange multipliers are:

\begin{align*} \lambda = \lim_{n \to \infty} \alpha_n (g(\theta_n))_+, \eta = \lim_{n \to \infty} \alpha_n h(\theta_n) \end{align*}

Use gradient based method:

Theorem 1.8 assumes we solve each subproblem exactly, but practically we use gradient based method to solve each sub problem. For each sub problem we do \(T_n\) iterations (or until an stopping criteria), and initialize the next sub problem with solution of previous sub problem \(\theta^{n+1}_0 = \theta^n_{T_n}\).

Usually \(T_n\) is small at beginning and is increased later on.

Alternatively, we can use \(T_n = 1\) and increase \(\alpha_n\) very slowly. This a two-timescale variation of the penalty method. [# 38]

There is no gurantee of convergence for inexact minimization, i.e. iterative algorithm for both penalty based and multiplier methods.

At each step of gradient descent, project the solution \(\tilde \theta_{n+1}\) to the space where constraints are satisfied.

Theorem 1.9 [# 41] gives same gurantees as Theorem 1.3 and Theorem 1.4 give for unconstrained optimization using variable and fixed step sizes respectively.

Useful for theoritical analysis:

The exact computation of projection is often the most computationally expensive part. And although not feasbile for most problems, the projection method is very useful for theoritical analysis of algorithms. If projected version of the algorithm converges, then the unprojected version also converges [# 42 Remark 1.3]. And projecting on a large enough bounded set relaxes some of the constraints for theoritical results in unprojected version, e.g. the need for gradient being bounded is removed if we project to some bounded set.

For an example of projection method see Gradient Projection for Sparse Reconstruction paper. There they convert a unconstrained problem (minimize \(|x|\)) to constrained problem (minimze \(u - v\) with \(u,v \geq 0\)) and use projection to a hypercube to enforce the constraint.

Solve the problem for a value of multiplier \(\eta_n\), then keep on increasing \(\eta\). The algorithm is:

\begin{align*} \theta_n = \arg \min_\theta \mathcal L (\theta, \eta_n) \\ \eta_{n+1} = \eta_n + \rho_n h(\theta_n) \end{align*}

where \(\rho_n \to \infty\), then the limit of the solution \((\theta_n, \eta_n) \to (\theta^*, \eta^*)\) leads to the local minima of original problem.

Instead of solving for \(\theta_n\) exactly, we can use gradient based method for inexact solution upto time step \(T_n\) like in penalty based method.

For both penalty method and multiplier methods there is no gurantee of convergence for inexact minimization.

For each lagrange problem there is a dual problem expressed as a min max problem.

In Uzawa algorithm [# 45], we alternative between

1. updating \(\theta\) that minimizes the lagrangian
2. updating \(\lambda, \eta\) to increase the lagrangian

Instead of exact minimization wrt \(\theta\), Arrow-Hurwicz iterative algorithm alternates between:

1. updating \(\theta\) to decrease the lagrangian (a gradient descent step)
2. updating \(\lambda, \eta\) to increase the lagrangian (a gradient ascent step)

Finding a parameter \(\theta\) so that a system output reached a specified value \(\alpha\). It is also called target tracking problem in control literature. This problem is an example of unsupervised learning.

E.g. Thermostat: The temperature readings \(L(\theta)\) are stochastic and we want it to match a desired temperature \(\alpha\).

Robbins-Monro Algorithm:

It proves that SA converges to root of a function if the step size satisfy a condition called the Robbins-Monro Conditions: \(\sum \epsilon_n = \infty\) and \(\sum \epsilon^2 < \infty\)

The proof assumes that \(L(\theta)\) is nondecreasing..

Take as an example:

\begin{align*} J(\theta) = \frac 1 2 \mathbb E [\left( Z(X) - (\theta_1 + \theta_2 X) \right)^2] \end{align*}

We can derive the expression for gradient and use an iterative algorithm. But we don't know the (random) function \(Z\), we just have estimate of \(Z(x)\) from random samples of \(x\).

Assuming that \(\{x_n\}\) are independent and randomly distributed we can use SA algorithm called Least mean square (LMS) or recursive mean square algorithm. [# 95]

• \(G(\theta)\) is a vector field whose zeros we want to find.
• We can't observe \(G(\theta)\)
• It is governed by an underlying process \(\xi(\theta)\) as \(G(\theta) = \mathbb E [ g(\xi(\theta, \theta))]\)
• But we don't know \(g\) either.
• Instead we just have a feedback function \(\phi(\xi(\theta), \theta)\) as a proxy for \(g\)

• So, take

  \begin{align*} G(\theta) = \mathbb E [\phi(\xi(\theta), \theta)] + \beta(\theta) \end{align*}

• Take initial value \(\theta_0\), and step size sequence following Robbin-Monro conditions and do \(\theta\) update

  At each step of update, we have \(\theta_n\) and we sample \(\xi_n(\theta)\) and evaluate the feedback function \(\phi\) and perform the update with stepsize \(\epsilon_n\).

For each fixed value of control parameter \(\theta\), the underlying process \(\{\xi_n(\theta)\}\) is a Markov chain.

And vector field \(G\) is meant to capture long-term behaviour of the model,

\begin{align*} G = \lim_{N \to \infty} \frac 1 N \mathbb E \left[\sum_{n=1}^N g(\xi_n(\theta), \theta) \right] = \int g(\xi_n(\theta), \theta) \pi_\theta(d\xi) \end{align*}