On the computational efficiency of catalyst accelerated coordinate descent

DOI10.1007/978-3-030-77876-7_12MaRDI QIDQ2117631zbMATH OpenOpenAlexFDO

Authors Dmitry Pasechnyuk, Vladislav Matyukhin

Publication date 22 March 2022

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)

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.

Recommendations

• Accelerated proximal envelopes: application to componentwise methods
• Efficiency of the accelerated coordinate descent method on structured optimization problems
• Catalyst acceleration for first-order convex optimization: from theory to practice
• Efficiency of coordinate descent methods on huge-scale optimization problems
• Optimization in high dimensions via accelerated, parallel, and proximal coordinate descent

Cites work

• scientific article; zbMATH DE number 1095138 (Why is no real title available?)
• An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods
• Catalyst acceleration for first-order convex optimization: from theory to practice
• Contracting proximal methods for smooth convex optimization
• Convex optimization: algorithms and complexity
• Efficiency of coordinate descent methods on huge-scale optimization problems
• Efficiency of the accelerated coordinate descent method on structured optimization problems
• Efficient numerical methods for entropy-linear programming problems
• Lectures on convex optimization
• Monotone Operators and the Proximal Point Algorithm
• Smooth minimization of non-smooth functions

Cited in

(1)

• Accelerated proximal envelopes: application to componentwise methods

Describes a project that uses

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)