PaperlayerView exact revision on arXiv

Source-linked AI summary

A Survey on Large-scale Machine Learning

Meng Wang, Weijie Fu, Xiangnan He, Shijie Hao, Xindong Wu

arXiv:2008.03911v1cs.LGstat.ML

TL;DR

Large-scale machine learning addresses the high time costs of sophisticated methods on growing datasets. The paper systematically surveys LML through model simplification, optimization approximation, and computation parallelism, categorizes methods by scenarios and strategies, and discusses limitations and future directions. Its central conclusion is that LML methods should be understood across these three complementary computational perspectives and their combinations.

  • Problem

    Sophisticated machine-learning methods can incur huge time costs on large-scale data, motivating LML for efficient learning from big data.

  • Method

    The paper surveys over 200 LML papers, organizing methods by three computational perspectives, targeted scenarios, intrinsic strategies, and hybrid approaches.

  • Results

    The survey provides a systematic framework covering model simplification, optimization approximation, computation parallelism, representative methods, and their limitations.

  • Takeaways & Limitations

    LML is presented as a field whose scalability strategies can be examined through complementary model, optimization, and system perspectives.

  • Takeaways & Limitations

    Optimization-approximation methods mostly focus on convex problems, while parallel methods often assume equally capable nodes, limiting broader applicability.

Abstract

from arXiv · show

Machine learning can provide deep insights into data, allowing machines to make high-quality predictions and having been widely used in real-world applications, such as text mining, visual classification, and recommender systems. However, most sophisticated machine learning approaches suffer from huge time costs when operating on large-scale data. This issue calls for the need of {Large-scale Machine Learning} (LML), which aims to learn patterns from big data with comparable performance efficiently. In this paper, we offer a systematic survey on existing LML methods to provide a blueprint for the future developments of this area. We first divide these LML methods according to the ways of improving the scalability: 1) model simplification on computational complexities, 2) optimization approximation on computational efficiency, and 3) computation parallelism on computational capabilities. Then we categorize the methods in each perspective according to their targeted scenarios and introduce representative methods in line with intrinsic strategies. Lastly, we analyze their limitations and discuss potential directions as well as open issues that are promising to address in the future.

1 INTRODUCTION

The paper motivates large-scale machine learning (LML) for learning from rapidly growing data with feasible computational costs, then surveys the field across complementary computational perspectives. It analyzes representative methods, hybrid strategies, limitations, and future directions.

  • LML targets machine-learning tasks on large-scale data using available computing resources and nearly linear or lower time complexities.
  • Existing surveys are incomplete because they typically focus on one perspective, omit complementarity, or lack computational and recent methodological analysis.
  • The paper reviews over 200 LML papers and provides lookup tables for selecting predictive models, optimization algorithms, and processing systems.
  • Its framework covers model simplification, optimization approximation, and computation parallelism as three complementary routes to scalability.
  • The survey categorizes methods by targeted scenarios, analyzes intrinsic acceleration strategies, and reviews hybrid methods that jointly improve multiple perspectives.
  • It analyzes method limitations, proposes potential directions based on extensions, and identifies open issues for future LML development.

2 FROM EFFECTIVENESS TO EFFICIENCY

The paper frames machine-learning efficiency through effectiveness error decomposition and shows how model complexity, optimization, and processing capabilities define three routes to large-scale learning. It then maps these routes to model simplification, optimization approximation, and computation parallelism.

  • Machine learning seeks an instance-to-label mapping that handles both existing and future data.
  • Effectiveness with error decomposition: The paper decomposes excess error into approximation, estimation, and optimization terms under a computational-time constraint.
  • Efficiency from three perspectives: The three efficiency perspectives target predictive-model computational complexity, optimization-algorithm efficiency, and processing-system computational capability.
  • Efficiency from three perspectives: Model simplification reduces complexity through smaller or sparser matrices, optimization approximation increases error reduction per computation, and computation parallelism distributes intensive operations across devices.

3 REVIEW ON LARGE-SCALE MACHINE LEARNING

The review organizes LML methods by three computational perspectives and presents their methods through a coarse-to-fine structure. It includes targeted scenarios, intrinsic strategies, experimental evidence, and method trade-offs.

  • Section 3 reviews LML methods through model simplification, optimization approximation, and computation parallelism, followed by their collaboration.
  • Table 1 is a brief lookup table for LML methods based on model simplification.

3.1 Model Simplification

Model simplification scales machine learning by reducing the size, density, or structure of computations while preserving useful predictive behavior. The survey covers sampling, sketching, graph sparsification, neural-network decomposition, and relaxed tree decisions, with speedups often accompanied by scenario-specific trade-offs.

  • Kernel-based models: Low-rank approximation reduces matrix-inversion costs to O(m^3+nmc), using sampling-based or projection-based sketches to replace full kernel matrices.Sampling methods select kernel columns, while projection methods use random combinations; orthonormal sketches can accelerate matrix products to O(n^2logm) instead of O(n^2m).
  • Kernel-based models: Sampling-based approximation is fastest in uniform form, whereas projection-based sketches generally outperform uniform sampling; streaming distributions limit sampling-based methods.Random features can instead use fast primal-form linear solvers for large-scale data with acceptable performance.
  • Graph-based models: Sparse label propagation reduces each iteration from O(n^2C) to O(nkC), and achieves 10× to 100× acceleration over matrix inversion without accuracy reduction.Anchor graphs further reduce optimization to a smaller set of anchor-related parameters, while divide-and-conquer graph construction improves consistency with exact graphs at lower time cost.
  • Deep models: Filter decomposition, efficient activations, and related neural-network simplifications substantially reduce deep-model computation while retaining comparable or useful accuracy.Reported examples include MobileNet at 32× smaller and 27× less compute-intensive than VGG16, hierarchical softmax speeding training by more than 250×, and ReLU training 6× faster than tanh on CIFAR-10.
  • Tree-based models: Relaxed tree decisions reduce costs through instance sampling, sparsity-aware splitting, feature sampling, histograms, and feature bundling.Sampling 20% to 30% of instances sped up GBDT 3× to 5×, while sparsity-aware splitting ran 50× faster than the naive version on Allstate-10K.
  • Summary: Model simplification exposes a trade-off between efficiency and model properties: deep models can achieve higher classification accuracy but require heavy training, whereas tree-based models are more interpretable.The survey also notes that simplification methods may require careful architecture design or add costs such as gradient computation and extra memory.

3.2 Optimization Approximation

Optimization approximation improves large-scale machine learning efficiency by computing gradients over only selected instances or parameters, reducing computation while preserving useful optimization progress. The section reviews mini-batch and coordinate gradient descent methods, their acceleration strategies, and reported efficiency gains and limitations.

  • Overview: Optimization approximation computes gradients over a few instances or parameters, increasing optimization-error reduction per computation unit with fewer computations.Advanced mathematical techniques are needed when the approximation error must remain small.
  • Mini-batch Gradient Descent: Mini-batch gradient descent targets problems with few parameters but many instances, using gradients estimated from more instances to achieve faster local convergence with lower variance than stochastic gradient descent.The paper treats MGD as equivalent to mini-batch SGD in other papers.
  • Mini-batch Gradient Descent: Mini-batch methods improve efficiency through adaptive sampling, first-order gradient correction, higher-order gradient approximation, and learning-rate adjustment.These strategies respectively target batch information, search-direction variance, ill-conditioning, and convergence behavior.
  • Mini-batch Gradient Descent: 45 mins to 30 mins: doubling mini-batch sizes reduced ImageNet training time, while adaptive sampling used 30% of epochs for the same accuracy as uniform sampling.Other reported results include 6× to 35× faster eigensystem solving and more than 50% fewer computations with Adam.
  • Coordinate Gradient Descent: Coordinate gradient descent targets problems with few instances and high dimensionality by updating selected parameters while using all instances.It is applied in settings such as natural language processing and recommender systems.
  • Coordinate Gradient Descent: CGD can incur expensive exact subproblem solutions and redundant computations when each parameter is updated for the same number of iterations.Reported results nevertheless include 2× to 8× fewer training costs, 5× to 10× fewer epochs, and substantial savings from accelerated proximal methods.

3.3 Computation Parallelism

Computation parallelism reduces practical runtime by executing independent subtasks across multiple cores or machines. The survey covers multi-core and distributed systems, their abstractions, implementation strategies, and reported acceleration results.

  • For Multi-core Machines: Multi-core systems execute independent subtasks concurrently while sharing memory, using multiple processors such as CPUs and GPUs.Practical speedups remain below theoretical linear scaling because of overhead and scheduling demands.
  • For Multi-core Machines: Highly optimized libraries and frameworks provide accessible interfaces for parallelizing LML models across CPUs and GPUs.Examples include MKL, CUDA, TensorFlow, and PyTorch.
  • For Multi-core Machines: When memory is insufficient, partitioning models or data makes efficient I/O access and storage utilization essential to parallel execution.GraphChi partitions a large graph into intervals for processing.
  • For Multi-core Machines: FPSG nearly achieved 7× matrix-factorization speedup on a 12-core CPU, while Theano was 5× faster for CNN training and 6× faster for DBN optimization on GPUs.Other systems trained large models with limited memory through scheduled I/O, including vDNN using a 12GB GPU for a model requiring 67GB.
  • For Multi-machine Clusters: Distributed systems add cluster-level and within-node parallelism but face heterogeneous-machine management and cross-node communication costs.These challenges can reduce resource utilization.
  • For Multi-machine Clusters: MapReduce partitions computations and data across machines, while graph-parallel systems exploit sparse adjacency to reduce communication.MapReduce uses Map and Reduce subtasks; graph-parallel systems run vertex programs that interact with neighboring vertices.
  • For Multi-machine Clusters: Parameter servers provide distributed shared memory for model parameters, whereas ring-allreduce communicates updates across workers without a central parameter store.The survey also describes MapReduce, graph-parallel, parameter-server, and ring-allreduce topologies as representative distributed abstractions.
  • For Multi-machine Clusters: Distributed implementations report substantial gains, including PowerLyra’s 1.4×–2× speedup over PowerGraph and Horovod halving naive distributed training time.Petuum also outperformed Spark and GraphLab for matrix factorization.

3.4 Hybrid Collaboration

Hybrid collaboration combines model simplification, optimization approximation, and computation parallelism to obtain synergistic efficiency gains. The survey emphasizes gradient compression and delayed or decentralized optimization as representative strategies.

  • Motivation: LML strategies can be jointly applied, and deep learning combines model simplification, mini-batch optimization, and GPU parallelism.The survey presents these combined strategies as contributors to deep learning’s development.
  • Hybrid Strategies: Hybrid methods improve collaboration through gradient compression and gradient delay.These strategies target communication and synchronization overhead in distributed optimization.
  • Gradient Compression: Gradient compression communicates fewer values across machines; 1-bit MGD quantizes gradients to one bit and feeds back quantization error.QSGD instead uses randomized rounding to a discrete set while preserving the expected gradient.
  • Gradient Delay: Gradient-delay methods reduce locking, idling, or communication overhead through stale synchronization, local optimization, tree-allreduce, or elastic coupling.Examples include SSP, CoCoA, Hydra, EASGD, and tree-allreduce.
  • Experimental Discussion: Using 4-bit QSGD on 16-GPU AlexNet produced more than 4× communication speedup and 2.5× overall-cost speedup at the same accuracy.SketchML achieved more than 4× improvement for linear models.

4 DISCUSSIONS

The survey argues that existing LML methods provide a solid foundation for big data analysis. It then frames extension directions and open issues as the next focus.

  • Discussions: Existing LML methods have established a solid foundation for big data analysis.The paper next outlines promising extensions and important open issues.

4.1 Extension Directions

The survey proposes extending LML through better use of instance distributions, broader optimization settings, flexible hardware abstractions, and modularized open-source software. It identifies nonconvex optimization and heterogeneous hardware as important boundaries for current approaches.

  • For Model Simplification: Model simplification can further exploit instance distributions and structures, including low-dimensional manifolds and graph-label relationships.These assumptions motivate scalable predictive models based on low-rank and graph-based methods.
  • For Optimization Approximation: Optimization approximation methods often emphasize error reduction per computation but predominantly address convex problems.The survey proposes randomized operations, curriculum-like instance ordering, and mathematically motivated solutions for broader scenarios.
  • For Optimization Approximation: Nonconvex optimization can reach poor local minima and unstable real-world performance, motivating methods that escape or bypass such minima.Suggested directions include randomized initialization, gradient noise, and progressively harder training instances.
  • For Computation Parallelism: Allreduce assumes comparable memory and computational ability across nodes, so heterogeneous distributed systems require more flexible hardware abstractions.Otherwise, resource utilization is limited by the weakest node.
  • For Computation Parallelism: Modularized open-source learning frameworks are proposed because developing general-purpose parallel systems is difficult and shared software can benefit broader communities.The survey relates this direction to normalized, architecture-like framework design.

4.2 Open Issues

The paper identifies open issues in LML involving tighter complexity estimates, scalable data construction, broader hardware specialization, and privacy-aware distributed learning. It also highlights quantum computing as requiring redesigned machine learning methods.

  • Bounds of computational complexities: Tighter complexity bounds should reflect real-world data distributions and specific optimization algorithms rather than only general guarantees.The paper suggests that heuristic arguments from statistical physics may assist this refinement.
  • Other related complexities: LML complexity analysis should also consider over-parameterized networks, adversarial training, communication, and circuit-gate counts.These measures can reveal practical computational limits beyond current sample-complexity estimates.
  • Large-scale datasets: Large-scale instance-level datasets require scalable supervised or unsupervised generation, easier annotation, and augmentation for insufficient or imbalanced data.The paper discusses scalable active learning for annotation and transformations ranging from image flipping to generative adversarial learning.
  • Moderate specialization of hardware: Future hardware should combine specialized performance and energy efficiency with compatibility across a broader range of machine learning methods.The paper notes that communication can be more expensive than computation and that many existing accelerators target narrow method types.
  • Emerging computational and privacy settings: Quantum computing and privacy-preserving distributed learning require adapted methods, including redesign for quantum programming models and secure aggregation for federated learning.Federated learning brings codes to edge devices while updating a global model with secure aggregation.

5 CONCLUSIONS

LML has supported large-scale data analysis, but rapidly increasing data still requires improvement. The survey organizes existing methods by computational perspective, discusses limitations and extensions, and identifies open issues for future development.

  • 5 CONCLUSIONS: The survey concludes that LML methods should improve scalability through model simplification, optimization approximation, and computation parallelism while addressing limitations and open issues.These perspectives target computational complexity, computational efficiency, and computational capability, respectively.
Loading 2008.03911v1…