We consider unconstrained randomized optimization of smooth convex objective
functions in the gradient-free setting. We analyze Random Pursuit (RP)
algorithms with fixed (F-RP) and variable metric (V-RP). The algorithms only
use zeroth-order information about the objective function and compute an
approximate solution by repeated optimization over randomly chosen
one-dimensional subspaces. The distribution of search directions is dictated by
the chosen metric.
Variable Metric RP uses novel variants of a randomized zeroth-order Hessian
approximation scheme recently introduced by Leventhal and Lewis (D. Leventhal
and A. S. Lewis., Optimization 60(3), 329--245, 2011). We here present (i) a
refined analysis of the expected single step progress of RP algorithms and
their global convergence on (strictly) convex functions and (ii) novel
convergence bounds for V-RP on strongly convex functions. We also quantify how
well the employed metric needs to match the local geometry of the function in
order for the RP algorithms to converge with the best possible rate.
Our theoretical results are accompanied by numerical experiments, comparing
V-RP with the derivative-free schemes CMA-ES, Implicit Filtering, Nelder-Mead,
NEWUOA, Pattern-Search and Nesterov's gradient-free algorithms.

研究在无梯度情况下，对光滑凸性目标函数进行无约束随机优化。Random Pursuit（RP）算法具有固定（F-RP）和可变度量（V-RP）两种。用于在随机选定的一维子空间上进行重复优化，并通过零阶信息计算近似解。对于严格凸函数，对 V-RP 的全局收敛性进行了分析，量化其所使用的度量需要多好才能实现最佳可能速率的情况，并通过数值实验进行了比较。

可变度量随机追踪

Variable Metric Random Pursuit

We propose a variable metric forward-backward splitting algorithm and prove
its convergence in real Hilbert spaces. We then use this framework to derive
primal-dual splitting algorithms for solving various classes of monotone
inclusions in duality. Some of these algorithms are new even when specialized
to the fixed metric case. Various applications are discussed.

我们提出了一种可变度量前向后向分裂算法，并在实数希尔伯特空间中证明了其收敛性。然后，我们使用这个框架导出原始 - 对偶分裂算法，以解决包含在对偶中的各种类的单调性问题。讨论了各种应用。