On the computational efficiency of catalyst accelerated coordinate descent

DOI10.1007/978-3-030-77876-7_12zbMATH Open1487.90526arXiv2103.06688OpenAlexW3176586272MaRDI QIDQ2117631FDOQ2117631

Dmitry Pasechnyuk, Vladislav Matyukhin

Publication date: 22 March 2022

Abstract: This article is devoted to one particular case of using universal accelerated proximal envelopes to obtain computationally efficient accelerated versions of methods used to solve various optimization problem setups. We propose a proximally accelerated coordinate descent method that achieves the efficient algorithmic complexity of iteration and allows taking advantage of the data sparseness. It was considered an example of applying the proposed approach to optimizing a SoftMax-like function, for which the described method allowing weaken the dependence of the computational complexity on the dimension $n$ in $mathcalO(sqrtn)$ times and, in practice, demonstrates a faster convergence in comparison with standard methods. As an example of applying the proposed approach, it was shown a variant of obtaining on its basis some efficient methods for optimizing Markov Decision Processes (MDP) in a minimax formulation with a Nesterov smoothed target functional.

Full work available at URL: https://arxiv.org/abs/2103.06688

zbMATH Keywords

Markov decision processescatalystaccelerated coordinate descent methodproximal accelerated methodSoftMax

Mathematics Subject Classification ID

Convex programming (90C25) Markov and semi-Markov decision processes (90C40)

Cites Work

• Title not available (Why is that?)
• Smooth minimization of non-smooth functions
• An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods
• Monotone Operators and the Proximal Point Algorithm
• Efficiency of coordinate descent methods on huge-scale optimization problems
• Convex optimization: algorithms and complexity
• Efficient numerical methods for entropy-linear programming problems
• Lectures on convex optimization
• Catalyst Acceleration for First-order Convex Optimization: from Theory to Practice
• Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes
• Efficiency of the Accelerated Coordinate Descent Method on Structured Optimization Problems
• Contracting Proximal Methods for Smooth Convex Optimization

Uses Software

• SciPy
• logsumexp-softmax-tests

This page was built for publication: On the computational efficiency of catalyst accelerated coordinate descent

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2117631)