The “Black-Box” Optimization Problem: Zero-Order Accelerated Stochastic Method via Kernel Approximation

Aleksandr Lobanov (), Nail Bashirov () and Alexander Gasnikov ()
Additional contact information
Aleksandr Lobanov: 9 Institutskiy per
Nail Bashirov: 9 Institutskiy per
Alexander Gasnikov: 9 Institutskiy per

Journal of Optimization Theory and Applications, 2024, vol. 203, issue 3, No 14, 2486 pages

Abstract: Abstract In this paper, we study the standard formulation of an optimization problem when the computation of gradient is not available. Such a problem can be classified as a “black box” optimization problem, since the oracle returns only the value of the objective function at the requested point, possibly with some stochastic noise. Assuming convex, and higher-order of smoothness of the objective function, this paper provides a zero-order accelerated stochastic gradient descent (ZO-AccSGD) method for solving this problem, which exploits the higher-order of smoothness information via kernel approximation. As theoretical results, we show that the ZO-AccSGD algorithm proposed in this paper improves the convergence results of state-of-the-art (SOTA) algorithms, namely the estimate of iteration complexity. In addition, our theoretical analysis provides an estimate of the maximum allowable noise level at which the desired accuracy can be achieved. Validation of our theoretical results is demonstrated both on the model function and on functions of interest in the field of machine learning. We also provide a discussion in which we explain the results obtained and the superiority of the proposed algorithm over SOTA algorithms for solving the original problem.

Keywords: Black-box optimization; Gradient-free methods; Kernel approximation; Maximum noise level; 65K05; 90C15; 90C25 (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10957-024-02556-6 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:203:y:2024:i:3:d:10.1007_s10957-024-02556-6

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

DOI: 10.1007/s10957-024-02556-6

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 ().