Accelerated Proximal Envelopes: Application to the Coordinate Descent Method

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. In this paper, we propose a proximally accelerated coordinate descent method that ac...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2021-01
Main Authors: Pasechnyuk, Dmitry, Anikin, Anton, Matyukhin, Vladislav
Format: Article
Language:English
Subjects:
Complexity
Descent
Envelopes
Iterative methods
Optimization
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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. In this paper, we propose a proximally accelerated coordinate descent method that achieves the efficient algorithmic complexity of iteration and allows one to take advantage of the problem sparseness. An example of applying the proposed approach to optimizing a SoftMax-like function considered, for which the described method allowing weaken the dependence of the computational complexity on the dimension of the problem \(n\) in \(\mathcal{O}(\sqrt{n})\) times, and in practice demonstrates a faster convergence in comparison with standard methods.
ISSN:2331-8422