Near-optimal tensor methods for minimizing the gradient norm of convex functions and accelerated primal-dual tensor methods

Understand

Motivated, in particular, by the entropy-regularized optimal transport problem, we consider convex optimization problems with linear equality constraints, where the dual objective has Lipschitz $p$-th order derivatives, and develop two approaches for solving such problems.

• The first approach is based on the minimization of the norm of the gradient in the dual problem and then the reconstruction of an approximate primal solution.
• Recently, Grapiglia and Nesterov in their work showed lower complexity bounds for the problem of minimizing the gradient norm of the function with Lipschitz $p$-th order derivatives.
• Still, the question of optimal or near-optimal methods remained open as the algorithms presented in the paper achieve suboptimal bounds only.