# Nonholonomic Stochastic Gradient Descent

In this lecture, we consider an application of the previous results on shaping the densities of stochastic processes using the corresponding Fokker-Planck equation. The application is mainly aimed at offering a new perspective on classic questions in control, and we will not derive anything new.

Recall the notion of asymptotic stabilizability of a control system:

$$\dot{x}= f(x,u)$$

The system is said to be smoothly asymptotically stabilizable using time-invariant feedback if there exists a smooth control law $u_i(x)$ such that a given equilibrium point $x^*$ is [locally asymptotically stable](https://).

Asymptotic stabilizability criteria are well known for linear systems $\dot{x} = Ax + Bu$ and for nonlinear systems whose linearizations are controllable. On the other hand, for a large class of nonlinear systems, such as those of the form
$$\dot{x} = \sum_{i=1}^m u_i(t)g_i(x)$$
linearizations can fail to be controllable, and hence stabilizability can be more challenging to verify. However, [Roger Brockett has shown](https://courses.ece.ucsb.edu/ECE594/594D_W10Byl/hw/Brockett83.pdf) that generally driftless systems cannot be smoothly stabilized.

Before we get to Brockett, let’s introduce a natural approach to stabilizability from an optimization point of view. Consider a gradient system:
$$\dot{x} = -\nabla V(x)$$
where $\nabla$ is our friendly neighborhood *gradient* operator, and $V$ is some *potential function*.

It is well known that under some conditions, the solution converges to local minima of the system. For instance, if the function has a single critical point that is a minimizer and the level sets of $V$ are compact, then using [LaSalle's invariance principle](https://en.wikipedia.org/wiki/LaSalle%27s_invariance_principle) the solution converges to the minimum. Therefore, this may provide a convenient way to feedback-stabilize a control system to a target point.

Suppose we have the simplest control system known to humanity, our painfully single integrator,
$$\dot{x} = u.$$

Then our strategy for feedback stabilization is simple:

1. Find a nice potential function $V: \mathbb{R}^d \rightarrow \mathbb{R}$
2. Choose the control law $u_i(x) = -\partial_{x_i} V$

Proportional control for the single integrator is the simplest instance of this idea, with $V = k\|x- x^*\|^2$ for some positive constant $k>0$. The corresponding choice of control is:
$$ u_i(x) = k (x_i-x^*)$$

## Non-holonomic Gradient Descent and Why It's Doomed

This idea of controlling using energies can be generalized using Lyapunov functions. But what is less well known is whether we can generalize gradient descent to nonlinear control systems. Here is a first attempt, along with an explanation of why it is bound to fail. Suppose we have a driftless control system
$$\dot{x} = \sum_{i=1}^m u_i(t) g_i(x)$$

Corresponding to the vector fields $g_i(x)$, [we saw](https://hackmd.io/A5jrrf8-SLG_w8tMls45Yg) the differential operators

$Y_i = g^j_i(x) \partial_{x_j}$

Mimicking the intuition from gradient systems, we might guess the following choice of feedback control laws:

1. Find a nice potential function $V: \mathbb{R}^d \rightarrow \mathbb{R}$
2. Choose the control law $u_i(x) = -Y_iV$

This would give us, as control theorists, our own version of gradient systems, or **nonholonomic gradient system**:

$$ \dot{x} = -\nabla_H V$$

where
$$\nabla_H V : = \sum_{i} -\big(X_iV(x)\big)g_i(x)$$

So now we can ask: **Do nonholonomic gradient systems behave as nicely as classical gradient systems?**

Unfortunately, nonholonomic gradient system is bound to fail to have nice long-term behavior if $V$ is twice differentiable. Part of the problem is that even if the system is globally controllable, the zeros of $\nabla_H V$ form a much larger set than the zeros of $\nabla V$, and this is almost always the case. To understand why, let’s review **Brockett's condition** for a topological obstruction to feedback stabilizability.

$$
\boxed{\begin{aligned}
&\textbf{Theorem (Brockett's condition).}\\
&\textit{If the equilibrium } x = 0 \textit{ of the } C^{1} \textit{ system } \dot{x} = f(x,u) \\
&\textit{is locally asymptotically stabilizable by a } C^{1} \textit{ state-feedback, then the image of} \\
&\textit{the mapping } f(x,u) \textit{ contains a neighborhood of } 0. \textit{ That is, there exists } \delta>0 \textit{ such that} \\
&\forall \,\xi \text{ with } \|\xi\|\le \delta,\ \exists\, x,u \text{ such that } f(x,u)=\xi .
\end{aligned}}$$

Let’s apply this theorem quickly to a concrete example to see what can go wrong for driftless systems. Consider the nonholonomic integrator

\begin{align*}
&\dot{x} = u_1 \\
&\dot{y} = u_2 \\
&\dot{\theta} = x_1 u_2 - x_2 u_1 \\
\end{align*}
This system is globally controllable -- one can transfer it from any point in space to another using a suitable choice of time-dependent controls $(u_1,u_2)$. However, it fails the necessary condition for stabilizability. Clearly, vectors of the form $$[0, ~0, ~\varepsilon ]^T$$ cannot be realized by a choice of $(x,u)$ for any $\varepsilon >0$, as the first two coordinates force the controls $u$ to be $0$.

There are multiple ways to get around this obstruction. One is to use time-varying feedback laws. Another is to use discontinuous or hybrid feedback. A third, less well known procedure is to use stochastic feedback laws.

We can interpret our results from Lecture 1, 2, and 3 as a form of stochastic stabilization. This brings us to the stochastic variations of gradient systems.

# Stochastic Gradient Systems

Adding noise is a standard way to regularize problems. A kind of regularization also happens at the stabilizability level when we use noise, which is of course counterintuitive given that our goal is to stabilize the system.

If we add white noise to gradient systems, the governing equation is modified as follows:
$$ dX = -\nabla V(x)dt + \sqrt{2}dW + dZ$$
where $W$ is Brownian motion and $dW$ is white noise, and we are once again considering the constrained version of the process with the confining process $Z$ that keeps the solution in the domain $\Omega$. Strictly speaking, $Z$ makes it a projected stochastic gradient descent.

We have seen in the first lecture that, in distribution, this system converges to the Gibbs distribution $e^{-V(x)}$. Therefore, instead of the process converging to a single point, it converges to a distribution with higher concentration around minimizers of $V$.

The same idea appears to work even when the system is non-holonomic, unlike in the deterministic case above. Loosely speaking, if we work with the version of the gradient system that is confined to a compact domain, we have seen that if $Y_i = -Y^*_i$, the choice
$$u_i(x) = -Y_iV + \sqrt{2}dW_i,$$
leads to
$$\rho_X(t) \rightarrow Ce^{-V(x)},$$
where $C$ is a normalization constant. Unfortunately, the solution to the more general non-skew-adjoint case is not as nice, but one can still salvage the situation by considering a drift-corrected version of the control law,
$$u_i(x) = \sum_{j=1}^n\frac{\partial g_i^j}{\partial x_j}-Y_iV + dW_i,$$
then once again we have,
$$\rho_X(t) \rightarrow Ce^{-V(x)}.$$
Therefore, while **controllability** does not necessarily imply stabilizability of driftless controllable systems, it does **imply density stabilizability**.

To summarize, we can generalize our strategy for stabilization using gradient systems in the following way.

1. Find a nice potential function $V: \mathbb{R}^d \rightarrow \mathbb{R}$
2. Choose the control law $u_i(x) = \sum_{j=1}^n\frac{\partial g_i^j}{\partial x_j}-Y_iV + \sqrt{2} dW_i$

Even if $V$ is smooth, the long-term behavior is uniquely determined by $e^{-V}$. This should be surprising. Though deterministic nonholonomic gradient descent is extremely degenerate. The behavior of the stochastic version remains fairly very much like that of the simple integrator version.

## Numerical Example
To see the usefulness of this, the following is a visualization of the unicycle model performing stochastic gradient descent on the potential $V(x) = \|x^2\|.$

|  |
|:--------------------------------------------------------------------------------:|
| A single unicycle performing nonholonomic gradient descent along a potential.

# It's Not all Rosy

One thing to keep in mind is that density stabilization does not (and cannot) imply the most well known notions of stability in a stochastic sense. We are only able to guarantee, in some sense, that as $t \rightarrow \infty$, the system will mostly concentrate around the minimizer of $V$, depending on the distribution $Ce^{-V}$, but there is always a small probability that it will linger away from the minimizer.