Indexed text attachment
cotangent-semantics.tex
Source for Cotangent Semantics for Distributed Optimization
View paper · Download original file
Lines 101–200 of 542. Source text is displayed literally.
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.181\end{proposition}182 183\begin{proof}184At \(j'\in J'\), \(a\) induces a bijection \((u')^{-1}(j')\to u^{-1}(b(j'))\). Reindexing the summands by this bijection gives the comparison. Both folds add exactly those summands, with the empty fold zero. Composing pullback squares composes their fiber bijections. The argument works for weighted linear maps when weights are transported with their occurrences.185\end{proof}186 187For context variation, take the site of opens of a smooth manifold \(B\). Let each interface over an open \(U\) be a smooth vector bundle, with products taken over \(U\). A primitive is a smooth bundle map over \(U\) that is allowed to be nonlinear on the fibers. Let \(T_v f\) denote its vertical differential and \(T_v f^*\) the pointwise dual of that differential. Both commute with restriction to smaller opens. In overlapping coordinates the usual chain rule transports \(T_v f\) and the dual transition maps transport the cotangents. This construction is interpreted in sheaves over \(B\), or in their embedding as \(0\)-truncated objects of \(\operatorname{Shv}(B;\Spc)\). It gives a topos-theoretic account of compatible local programs, with no derivative assigned to an arbitrary internal morphism.188 189\begin{proposition}[Descent in the parameter context]\label{prop:descent}190Fix the finite circuit and its port occurrences over \(B\). Compatible smooth local primitive maps on an open cover, with their vector bundle transition functions, define a global forward map and a global vertical cotangent pullback. The global pullback restricts to the composite local dual protocol.191\end{proposition}192 193\begin{proof}194Vector bundle sections and smooth maps over \(B\) glue uniquely when the local maps agree under the given transitions. In particular the local forward interpretations glue. The vertical chain rule makes the local dual maps agree on each overlap. Finite sums and composition of smooth maps commute with restriction, so the local execution of the dual also glues. On each member of the cover it is the vertical cotangent pullback by Theorem~\ref{thm:pullback}, applied fiberwise. Uniqueness of the glued map identifies the two global maps.195\end{proof}196 197The finite-fiber law concerns how indexed contributions are regrouped. For example, partitioning a batch into unequal blocks requires multiplying each local mean by its block size before taking the global mean. An unweighted mean of local means changes the objective whenever block sizes differ and the block means are unequal. The experiments instead shard the model and features, and their output reduction is a sum of partial logits.198 199\section{Optimization from the dual}200