Conflict-Aware Parallel Boosting for Sparse High-Dimensional Models

Boosting builds a model one piece at a time. Each new piece fixes what the earlier pieces got wrong, so piece $t$ cannot be trained until piece $t-1$ is finished. This sequential dependency is provably hard to escape when the learner is a black box. When the pieces are single sparse features, though, as with the millions of word, n-gram, and rule indicators in text classifiers and statistical machine translation, the data itself says which updates can safely happen together. Two rare features that never fire on the same example cannot interfere, so their weights can be changed at full strength in the same round. We propose a parallel coordinate-boosting method that, in each round, picks a set of features chosen to rarely fire together and to have large gradients. The size of each step is then set by how much the chosen features actually overlap, not by the worst-case density of any single example.

The opportunity matters because the best existing parallel method, Parallel Boosting with Momentum (BOOM), already treats coordinate descent as boosting over features. It makes simultaneous updates safe by shrinking every step by a single global constant $\kappa$, the largest number of nonzero features in any training record. That constant is a maximum over the whole dataset. One long document or one long n-best translation hypothesis sets it for everyone, while the typical rare feature co-occurs with almost nothing it is updated alongside. We want to replace this worst-case damping with a measured, per-round interference count, and to choose rounds so that the count stays small. If this works, the number of sequential rounds needed to reach a target loss on heavy-tailed sparse data drops substantially. It would also give a concrete instance of the "white-box structure" that Algorithms and hardness results for parallel large margin learning leaves open as the route around its sequential lower bound.

Core Claim

Consider a linear model with weights $w$ and per-example loss whose second derivative is bounded. Suppose a round updates only the coordinates in a set $S$ by amounts $\delta_j$. By Cauchy–Schwarz on $x_i \cdot \delta$, which has at most $|{\rm supp}(x_i) \cap S|$ nonzero terms, the objective $f$ satisfies a separable upper bound:

$$f(w+\delta) \le f(w) + \sum_{j \in S} \partial_j f(w)\,\delta_j + \frac{\kappa_S}{2}\sum_{j\in S} L_j \delta_j^2, \qquad \kappa_S = \max_i |{\rm supp}(x_i)\cap S|.$$

Here $L_j$ is the curvature constant of coordinate $j$, and ${\rm supp}(x_i)$ is the set of features active in example $i$. BOOM uses this kind of bound with $S$ equal to all coordinates, so $\kappa_S = \kappa$. Minimizing the bound gives coordinate-wise steps scaled by $1/(\kappa_S L_j)$. The guaranteed progress per round therefore grows with $\sum_{j\in S} (\partial_j f)^2 / (\kappa_S L_j)$.

Our claim has two parts. First, on sparse heavy-tailed data there exist sets $S$ that cover most of the gradient mass while $\kappa_S$ is one to two orders of magnitude below $\kappa$. Second, a cheap greedy selection over the feature co-occurrence graph finds such sets. The result should be fewer sequential rounds to a fixed loss than either BOOM or one-at-a-time greedy boosting, with no change to the model or the objective.

The natural structure is a split between head and tail features. The few very frequent features co-occur with everything, so they must be handled together. We give them a small dense quasi-Newton block, following the batch log-linear practice in Parsing the WSJ Using CCG and Log-Linear Models. The long tail is updated in large, nearly conflict-free blocks.

Relation to Prior Work

BOOM supplies the method we build on: momentum (Nesterov-style acceleration that reuses the previous step direction), coordinate-specific curvatures, and the separable-bound argument. It reports that FISTA, a standard accelerated proximal method with one global step size, "made negligible progress" on its 712-million-feature industrial data. We keep all of this and change only how the update set and the damping factor are chosen.

The hardness result of Servedio and Long motivates the work. They prove that querying a weak learner in parallel cannot reduce the number of boosting stages below $\Omega(\gamma^{-2}\log(1/\epsilon))$, where $\gamma$ is the margin and $\epsilon$ the target error. Their positive parallel algorithm relies on random projections, which destroy exactly the coordinate sparsity we exploit. We do not claim to beat their lower bound in general, since it is a black-box statement. We claim that a measurable property of the data, low co-occurrence among the features updated together, lets many boosting steps be taken per round.

Two other lines of work address diversity and parallelism differently. Exclusivity Regularized Machine imposes feature exclusivity on ensemble members through a penalty, so that members use disjoint features and can be trained jointly. We instead find exclusivity already present in the data and leave the model unchanged. The online parallel booster Online Parallel Boosting and the spatial-grid booster Theoretical and Empirical Analysis of a Parallel Boosting Algorithm parallelize by reshaping data flow or learning rates across learners. Both were tested only on low-dimensional UCI-style data and give no handle on sparse feature interference.

On the application side, the structured-prediction trainers set the application regime. Joint Feature Selection in Distributed Stochastic Learning runs sharded SGD on a pairwise ranking loss with cross-shard $\ell_1/\ell_2$ selection. Max-Violation Perceptron and Forced Decoding gets roughly 7x speedup on 24 cores over 20M+ features. Both treat parallelism as data sharding. Neither asks which feature updates can be applied together exactly.

Research Program

The first component is a diagnostic study, done before any new algorithm. For each benchmark we compute $\kappa$, the distribution of per-example feature counts, and the co-occurrence graph restricted to features carrying the top fraction of gradient norm at a warm-started solution. From these we estimate the achievable trade-off between gradient mass covered and $\kappa_S$. This tells us immediately whether the idea has room: if typical $\kappa_S$ for useful sets is close to $\kappa$, the proposal fails cheaply.

The second component is the selection rule. Each round, features are scored by their predicted gain $(\partial_j f)^2/L_j$. They are added greedily to $S$ while tracking, per example, how many selected features it contains, stopping when the gain-per-unit-$\kappa_S$ stops improving. This needs one pass over the inverted index of the candidate features, which is distributed by feature, as BOOM's updates already are. We will also test a smoothed variant that replaces the max in $\kappa_S$ with a high quantile and handles the few offending examples with a correction step. We expect long outlier records to be the main obstacle.

The third component integrates momentum and $\ell_1$ regularization. The selection changes each round, so we must check that BOOM's accelerated rate survives under a varying separable bound. We will either prove a rate in terms of the average $\kappa_{S_t}$ or show empirically where it breaks.

The fourth component is an application to machine translation tuning. Given fixed n-best lists, the pairwise ranking loss used by IterSelSGD is a convex sparse linear problem, so our solver can replace its per-shard SGD inside the same outer loop.

Baselines

The naive reference point is sequential greedy coordinate boosting: one feature, the one with the largest gain, updated per round. It defines the "fully sequential" end of the spectrum. Every parallel method's rounds-to-loss is reported as a speedup relative to it.

The strongest existing competitor is BOOM, run with its global $\kappa$, coordinate curvatures, and momentum. It is the only method in the material designed for exactly this geometry at this scale, and it already beats FISTA and unaccelerated parallel boosting there. We will implement it in the same codebase, sharing the curvature estimates, $\ell_1$ strength, data partitioning, and number of workers, so that the only difference is the choice of $S$ and the damping factor. No reported result was found on Lacuna for BOOM's exact objective values on any benchmark, since the paper reports curves qualitatively. We therefore reproduce it. Beating it means reaching BOOM's final training objective, and matching held-out accuracy, in at least 2x fewer sequential rounds and less wall-clock time on the sparse benchmarks.

FISTA is included as the global-step-size reference point, because BOOM's main reported finding is that FISTA stalls on elliptical data.

Two ablations isolate the key ingredient. The first draws a random set $S$ of the same size each round and damps by its measured $\kappa_S$. This separates the benefit of exact interference measurement from the benefit of deliberate selection. The second applies conflict-aware selection with the global $\kappa$ as damping, which checks that the gain truly comes from the smaller step-size denominator.

For machine translation, the baseline is IterSelSGD on WMT11 German–English News Commentary. That paper reports 28.81 BLEU against a 27.10 baseline. We use identical n-best lists, features, and selection budget. Success there means matching 28.81 BLEU in fewer synchronizations and less wall-clock time, not necessarily exceeding it.

Why not just…?

Why not just use BOOM, since sparse data already has small $\kappa$? If the maximum record density is already small, conflict-aware selection buys nothing, and this is the main threat. The diagnostic study settles it directly by comparing $\kappa$ with the $\kappa_S$ achievable at high gradient coverage. Text corpora such as RCV1, with 804,414 news documents of varying length, and n-best translation lists are exactly where we expect long outliers to inflate the maximum. If the gap is under about 3x on all sparse benchmarks, we will drop the selection algorithm. We would then report the diagnostic as a finding about when BOOM's bound is tight.

Why not just run asynchronous data-parallel SGD with per-coordinate adaptive step sizes? Per-coordinate step sizes address the elliptical geometry, and lock-free sparse SGD is a strong practical choice for wall-clock speed, so this is a real competitor. It does not optimize $\ell_1$-regularized objectives to high precision. The material also shows that uniform first-order steps struggle on heavy-tailed features (BOOM's FISTA comparison) and that sharded SGD needed an extra selection step to avoid overfitting rare features (IterSelSGD). We will include an adaptive-step-size sharded SGD baseline with the same cores and tuning budget, and report both time-to-objective and held-out accuracy. If it matches us on held-out accuracy, the contribution narrows to high-precision and sparse solutions, and we will say so.

Why not just partition features across workers and train independent sub-models, as in an exclusivity-regularized ensemble? This removes interference by changing the model into an ensemble with disjoint supports. ExRM shows that such ensembles train jointly and fast on small data. That route was never tested beyond UCI scale, and it optimizes a different hypothesis class. Our method solves the original single-model objective exactly. A feature-sharded ensemble baseline at matched parameter count will show whether the restriction costs accuracy on RCV1 and translation.

Why not just use random coordinate subsets with smaller damping? That is precisely the first ablation. If random sets achieve similar $\kappa_S$ at similar gradient coverage, the selection rule is unnecessary and the result reduces to "measure interference instead of bounding it." That would still be a useful but smaller claim.

Proposed Experiments

The convex experiments use RCV1 Topics, w8a, BOOM's 18 synthetic elliptical datasets, and ijcnn1. The synthetic suite lets us vary ellipticity and sparsity in a controlled way. ijcnn1 has few, mostly dense features, so we include it as a negative control where $\kappa_S \approx \kappa$ and we predict no gain over BOOM. Seeing a gain there would indicate a bug or an unfair comparison.

For RCV1 we report microaveraged $F_1$ alongside optimization curves. The RCV1 paper reports 0.816 for an SVM on Topics. That number is an accuracy sanity check, not a target to beat, since our contribution is speed at equal objective.

The primary metrics are sequential rounds to reach within $10^{-3}$ relative suboptimality of the best objective found by any method, wall-clock time at 8, 32, and 128 workers, and the per-round ratio $\kappa/\kappa_{S_t}$.

The machine translation experiment reruns the IterSelSGD pairwise ranking setup on WMT11 German–English News Commentary with our solver replacing sharded SGD, and reports BLEU, rounds, and time. If resources allow, we will repeat it on the Chinese–English setting of the max-violation paper, using n-best lists from reachable sentences only.

The decisive check is a correlation across all datasets. Speedup over BOOM should track the measured ratio $\kappa/\kappa_S$: large on synthetic high-ellipticity data and RCV1, near one on ijcnn1. If speedup does not follow this ratio, the mechanism we propose is not what drives the results, whatever the headline numbers say.