Randomized Smoothing Variance Reduction Method for Large-Scale Non-smooth Convex Optimization

Wenjie Huang () and Xun Zhang ()
Additional contact information
Wenjie Huang: The Chinese University of Hong Kong
Xun Zhang: National University of Singapore

SN Operations Research Forum, 2021, vol. 2, issue 2, 1-28

Abstract: Abstract We consider a new method for minimizing the average of a large number of non-smooth and convex functions. Such a problem often arises in typical machine learning problems, but is computationally challenging. We apply an implementable randomized smoothing method and propose a multistage scheme to progressively reduce the variance of the gradient estimator of the smoothed functions. Our algorithm achieves a linear convergence rate. Both its time complexity and gradient complexity are superior to the current standard algorithms for non-smooth minimization as well as subgradient-based algorithms. Besides, our algorithm works well without the error-bound condition on the minimizing sequence as well as the commonly imposed (but strong) smoothness and strongly convexity condition. We show that our algorithm has wide applications in optimization and machine learning problems. As an illustrative example, we demonstrate experimentally that our algorithm performs well on large-scale ranking problems and risk-aware portfolio optimization problems.

Keywords: Non-smooth optimization; Randomized smoothing; Variance reduction; Stochastic gradient descent; Linear convergence (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s43069-021-00059-y 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:snopef:v:2:y:2021:i:2:d:10.1007_s43069-021-00059-y

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/43069

DOI: 10.1007/s43069-021-00059-y

Access Statistics for this article

SN Operations Research Forum is currently edited by Marco Lübbecke

More articles in SN Operations Research Forum from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().