We describe a novel optimization method for finite sums (such as empirical
risk minimization problems) building on the recently introduced SAGA method.
Our method achieves an accelerated convergence rate on strongly convex smooth
problems. Our method has only one parameter (a step size), and is radically
simpler than other accelerated methods for finite sums. Additionally it can be
applied when the terms are non-smooth, yielding a method applicable in many
areas where operator splitting methods would traditionally be applied.

该研究提出了一种针对小批量优化问题的新优化方法 SAGA，通过引入一种步长参数，在强凸光滑问题上获得了加速收敛率，同时应用于分割算子方法难以解决的许多领域。

一种简单实用的有限和加速方法

A Simple Practical Accelerated Method for Finite Sums

A thesis submitted for the degree of Doctor of Philosophy of The Australian
National University.
In this work we introduce several new optimisation methods for problems in
machine learning. Our algorithms broadly fall into two categories: optimisation
of finite sums and of graph structured objectives. The finite sum problem is
simply the minimisation of objective functions that are naturally expressed as
a summation over a large number of terms, where each term has a similar or
identical weight. Such objectives most often appear in machine learning in the
empirical risk minimisation framework in the non-online learning setting. The
second category, that of graph structured objectives, consists of objectives
that result from applying maximum likelihood to Markov random field models.
Unlike the finite sum case, all the non-linearity is contained within a
partition function term, which does not readily decompose into a summation.
For the finite sum problem, we introduce the Finito and SAGA algorithms, as
well as variants of each.
For graph-structured problems, we take three complementary approaches. We
look at learning the parameters for a fixed structure, learning the structure
independently, and learning both simultaneously. Specifically, for the combined
approach, we introduce a new method for encouraging graph structures with the
"scale-free" property. For the structure learning problem, we establish
SHORTCUT, a O(n^{2.5}) expected time approximate structure learning method for
Gaussian graphical models. For problems where the structure is known but the
parameters unknown, we introduce an approximate maximum likelihood learning
algorithm that is capable of learning a useful subclass of Gaussian graphical
models.

介绍了优化机器学习问题的几种新方法，包括针对有限和图结构目标的优化方法，其中包括针对固定结构的参数学习、结构学习和同时学习等方法。

机器学习的新优化方法

New Optimisation Methods for Machine Learning

Recent advances in optimization theory have shown that smooth strongly convex
finite sums can be minimized faster than by treating them as a black box
"batch" problem. In this work we introduce a new method in this class with a
theoretical convergence rate four times faster than existing methods, for sums
with sufficiently many terms. This method is also amendable to a sampling
without replacement scheme that in practice gives further speed-ups. We give
empirical results showing state of the art performance.

本文通过优化理论，针对平滑且强凸的有限和问题，提出一种新的求解方法，其理论收敛速度是现有方法的 4 倍，同时还可以实现不重复的抽样，提高计算速度，并通过实证研究已达到了最优表现。