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

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