English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Motivated, in particular, by the entropy-regularized optimal transportproblem, we consider convex optimization problems with linear equalityconstraints, where the dual objective has Lipschitz $p$-th order derivatives,and develop two approaches for solving such problems. The first approach isbased on the minimization of the norm of the gradient in the dual problem andthen the reconstruction of an approximate primal solution. Recently, Grapigliaand Nesterov in their work showed lower complexity bounds for the problem ofminimizing the gradient norm of the function with Lipschitz $p$-th orderderivatives. Still, the question of optimal or near-optimal methods remainedopen as the algorithms presented in the paper achieve suboptimal bounds only.We close this gap by proposing two near-optimal (up to logarithmic factors)methods with complexity bounds $\tilde{O}(\varepsilon^{-2(p+1)/(3p+1)})$ and$\tilde{O}(\varepsilon^{-2/(3p+1)})$ with respect to the initial objectiveresidual and the distance between the starting point and solution respectively.We then apply these results (having independent interest) to our primal-dualsetting. As the second approach, we propose a direct accelerated primal-dualtensor method for convex problems with linear equality constraints, where thedual objective has Lipschitz $p$-th order derivatives. For this algorithm, weprove $\tilde O (\varepsilon^{-1 / (p + 1)})$ complexity in terms of theduality gap and the residual in the constraints. We illustrate the practicalperformance of the proposed algorithms in experiments on logistic regression,entropy-regularized optimal transport problem, and the minimal mutualinformation problem.

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