Indexed text attachment
cotangent-semantics.tex
Source for Cotangent Semantics for Distributed Optimization
View paper · Download original file
Lines 241–340 of 542. Source text is displayed literally.
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)301 node[tag,pos=.53,below left]{cotangent};302\end{tikzpicture}303\caption{Primal outputs and their reverse seeds on three guests. Requests carry batch indices and the parameter snapshot. In the reverse round, the workers return their parameter-block pullbacks.}304\label{fig:cluster}305\end{figure}306 307Each worker emits \(z_i\in\R^K\) per row. The coordinator uses \(z=(b+z_1)+z_2\). For a linear shard the worker computes \(z_i=W_i^\top x_i\) and its pullback accumulates \(x_i\bar z^\top\). For the MLP it computes \(z_i=V_i^\top\tanh(A_i x+b_i)\), with 16 hidden units per worker. Both MLP workers receive the same preprocessed inputs and own disjoint hidden/output blocks. For \(h_i=\tanh(A_i x+b_i)\), its local formulas are308\begin{align*}309 \bar V_i &= h_i \bar z^\top,\qquad310 t_i = (V_i\bar z)\odot(1-h_i^2),\\311 \bar A_i &= t_i x^\top,\qquad \bar b_i = t_i .312\end{align*}313The coordinator sums its bias cotangents over rows and adds the ridge gradient once, after collecting all parameter blocks. The tape stores hidden activations and the snapshot used for each worker. Cross-guest messages carry a 20-byte header on requests and arrays of indices or binary64 values as appropriate. Bytes reported below are application payload and framing over both links, excluding the TCP/IP and Ethernet headers.314 315\subsection{Datasets and hypotheses}316 317\begin{table}[t]318\centering\small319\caption{Fixed training, validation and test splits. Counts refer to the data loaded by the guests.}320\label{tab:data}321\begin{tabular}{@{}lrrr r@{}}322\toprule323Workload & Train & Val. & Test & Params.\\324\midrule325Iris RBF & 90 & 30 & 30 & 75\\326Digits RBF & 1,074 & 355 & 368 & 810\\327Digits MLP & 1,074 & 355 & 368 & 2,410\\328Fashion linear & 4,000 & 1,000 & 2,000 & 500\\329\bottomrule330\end{tabular}331\end{table}332 333\paragraph{Iris RBF.}334The three-class Iris task uses the corrected UCI rows \cite{iris}. Train/validation/test indices are fixed by a stratified 60/20/20 split. The four input measurements are standardized using training statistics. The head uses eight training landmarks per class, giving 24 Gaussian radial basis features.335 336\paragraph{Digits RBF and MLP.}337The 1,797 rows of the UCI Optical Recognition of Handwritten Digits test file \cite{digits} are split into new, disjoint 60/20/20 partitions by class. Thus these accuracies are for the supplied split of that file. Inputs are 8-by-8 pixel counts divided by 16. The kernel model uses 80 training landmarks, eight per class. The neural model standardizes its 64 inputs with training statistics and learns 32 tanh units in two shards.338 339\paragraph{Fashion linear.}340We take 400 training and 100 validation images per class from the official Fashion-MNIST training set and 200 test images per class from its official test set \cite{fashion}. Nonoverlapping \(4\times4\) average pooling produces 49 features from each \(28\times28\) grayscale image. Training-only standardization follows. The head is ten-class softmax with 49 features and a bias. This is an image classification workload with a deliberately small linear head.