Indexed text attachment
cotangent-semantics.tex
Source for Cotangent Semantics for Distributed Optimization
View paper · Download original file
Lines 181–280 of 542. Source text is displayed literally.
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}\\261 (q_\tau)_a&=\frac{\exp(\ell_a/\tau)}{\sum_b\exp(\ell_b/\tau)},262 \qquad \tau>0.\nonumber263\end{align}264This tradeoff assigns more weight to high-loss positions and rewards entropy. If one fixes the mean loss at \(\sum_a(q_\tau)_a\ell_a\), then \(q_\tau\) is the unique maximum-entropy distribution for that constraint. Indeed the expression in \eqref{eq:kl} equals265\[266 \tau\log\Big(B^{-1}\textstyle\sum_a e^{\ell_a/\tau}\Big)267 -\tau\KL(q\|q_\tau).268\]269On the constraint set, maximizing it is the same as maximizing entropy. Its maximum value is a smooth batch risk, whose derivative is \(\sum_a(q_\tau)_a\nabla\ell_a\). At fixed losses the derivative of \(H(q_\tau)\) in \(\tau\) is \(\operatorname{Var}_{q_\tau}(\ell)/\tau^3\). Uniform weighting is the \(\tau\to\infty\) control. Minimizing the smoothed batch risk is a different stochastic objective from minimizing the ordinary batch mean. In particular the nonlinear batch weights do not in general give an unbiased gradient for the corresponding full-training-set entropic risk.270 271With \(p_a=\softmax(f_\theta(x_{i_a}))\) and \(e_y\) the one-hot vector, define272\begin{align*}273 g_j &= \lambda v_j+274 \sum_a (q_\tau)_a a_j(x_{i_a})(p_a-e_{y_{i_a}}),\\275 D_j &= .05+\lambda+\sum_a(q_\tau)_a a_j(x_{i_a})^2 .276\end{align*}277Minimizing the block surrogate \(g_j^\top \delta+D_j\|\delta\|^2/2\) would improve it by \(\|g_j\|^2/(2D_j)\). The implementation chooses the largest \(\|g_j\|^2/D_j\) and takes \(-.75\,g_j/D_j\) on that block. The coordinator sends \(q_\tau\) and the weighted logit residuals to both workers. Each returns its best local atom with score, divisor and gradient. The coordinator also considers the bias. A tie keeps the earlier candidate, with bias first, followed by worker 1 and worker 2, and feature index order within a worker. This damped surrogate is a selection rule. No claim of per-round monotonicity for the full training loss is needed. The method is related to stagewise boosting and entropy-regularized boosting \cite{freund,warmuth}, with a different multiclass objective and update.278 279\section{Three-guest experiment}280