Optimal transport (OT) plays an essential role in various areas like machine
learning and deep learning. However, computing discrete optimal transport plan
for large scale problems with adequate accuracy and efficiency is still highly
challenging. Recently, methods based on the Sinkhorn algorithm add an entropy
regularizer to the prime problem and get a trade off between efficiency and
accuracy. In this paper, we propose a novel algorithm to further improve the
efficiency and accuracy based on Nesterov's smoothing technique. Basically, the
non-smooth c-transform of the Kantorovich potential is approximated by the
smooth Log-Sum-Exp function, which finally smooths the original non-smooth
Kantorovich dual functional (energy). The smooth Kantorovich functional can be
optimized by the fast proximal gradient algorithm (FISTA) efficiently.
Theoretically, the computational complexity of the proposed method is given by
$O(n^{\frac{5}{2}} \sqrt{\log n} /\epsilon)$, which is lower than that of the
Sinkhorn algorithm. Empirically, compared with the Sinkhorn algorithm, our
experimental results demonstrate that the proposed method achieves faster
convergence and better accuracy with the same parameter.

本研究提出了一种基于 Nesterov 的平滑技术的新算法，通过近似 Log-Sum-Exp 函数来平滑 Kantorovich 势的非平滑 c-transform，并将此平滑后的 Kantorovich 泛函应用于快速的 FISTA 算法以提高计算效率和精确度。实验结果表明，该方法相较于 Sinkhorn 算法在相同参数下具有更快的收敛速度和更高的准确性。

通过加速梯度下降实现高效最优传输算法

Efficient Optimal Transport Algorithm by Accelerated Gradient descent

Optimization algorithms for solving nonconvex inverse problem have attracted
significant interests recently. However, existing methods require the nonconvex
regularization to be smooth or simple to ensure convergence. In this paper, we
propose a novel gradient descent type algorithm, by leveraging the idea of
residual learning and Nesterov's smoothing technique, to solve inverse problems
consisting of general nonconvex and nonsmooth regularization with provable
convergence. Moreover, we develop a neural network architecture intimating this
algorithm to learn the nonlinear sparsity transformation adaptively from
training data, which also inherits the convergence to accommodate the general
nonconvex structure of this learned transformation. Numerical results
demonstrate that the proposed network outperforms the state-of-the-art methods
on a variety of different image reconstruction problems in terms of efficiency
and accuracy.

本文提出一种新的梯度下降类型算法来解决一般的非凸和非光滑规则化的反问题，并开发了一种神经网络架构来从训练数据中自适应地学习非线性稀疏转换，该算法可以适应非凸结构的拓扑变换。数值结果表明，所提出的神经网络在各种不同的图像重建问题上的准确性和效率方面优于最先进的方法。

一种新的可学习梯度下降型算法用于非凸非光滑反问题

A Novel Learnable Gradient Descent Type Algorithm for Non-convex  Non-smooth Inverse Problems

In this paper, we develop a novel {\bf ho}moto{\bf p}y {\bf s}moothing (HOPS)
algorithm for solving a family of non-smooth problems that is composed of a
non-smooth term with an explicit max-structure and a smooth term or a simple
non-smooth term whose proximal mapping is easy to compute. The best known
iteration complexity for solving such non-smooth optimization problems is
$O(1/\epsilon)$ without any assumption on the strong convexity. In this work,
we will show that the proposed HOPS achieved a lower iteration complexity of
$\widetilde O(1/\epsilon^{1-\theta})$\footnote{$\widetilde O()$ suppresses a
logarithmic factor.} with $\theta\in(0,1]$ capturing the local sharpness of the
objective function around the optimal solutions. To the best of our knowledge,
this is the lowest iteration complexity achieved so far for the considered
non-smooth optimization problems without strong convexity assumption. The HOPS
algorithm employs Nesterov's smoothing technique and Nesterov's accelerated
gradient method and runs in stages, which gradually decreases the smoothing
parameter in a stage-wise manner until it yields a sufficiently good
approximation of the original function. We show that HOPS enjoys a linear
convergence for many well-known non-smooth problems (e.g., empirical risk
minimization with a piece-wise linear loss function and $\ell_1$ norm
regularizer, finding a point in a polyhedron, cone programming, etc).
Experimental results verify the effectiveness of HOPS in comparison with
Nesterov's smoothing algorithm and the primal-dual style of first-order
methods.

本文提出一种新的 HOPS 算法来解决由非光滑项和平滑项组成的一类非光滑问题，证明该算法在没有强凸假设的情况下实现了比现有算法更低的迭代复杂度，并且在许多著名的非光滑问题中具有线性收敛性能。