In data-parallel optimization of machine learning models, workers collaborate
to improve their estimates of the model: more accurate gradients allow them to
use larger learning rates and optimize faster. We consider the setting in which
all workers sample from the same dataset, and communicate over a sparse graph
(decentralized). In this setting, current theory fails to capture important
aspects of real-world behavior. First, the 'spectral gap' of the communication
graph is not predictive of its empirical performance in (deep) learning.
Second, current theory does not explain that collaboration enables larger
learning rates than training alone. In fact, it prescribes smaller learning
rates, which further decrease as graphs become larger, failing to explain
convergence in infinite graphs. This paper aims to paint an accurate picture of
sparsely-connected distributed optimization when workers share the same data
distribution. We quantify how the graph topology influences convergence in a
quadratic toy problem and provide theoretical results for general smooth and
(strongly) convex objectives. Our theory matches empirical observations in deep
learning, and accurately describes the relative merits of different graph
topologies.

研究了具有罕见连接的分布式机器学习优化问题，提出了理论解释，解释了合作可以获得比训练单独更大的学习率，并描述了不同图形拓扑的相对优点。

超越谱隙：拓扑在分散式学习中的作用

Beyond spectral gap: The role of the topology in decentralized learning

With the emergence of the big data age, the issue of how to obtain valuable
knowledge from a dataset efficiently and accurately has attracted increasingly
attention from both academia and industry. This paper presents a Parallel
Random Forest (PRF) algorithm for big data on the Apache Spark platform. The
PRF algorithm is optimized based on a hybrid approach combining data-parallel
and task-parallel optimization. From the perspective of data-parallel
optimization, a vertical data-partitioning method is performed to reduce the
data communication cost effectively, and a data-multiplexing method is
performed is performed to allow the training dataset to be reused and diminish
the volume of data. From the perspective of task-parallel optimization, a dual
parallel approach is carried out in the training process of RF, and a task
Directed Acyclic Graph (DAG) is created according to the parallel training
process of PRF and the dependence of the Resilient Distributed Datasets (RDD)
objects. Then, different task schedulers are invoked for the tasks in the DAG.
Moreover, to improve the algorithm's accuracy for large, high-dimensional, and
noisy data, we perform a dimension-reduction approach in the training process
and a weighted voting approach in the prediction process prior to
parallelization. Extensive experimental results indicate the superiority and
notable advantages of the PRF algorithm over the relevant algorithms
implemented by Spark MLlib and other studies in terms of the classification
accuracy, performance, and scalability.

本文介绍了在 Apache Spark 平台上针对大数据的并行随机森林（PRF）算法，其使用数据并行和任务并行优化的混合方法进行优化，包括垂直数据分区、数据多路复用、维度约减、加权投票等技术，实验结果显示该算法在分类准确性、性能、可扩展性等方面具有卓越的优势。