This paper considers a type of incremental aggregated gradient (IAG) method
for large-scale distributed optimization. The IAG method is well suited for the
parameter server architecture as the latter can easily aggregate potentially
staled gradients contributed by workers. Although the convergence of IAG in the
case of deterministic gradient is well known, there are only a few results for
the case of its stochastic variant based on streaming data. Considering
strongly convex optimization, this paper shows that the streaming IAG method
achieves linear speedup when the workers are updating frequently enough, even
if the data sample distribution across workers are heterogeneous. We show that
the expected squared distance to optimal solution decays at O((1+T)/(nt)),
where $n$ is the number of workers, t is the iteration number, and T/n is the
update frequency of workers. Our analysis involves careful treatments of the
conditional expectations with staled gradients and a recursive system with both
delayed and noise terms, which are new to the analysis of IAG-type algorithms.
Numerical results are presented to verify our findings.

本论文研究了一种用于大规模分布式优化的增量聚合梯度（IAG）方法，证明了基于流式数据的随机变体的 IAG 方法在强凸优化情况下实现了线性加速，并且即使在数据样本在工作者之间分布不均匀的情况下，该方法仍可以保证达到最优解的期望平方距离以 O ((1+T)/(nt)) 的速率衰减。

流式数据上增量聚合梯度方法的线性加速

Linear Speedup of Incremental Aggregated Gradient Methods on Streaming  Data

We consider the problem of solving robust Markov decision process (MDP),
which involves a set of discounted, finite state, finite action space MDPs with
uncertain transition kernels. The goal of planning is to find a robust policy
that optimizes the worst-case values against the transition uncertainties, and
thus encompasses the standard MDP planning as a special case. For
$(\mathbf{s},\mathbf{a})$-rectangular uncertainty sets, we develop a
policy-based first-order method, namely the robust policy mirror descent
(RPMD), and establish an $\mathcal{O}(\log(1/\epsilon))$ and
$\mathcal{O}(1/\epsilon)$ iteration complexity for finding an
$\epsilon$-optimal policy, with two increasing-stepsize schemes. The prior
convergence of RPMD is applicable to any Bregman divergence, provided the
policy space has bounded radius measured by the divergence when centering at
the initial policy. Moreover, when the Bregman divergence corresponds to the
squared euclidean distance, we establish an $\mathcal{O}(\max \{1/\epsilon,
1/(\eta \epsilon^2)\})$ complexity of RPMD with any constant stepsize $\eta$.
For a general class of Bregman divergences, a similar complexity is also
established for RPMD with constant stepsizes, provided the uncertainty set
satisfies the relative strong convexity. We further develop a stochastic
variant, named SRPMD, when the first-order information is only available
through online interactions with the nominal environment. For general Bregman
divergences, we establish an $\mathcal{O}(1/\epsilon^2)$ and
$\mathcal{O}(1/\epsilon^3)$ sample complexity with two increasing-stepsize
schemes. For the euclidean Bregman divergence, we establish an
$\mathcal{O}(1/\epsilon^3)$ sample complexity with constant stepsizes. To the
best of our knowledge, all the aforementioned results appear to be new for
policy-based first-order methods applied to the robust MDP problem.

研究如何解决具有不确定转移内核的折现，有限状态，有限行动空间 MDP 的强鲁棒性问题，旨在寻找一个抵抗传递不确定性的最佳策略。与标准 MDP 规划相比，本文提出了一个名为 RPMD 的策略型一阶方法，并对于两种递增步长的情形，建立了寻找 ε- 最优策略的 O (log (1/ε)) 和 O (1/ε) 迭代复杂度。本文还提出了一种名为 SRPMD 的随机变量。

鲁棒马尔科夫决策过程的一阶策略优化

First-order Policy Optimization for Robust Markov Decision Process

We present and analyze a momentum-based gradient method for training linear
classifiers with an exponentially-tailed loss (e.g., the exponential or
logistic loss), which maximizes the classification margin on separable data at
a rate of $\widetilde{\mathcal{O}}(1/t^2)$. This contrasts with a rate of
$\mathcal{O}(1/\log(t))$ for standard gradient descent, and $\mathcal{O}(1/t)$
for normalized gradient descent. This momentum-based method is derived via the
convex dual of the maximum-margin problem, and specifically by applying
Nesterov acceleration to this dual, which manages to result in a simple and
intuitive method in the primal. This dual view can also be used to derive a
stochastic variant, which performs adaptive non-uniform sampling via the dual
variables.

介绍了一种基于动量的梯度方法，使用最大化分类间隔相结合的凸对偶来训练线性分类器，表现出优异的性能

双重加速快速实现边缘最大化

Fast Margin Maximization via Dual Acceleration

This paper proposes a stochastic variant of a classic algorithm---the
cubic-regularized Newton method [Nesterov and Polyak 2006]. The proposed
algorithm efficiently escapes saddle points and finds approximate local minima
for general smooth, nonconvex functions in only
$\mathcal{\tilde{O}}(\epsilon^{-3.5})$ stochastic gradient and stochastic
Hessian-vector product evaluations. The latter can be computed as efficiently
as stochastic gradients. This improves upon the
$\mathcal{\tilde{O}}(\epsilon^{-4})$ rate of stochastic gradient descent. Our
rate matches the best-known result for finding local minima without requiring
any delicate acceleration or variance-reduction techniques.

本文提出了一个随机变体的经典算法 -- 立方正则化牛顿方法。该算法可以有效地避免鞍点问题，并在仅需要 $\mathcal {\tilde {O}}(\epsilon^{-3.5})$ 个随机梯度和随机海森向量乘积评估的情况下，为一般光滑的非凸函数找到近似的局部极小值。