Trust-region (TR) and adaptive regularization using cubics (ARC) have proven
to have some very appealing theoretical properties for non-convex optimization
by concurrently computing function value, gradient, and Hessian matrix to
obtain the next search direction and the adjusted parameters. Although
stochastic approximations help largely reduce the computational cost, it is
challenging to theoretically guarantee the convergence rate. In this paper, we
explore a family of stochastic TR and ARC methods that can simultaneously
provide inexact computations of the Hessian matrix, gradient, and function
values. Our algorithms require much fewer propagations overhead per iteration
than TR and ARC. We prove that the iteration complexity to achieve
$\epsilon$-approximate second-order optimality is of the same order as the
exact computations demonstrated in previous studies. Additionally, the mild
conditions on inexactness can be met by leveraging a random sampling technology
in the finite-sum minimization problem. Numerical experiments with a non-convex
problem support these findings and demonstrate that, with the same or a similar
number of iterations, our algorithms require less computational overhead per
iteration than current second-order methods.

通过使用随机 TR 和 ARC 方法，我们可以在同时提供 Hessian 矩阵、梯度和函数值的不精确计算的基础上，减少每次迭代的传播开销，从而获得与之前研究中的准确计算同级别的迭代复杂度以实现近似二阶最优性，并通过有限和最小化问题中的随机采样技术满足不精确性的温和条件。数值实验支持这些发现，并表明我们的算法在进行相同或相似次数的迭代时，每次迭代所需的计算开销较当前的二阶方法更少。

非凸问题的近似 Hessian 矩阵、梯度和函数随机优化

Stochastic Optimization for Non-convex Problem with Inexact Hessian  Matrix, Gradient, and Function

Stein Variational Gradient Descent (SVGD) is a popular variational inference
algorithm which simulates an interacting particle system to approximately
sample from a target distribution, with impressive empirical performance across
various domains. Theoretically, its population (i.e, infinite-particle) limit
dynamics is well studied but the behavior of SVGD in the finite-particle regime
is much less understood. In this work, we design two computationally efficient
variants of SVGD, namely VP-SVGD (which is conceptually elegant) and GB-SVGD
(which is empirically effective), with provably fast finite-particle
convergence rates. We introduce the notion of \emph{virtual particles} and
develop novel stochastic approximations of population-limit SVGD dynamics in
the space of probability measures, which are exactly implementable using a
finite number of particles. Our algorithms can be viewed as specific
random-batch approximations of SVGD, which are computationally more efficient
than ordinary SVGD. We show that the $n$ particles output by VP-SVGD and
GB-SVGD, run for $T$ steps with batch-size $K$, are at-least as good as i.i.d
samples from a distribution whose Kernel Stein Discrepancy to the target is at
most $O\left(\tfrac{d^{1/3}}{(KT)^{1/6}}\right)$ under standard assumptions.
Our results also hold under a mild growth condition on the potential function,
which is much weaker than the isoperimetric (e.g. Poincare Inequality) or
information-transport conditions (e.g. Talagrand's Inequality $\mathsf{T}_1$)
generally considered in prior works. As a corollary, we consider the
convergence of the empirical measure (of the particles output by VP-SVGD and
GB-SVGD) to the target distribution and demonstrate a \emph{double exponential
improvement} over the best known finite-particle analysis of SVGD.

本文提出了两种计算有效（VP-SVGD 和 GB-SVGD）的 Stein 变分梯度下降算法，它们是特定的随机批处理逼近 SVG，具有证明的快速有限粒子收敛率。

基于虚拟粒子随机逼近的可证明快速 SVGD 有限粒子变体

Provably Fast Finite Particle Variants of SVGD via Virtual Particle  Stochastic Approximation

In this paper, we propose an iterative scheme for distributed
Byzantineresilient estimation of a gradient associated with a black-box model.
Our algorithm is based on simultaneous perturbation, secure state estimation
and two-timescale stochastic approximations. We also show the performance of
our algorithm through numerical experiments.

本文提出分布式迭代方案，用于对与黑箱模型相关的梯度进行拜占庭容错评估，基于同时扰动、安全状态评估和双时间尺度随机逼近，同时通过数值实验展示了算法性能。

在线多智能体去中心化拜占庭容错梯度估计

Online Multi-Agent Decentralized Byzantine-robust Gradient Estimation

Sparse coding--that is, modelling data vectors as sparse linear combinations
of basis elements--is widely used in machine learning, neuroscience, signal
processing, and statistics. This paper focuses on the large-scale matrix
factorization problem that consists of learning the basis set, adapting it to
specific data. Variations of this problem include dictionary learning in signal
processing, non-negative matrix factorization and sparse principal component
analysis. In this paper, we propose to address these tasks with a new online
optimization algorithm, based on stochastic approximations, which scales up
gracefully to large datasets with millions of training samples, and extends
naturally to various matrix factorization formulations, making it suitable for
a wide range of learning problems. A proof of convergence is presented, along
with experiments with natural images and genomic data demonstrating that it
leads to state-of-the-art performance in terms of speed and optimization for
both small and large datasets.

本文主要介绍了一种新的基于随机逼近的在线优化算法，用于解决以学习基础集合和将其适应特定数据为主的大规模矩阵分解问题，其在各种矩阵分解方面有良好的表现，并在自然图像和基因数据上进行的实验中具有速度和优化方面的先进性能。