Accelerated Randomized Mirror Descent Algorithms for Composite Non-strongly Convex Optimization

Le Thi Khanh Hien (), Cuong V. Nguyen (), Huan Xu (), Canyi Lu () and Jiashi Feng ()
Additional contact information
Le Thi Khanh Hien: National University of Singapore
Cuong V. Nguyen: University of Cambridge
Huan Xu: Georgia Institute of Technology
Canyi Lu: Carnegie Mellon University
Jiashi Feng: National University of Singapore

Journal of Optimization Theory and Applications, 2019, vol. 181, issue 2, No 10, 566 pages

Abstract: Abstract We consider the problem of minimizing the sum of an average function of a large number of smooth convex components and a general, possibly non-differentiable, convex function. Although many methods have been proposed to solve this problem with the assumption that the sum is strongly convex, few methods support the non-strongly convex case. Adding a small quadratic regularization is a common devise used to tackle non-strongly convex problems; however, it may cause loss of sparsity of solutions or weaken the performance of the algorithms. Avoiding this devise, we propose an accelerated randomized mirror descent method for solving this problem without the strongly convex assumption. Our method extends the deterministic accelerated proximal gradient methods of Paul Tseng and can be applied, even when proximal points are computed inexactly. We also propose a scheme for solving the problem, when the component functions are non-smooth.

Keywords: Acceleration techniques; Mirror descent method; Inexact proximal point; Composite optimization; 65K05; 90C06; 90C30 (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10957-018-01469-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:181:y:2019:i:2:d:10.1007_s10957-018-01469-5

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-018-01469-5

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().