Gradient-free methods for non-smooth convex stochastic optimization with heavy-tailed noise on convex compact

Nikita Kornilov (), Alexander Gasnikov (), Pavel Dvurechensky () and Darina Dvinskikh ()
Additional contact information
Nikita Kornilov: Moscow Institute of Physics and Technology
Alexander Gasnikov: Moscow Institute of Physics and Technology
Pavel Dvurechensky: Weierstrass Institute for Applied Analysis and Stochastics
Darina Dvinskikh: HSE University

Computational Management Science, 2023, vol. 20, issue 1, No 37, 43 pages

Abstract: Abstract We present two easy-to-implement gradient-free/zeroth-order methods to optimize a stochastic non-smooth function accessible only via a black-box. The methods are built upon efficient first-order methods in the heavy-tailed case, i.e., when the gradient noise has infinite variance but bounded $$(1+\kappa)$$ ( 1 + κ ) -th moment for some $$\kappa \in(0,1]$$ κ ∈ ( 0 , 1 ] . The first algorithm is based on the stochastic mirror descent with a particular class of uniformly convex mirror maps which is robust to heavy-tailed noise. The second algorithm is based on the stochastic mirror descent and gradient clipping technique. Additionally, for the objective functions satisfying the r-growth condition, faster algorithms are proposed based on these methods and the restart technique.

Keywords: Zeroth-order optimization; Derivative-free optimization; Stochastic optimization; Non-smooth problems; Heavy tails; Gradient clipping; Stochastic mirror descent (search for similar items in EconPapers)
Date: 2023
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/s10287-023-00470-2 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:comgts:v:20:y:2023:i:1:d:10.1007_s10287-023-00470-2

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

DOI: 10.1007/s10287-023-00470-2

Access Statistics for this article

Computational Management Science is currently edited by Ruediger Schultz

More articles in Computational Management Science from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().