Local SGD is a popular optimization method in distributed learning, often
outperforming other algorithms in practice, including mini-batch SGD. Despite
this success, theoretically proving the dominance of local SGD in settings with
reasonable data heterogeneity has been difficult, creating a significant gap
between theory and practice. In this paper, we provide new lower bounds for
local SGD under existing first-order data heterogeneity assumptions, showing
that these assumptions are insufficient to prove the effectiveness of local
update steps. Furthermore, under these same assumptions, we demonstrate the
min-max optimality of accelerated mini-batch SGD, which fully resolves our
understanding of distributed optimization for several problem classes. Our
results emphasize the need for better models of data heterogeneity to
understand the effectiveness of local SGD in practice. Towards this end, we
consider higher-order smoothness and heterogeneity assumptions, providing new
upper bounds that imply the dominance of local SGD over mini-batch SGD when
data heterogeneity is low.

本文利用现有的一阶数据异质性假设，为本地 SGD 提供了新的下界，显示了这些假设不足以证明本地更新步骤的有效性。此外，在相同的假设下，我们证明了加速小批量 SGD 的极小 - 极大优化性质，完全解决了几个问题类的分布式优化。我们的结果强调了需要更好的数据异质性模型，以了解本地 SGD 在实践中的有效性。为此，我们考虑了高阶平滑性和异质性假设，并提供了新的上界，暗示了当数据异质性较低时，本地 SGD 优于小批量 SGD。

基于间歇通信的分布异构学习中局部 SGD 的局限性与潜力

The Limits and Potentials of Local SGD for Distributed Heterogeneous  Learning with Intermittent Communication

While random forests are commonly used for regression problems, existing
methods often lack adaptability in complex situations or lose optimality under
simple, smooth scenarios. In this study, we introduce the adaptive split
balancing forest (ASBF), capable of learning tree representations from data
while simultaneously achieving minimax optimality under the Lipschitz class. To
exploit higher-order smoothness levels, we further propose a localized version
that attains the minimax rate under the H\"older class $\mathcal{H}^{q,\beta}$
for any $q\in\mathbb{N}$ and $\beta\in(0,1]$. Rather than relying on the
widely-used random feature selection, we consider a balanced modification to
existing approaches. Our results indicate that an over-reliance on auxiliary
randomness may compromise the approximation power of tree models, leading to
suboptimal results. Conversely, a less random, more balanced approach
demonstrates optimality. Additionally, we establish uniform upper bounds and
explore the application of random forests in average treatment effect
estimation problems. Through simulation studies and real-data applications, we
demonstrate the superior empirical performance of the proposed methods over
existing random forests.

本研究介绍了自适应分割平衡森林（ASBF）方法，能够在同时达到 Lipschitz 类的极小极值优化和 H"older 类的极小速率优化的条件下，从数据中学习树的表示。通过平衡修改现有方法，我们进一步提出了一种局部化版本来利用更高阶的平滑水平。实验结果表明，过度依赖辅助随机性可能会损害树模型的逼近能力，导致次优结果。相反，一种不那么随机、更加平衡的方法表现出最佳性。此外，我们还确定了均匀上界，并探讨了随机森林在平均处理效应估计问题中的应用。通过模拟研究和实际数据应用，我们展示了所提出方法相对于现有随机森林的卓越实证表现。