Efficient Discrete Optimal Transport Algorithm by Accelerated Gradient Descent.

Area of Science:

• Computational mathematics
• Machine learning
• Deep learning

Background:

• Optimal transport (OT) is crucial in machine learning and deep learning but computationally challenging for large-scale problems.
• Existing methods like the Sinkhorn algorithm offer a trade-off between efficiency and accuracy using entropy regularization.

Purpose of the Study:

• To develop a novel algorithm that enhances both the efficiency and accuracy of discrete optimal transport computations.
• To address the limitations of current methods in handling large-scale OT problems.

Main Methods:

• The proposed algorithm utilizes Nesterov's smoothing technique to approximate the non-smooth c-transform of the Kantorovich potential with the Log-Sum-Exp function.
• This smoothing transforms the non-smooth Kantorovich dual functional into a smooth one.
• The smooth functional is then optimized using the fast iterative shrinkage thresholding algorithm (FISTA), a fast proximal gradient method.

Main Results:

• Theoretically, the new method exhibits a lower computational complexity compared to the Sinkhorn algorithm.
• Experimentally, the proposed algorithm demonstrates faster convergence and superior accuracy than the Sinkhorn algorithm under identical parameter settings.
• The method effectively improves the efficiency and accuracy of computing discrete optimal transport.

Conclusions:

• The novel algorithm based on Nesterov's smoothing and FISTA offers a significant improvement over existing methods for large-scale optimal transport.
• This approach provides a better balance between computational efficiency and accuracy in optimal transport calculations for machine learning applications.