Indexed text attachment
cotangent-semantics.tex
Source for Cotangent Semantics for Distributed Optimization
View paper · Download original file
Lines 201–300 of 542. Source text is displayed literally.
201Let \(f_\theta(x)\in\R^K\) be the logits and \(\ell_i(\theta)=\operatorname{lse}(f_\theta(x_i))-f_\theta(x_i)_{y_i}\), where \(\operatorname{lse}(z)=\log\sum_c e^{z_c}\). For \(n\) training examples, set202\[203 \Obj(\theta)=\frac{1}{n}\sum_{i=1}^n \ell_i(\theta)204 +\frac{\lambda}{2}\|\theta\|^2 .205\]206A batch \(I=(i_1,\ldots,i_B)\) is sampled independently with replacement from the training indices. The pullback of its mean loss uses seed \(1\) and returns207\[208 g_I(\theta)209 =\frac{1}{B}\sum_{a=1}^{B}\nabla\ell_{i_a}(\theta)+\lambda\theta .210\]211Each worker computes its parameter block at the parameter version from the forward pass. For shared parameter blocks, the result includes the transpose of the replication map. The coordinator then applies \(\theta\leftarrow\theta-\eta g_I(\theta)\). The Euclidean update depends on the chosen metric, even though the cotangent pullback is natural under smooth coordinate changes. A change of coordinates must carry the metric along to compare intrinsic gradient directions.212 213\begin{proposition}[Synchronous SGD]\label{prop:sgd}214For an independent uniform minibatch and fixed \(\theta\), \(\E[g_I\mid\theta]=\nabla\Obj(\theta)\). If \(\Obj\) is \(L\)-smooth along the update segments and the trace of the single-example gradient covariance at the visited \(\theta\) is at most \(\sigma^2\), then for \(0<\eta\le 1/L\),215\begin{align*}216 \E[\Obj(\theta-\eta g_I)\mid\theta]217 &\le \Obj(\theta)-\frac{\eta}{2}\|\nabla\Obj(\theta)\|^2\\218 &\qquad+\frac{L\eta^2\sigma^2}{2B}.219\end{align*}220\end{proposition}221 222\begin{proof}223Linearity of expectation gives unbiasedness, and independence gives conditional variance at most \(\sigma^2/B\). Substitute \(v=-\eta g_I\) in224\(\Obj(\theta+v)\le\Obj(\theta)+\langle\nabla\Obj(\theta),v\rangle+L\|v\|^2/2\).225Taking the conditional expectation and using \(L\eta\le 1\) gives the claim.226\end{proof}227 228The bound uses the stipulated smoothness and step size, as in standard stochastic optimization \cite{bottou}. The benchmark chooses the learning rate on validation loss. For a linear softmax head on fixed features, the Hessian is positive semidefinite before regularization. With ridge on all parameters it is at least \(\lambda I\), and its upper bound is finite on a finite feature matrix. A bound \(L\le\lambda+\max_i\|\tilde x_i\|^2\) follows by using the bias-augmented feature vector \(\tilde x_i\) and the inequality \(0\preceq\operatorname{diag}(p)-pp^\top\preceq I\). The tanh network is nonconvex. Its empirical comparison does not require a global smoothness or global convergence claim.229 230The optimizer acts on the state after evaluating a circuit and its cotangent. Write \(S\) for a standard Borel space of parameters and optimizer state, and \(\Omega\) for the space of draws. For a schedule \(\alpha\), let \(U_\alpha(s,\omega)\) apply the deterministic update given the objective value and cotangent, with the batch and any other randomness fixed by \(\omega\). The resulting state evolution is the Markov kernel231\[232 K_\alpha(s,A)=\int_\Omega233 \mathbf{1}_{A}\bigl(U_\alpha(s,\omega)\bigr)\,\mu_s(d\omega),234\]235where \(\mu_s\) is the stipulated sampling kernel. The genetic population and mutation draws, and the boosting dictionary index, define analogous state transitions \cite{fritz}. Hard rank selection, tie breaking, and accuracy evaluation are measurable operations. Cotangents differentiate the smooth objective conditional on its inputs.236 237\begin{proposition}[Schedule invariance of the update law]238For fixed sampling and an update that depends only on the optimizer state, objective and cotangent, two schedules identified in \(\Sched\) yield the same one-step Markov kernel. The joint law of any finite sequence of such updates is also the same when each schedule may be chosen anew at each step.239\end{proposition}240 241\begin{proof}242For each fixed draw, the forward and backward interpretations agree by Theorem~\ref{thm:coherence}. The state updates are consequently equal pointwise, and integrating against the same sampling kernel gives equal transition probabilities. Coupling the iterates by the same draw conditional on the current state makes their states agree inductively. The same reasoning allows the schedule to depend on earlier draws and observed states as long as it preserves the circuit and the conditional sampling kernel.243\end{proof}244 245This result concerns the law of the model state. When a scheduler changes the sample stream, accepts stale snapshots, or changes a reduction in finite precision, equality of the ideal lenses alone gives no corresponding runtime guarantee.246 247\section{Baselines and entropy weighting}248 249\subsection{Real-coded genetic algorithm}250 251The genetic baseline uses a population of eight parameter vectors and ranks them by the regularized batch objective, using the same batch for all candidates in a generation. The two best candidates are copied to the next generation. For each of six offspring, two parents are drawn independently from the best four, and a uniformly drawn scalar gives an affine crossover between the parents. Independent normal mutations are scaled by parameter block. Every candidate evaluation uses the same distributed forward program as SGD. It sends no backward request. At a checkpoint the best individual of the latest evaluated generation is used. This is a specific real-coded genetic algorithm in the sense of selection, recombination and mutation \cite{holland}.252 253\subsection{Entropy-maximizing additive boosting}\label{sec:entropy}254 255A weak atom \(a_j(x)\) is one scalar feature, one frozen hidden unit, or the constant bias atom. A block \(v_j\in\R^K\) controls the additive logits \(a_j(x)v_j\). At each round, the baseline chooses one atom and adds a vector to its coefficient. Repeated selections add to the same coefficient, so the number of active atoms is bounded by the dictionary size. The linear and RBF tasks use the same hypothesis class as SGD. On the MLP, the weak dictionary freezes the hidden units at the matched initialization. We include SGD with the same hidden blocks frozen as a separate control.256 257Let \(u\) denote the uniform distribution on the \(B\) batch positions. Given the current losses \(\ell_a\), choose weights258\begin{align}259 q_\tau&=\arg\max_{q\in\Delta_B}260 \bigg\{\sum_a q_a\ell_a-\tau\KL(q\|u)\bigg\},\label{eq:kl}\\261 (q_\tau)_a&=\frac{\exp(\ell_a/\tau)}{\sum_b\exp(\ell_b/\tau)},262 \qquad \tau>0.\nonumber263\end{align}264This tradeoff assigns more weight to high-loss positions and rewards entropy. If one fixes the mean loss at \(\sum_a(q_\tau)_a\ell_a\), then \(q_\tau\) is the unique maximum-entropy distribution for that constraint. Indeed the expression in \eqref{eq:kl} equals265\[266 \tau\log\Big(B^{-1}\textstyle\sum_a e^{\ell_a/\tau}\Big)267 -\tau\KL(q\|q_\tau).268\]269On the constraint set, maximizing it is the same as maximizing entropy. Its maximum value is a smooth batch risk, whose derivative is \(\sum_a(q_\tau)_a\nabla\ell_a\). At fixed losses the derivative of \(H(q_\tau)\) in \(\tau\) is \(\operatorname{Var}_{q_\tau}(\ell)/\tau^3\). Uniform weighting is the \(\tau\to\infty\) control. Minimizing the smoothed batch risk is a different stochastic objective from minimizing the ordinary batch mean. In particular the nonlinear batch weights do not in general give an unbiased gradient for the corresponding full-training-set entropic risk.270 271With \(p_a=\softmax(f_\theta(x_{i_a}))\) and \(e_y\) the one-hot vector, define272\begin{align*}273 g_j &= \lambda v_j+274 \sum_a (q_\tau)_a a_j(x_{i_a})(p_a-e_{y_{i_a}}),\\275 D_j &= .05+\lambda+\sum_a(q_\tau)_a a_j(x_{i_a})^2 .276\end{align*}277Minimizing the block surrogate \(g_j^\top \delta+D_j\|\delta\|^2/2\) would improve it by \(\|g_j\|^2/(2D_j)\). The implementation chooses the largest \(\|g_j\|^2/D_j\) and takes \(-.75\,g_j/D_j\) on that block. The coordinator sends \(q_\tau\) and the weighted logit residuals to both workers. Each returns its best local atom with score, divisor and gradient. The coordinator also considers the bias. A tie keeps the earlier candidate, with bias first, followed by worker 1 and worker 2, and feature index order within a worker. This damped surrogate is a selection rule. No claim of per-round monotonicity for the full training loss is needed. The method is related to stagewise boosting and entropy-regularized boosting \cite{freund,warmuth}, with a different multiclass objective and update.278 279\section{Three-guest experiment}280 281\subsection{Placement and message accounting}282 283Every run boots three independent Alpine Linux 3.23.8 initramfs guests, one virtual CPU and 192 MiB each, on QEMU 10.0.13 with TCG \cite{qemu}. The coordinator \(C\) owns labels, the global bias, parameter snapshots, the loss and optimizer state. Workers \(W_1,W_2\) own feature shards and their local forward and reverse computations. The host builds the guests and relays Ethernet frames on an isolated virtual LAN. No optimization or scoring runs on the host. Guests exchange TCP messages over emulated e1000 interfaces. Each worker records its own application-byte and operation counts, which the verifier reconciles against the coordinator's records.284 285\begin{figure}[t]286\centering287\begin{tikzpicture}[x=1cm,y=1cm,288 vm/.style={draw=inkblue,rounded corners=2pt,fill=inkblue!5,minimum width=2.05cm,289 minimum height=.60cm,align=center,font=\footnotesize},290 tag/.style={font=\scriptsize,text=graytext,fill=white,inner sep=1pt}]291 \node[vm] (one) at (-2.13,0) {\(W_1\)\\feature shard 1};292 \node[vm] (two) at (2.13,0) {\(W_2\)\\feature shard 2};293 \node[vm,minimum width=2.3cm] (core) at (0,1.54) {\(C\)\\loss and updates};294 \draw[->,thick,inkblue] (one.north east) -- (core.south west)295 node[tag,pos=.51,above left]{partial logits};296 \draw[->,thick,inkblue] (two.north west) -- (core.south east)297 node[tag,pos=.51,above right]{partial logits};298 \draw[->,thick,boostteal] (core.south) -- (one.east)299 node[tag,pos=.53,below right]{cotangent};300 \draw[->,thick,boostteal] (core.south) -- (two.west)