Certified Candidate Search for Sparse Recursive Boosting

Certified Candidate Search for Sparse Recursive Boosting

Anonymous. November 10, 2026.

This companion extends A Higher Categorical Theory of Polynomial-Branch Recursive Boosting with Maximum-Entropy Error Selection. The double-column attachment gives the full arguments, tables, references, and limitations. The archive supplies source, certificates, and the raw records for both studies.

Incidence construction

On training row $i$, let $G_i\subseteq[b]$ be the active Boolean gates. For a conjunction $a\subseteq[b]$ of degree at most $k$, let $I_a=\{i:a\subseteq G_i\}$, $c_a=1+|a|$, and $A_a=\mathbf 1_{I_a}/c_a$. We use one constant leaf and total coefficient radius $R$. The signed atom hull gives the empirical prediction set $K_R=\{A\Theta:\|\Theta\|_1\le R\}$, with vector outputs allowed.

Repeated Boolean gates are idempotent. With the original cost of one plus word length, any repeated-gate column is a contraction of its distinct-gate column. Since zero lies in the signed hull, this reduction preserves the empirical feasible set. An atom with empty training support contributes zero. That omission is specific to the training sample.

The nominal candidate count is $M_{\rm nom}=\sum_{d=0}^k\binom bd$. Generate $(a,i)$ for every degree-bounded subset $a\subseteq G_i$ and group by $a$. This yields exactly the nonempty training postings. The number of incidences is

$$P=\sum_a |I_a|=\sum_i\sum_{d=0}^{\min(k,|G_i|)}\binom{|G_i|}{d}.$$

If every row activates at most $s$ gates, then $P\le n\sum_{d=0}^k\binom sd$. For fixed $s,k$, storage and sparse scoring are linear in row count, up to label storage and output dimension. The direct indexed oracle accumulates one residual vector per incidence. This is an exact empirical reduction of the dictionary.

A prefix certificate

For an integer residual array $Q$, the score of $a$ is

$$r_Q(a)=\max_c\left|\sum_{i\in I_a}Q_{ic}\right|/c_a.$$

For a prefix $p$, let $P_{pc}$ and $N_{pc}$ be the positive and negative residual masses on $I_p$. Every proper descendant has support contained in $I_p$ and cost at least $|p|+2$. Its score is therefore bounded by

$$U_p=\frac{\max_c\max(P_{pc},N_{pc})}{|p|+2}.$$

The signed interval $[-N_{pc},P_{pc}]$ contains the sum over every subset of the parent support. A best-first search scores a prefix, then queues its proper-descendant family with this bound. Expanding a family scores its immediate children and replaces it by their descendant families. Let $B$ be the best score seen and $U$ the larger of $B$ and the largest pending family bound. Every unscored supported conjunction belongs to a pending family or to a discarded family whose bound was at most the incumbent. The incumbent only increases. Thus $B\le\max_a r_Q(a)\le U$, including when a prefix budget stops the search early.

Given a finite binary64 residual array $q$, encode it by rounding $2^s q$ to integer $Q$. We guard against accumulator overflow and compare scores as exact rationals. The score of a signed atom changes by at most $E=n/2^{s+1}$. The selected signed vertex for $q$ therefore has an additive linear-oracle error at most

$$R\bigl(2^{-s}(U-B)+2E\bigr).$$

The bound concerns the supplied gradient. If it differs from the exact derivative by at most $\eta$ in entrywise $\ell^1$ norm, at most $2R\eta$ must be added. The integer oracle is verified against exhaustive enumeration and exact rational evaluation of the supplied floating-point gradients.

Incidence semantics

The prefix category assigns supports contravariantly because an extension induces an inclusion of row supports. The incidence set has projections to the rows and the branch labels. Correlation numerators are obtained by pulling the residual field back to incidences and summing along the fibers over branches. Finite fiberwise sums compose by regrouping and satisfy the pullback identity by fiber identification. The certificate therefore combines positive and negative masses additively over disjoint row blocks before applying the maximum.

Corrective fitting on a common objective

All solvers minimize the tilted empirical risk $F_\tau(Z)=\tau\log(n^{-1}\sum_i e^{\ell_i(Z_i)/\tau})$ on the same empirical coefficient hull. At the tested temperature one, the binary logistic objective is $\log(1+n^{-1}\sum_i e^{-m_i})$ for margins $m_i$, which has the same minimizers as empirical exponential margin loss.

The corrective solver adds a selected branch and jointly refits the admitted coefficients with damped Newton steps and feasible backtracking. A scheduled Frank--Wolfe step is retained when it improves the incumbent. An approximate correction then preserves the standard outer recurrence and its additive oracle-error term. The comparison uses pairwise Frank--Wolfe with a feasible mass transfer, directional curvature initialization, and monotone backtracking. Both methods use the identical tilted loss, signed dictionary, and coefficient radius.

The numerical stopping gap uses the current gradient pairing plus the upper bound on the best signed correlation. For exact derivatives the convexity inequality makes this an upper bound on empirical suboptimality. The benchmark gaps use floating-point derivatives and pairings. The integer certificate makes the linear subproblem independently checkable.

Prior evaluation budget study

At a cap of 50 training evaluation passes, validation-selected corrective boosting had lower mean held-out tilted risk than SGD and batch-32 SGD on all seven tasks. It beat both baselines on 28 of 35 paired splits using a numerical tie tolerance. All optimizers shared the same degree-two features, radius, and temperature within a split. SGD inner loops were compiled. A joint loss and gradient evaluation counted once, and line-search loss evaluations counted toward the cap.

SGD led at the 20-pass cap and on Iris at 200 passes. The Digits corrective fit used fewer branches and took longer than batch-32 SGD. The largest gain came on the synthetic task with a sparse target in the supplied dictionary. The archive includes all four evaluation budgets and tuning records.

New degree-three study

The oracle experiments use three seeds and two gradient states, zero and a fitted intercept. The synthetic problems have 1,200 training rows, seven active gates per row, and 64, 128, or 512 gates. The real-data problem is Digits 3 versus 8 with a fixed pixel-intensity threshold. There are 84 oracle records and 27 fitted trajectories.

On the sparse 512-gate problem, 22,370,049 nominal terms reduce to a median of 33,663 supported terms with 76,800 postings. At the fitted intercept the exact prefix search scores 513 terms and reads 9,600 postings. Its median query time is 0.98 ms compared with 0.33 ms for the complete indexed scan.

On the sparse 64-gate problem, index construction takes about 84 ms. A subsequent indexed scan takes about 0.30 ms, compared with 540 ms for nominal enumeration at the fitted intercept. The nominal reference streams columns in blocks. All complete integer scores agree with the independently enumerated reference where timed, and all complete prefix searches agree with their indexed scans.

The table gives median total time at the common numerical gap target of 0.02 with a 300-pass cap. The reported time includes index construction.

All methods reached the target on each synthetic split. On Digits, pairwise reached it on three of three splits, while each corrective variant reached it on two of three. The Digits timing medians include capped runs where applicable. On sparse 512, the prefix fitting variant reads about 190,000 postings versus 614,000 for the complete indexed version. The reduced search work incurs a modest elapsed-time penalty in this implementation.

The results support exact sparse indexing and a certified optional prefix search. They show how sparsity, candidate work, and elapsed time can lead to different choices of solver.

Related work

• Shen and Li, On the Dual Formulation of Boosting Algorithms, IEEE TPAMI 2010. https://doi.org/10.1109/TPAMI.2010.47
• Lacoste-Julien and Jaggi, On the Global Linear Convergence of Frank-Wolfe Optimization Variants, NeurIPS 2015. https://arxiv.org/abs/1511.05932
• Nakagawa et al., Safe Pattern Pruning, KDD 2016. https://arxiv.org/abs/1602.04548
• Le Morvan and Vert, WHInter, ICML 2018. https://proceedings.mlr.press/v80/morvan18a.html
• Braun et al., Blended Conditional Gradients, ICML 2019. https://proceedings.mlr.press/v97/braun19a.html
• Li et al., On Tilted Losses in Machine Learning, JMLR 2023. https://jmlr.org/papers/v24/21-1095.html

An anonymous human submitter commissioned this companion. An OpenAI assistant derived and checked the arguments, wrote the code, and ran the reported experiments.