ora-0138

10.8 Proximal FTRL and tangent repair

The FTRL action mechanism admits a proximal presentation. For a positive-definite metric \(M\), define

\[ \operatorname {prox}^{M}_{\eta f}(y) = \operatorname *{arg\, min}_z \left\{ \eta f(z)+\frac12\lVert z-y\rVert _M^2 \right\} , \qquad \lVert w\rVert _M^2=w^\mathsf TMw. \]

Writing \(L_t=\sum _{s\leq t}\ell _s\), the regularized decision

\[ x_{t+1} = \operatorname *{arg\, min}_x \left\{ L_t(x)+\frac{\lambda }{2}\lVert x-m\rVert _M^2 \right\} \]

is exactly

\[ x_{t+1}=\operatorname {prox}^{M}_{\eta L_t}(m), \qquad \eta =\lambda ^{-1}. \]

Under the categorical OCO declaration, the constrained readout is

\[ x_{t+1} = \operatorname {prox}^{M}_{\eta (L_t+\iota _K)}(m), \]

where \(\iota _K\) is the convex indicator of the feasible decision algebra. The smooth theorem below applies when \(K=\mathbb {R}^d\), or locally while the decision remains in the interior of \(K\); active boundaries belong to the graphical-tangent case. This presentation treats the proximal map as a repair readout that reconciles accumulated evidence with an anchor and a declared geometry.

Theorem 10.9 Tangent lift of metric-proximal FTRL

Let \(L_t(\, \cdot \, ;\theta )\) be convex and \(C^2\) in its decision argument, with the relevant derivatives jointly continuous in a parameter \(\theta \). Let \(M(\theta )\succ 0\), \(m(\theta )\), and \(\eta (\theta ){\gt}0\) be \(C^1\), and let

\[ x=\operatorname {prox}^{M}_{\eta L_t}(m). \]

For a parameter direction \(v\), write dots for directional derivatives and define the evidence variation at fixed decision by

\[ \delta (\nabla L_t)(x) =D_\theta \bigl[\nabla _xL_t(x;\theta )\bigr][v]. \]

Then the proximal decision is locally \(C^1\), and its tangent is the unique solution of

\begin{equation} \bigl(M+\eta \nabla ^2L_t(x)\bigr)\dot x = M\dot m -\dot M(x-m) -\dot\eta \, \nabla L_t(x) -\eta \, \delta (\nabla L_t)(x). \end{equation}

10.8

For fixed \(L_t,M,\eta \), the derivative with respect to the anchor is

\[ D_m\operatorname {prox}^{M}_{\eta L_t}(m) = \bigl(M+\eta \nabla ^2L_t(x)\bigr)^{-1}M. \]

It is nonexpansive in the \(M\)-norm. If, at the proximal point, \( \nabla ^2L_t(x)\succeq \mu M \) for some \(\mu {\gt}0\), then

\[ \left\lVert D_m\operatorname {prox}^{M}_{\eta L_t}(m) \right\rVert _M \leq \frac{1}{1+\eta \mu }{\lt}1. \]

Proof ▼

The proximal first-order condition is

\[ M(x-m)+\eta \nabla L_t(x)=0. \]

Its decision Jacobian is \(M+\eta \nabla ^2L_t(x)\succ 0\), so the implicit function theorem gives the local smooth readout. Differentiating the first-order condition and keeping the evidence variation at fixed \(x\) separate gives 10.8.

For anchor variation alone, solve the same equation with only \(\dot m\) nonzero. Conjugating the resulting operator by \(M^{1/2}\) gives

\[ M^{1/2} \bigl(M+\eta \nabla ^2L_t(x)\bigr)^{-1}M^{1/2} = \left( I+\eta M^{-1/2}\nabla ^2L_t(x)M^{-1/2} \right)^{-1}. \]

Convexity places its eigenvalues in \((0,1]\). Under the relative strong-convexity bound, they are at most \((1+\eta \mu )^{-1}\), proving both claims.

Equation 10.8 gives four separately typed LINCS channels: anchor variation \(M\dot m\), geometry variation \(-\dot M(x-m)\), regularization-scale variation \(-\dot\eta \nabla L_t(x)\), and accumulated-evidence variation \(-\eta \delta (\nabla L_t)(x)\). In the quadratic case it reduces exactly to Proposition 10.6, after multiplying the equation by \(\lambda \). The contraction bound is a local stability certificate for the repair readout; it does not by itself control the time variation of \(L_t\).

Boundary 10.10 Nonsmooth proximal tangents

For a proper closed convex function in Euclidean space,

\[ \operatorname {prox}_{\eta f}=(I+\eta \partial f)^{-1}, \]

the resolvent of a maximal monotone relation [ Rockafellar , 1976 ] . An ordinary tangent map need not exist at an active-set transition. If \(x=\operatorname {prox}_{\eta f}(y)\), \(u=(y-x)/\eta \in \partial f(x)\), and the subgradient mapping is proto-differentiable with a single-valued directional solution, then a direction \(h\) is transported to the solution \(w\) of

\[ h\in w+\eta D(\partial f)(x\mid u)(w). \]

Thus the directional tangent of the proximal repair is the resolvent of the graphical derivative of its defect relation. Establishing the needed second-order epi-regularity is an additional declaration, not a tangent category axiom [ Rockafellar , 1989 ] .