Chemokinetic optimization under stochastic actuation

In chemokinetic optimization, an external stochastic process supplies an isotropic random unit direction \(u_t\), while the controller chooses only a nonnegative step length \(s_t\):

\[ \theta _{t+1}=\theta _t+s_tu_t,\qquad s_t\geq 0. \]

The controller must choose \(s_t\) before observing any loss along the current direction, cannot replace \(u_t\) by \(-u_t\), and receives only scalar loss values. With \(g=\nabla L(\theta )\) and \(H=\nabla ^2L(\theta )\), the local loss change is

\[ L(\theta +su)-L(\theta )=qs+\tfrac 12hs^2+o(s^2), \qquad q=g^\top u,\quad h=u^\top Hu. \]

Two questions follow: how much progress is possible when the current directional slope \(q\) is known, and how accurately \(q\) can be predicted before the move.

One-sided ray action and effective dimension

If \(q\) and \(h>0\) are available before the move, minimizing the local quadratic over \(s\geq 0\) gives

\[ s^*(u)=\frac {(-q)_+}{h}. \]

The positive part assigns zero motion when \(q\geq 0\). For a quadratic \(L(x)=\tfrac 12x^\top Hx\), consider the curvature-independent update \(x^+=x+\alpha (-g^\top U)_+U\), where \(U\) is uniform on the unit sphere and one scalar \(\alpha \) is chosen to maximize expected progress. Its optimal expected decrease relative to exact gradient line search is

\[ d_{\mathrm {eff}}(g,H) =\frac {d}{d+2}\left (\frac {\operatorname {tr}H}{\lambda _g}+2\right ), \qquad \lambda _g=\frac {g^\top Hg}{\lVert g\rVert ^2}, \qquad \frac {\Delta ^*_{\alpha \text {-Ray}}}{\Delta ^*_{\mathrm {GD}}} =\frac {1}{2d_{\mathrm {eff}}}. \]

This ratio concerns the single-\(\alpha \) update, not the directional-curvature oracle above. If \(H=\lambda P\) for a rank-\(r\) projector and \(g\in \operatorname {range}(P)\), then \(d_{\mathrm {eff}}=d(r+2)/(d+2)\to r+2\). With fixed active rank \(r\), adding exactly flat coordinates therefore leaves the limiting progress ratio unchanged.

The causal information barrier

Without a same-direction probe, the information available before the move is summarized by the posterior mean slope and curvature,

\[ \mu _t(u_t)=\mathbb E[u_t^\top g_t\mid \mathcal F_t^-,u_t], \qquad \kappa _t(u_t)=\mathbb E[u_t^\top H_tu_t\mid \mathcal F_t^-,u_t]. \]

For \(\kappa _t>0\), minimizing the conditional expected local quadratic gives \(s_t^*=(-\mu _t)_+/\kappa _t\). Replacing a gradient estimator with a direct scalar predictor does not add information about \(\mu _t\).

For \(g\sim \mathcal N(0,\sigma ^2I_d)\), \(M\leq d\) noiseless random measurements \(y_i=u_i^\top g\) reveal only the projection of \(g\) onto their span \(S\). When directional curvature is constant, the posterior predictor retains exactly

\[ \frac {\mathbb E[(u^\top P_Sg)^2]}{\mathbb E[(u^\top g)^2]} =\frac {M}{d} \]

of the current-slope oracle’s expected progress. Parallel evaluation reduces acquisition time but does not increase the dimension of \(S\). SPSA and Random Pursuit can instead evaluate and retain the current direction, so their observations contain information that this actuation model forbids ( Spall 1992; Stich et al. 2013).

Projected oracle and operational optimizer

Suppose a warmup identifies \(P_Sg\), the component of the local gradient in a measured subspace \(S\). The projected oracle uses

\[ s_S^*(u)=\frac {(-u^\top P_Sg)_+}{u^\top Hu}. \]

When \(u^\top Hu\) is constant over directions, its expected progress fraction is \(\lVert P_Sg\rVert ^2/\lVert g\rVert ^2\), whose expectation is \(m/d\) for a random \(m\)-dimensional \(S\). A fresh direction need not lie in \(S\), because its projection onto \(S\) still predicts part of its slope.

An operational approximation collects parallel forward differences \(y_i=[L(\theta _0+\delta u_i)-L(\theta _0)]/\delta \), stacks the directions as rows of \(V\), and estimates

\[ \widehat g=V^\top (VV^\top +\lambda I)^{-1}y. \]

It then applies \(\theta _{t+1}=\theta _t+a_t(-u_t^\top \widehat g_t)_+u_t\) and periodically refits after adding loss differences measured across realized aggregate displacements. The update uses one scalar gain \(a_t\) and does not estimate \(H\) online.

MNIST check

On MNIST, the operational method reached \(2.05\) negative log-likelihood, compared with \(1.97\) for gradient descent. Matching the gradient-descent loss trajectory required about \(30\) loss evaluations per gradient-descent step for the directional oracle and about \(200\) for the operational method. Comparable endpoint loss therefore did not imply comparable evaluation efficiency. The known-current-ray results describe the cost of exploiting a direction, whereas the operational method must also estimate which component of each new direction is descending.

Derivations

For \(x^+=x+\alpha (-g^\top U)_+U\) with \(U\) uniform on the sphere,

\[ \mathbb E[L(x^+)-L(x)\mid x] =-\frac {\alpha }{2d}\lVert g\rVert ^2 +\frac {\alpha ^2}{4d(d+2)} \left (\operatorname {tr}(H)\lVert g\rVert ^2+2g^\top Hg\right ). \]

Minimizing over \(\alpha \) and dividing by the exact gradient-line-search decrease \(\lVert g\rVert ^4/(2g^\top Hg)\) gives the \(1/(2d_{\mathrm {eff}})\) progress ratio.

Conditioning an isotropic Gaussian on \(M\) exact projections leaves an independent isotropic component in \(S^\perp \), so \(\widehat g=P_Sg\). The identities \(\mathbb E_u[(u^\top a)^2]=\lVert a\rVert ^2/d\) and \(\mathbb E\lVert P_Sg\rVert ^2=(M/d)\mathbb E\lVert g\rVert ^2\) give both \(M/d\) fractions.