A Weighted Mirror Descent Algorithm for Nonsmooth Convex Optimization Problem

Luong DVN, Parpas P, Rueckert D, Rustem B (2016)

Publication Type: Journal article

Publication year: 2016

Journal

Journal of Optimization Theory and Applications Springer Verlag (Germany)

Book Volume: 170

Pages Range: 900-915

Journal Issue: 3

DOI: 10.1007/s10957-016-0963-5

Abstract

Large-scale nonsmooth convex optimization is a common problem for a range of computational areas including machine learning and computer vision. Problems in these areas contain special domain structures and characteristics. Special treatment of such problem domains, exploiting their structures, can significantly reduce the computational burden. In this paper, we consider a Mirror Descent method with a special choice of distance function for solving nonsmooth optimization problems over a Cartesian product of convex sets. We propose to use a nonlinear weighted distance in the projection step. The convergence analysis identifies optimal weighting parameters that, eventually, lead to the optimally weighted step-size strategy for every projection on a corresponding convex set. We show that the optimality bound of the Mirror Descent algorithm using the weighted distance is either an improvement to, or in the worst case as good as, the optimality bound of the Mirror Descent using unweighted distances. We demonstrate the efficiency of the algorithm by solving the Markov Random Fields optimization problem. In order to exploit the domain of the problem, we use a weighted log-entropy distance and a weighted Euclidean distance. Promising experimental results demonstrate the effectiveness of the proposed method.

Involved external institutions

Imperial College London / The Imperial College of Science, Technology and Medicine GB United Kingdom (GB)

How to cite

APA:

Luong, D.V.N., Parpas, P., Rueckert, D., & Rustem, B. (2016). A Weighted Mirror Descent Algorithm for Nonsmooth Convex Optimization Problem. Journal of Optimization Theory and Applications, 170(3), 900-915. https://doi.org/10.1007/s10957-016-0963-5

MLA:

Luong, Duy V. N., et al. "A Weighted Mirror Descent Algorithm for Nonsmooth Convex Optimization Problem." Journal of Optimization Theory and Applications 170.3 (2016): 900-915.

BibTeX: Download