The diffusion strategy for distributed learning from streaming data employs
local stochastic gradient updates along with exchange of iterates over
neighborhoods. In Part I [2] of this work we established that agents cluster
around a network centroid and proceeded to study the dynamics of this point. We
established expected descent in non-convex environments in the large-gradient
regime and introduced a short-term model to examine the dynamics over
finite-time horizons. Using this model, we establish in this work that the
diffusion strategy is able to escape from strict saddle-points in O(1/$\mu$)
iterations; it is also able to return approximately second-order stationary
points in a polynomial number of iterations. Relative to prior works on the
polynomial escape from saddle-points, most of which focus on centralized
perturbed or stochastic gradient descent, our approach requires less
restrictive conditions on the gradient noise process.

分布式学习算法中应用了扩散策略，能够在限制条件较少的情况下从严格的鞍点中逃脱并返回次二级稳定点.

非凸环境下的分布式学习 -- 第二部分：从鞍点中多项式逃脱

Distributed Learning in Non-Convex Environments -- Part II: Polynomial  Escape from Saddle-Points

Optimization of machine learning models is commonly performed through
stochastic gradient updates on randomly ordered training examples. This
practice means that sub-epochs comprise of independent random samples of the
training data that may not preserve informative structure present in the full
data. We hypothesize that the training can be more effective with {\em
self-similar} arrangements that potentially allow each epoch to provide
benefits of multiple ones. We study this for "matrix factorization" -- the
common task of learning metric embeddings of entities such as queries, videos,
or words from example pairwise associations. We construct arrangements that
preserve the weighted Jaccard similarities of rows and columns and
experimentally observe training acceleration of 3\%-37\% on synthetic and
recommendation datasets. Principled arrangements of training examples emerge as
a novel and potentially powerful enhancement to SGD that merits further
exploration.

本研究证明，对机器学习模型进行随机梯度更新常常使子时期包括独立随机样本，可能无法保留完整数据中存在的信息结构，建立自相似的训练样本可以更有效地训练矩阵分解等任务，并且通过实验证明加速了训练。