Indexed text attachment
cotangent-semantics.tex
Source for Cotangent Semantics for Distributed Optimization
View paper · Download original file
Lines 21–120 of 542. Source text is displayed literally.
21\color{black}22\setlength{\parindent}{1em}23\setlength{\parskip}{0pt}24\setlength{\headheight}{14pt}25\setlength{\textfloatsep}{13pt plus 3pt minus 3pt}26\setlength{\floatsep}{12pt plus 2pt minus 2pt}27\setlength{\intextsep}{10pt plus 2pt minus 2pt}28\setlength{\abovecaptionskip}{5pt}29\setcounter{topnumber}{3}30\renewcommand{\topfraction}{.88}31\renewcommand{\textfraction}{.08}32\renewcommand{\arraystretch}{1.15}33\pagestyle{fancy}34\fancyhf{}35\fancyhead[L]{\small\textsc{Cotangent semantics}}36\fancyhead[R]{\small\textsc{Distributed optimization}}37\fancyfoot[C]{\small\thepage}38\renewcommand{\headrulewidth}{.3pt}39\fancypagestyle{plain}{\fancyhf{}\fancyfoot[C]{\small\thepage}\renewcommand{\headrulewidth}{0pt}}40\raggedbottom41\lefthyphenmin=342\righthyphenmin=343\theoremstyle{plain}44\newtheorem{theorem}{Theorem}[section]45\newtheorem{lemma}[theorem]{Lemma}46\newtheorem{proposition}[theorem]{Proposition}47\theoremstyle{definition}48\newtheorem{definition}[theorem]{Definition}49\input{glyphtounicode}50\pdfgentounicode=151\newcommand{\R}{\mathbb R}52\newcommand{\N}{\mathbb N}53\newcommand{\id}{\mathrm{id}}54\newcommand{\Spc}{\mathcal S}55\newcommand{\curvekey}[3]{\tikz[baseline=-.45ex]{\draw[#1,#2,very thick] (0,0)--(.44,0);}\,\footnotesize #3}56\newcommand{\Graph}{\mathsf{Circ}}57\newcommand{\Sched}{\mathsf{Sched}}58\newcommand{\Lens}{\mathsf{CotLens}}59\newcommand{\Obj}{\mathcal L}60\newcommand{\KL}{\operatorname{KL}}61\newcommand{\E}{\mathbb E}62\newcommand{\softmax}{\operatorname{softmax}}63\newcommand{\MaxDerivativeError}{3.83\times 10^{-11}}64\newcommand{\FrameCount}{2,934,129}65\newcommand{\ForwardCount}{87,460}66\newcommand{\ReverseCount}{28,808}67\newcommand{\CorrelationCount}{30,720}68\newcommand{\TrafficTotal}{1.922}69\newcommand{\FrozenAccuracy}{88.91}70\newcommand{\FrozenLoss}{0.380}71\begin{document}72\twocolumn[{\begin{@twocolumnfalse}73\noindent{\color{inkblue}\small\textsc{Research manuscript}\par}74\vspace{.55em}75{\LARGE\bfseries Cotangent Semantics for Distributed Optimization\par}76\vspace{.40em}77{\large Schedule coherence and reproducible benchmarks on three QEMU guests\par}78\vspace{.55em}79{\normalsize Anonymous submission\par}80\vspace{.95em}81\noindent{\color{inkblue}\rule{\textwidth}{.55pt}}\par82\vspace{.40em}83\noindent\textbf{Abstract.}\quad84A distributed smooth program can expose its reverse dependency graph as a protocol for cotangent messages. We construct a semantics in which legal schedules of a typed acyclic circuit are related by coherent 2-cells. A symmetric monoidal reverse interpretation sends every legal schedule to the same cotangent lens, with transposed derivatives and additive cotangent fan-in. A finite-fiber base-change identity describes aggregation under reindexing, and the interpretation descends for compatible smooth families over a context site. We derive synchronous minibatch SGD from the distributed pullback and implement the forward and reverse traffic on three QEMU guests. At 18,432 training example evaluations per configuration, SGD gave the lowest mean test log loss on Iris with radial basis features, handwritten digits with radial basis features and with a tanh network, and pooled Fashion-MNIST. The comparison includes a real-coded genetic algorithm, an entropy-maximizing additive boosting rule, and uniform and frozen-feature controls. Two independently booted cluster runs reproduced all logged losses, accuracy counts, derivative checks, and application-byte counts exactly.85\par\vspace{.55em}86\noindent\textbf{Keywords.}\quad Reverse-mode differentiation, categorical semantics, distributed optimization, stochastic gradient descent, entropy regularization, reproducibility87\par\vspace{.95em}88\end{@twocolumnfalse}}]89\thispagestyle{plain}90 91\section{Introduction}92 93A distributed implementation exposes more structure than its extensional input--output map. Independent operations can finish in different orders. A feature shard can be moved to a different machine. A parameter can contribute to several outputs, so several messages must be combined before a reverse operation can execute. The semantics has to say which changes preserve the computed differential and which affect the cost of computing it. We address this question for finite smooth programs whose primal trace and vector--Jacobian products are available.94 95Reverse derivative categories provide an axiomatic setting for reverse differentiation \cite{cockett}. Parametric lenses describe how learning rules act on models \cite{cruttwell}. Adjoinable MPI studies the reversal of communication in numerical programs \cite{utke}. Our construction relates these ideas at the level of typed schedules. It gives a two-dimensional presentation of reorderings, a cotangent correctness theorem with explicit wire occurrences, and a base-change law for finite aggregation. The presentation also specifies what is preserved when a forward and reverse exchange is placed across a virtual network.96 97The experiments ask two separate questions. First, do actual cross-guest cotangents agree with independent finite differences and survive a change in scheduling? Second, what happens when full SGD, a forward-only genetic algorithm, and a boosting rule using entropy-maximizing example weights are given the same number of forward evaluations? The boosting rule adds to a finite dictionary of weak learners. Its weighting policy has a precise variational characterization, and a uniform-weight ablation isolates that policy.98 99\section{Typed circuits and their dual}100 101\subsection{Smooth primitives and occurrences}102 103An interface is an ordered list of finite-dimensional real vector spaces, interpreted as their product. Execution uses fixed coordinates on each factor. The empty list is interpreted by the zero-dimensional space. An open circuit has a finite acyclic event graph with ordered input and output ports. Each event \(v\) carries a smooth map \(f_v\) from the product of its input types to the product of its output types. Each input port has exactly one source wire. An output wire may be unused or may feed multiple ports, including repeated inputs to one event. Numbering consumers by \emph{port occurrence} retains that multiplicity. Boundary output ports count as consumers. We write \(F_C\colon X\to Y\) for the resulting smooth map of a circuit \(C\).104 105Parameter and data inputs may be written \(X=P\times A\). Shared parameters are wires with multiple consumers. Batching is a finite product of per-example computations with copies of a shared parameter input and a final loss aggregation. The smoothness requirement applies to parameters for each fixed data record and each fixed branch of the training protocol. We use \(C^1\) for the reverse semantics and additional smoothness assumptions for optimization estimates. Discrete labels and minibatch indices are held fixed during differentiation.106 107For a smooth map \(f\colon X\to Y\), its reverse at \(x\) is the linear map108\[109 f_x^*\colon Y^*\longrightarrow X^*,110 \qquad f_x^*\bar y=\bar y\circ Df_x .111\]112A reverse lens from \(X\) to \(Y\) consists of a smooth forward map \(f\) and a smoothly varying, fiberwise linear backward map \(r_x\colon Y^*\to X^*\). The composite of \((f,r)\) followed by \((g,s)\) is113\[114 (g,s)\circ(f,r)=(g\circ f,\ x\mapsto r_x\,s_{f(x)}) .115\]116We use smooth maps in the lens category and the corresponding \(C^1\), continuous-backward variant when only first differentiability is assumed. The product of lenses uses the product forward map and the direct sum of backward maps. This defines \(\Lens\), with reverse differentiation \(f\mapsto(f,f^*)\) respecting composition and products by the chain rule. Standard coordinates identify a cotangent with its Euclidean gradient when an optimizer needs a vector.117 118\begin{definition}[Dual graph]119The dual of an executed circuit has a reverse edge for each primal port occurrence. Its value is the cotangent sent from that consumer to the source. The reverse event uses the primal inputs, or equivalent saved data, to apply \(f_v^*\). At every wire, the event waits for its required cotangents and sums them. A boundary seed contributes once per output occurrence. A wire with no contribution receives zero.120\end{definition}