Machine learning algorithms keep up with big data through a few ideas rather than one breakthrough: they update the model from small random samples (stochastic gradient descent), approximate the expensive step (histograms, sketches, approximate indexes), split the work across processors and machines, and read data in blocks that fit in memory. Which one matters depends on your data.
This page first ran in July 2024 as a news item about an unnamed "revolutionary" machine learning algorithm, said to make data processing faster, more accurate and more scalable. It named no paper, lab or result, and its only link was to a blog post about quantum machine learning that cited no study either, so this rewrite reports no single breakthrough. Instead it explains the techniques that made machine learning scale, with the papers that measured them, what quantum machine learning has and has not shown, and how to judge the next "revolutionary algorithm" headline.
What scaling to big data means for a machine learning algorithm
A machine learning algorithm fits a model to examples so that it can make predictions or find structure in data it has not seen. Google's introduction to machine learning groups the systems into supervised learning (labelled examples, used for regression and classification), unsupervised learning (patterns in unlabelled data, such as clusters), reinforcement learning (a policy learned from rewards and penalties) and generative AI.
"Big data" has a working definition too. NIST's Big Data Interoperability Framework (October 2019) describes it as extensive datasets, mainly in volume, velocity, variety or variability, that need a scalable architecture to store, manipulate and analyze efficiently. For a learning algorithm, scaling comes down to three questions: does the cost of one update grow with the size of the dataset, does the work fit in one machine's memory, and can it be split across processors?
In 2010 Léon Bottou, then at NEC Labs America, set out why this changes which algorithm wins. Data had grown faster than processor speed, so for large problems the limit on learning is computing time, not the number of examples. In that regime, an algorithm that optimizes less precisely but gets through more examples in the time available ends up with the better model. The techniques below make the same trade: a little exactness for a lot of throughput.
| Bottleneck | Technique that removes it | Where you meet it |
|---|---|---|
| Every update reads the whole dataset | Stochastic and mini-batch gradient descent | Neural networks, linear models |
| Finding a tree split looks at every value | Histograms and quantile sketches | XGBoost, LightGBM, scikit-learn HistGradientBoosting |
| The data is larger than memory | Out-of-core blocks, streamed mini-batches | XGBoost external memory, data loaders |
| One machine is too slow | Data parallelism, in-memory cluster compute | Spark MLlib, distributed XGBoost, multi-GPU training |
| Similarity search compares against every item | Approximate nearest neighbor indexes | FAISS, HNSW, pgvector |
Learn from a sample at a time: stochastic gradient descent
Training most models means lowering an error measured on the training data. The gradient says which way to change each parameter to lower it, and gradient descent takes a step in that direction, over and over. Plain, or full-batch, gradient descent computes the gradient over every example before each step. Google's Machine Learning Crash Course puts the problem plainly: with hundreds of thousands or millions of examples, using the full batch is not practical.
Stochastic gradient descent (SGD) estimates the gradient from a single randomly picked example and takes a step at once. Each step is noisy, but it costs the same whether the dataset has a thousand rows or a billion. Mini-batch SGD sits in between: pick a small random batch, average its gradients, update, repeat. Bottou's paper adds two properties that matter for big data. SGD does not need to remember which examples it has already seen, so it can learn from data as it arrives. And although it is a poor optimizer by the classical measure, it needs less time than exact methods to reach a given expected error when computing time is the constraint. In theory, a single pass of averaged SGD over the training data gives a model as good, asymptotically, as fully optimizing on all of it, although Bottou notes that reaching that regime can take a long time in practice.
Batch size is a setting to tune, not a fixed rule. Google's course notes that small batches behave like pure SGD and large ones like full-batch descent, and that some of the noise even helps a model generalize.
Approximate the expensive step: histograms in gradient boosting
For tabular data, the rows and columns of transactions, CRM records and sensor logs, gradient-boosted trees are the method to beat. Boosting adds decision trees one at a time, each fitted to the errors the earlier trees left. The expensive step is choosing where each tree splits: the exact method sorts every value of every feature and tries every candidate split.
XGBoost, by Tianqi Chen and Carlos Guestrin of the University of Washington (KDD, August 2016), made three changes that let boosting scale:
- Approximate splits. A weighted quantile sketch proposes a short list of candidate split points from the percentiles of each feature, and the algorithm only evaluates those. The paper found this matched the exact method's accuracy at a reasonable level of approximation.
- Sparsity-aware splits. Each tree node learns a default direction for missing values, so the algorithm only visits entries that are present. On a sparse insurance dataset it ran 50 times faster than a naive implementation.
- Out-of-core learning. Data is stored in compressed, sorted column blocks that can be read from disk. The system trained on 1.7 billion examples on a single machine, and on all of them with only four machines in a cluster.
The paper reports that XGBoost ran more than ten times faster than popular existing solutions on one machine, and that 17 of the 29 winning solutions published on Kaggle's blog during 2015 used it. LightGBM (NIPS 2017), from Microsoft Research and Peking University, went further on the same bottleneck. Gradient-based one-side sampling drops a large share of the rows with small gradients, which say little about where to split, and exclusive feature bundling merges features that are rarely non-zero at the same time. Its authors report training up to more than 20 times faster than conventional gradient boosting with almost the same accuracy.
Histogram-based split finding is easiest to see in scikit-learn's documentation. Its HistGradientBoosting estimators, added in version 0.21 and inspired by LightGBM, sort each feature once at the start and bin it into integer buckets, typically 256; from then on, each split considers only the bucket boundaries. The documentation says they can be orders of magnitude faster than the classic implementation once a dataset passes tens of thousands of samples.
The approximation won. As of September 2026, XGBoost's documentation describes the exact method as slow and hard to scale, and its default tree method, auto, is the same as hist, the histogram method it describes as close to LightGBM's.
Tree models have also held their ground against deep learning on this kind of data. A NeurIPS 2022 benchmark by Léo Grinsztajn, Edouard Oyallon and Gaël Varoquaux compared them across 45 tabular datasets and found tree-based models still state of the art on medium-sized data, around 10,000 samples, even before counting their speed. Our comparison of AI frameworks covers the libraries themselves.
Split the work: in-memory clusters and data parallelism
Many learning algorithms are iterative: k-means clustering and logistic regression pass over the same data again and again. The Resilient Distributed Datasets paper from UC Berkeley (NSDI 2012) pointed out that in most frameworks of the time, the only way to reuse data between two MapReduce jobs was to write it to a distributed file system, paying for replication, disk I/O and serialization on every pass. Its answer, Spark, keeps working data in memory across the cluster and rebuilds lost pieces from their lineage. The paper measured Spark at up to 20 times faster than Hadoop on iterative machine learning and graph applications.
MLlib is the distributed machine learning library that grew on top. As of September 2026, the Spark documentation names the DataFrame-based API (spark.ml) as MLlib's primary API; the older RDD-based spark.mllib has been in maintenance mode since Spark 2.0.
Deep learning, whose layers and training are explained in deep learning and NLP explained, parallelizes differently. In data parallelism, every worker holds a copy of the same model, takes its share of each mini-batch, computes gradients, and an allreduce operation combines the gradients so every copy applies the same update. The difficulty is that more workers means a larger total batch, and large batches are harder to optimize. In June 2017, a Facebook team with Priya Goyal as first author showed two simple fixes: scale the learning rate in proportion to the batch size (their linear scaling rule), and warm it up gradually at the start. With them, a ResNet-50 image classifier trained on ImageNet with a batch of 8,192 images across 256 GPUs in one hour, matched the accuracy of small-batch training, and reached about 90% scaling efficiency going from 8 to 256 GPUs.
Training frontier-scale models raises a different set of limits; our post on the path to AGI and AI supercomputers covers that end of the scale.
Search instead of scanning: approximate nearest neighbor indexes
Modern systems turn documents, images and products into embeddings, lists of numbers where similar items sit close together. Finding the most similar items to a query exactly means comparing it with every stored vector, which grows with the collection. Approximate nearest neighbor (ANN) search gives up a little recall to avoid that scan.
Two papers set the pattern. FAISS, from Facebook AI Research (February 2017, later in IEEE Transactions on Big Data), rebuilt similarity search for GPUs: its nearest neighbor search ran 8.5 times faster than the previous GPU state of the art, and it built a graph linking 1 billion vectors in under 12 hours on four GPUs. HNSW, by Malkov and Yashunin (first posted in 2016, published in IEEE TPAMI in 2020), stacks several proximity graphs in layers; a search starts in the sparse top layer and descends, which gives logarithmic scaling of search complexity.
Both ideas are now ordinary database features. As of September 2026, pgvector, the PostgreSQL extension, does exact search by default, with perfect recall, and offers HNSW and IVFFlat indexes for approximate search. Its documentation notes that HNSW has the better speed-recall trade-off but builds more slowly and uses more memory, and that queries can return different results once an approximate index is added. Vector search of this kind is also the retrieval step in retrieval-augmented generation (RAG), where an assistant looks up passages from a company's documents before it answers. How vector search and text-to-SQL work inside a database is covered in generative AI for databases.
Is quantum machine learning the next revolution?
The article the 2024 page linked to was about quantum machine learning, the promise that quantum computers will process big data exponentially faster. The promise has a real origin: HHL, published by Aram Harrow, Avinatan Hassidim and Seth Lloyd in Physical Review Letters in 2009, handles sparse systems of linear equations in time polynomial in the logarithm of the system's size (and in its condition number), exponentially faster than the best classical method for the task as they defined it. Many quantum machine learning algorithms build on it.
In 2015, Scott Aaronson set out the fine print in Nature Physics. The speedup holds only if the input can be loaded into quantum memory quickly, if the matrix is sparse or has other special structure, and if it is well-conditioned. And the output is a quantum state that encodes the solution, not the solution itself: reading out individual entries means running the algorithm about as many times as there are entries, which cancels the gain. With big data, those are exactly the expensive steps: getting the data in and the answer out.
Then the best-known example fell. Kerenidis and Prakash's 2016 quantum recommendation algorithm ran in time polylogarithmic in the size of the ratings matrix, and was regarded as one of the strongest candidates for a provable exponential speedup. In July 2018, Ewin Tang posted a classical algorithm, presented at STOC in June 2019, that is only polynomially slower when the data sits in a structure that supports the same kind of sampling. The quantum algorithm's exponential advantage was gone.
Parameterized quantum circuits, trained by a classical optimizer, have a different problem. Jarrod McClean and colleagues showed in 2018 that for a wide class of these circuits the gradient vanishes exponentially as qubits are added: a barren plateau, with no slope to follow. An August 2025 Nature Communications perspective by M. Cerezo of Los Alamos National Laboratory and colleagues gathered evidence that many models built to avoid barren plateaus can then be simulated classically, once some data has been collected from a quantum device, with caveats the authors list.
Benchmarks point the same way. In March 2024, Bowles, Ahmed and Schuld tested 12 popular quantum machine learning models on 6 binary classification tasks, 160 datasets in all. Out-of-the-box classical models outperformed the quantum classifiers, and removing entanglement from a quantum model often did as well or better.
Note
A demonstrated advantage does exist for a different kind of data: data that comes from quantum systems. In Science in June 2022, Hsin-Yuan Huang and colleagues proved that quantum machines can learn some properties of physical systems from exponentially fewer experiments, and demonstrated it with up to 40 superconducting qubits. That is a result about physics experiments, not spreadsheets.
None of the results above shows a quantum speedup on ordinary business data such as tables, text or images. For that data, the techniques in the earlier sections are where the gains are today.
How to judge a "revolutionary algorithm" headline
The 2024 story this page began as could not be checked, because it gave nothing to check. When the next one arrives, work through the claim in this order:
- Find the paper. A real result has authors, a date and usually a venue: a journal, a conference or at least an arXiv preprint. A story without one is not evidence.
- Find what was measured. Accuracy on which benchmark, speed on which hardware, compared with what. LightGBM's speedup of up to more than 20 times is measured against conventional gradient boosting, at almost the same accuracy; that is a specific, testable claim.
- Check that the baseline was tuned. In a 2017 study, Gábor Melis, Chris Dyer and Phil Blunsom re-ran popular language model architectures with large-scale automatic hyperparameter tuning and found that standard LSTMs, properly regularized, outperformed more recent models. The earlier results had been measured with different code bases and limited computing budgets.
- Check for leakage. Sayash Kapoor and Arvind Narayanan surveyed leakage, information from the test data reaching the model during training, and found it in 17 fields, affecting 294 papers (Patterns, 2023). In their reproduction of civil war prediction studies, complex models did not perform substantively better than decades-old logistic regression once the errors were fixed. Our first Python machine learning project shows how leakage creeps into an ordinary train and test split.
- Check that it fits your data. A method that wins on images may lose on tables, as the NeurIPS 2022 tabular benchmark showed.
- Look for code. XGBoost, LightGBM and FAISS all shipped with their code, so anyone could rerun the comparisons. A result nobody can run stays a claim.
Tip
The fastest check is the abstract. Read each number next to the baseline and the dataset it was measured against. An abstract with no numbers is a warning sign.
The same habits apply to AI research news in general; our look at AI scientific discoveries and what held up applies them to protein folding, materials and weather forecasting.
Which technique fits your data
Start from the shape of the data, not from the newest paper:
| Your data | Start with | Why |
|---|---|---|
| A table that fits in memory | Histogram gradient boosting: XGBoost, LightGBM or scikit-learn | Tree models led deep learning on medium-sized tables in the NeurIPS 2022 benchmark, and binning keeps them fast |
| A table larger than one machine's memory | XGBoost reading from disk, or distributed training on Spark | XGBoost's paper trained on 1.7 billion rows on one machine, and on four in a cluster |
| Images, audio or free text | Neural networks trained with mini-batch SGD on GPUs | Mini-batches keep each update cheap, and data parallelism spreads them across GPUs |
| Data that arrives continuously | Online learning with SGD | SGD needs no memory of past examples, so it can learn as the data arrives |
| Millions of documents or images to search by meaning | An ANN index: HNSW in pgvector, or FAISS | A little recall buys search that does not scan every vector |
Whatever the algorithm, the test is the same: a held-out set from your own data, and a simple baseline it has to beat. If the harder question is where a model belongs in a business process at all, our AI and automation service starts from one real workflow, uses a model only at the steps that need judgment, and runs an evaluation set built from your real cases before any model, prompt or source change goes live.
