ora-0145

11.6 Bandit convex optimization changes the repair target

Let \(C\subset \mathbb {R}^d\) be convex, let \(C_\delta \) contain the points whose closed \(\delta \)-ball lies in \(C\), and define ball smoothing by

\[ \widetilde f_\delta (z) =\frac{1}{\operatorname {vol}(B^d)} \int _{B^d}f(z+\delta v)\, dv. \]

Here a one-point scalar observation cannot reconstruct \(f\). The useful repair target is instead a tangent covector of the smoothed loss.

Proposition 11.9 One-point reconstruction of a smoothed gradient

Let \(U\) be uniform on the unit sphere \(S^{d-1}\), and observe \(f(z+\delta U)\) for \(z\in C_\delta \). Then

\[ G_\delta (z,U)=\frac d\delta f(z+\delta U)U \qquad \text{satisfies}\qquad \mathbb E[G_\delta (z,U)]=\nabla \widetilde f_\delta (z) \]

whenever the displayed derivative exists.

Proof ▼

Differentiate the ball average and apply the divergence theorem. The boundary integral over \(S^{d-1}\) introduces the outward normal \(U\); the ratio of sphere area to ball volume is \(d\), yielding the displayed identity.

Thus bandit convex optimization factors through a different reconstruction diagram: scalar evidence is sent to a distribution of tangent covectors and then averaged. Approximation bias enters because \(\widetilde f_\delta \neq f\); sampling variance enters through the norm of \(G_\delta \). UODL keeps these two defects typed separately. The broader theorem problem is to characterize distribution monads and tangent structures for which barycentric reconstruction commutes with the relevant tangent lift.