A Higher Categorical Theory of Polynomial-Branch Recursive Boosting with Maximum-Entropy Error Selection
Author: Anonymous. Version: 1.0, November 10, 2026.
The attached double-column PDF is the complete manuscript. The source and reproducibility archive supplies proofs, executable algorithms, exact rational output, individual experiments, generated tables and figures, and checksums. This journal body presents the principal definitions, results, and experimental contract.
1. Scope
The problem is to fit a finite dataset using recursive gated predictors while keeping branch growth polynomial. We distinguish candidate-dictionary size, active model size, and optimization work. The main fitting problem is convex-hull optimization under a weighted variation constraint. It is not arbitrary neural architecture search or globally optimal fixed-support selection.
Assume a sample $D=((x_i,y_i))_{i=1}^n$, a finite family of $b$ gates $g_j:X\to[0,1]$, and $H$ leaves $h_r:X\to[-1,1]$. The interaction degree $k$ is fixed during a run. Analytic claims use bounded smooth convex losses. Effective claims use finite rational or computable sample evaluations. A higher semantic object is not assumed computable merely because it exists.
2. Recursive polynomial dictionary
For $\alpha\in\mathbb N^b$, $|\alpha|\le k$, define
$$u_{\alpha,r}(x)=h_r(x)\prod_jg_j(x)^{\alpha_j},\qquad a_{\alpha,r}=u_{\alpha,r}/c_{\alpha,r},\quad c_{\alpha,r}\ge1.$$
Sorting a gate word produces a canonical multiset. Repeated gates are retained: for a soft gate, $g^2$ need not equal $g$. The number of unsigned labelled candidates is exactly
$$M=H\sum_{d=0}^k\binom{b+d-1}{d}=H\binom{b+k}{k}.$$
Proof. Count degree-$d$ multisets by stars and bars, and sum by the hockey-stick identity. Equivalently append a slack exponent so that the total degree is exactly $k$ in $b+1$ coordinates. This is polynomial in $b$ at fixed $k$. Boolean idempotence permits the smaller subset dictionary, but the implementation consistently keeps multiset labels.
Let $A$ be the normalized atom matrix. The feasible prediction set is
$$\mathcal K_{R,k}=\{A\theta:\|\theta\|_1\le R\}=R\operatorname{conv}(\{0\}\cup\{\pm A_j\}).$$
In raw coefficients the constraint is $\sum c_{\alpha,r}|\beta_{\alpha,r}|\le R$. Every prediction has magnitude at most $R$. Compactness gives existence of a minimizer for every continuous objective. For multiclass fitting use atoms $A_je_c$ and the total entrywise coefficient norm.
Finite expressions built from leaves, gate multiplication, addition and scalar multiplication flatten into these atoms when every path has gate degree at most $k$. Structural induction proves equality of evaluations; combining equal labels decreases weighted variation by the triangle inequality. Multiplication of two arbitrary boosted ensembles is not silently treated as a primitive: it can multiply support and must be recompiled with a new degree and cost check.
3. Higher categorical presentation
Work in an infinity-topos $\mathcal X$, or a slice for parameter contexts, with a data object $\mathbf X$, a 0-truncated ordered scalar ring $\mathbf R$, a gate object $\mathbf G$, and a leaf object $\mathbf H$. Gate and leaf interpretations are maps to bounded scalar functions. Labels can have higher automorphisms.
The finitary polynomial signature
$$P(Z)=1\amalg(\mathbf G\times Z)\amalg(\mathbf R\times Z)\amalg Z^2$$
specifies zero, gating, scaling and addition. Its free-algebra monad is constructed by
$$T_0(V)=V,\quad T_{m+1}(V)=V\amalg P(T_m(V)),\quad T_P(V)=\operatorname*{colim}_mT_m(V).$$
Free syntax theorem. This construction is the free $P$-algebra monad. Ground recursive syntax is $T_P(\mathbf H)$, and the pointwise algebra structure of $\mathbf R^{\mathbf X}$ supplies evaluation.
Proof. Finite products commute with filtered colimits in an infinity-topos, and the remaining operations preserve colimits. Shifting the chain gives the free-algebra fixed point. An algebra map is defined recursively at each stage, with a contractible space of compatible choices. Substitution gives monad multiplication and its coherent identities by this universal property.
Scalar evaluation is 0-truncated: if $\mathbf R$ is 0-truncated, so is $\mathbf R^{\mathbf X}$, because its mapping spaces are $\operatorname{Map}(V\times\mathbf X,\mathbf R)$. Hence evaluation factors through $\tau_{\le0}T_P(\mathbf H)$. Higher presentation symmetries remain meaningful in the fibers of evaluation, but are invisible to scalar empirical loss. For example a leaf-label space $BC_2$ interpreted as the constant predictor one retains its automorphism in syntax and loses it under scalar evaluation.
If a presentation has at most $B$ leaves and depth $k$, and each replacement has at most $C$ leaves and depth $l$, substitution gives bounds $(BC,k+l)$. Count replacement leaves and concatenate gate paths. This identifies why unrestricted repeated substitution may expand exponentially. Adding one canonical branch per optimization step has a different growth law.
For costs $c_\alpha=1+|\alpha|$, use judgments $\Gamma\vdash t:\operatorname{Pred}(B,k,U,V)$, where $U$ bounds unweighted coefficient mass and $V$ bounds degree-weighted mass. A leaf has $(1,0,1,1)$; zero has $(0,0,0,0)$. Addition sums the masses and branch counts and takes the maximum depth; scaling multiplies masses by $|\lambda|$; gating sends $(B,k,U,V)$ to $(B,k+1,U,V+U)$. Induction proves soundness of the canonical compiler and shows $V\le R$ certifies feasibility.
Transport theorem. For a geometric inverse image $f^*$,
$$f^*T_P(V)\simeq T_{f^*P}(f^*V).$$
It preserves the finite operations and the chain colimit, and thus unit, substitution and resource witnesses. Finite empirical evaluation commutes because $f^*(\mathbf R^n)\simeq(f^*\mathbf R)^n$. For a general data object we use the canonical comparison $f^*(\mathbf R^{\mathbf X})\to(f^*\mathbf R)^{f^*\mathbf X}$, not an unjustified equivalence. Presentation objects and homotopy fibers satisfy descent with their coherence data.
Tie-breaking is not claimed natural under every atom relabelling. The minimizing correspondence, or a symmetric distribution on tied atoms, has a better invariance property than an arbitrary single-atom selector.
4. Maximum-entropy error selection
Let $e_i=\ell(y_i,z_i)\ge0$, $u_i=1/n$, and $\tau>0$. Select errors by
$$\max_{p\in\Delta_n}\left\{\sum_ip_ie_i-\tau\operatorname{KL}(p\Vert u)\right\}.$$
This maximizes selected mean error plus $\tau$ times Shannon entropy, up to a constant. Pure entropy maximization alone would give uniform weights and would ignore which examples have larger errors.
Gibbs theorem. The unique solution and its optimized value are
$$p_i^*=\frac{e^{e_i/\tau}}{\sum_je^{e_j/\tau}},\qquad F_\tau(z)=\tau\log\left(\frac1n\sum_ie^{e_i/\tau}\right).$$
For every distribution $p$ the difference between this optimum and its objective is $\tau\operatorname{KL}(p\Vert p^*)$. Expansion of $\log p_i^*$ proves the identity and uniqueness. At its selected mean error, $p^*$ also solves literal constrained maximum-entropy selection.
If losses lie in $[0,B]$, then $\bar e\le F_\tau\le\max e_i$, $F_\tau\ge\max e_i-\tau\log n$, $n\max p_i^*\le\min(n,e^{B/\tau})$, and $H(p^*)\ge\log n-B/\tau$. Thus the entropy effective count is at least $ne^{-B/\tau}$. Small temperature prioritizes large errors and may also prioritize outliers; this positive tilt is not a claim of automatic outlier rejection.
Smoothness theorem. If the individual losses are convex, have gradient norm at most $G_0$ and Hessian at most $L_0I$, then $F_\tau$ is convex. In the empirical inner product $\langle u,v\rangle_n=n^{-1}\sum_i u_i\cdot v_i$,
$$q_i=\nabla_nF_\tau(z)_i=np_i^*\nabla\ell_i(z_i),\qquad L_\tau\le\kappa(L_0+G_0^2/\tau),$$
where $\kappa$ bounds $n\max p_i^*$ on the feasible domain.
Proof. The Gibbs variational formula is a supremum of convex functions. The second derivative in direction $v$ is
$$\sum_ip_i^*D^2\ell_i[v_i,v_i]+\tau^{-1}\operatorname{Var}_{p^*}(\nabla\ell_i\cdot v_i),$$
which is bounded above by $(L_0+G_0^2/\tau)\sum_ip_i^*\|v_i\|^2\le\kappa(L_0+G_0^2/\tau)\|v\|_n^2$. The concentration factor cannot in general be omitted.
Square loss has $L_0=1$, $G_0=R+Y$ for $|y|\le Y$. Binary logistic loss has $L_0=1/4$, $G_0=1$. Multiclass cross entropy has $L_0=1/2$, $G_0=\sqrt2$ in the Euclidean row norm.
5. Effective recursive entropic boosting
At each round compute Gibbs weights and gradient, scan the finite signed dictionary for a minimizing linear score, then take a feasible convex update. An exact oracle chooses $j$ maximizing $|\langle q,A_j\rangle_n|$ and the opposite sign. In multiclass fitting maximize over atom and class coordinate.
Suppose the approximate gradient obeys $\|\widetilde q-\nabla F(z)\|_n\le\eta$ and the returned $s\in\mathcal K$ is within $\delta$ of the minimum linear score for $\widetilde q$. Then
$$F(z)-F^*\le\langle\widetilde q,z-s\rangle_n+\delta+2R\eta.$$
Proof. Convexity bounds suboptimality by the true gradient against an optimal comparator. The approximate oracle contributes $\delta$. Replacing the gradient contributes at most $\eta\|z-z^*\|_n\le2R\eta$.
Use $\gamma_t=2/(t+2)$ and $z_{t+1}=(1-\gamma_t)z_t+\gamma_ts_t$, or a step whose objective is no larger. Let $e$ bound all $\delta_t+2R\eta_t$.
Fitting theorem. For convex $L$-smooth $F$ and every $T\ge1$,
$$F(z_T)-F^*\le\frac{8LR^2}{T+2}+e.$$
Proof. The feasible diameter is at most $2R$, hence curvature $C_F\le4LR^2$. Smoothness and the approximate oracle give $h_{t+1}\le(1-\gamma_t)h_t+\gamma_te+C_F\gamma_t^2/2$. Since $\gamma_0=1$, $h_1\le e+C_F/2$. Induction yields $h_T\le e+2C_F/(T+2)$, proving the result. For the entropy-selected errors take $L=L_\tau$.
Each update adds at most one signed atom coordinate, so there are at most $T$ active coordinates, at most $kT$ unshared gates and at most $T-1$ additions. More generally inserting at most $C(t+1)^p$ branches in round $t$ gives at most $CT^{p+1}$ branches after $T$ rounds. The proof is summation; it assumes insertion rather than substitution into every existing branch.
An optional entropy-regularized branch selector assigns probability proportional to $\exp(-\langle q,v_j\rangle_n/\sigma)$. Sampling one vertex has expected oracle defect at most $\sigma\log(2MC)$ and preserves one-branch insertion. The same convergence induction applies in expectation. The principal experiments use Gibbs example selection and an exact branch oracle, avoiding this extra sampling variance.
Canonical product caching builds the dictionary in $O(nM)$ arithmetic work. A scalar full scan costs $O(nM)$ per round; multiclass scans cost $O(nMC)$. Extra line-search loss evaluations are charged separately. At fixed degree this is polynomial in gate count and the numerical update budget.
The exact rational square-loss implementation uses the fixed schedule. A vertex selected at round $j$ has final weight $2(j+1)/(T(T+1))$; accumulating signed integers $j+1$ keeps bit lengths polynomial in the input encoding and $T$. Computable real losses admit positive oracle/gradient tolerances without exact real equality testing. Floating-point experiment gaps are numerical diagnostics, not interval-certified bounds.
Prefix pruning is valid because any continuation multiplies a prefix product $v_i$ by bounded additional gates and leaves. Its score is bounded by $R(nc_{\min})^{-1}\sum_i|q_i|v_i$. This can certify an unfinished oracle search, but need not improve the worst case.
6. SGD on the identical entropic risk
A Gibbs distribution formed inside each minibatch would change the target objective. Instead introduce an auxiliary scalar:
$$\Phi(\theta,a)=a+\frac\tau n\sum_i\exp\left(\frac{\ell_i((A\theta)_i)-a}{\tau}\right)-\tau.$$
Stochastic reduction theorem. This function is jointly convex and $\min_a\Phi(\theta,a)=F_\tau(A\theta)$, with optimizer $a^*=F_\tau(A\theta)$. If losses are in $[0,B]$, restricting $a$ to $[0,B]$ preserves the minimum. A uniformly sampled example supplies unbiased stochastic gradients
$$\widehat\nabla_\theta=w_I\nabla_\theta\ell_I,\qquad\widehat\partial_a=1-w_I,\qquad w_I=e^{(\ell_I-a)/\tau}.$$
Proof. Exponential is convex and increasing, so each summand is jointly convex. The derivative in $a$ vanishes when the exponential average equals one. Substitution gives exactly the log-sum-exp risk. Averaging the displayed sample derivatives gives the exact derivatives of $\Phi$.
Project the coefficient step onto the same $\ell^1$ ball and the auxiliary step onto $[0,B]$. For unbiased gradients with squared norm expectation at most $G^2$, the ordinary projected-SGD telescoping argument gives expected error at most $DG/\sqrt S$ for a suitable constant step and iterate average, where $D\le\sqrt{4R^2+B^2}$. The manuscript proves this bound and supplies a finite, possibly loose gradient bound. This is not a comparison of one full-gradient boosting step with one single-example SGD step as if they consumed equal data.
7. Statistical and computational limits
For a fixed independent scalar dictionary, the Rademacher complexity of its radius-$R$ hull is at most $R\sqrt{2\log(2M)/n}$. The proof takes the maximum over the $2M$ signed atom correlations. Bounded-loss contraction applied to $\exp(\ell/\tau)$ gives a population entropic-risk bound; the complete manuscript states its constants and the potentially large $e^{B/\tau}$ dependence. A training gap alone is not a generalization theorem. Training-dependent dictionaries require extra analysis or sample splitting.
When $b=k$, the dictionary contains all $2^k$ subset monomials, so there is no uniform polynomial bound in both parameters. Sharing a DAG can reduce storage without changing unrolled branch count. Exact training-prediction compression to $nC+1$ signed vertices follows by affine-dependence elimination, but may change held-out predictions and is not used in the reported evaluations.
8. Undergraduate comparison contract
The suite includes synthetic linear regression, balanced XOR, two moons, breast-cancer binary logistic regression, three-class Iris and ten-class Digits softmax classification. Digits is the bundled 1797-example 8-by-8 dataset, not MNIST. There are three recorded seeds, training/validation/test splits of approximately 60/20/20 percent, training-only preprocessing, and at most eight PCA components when dimension exceeds eight. Costs are $1+|\alpha|$, and all entropic comparisons use temperature one.
For each degree-two comparison, boosting, SGD-1 and SGD-32 use the same features, norm radius and 200 passes worth of example-gradient evaluations. SGD-32 and boosting are also compared at degree one. SGD-1 rates are selected from 0.003, 0.03 and 0.3; minibatch rates also include 3 and 30. Validation selects the rate, and the test split is not used for tuning. Extra boosting objective evaluations and all candidate tuning costs are recorded. Reference Python timings are exploratory and do not establish optimized solver speedups.
Mean held-out entropic risks for degree two (boosting / SGD-1 / SGD-32):
- Linear regression: 0.01643 / 0.01915 / 0.01557.
- XOR: 0.01346 / 0.01033 / 0.14632.
- Two moons: 0.41578 / 0.41365 / 0.41412.
- Breast cancer: 0.32439 / 0.30560 / 0.28341.
- Iris: 0.35316 / 0.29235 / 0.32692.
- Digits: 1.92576 / 1.55501 / 1.56848.
An SGD variant has the lowest mean test entropic risk on every task. Boosting uses fewer active branches. On Digits it obtains about 59.8 percent accuracy versus 78.6 and 79.3 percent for SGD-1 and SGD-32, so no general accuracy or sample-efficiency advantage is claimed. Its remaining training gap shows underfitting at this 200-update budget. The complete PDF gives standard deviations, active counts, timings and numerical gap diagnostics.
9. References
1. Schapire, R. E. The strength of weak learnability. Machine Learning 5, 197–227 (1990). https://doi.org/10.1007/BF00116037 2. Freund, Y.; Schapire, R. E. A decision-theoretic generalization of on-line learning and an application to boosting. JCSS 55(1), 119–139 (1997). https://doi.org/10.1006/jcss.1997.1504 3. Friedman, J. H. Greedy function approximation: A gradient boosting machine. Annals of Statistics 29(5), 1189–1232 (2001). https://doi.org/10.1214/aos/1013203451 4. Jaggi, M. Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization. PMLR 28(1), 427–435 (2013). https://proceedings.mlr.press/v28/jaggi13.html 5. Cortes, C. et al. AdaNet. PMLR 70, 874–883 (2017). https://proceedings.mlr.press/v70/cortes17a.html 6. Gambino, N.; Kock, J. Polynomial functors and polynomial monads. MPCPS 154, 153–192 (2013). https://arxiv.org/abs/0906.4931 7. Gepner, D.; Haugseng, R.; Kock, J. Infinity-Operads as Analytic Monads. IMRN 2022(16), 12516–12624. https://arxiv.org/abs/1712.06469 8. Lurie, J. Higher Topos Theory. Princeton University Press (2009). https://www.math.ias.edu/~lurie/papers/HTT.pdf 9. Li, T.; Beirami, A.; Sanjabi, M.; Smith, V. On Tilted Losses in Machine Learning: Theory and Applications. JMLR 24(142), 1–79 (2023). https://jmlr.org/papers/v24/21-1095.html 10. Bartlett, P. L.; Mendelson, S. Rademacher and Gaussian Complexities. JMLR 3, 463–482 (2002). https://www.jmlr.org/papers/v3/bartlett02a.html 11. Robbins, H.; Monro, S. A Stochastic Approximation Method. Annals of Mathematical Statistics 22(3), 400–407 (1951). https://doi.org/10.1214/aoms/1177729586 12. Scikit-learn developers. Toy datasets. https://scikit-learn.org/stable/datasets/toy_dataset.html
10. Authorship and evidence
An OpenAI assistant generated the exposition and software and executed the recorded checks at the direction of the responsible human submitter. The byline is anonymous at the submitter's direction. The PDF supplies the complete proofs and the archive supplies exact fractions, source code and per-run data. No Lean certification, independent referee review or publication approval is asserted by this submission.