Independent scholarship · Open accessThe monthly digest

Indexed text attachment

cotangent-semantics.tex

Source for Cotangent Semantics for Distributed Optimization

View paper · Download original file

Lines 81–180 of 542. Source text is displayed literally.

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}121 122For example, if a scalar input is used in both arguments of multiplication, the derivative of \(m\circ\Delta\) at \(x\), with \(m(a,b)=ab\), is \(2x\). In the dual graph, each argument sends \(x\bar y\) to the same source. A graph that deduplicates those messages returns \(x\bar y\). If \(x\) is duplicated onto \(n\) destinations, \(\Delta(x)=(x,\ldots,x)\) has pullback \((\bar x_i)_i\mapsto\sum_i\bar x_i\). Conversely the pullback of an addition node sends its output cotangent to every input. Identity transport and wire permutations pull back by the transpose of their routing maps. The operation does not require the forward primitive to be invertible.123 124\subsection{Correctness and communication}125 126\begin{theorem}[Distributed pullback]\label{thm:pullback}127Fix a circuit \(C\), input \(x\), and output seed \(\bar y\). Any legal forward evaluation followed by a reverse evaluation that delivers each contribution exactly once returns \(DF_C(x)^*\bar y\). The result is invariant under event placement provided communication implements the specified wire maps.128\end{theorem}129 130\begin{proof}131For any input variation \(\dot x\), propagate a tangent \(\dot w\) along every wire by applying \(Df_v\) to the tuple of event-input tangents. Pair the resulting boundary output tangents with \(\bar y\). During reverse evaluation, replace each pairing of event-output cotangents with event-output tangents by the corresponding pairing of \(f_v^*\) with event-input tangents. This follows from the definition of the transpose. At each wire collect all pairings with its common tangent by additivity. Reverse acyclicity eventually leaves only the boundary input pairings. The sum of those pairings equals \(\langle\bar y,DF_C(x)\dot x\rangle\) for every \(\dot x\). Nondegeneracy of the pairing gives the claim. A transmission of the same typed value changes none of the pairings. For a nonidentity wire map its transpose enters the same argument.132\end{proof}133 134This proof models a complete logical trace. Ordered TCP gives the byte stream used by our implementation. Its requests also name a sequence, task, row count, and the forward tape identifier, which is consumed once by a reverse or statistics operation. A lost or stale tape invalidates that iteration. In real arithmetic the sum is independent of its order. The implementation fixes operand order at the coordinator so that changing the worker dispatch order does not change the floating-point sum. An asynchronous system with duplicate retries would need occurrence-level deduplication or a protocol establishing exactly-once contributions.135 136\section{Schedules and higher coherence}137 138\subsection{A locally groupoidal 2-category}139 140Let \(\Graph\) be the category with typed interfaces as objects and open circuits up to boundary-preserving isomorphism as arrows. An isomorphism preserves the primitive labels, port orders, and wiring. Composition glues matching boundary ports, and its isomorphism class is independent of the order of gluing. The tensor is disjoint union of events and concatenation of interfaces, with the symmetry induced by reordering boundary wires. A placement may be carried as a vertex label when the schedule is to be compared at fixed deployment. Erasing that label is a functor.141 142A schedule is a linear extension of the precedence order on events. Let \(\Sched\) have the same objects and scheduled circuits, up to schedule-preserving isomorphism, as 1-cells. For any two 1-cells with the same underlying circuit in \(\Graph\), give the hom-category exactly one invertible 2-cell between them. It represents the identification of legal reschedulings. For distinct underlying circuits there are no such 2-cells. Concatenation after gluing composes 1-cells. Vertical composition of 2-cells is forced by uniqueness. Horizontal composition is well defined since equality in \(\Graph\) is a congruence for gluing. Interchange, associativity and the unit axioms follow from this description.143 144\begin{lemma}[Adjacent exchanges]\label{lem:swaps}145Every rescheduling 2-cell is generated by exchanges of adjacent incomparable events.146\end{lemma}147 148\begin{proof}149Fix a target linear extension. In the current extension move its first event to the first position by adjacent swaps. Each event passed is incomparable with it. If a passed event preceded it in the order, the target could not start with the chosen event. If it followed it, the current extension could not place it earlier. Remove the common first event and repeat on the remaining finite order.150\end{proof}151 152Equivalently, take the groupoid of paths of such exchanges and identify parallel paths. This quotient records schedule equivalence and omits the history of swaps. Tensoring 1-cells concatenates their independent schedules. Its compositor identifies two legal schedules on the same glued disjoint circuit. The unit and symmetry comparisons use the empty schedule and boundary permutation. The coherence diagrams commute since their comparisons have the same boundary permutation and there is at most one 2-cell between their scheduled circuits.153 154\begin{theorem}[Coherent reverse interpretation]\label{thm:coherence}155Reverse differentiation induces a symmetric monoidal interpretation of \(\Sched\) in the locally discrete 2-category of cotangent lenses. It factors through \(\Graph\), and forgetting schedules induces an equivalence on the homotopy-coherent nerves of the corresponding categories enriched in spaces.156\end{theorem}157 158\begin{proof}159For each scheduled circuit \(C\), assign the lens \((F_C,DF_C^*)\). The extensional forward evaluation depends only on wiring. Theorem~\ref{thm:pullback} gives equality of reverse evaluations for any two schedules of that wiring. Gluing is composition of the forward maps, and its reverse is the composite of the transposes in reverse order. Disjoint union gives the product lens, so the tensor and its comparison 2-cells are preserved. The hom-groupoid of \(\Sched\) maps to the discrete hom-set of \(\Graph\). Each fiber is a nonempty groupoid with exactly one arrow between any two objects, hence has contractible nerve. This gives a weak equivalence on every simplicial mapping space and identity on objects. The homotopy-coherent nerve gives the stated equivalence \cite[Sec.~1.1.5]{lurie}.160\end{proof}161 162This is a particular higher semantics with contractible spaces of schedule choices. We quotient reorderings of a fixed dependency graph. Graph rewrites, timings, partial failure histories and resource allocations can give finer observations. Theorem~\ref{thm:coherence} only identifies the value and cotangent semantics. Our executable audit compares two worker dispatch orders on identical inputs and stores cost measurements independently.163 164\subsection{Indexed aggregation and descent}165 166Let \(R\) be a commutative ring and let \(u:I\to J\) be a finite map of indexing sets. On families of \(R\)-modules, reindexing \(u^*\) has a left adjoint \(\Sigma_u\) given by fiberwise direct sums and a right adjoint \(\Pi_u\) given by fiberwise products. The canonical map from sum to product is an isomorphism for finite fibers, including an empty fiber. For a repeated module \(M_j\), the induced replication map has diagonal components \(M_j\to\prod_{u(i)=j}M_j\). When these modules are finite free, the dual map has summation components \(\bigoplus_{u(i)=j}M_j^*\to M_j^*\).167 168\begin{proposition}[Base change for reverse aggregation]\label{prop:bc}169Given a pullback square of finite sets170\[171\begin{tikzpicture}[baseline=(J.base),scale=.76]172  \node (I1) at (0,1) {\(I'\)}; \node (I) at (2,1) {\(I\)};173  \node (J1) at (0,0) {\(J'\)}; \node (J) at (2,0) {\(J\)};174  \draw[->] (I1)--node[above]{\(\scriptstyle a\)}(I);175  \draw[->] (I1)--node[left]{\(\scriptstyle u'\)}(J1);176  \draw[->] (I)--node[right]{\(\scriptstyle u\)}(J);177  \draw[->] (J1)--node[below]{\(\scriptstyle b\)}(J);178\end{tikzpicture}179\]180the comparison \(b^*\Sigma_u\cong\Sigma_{u'}a^*\) identifies the two reverse aggregations under fiber reindexing. It is compatible with pasting pullback squares.