Vertical Partitioning for High Dimensional Distributed Learning

This direction is split into other directions: vertical data partitioning. Its last version stays readable and citable here.

Version 1 of 156 papers74 conceptsfrozen 2026-10-04

In the standard playbook of distributed machine learning, we scale up by "sharding" data: we chop a massive dataset into rows and give each worker a subset of examples. This horizontal partitioning works beautifully for "tall" datasets where the number of samples ($n$) dwarfs the number of features ($p$). However, as we move into domains like genomics, web-scale advertising, and natural language processing, we increasingly encounter "wide" datasets where $p$ reaches into the millions or billions.

In these ultra-high-dimensional regimes, horizontal partitioning breaks down. If every worker owns a few rows but all $p$ features, they must all maintain and synchronize a massive $p$-dimensional weight vector. The communication cost of syncing these gradients becomes a bottleneck that can outweigh the benefits of parallelization.

The solution, championed across diverse subfields from linear regression to gradient boosting, is vertical partitioning. Instead of splitting the data by samples, we split it by features.

Flipping the Data Matrix

Vertical partitioning (or feature sharding) assigns distinct subsets of feature columns to different worker nodes. Each node stores the values of its assigned features for all training instances.

As Daniel Hsu, John Langford, and Alex Smola noted in Scaling Up Machine Learning: Parallel Online Learning, this shift fundamentally changes the communication topology of the system. In a horizontally partitioned system, workers communicate to agree on a global model. In a vertically partitioned system, workers communicate to combine their local, partial predictions into a global result.

Why It Works: Communication Efficiency

The primary intuition for vertical partitioning is a trade-off between $n$ and $p$. Virginia Smith, Martin Jaggi, and Michael Jordan formalized this in their work on the CoCoA framework and L1-regularized optimization.

When $p \gg n$, the "update" a worker needs to share is no longer a $p$-dimensional gradient. Instead, workers can exchange low-dimensional scalars or $n$-dimensional vectors representing partial inner products. For example, in a linear model $y = Xw$, a worker owning a subset of columns $X_k$ only needs to share its local contribution $X_k w_k$ to the total prediction. This reduces the communication volume from being proportional to the massive feature count to being proportional to the (relatively) smaller sample count.

Scaling Decision Trees and Ensembles

Vertical partitioning has proven particularly transformative for tree-based models. Traditional distributed Gradient Boosting Decision Trees (GBDTs) struggle because they require global histograms of gradients for every feature to find the best split.

Systems like Yggdrasil, developed by Firas Abuzaid and Joseph K. Bradley, and Vero, introduced by Fangcheng Fu and Bin Cui, leverage vertical partitioning to keep feature-specific calculations local. In An Experimental Evaluation of Large Scale GBDT Systems, the authors demonstrate that by assigning specific features to specific workers, they eliminate the need for expensive global aggregation of histograms, achieving up to 34x speedups on high-dimensional workloads.

Similarly, Mathieu Guillame-Bert showed that Exact Distributed Training for Random Forests becomes possible at the scale of billions of examples when workers are responsible for specific feature subsets, preventing any single node from needing the entire dataset in memory.

Parallelizing the Sequential: Coordinate Descent

Vertical partitioning also unlocks the parallel potential of algorithms that are traditionally seen as sequential. Coordinate Descent (CD) updates one feature at a time, which is ideal for sparse, high-dimensional problems but difficult to parallelize.

The Shotgun algorithm, proposed by Joseph K. Bradley and colleagues in Parallel Coordinate Descent for L1-Regularized Loss Minimization, demonstrates that if you partition features across cores, you can update multiple features simultaneously. While this introduces some staleness or "interference" if features are highly correlated, the speed gains on high-dimensional data are near-linear. This "feature-parallel" approach is often the only tractable way to solve ultra-high dimensional quantile regression or sparse SDR where $p$ is in the millions.

Overcoming Global Dependencies

The main challenge of vertical partitioning is that features are rarely independent. A model needs to know how features interact to make accurate predictions.

Researchers have developed several "split-and-conquer" strategies to handle these dependencies:

  1. Decorrelation: Xiangyu Wang and David B. Dunson proposed DECO (DECOrrelated feature space partitioning), which applies a preprocessing step to decorrelate features before partitioning, ensuring that local updates remain statistically valid.
  2. Random Projections: Christina Heinze-Deml introduced Dual-Loco (Distributing Statistical Estimation Using Random Projections), which uses low-dimensional random projections to allow workers to "glimpse" the features held by other nodes, approximating global dependencies without massive data transfers.
  3. Progressive Merging: Algorithms like PFS (A Progressive Feature Selection Algorithm) by Qi Zhang and Fuliang Weng iteratively select the best features within chunks and then merge the winners, effectively winnowing down ultra-large spaces into manageable subsets.

By shifting the unit of parallelism from the sample to the feature, vertical partitioning allows machine learning systems to scale not just to more data, but to more complex data, turning the "curse of dimensionality" into a parallelizable advantage.

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_vertical_partitioning_for_high_dimension_cfd0c066,
  title = {Vertical Partitioning for High Dimensional Distributed Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/vertical-partitioning-for-high-dimensional-distributed-learning/rdr_cfd0c0669b8549abb05cb33614e9854b},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_vertical_partitioning_for_high_dimension_cfd0c066_v1,
  title = {Vertical Partitioning for High Dimensional Distributed Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/vertical-partitioning-for-high-dimensional-distributed-learning/rdr_cfd0c0669b8549abb05cb33614e9854b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}