Chemokinesis and the Curse of Dimensionality
Chemokinesis is movement whose speed depends on a local chemical signal, without any directional sensing.
This can create accumulation without directional knowledge, which makes it tempting to view as gradient-free optimization. That interpretation is only partly right.
The Basic Mechanism
Particles that move more slowly in some regions than others tend to accumulate in the slow regions. If a particle enters a slow region, it takes longer to leave. After enough time, more particles are found there, even though no individual particle ever knew that region was special.
The same idea carries over to optimization. A chemokinetic optimizer does not estimate a gradient or compare directions. It only changes its step size based on a local scalar observation. That is both the appeal and the limitation.
A Direction-Free Random Walk
Suppose we want to minimize a cost function
\[f : \mathbb{R}^d \to \mathbb{R}.\]A simple chemokinetic random walk: at position $x_t$, choose a random unit direction $u_t$, take a step of length $r(x_t)$, and move to
\[x_{t+1} = x_t + r(x_t) u_t.\]The direction is still random. There is no hidden gradient. In continuous time, a related idealization is a diffusion with state-dependent mobility,
\[dX_t = \sigma(X_t)\,dW_t,\]where $W_t$ is isotropic Brownian motion. There is no explicit drift term. But if $\sigma(x)$ is smaller in some regions, the particle moves more slowly there, biasing the stationary distribution toward low-mobility regions. This is called the residence-of-time effect and one can exploit this effect by coupling mobility to cost. We will now explore how this behaves in high dimensions.
Where The Curse of Dimensionality Enters
In high dimensions, random directions are almost always unhelpful.
Let $x^\ast$ be a minimizer, and let
\[\rho = \|x - x^\ast\|\]be the distance to it. For a random unit vector $u$ and a fixed unit direction $v$, the inner product $\langle u, v \rangle$ has mean zero and variance $1/d$. The component of a step in the useful direction is typically $O(r/\sqrt{d})$. The rest is transverse. So intuitively, as dimensionality increases, we can’t rely on random steps to create a residence-of-time effect, because they are increasingly unlikely to pointin the right direction.
A complementary perspetive is that of volumes: Most of the volume of a high-dimensional ball lies near its boundary. The ratio between the volume of a thin outer shell of thickness $\varepsilon$ and the volume of the whole ball of radius $R$ is approximately
\[1 - \left(1 - \frac{\varepsilon}{R}\right)^d.\]For fixed relative thickness $\varepsilon/R$, this ratio approaches one as $d$ grows.
This matters because a random walk has no natural reason to move inward. From a fixed target, an unbiased random step tends to increase distance. For small $r/\rho$, the expected change in distance behaves like
\[\mathbb{E}[\Delta \rho] \approx \frac{r^2}{2\rho}\left(1 - \frac{1}{d}\right).\]What Chemokinesis Can Still Do In Sufficiently High Dimensions
Chemokinesis can still be useful as an avoidance rule. Let’s revisit our biological intuitiion from before. It’s practically more important for bacteria to quickly leave harmful environments than to find the globally optimal one to avoid timely death. We can analyze this mathematically:
Near a local maximum at $x^\ast$, a second-order approximation gives
\[f(x^\ast + \delta) \approx f(x^\ast) + \frac{1}{2}\delta^T H \delta,\]where $H$ is the negative definite Hessian of the cost. Every sufficiently small step away from $x^\ast$ lowers the cost, so even a purely random walk will take a directionally correct step.
Take a random step $\delta = r u$ with step size $r$ and random unit direction $u$. The expected change in cost is
\[\mathbb{E}[f(x^\ast + r u) - f(x^\ast)] \approx \frac{r^2}{2} \mathbb{E}[u^T H u] = \frac{r^2}{2d} \operatorname{tr}(H),\]where we use $\mathbb{E}[u u^T] = \frac{1}{d} I$. Since $H$ is negative definite, $\operatorname{tr}(H) < 0$, so the expectation is negative: the walk descends in expectation.
Now suppose the chemokinetic rule sets step size $r(x)$ proportional to cost. It takes steps of size $r_{\max}$, while a plain random walk is stuck with some fixed $r_0 < r_{\max}$. The ratio of expected descent is
\[\frac{\mathbb{E}[\Delta f_{\text{chemokinetic}}]}{\mathbb{E}[\Delta f_{\text{random}}]} = \left(\frac{r_{\max}}{r_0}\right)^2.\]The chemokinetic walker does not know which direction is downhill, but because it takes larger steps exactly where any direction is likely to help, it descends faster in expectation. The quadratic scaling comes from the fact that the expected cost change is proportional to $r^2$ through the second-order term $\delta^T H \delta$.
Conclusion
Chemokinesis is best understood as a residence-time mechanism. It can make a process linger in favorable regions and move away quickly from unfavorable ones. In low-dimensional systems such as pyhsical reality, this is a useful strategy and can be used as mathematical model for the movement of simple organisms. But as dimensionality increases, the bias decreases until it becomes as unhelpful as a purely random walk. Hence, it’s a prime example for how the curse of dimensionality can destory some ideas. At the same time, we also found out that chemokinesis is superior compared to a random walk for escaping maxima independent of dimension.