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 141–240 of 542. Source text is displayed literally.

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 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