IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v34y2022i5p2384-2388.html
   My bibliography  Save this article

Finite Difference Gradient Approximation: To Randomize or Not?

Author

Listed:
  • Katya Scheinberg

    (School of Operations Research and Information Engineering, Cornell University, Ithaca, New York 14853)

Abstract

We discuss two classes of methods of approximating gradients of noisy black box functions—the classical finite difference method and recently popular randomized finite difference methods. Despite of the popularity of the latter, we argue that it is unclear whether the randomized schemes have an advantage over the traditional methods when employed inside an optimization method. We point to theoretical and practical evidence that show that the opposite is true at least in a general optimization setting. We then pose the question of whether a particular setting exists when the advantage of the new method may be clearly shown, at least numerically. The larger underlying challenge is a development of black box optimization methods that scale well with the problem dimension.

Suggested Citation

  • Katya Scheinberg, 2022. "Finite Difference Gradient Approximation: To Randomize or Not?," INFORMS Journal on Computing, INFORMS, vol. 34(5), pages 2384-2388, September.
    • Handle: RePEc:inm:orijoc:v:34:y:2022:i:5:p:2384-2388
    DOI: 10.1287/ijoc.2022.1218
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/ijoc.2022.1218
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2022.1218?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Yurii NESTEROV & Vladimir SPOKOINY, 2017. "Random gradient-free minimization of convex functions," LIDAM Reprints CORE 2851, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Aleksandr Lobanov & Nail Bashirov & Alexander Gasnikov, 2024. "The “Black-Box” Optimization Problem: Zero-Order Accelerated Stochastic Method via Kernel Approximation," Journal of Optimization Theory and Applications, Springer, vol. 203(3), pages 2451-2486, December.
    2. Guo Liang & Guangwu Liu & Kun Zhang, 2025. "Enhanced Derivative-Free Optimization Using Adaptive Correlation-Induced Finite Difference Estimators," Papers 2502.20819, arXiv.org.
    3. Lam M. Nguyen & Katya Scheinberg & Trang H. Tran, 2025. "Stochastic ISTA/FISTA Adaptive Step Search Algorithms for Convex Composite Optimization," Journal of Optimization Theory and Applications, Springer, vol. 205(1), pages 1-37, April.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Ghadimi, Saeed & Powell, Warren B., 2024. "Stochastic search for a parametric cost function approximation: Energy storage with rolling forecasts," European Journal of Operational Research, Elsevier, vol. 312(2), pages 641-652.
    2. V. Kungurtsev & F. Rinaldi, 2021. "A zeroth order method for stochastic weakly convex optimization," Computational Optimization and Applications, Springer, vol. 80(3), pages 731-753, December.
    3. Hoang Tran & Qiang Du & Guannan Zhang, 2025. "Convergence analysis for a nonlocal gradient descent method via directional Gaussian smoothing," Computational Optimization and Applications, Springer, vol. 90(2), pages 481-513, March.
    4. Nikita Kornilov & Alexander Gasnikov & Pavel Dvurechensky & Darina Dvinskikh, 2023. "Gradient-free methods for non-smooth convex stochastic optimization with heavy-tailed noise on convex compact," Computational Management Science, Springer, vol. 20(1), pages 1-43, December.
    5. Jean-Jacques Forneron, 2023. "Noisy, Non-Smooth, Non-Convex Estimation of Moment Condition Models," Papers 2301.07196, arXiv.org, revised Feb 2023.
    6. David Kozak & Stephen Becker & Alireza Doostan & Luis Tenorio, 2021. "A stochastic subspace approach to gradient-free optimization in high dimensions," Computational Optimization and Applications, Springer, vol. 79(2), pages 339-368, June.
    7. Marco Rando & Cesare Molinari & Silvia Villa & Lorenzo Rosasco, 2024. "Stochastic zeroth order descent with structured directions," Computational Optimization and Applications, Springer, vol. 89(3), pages 691-727, December.
    8. Vyacheslav Kungurtsev & Francesco Rinaldi & Damiano Zeffiro, 2024. "Retraction-Based Direct Search Methods for Derivative Free Riemannian Optimization," Journal of Optimization Theory and Applications, Springer, vol. 203(2), pages 1710-1735, November.
    9. Aleksandr Lobanov & Andrew Veprikov & Georgiy Konin & Aleksandr Beznosikov & Alexander Gasnikov & Dmitry Kovalev, 2023. "Non-smooth setting of stochastic decentralized convex optimization problem over time-varying Graphs," Computational Management Science, Springer, vol. 20(1), pages 1-55, December.
    10. Stefan Wager & Kuang Xu, 2021. "Experimenting in Equilibrium," Management Science, INFORMS, vol. 67(11), pages 6694-6715, November.
    11. Marco Boresta & Tommaso Colombo & Alberto Santis & Stefano Lucidi, 2022. "A Mixed Finite Differences Scheme for Gradient Approximation," Journal of Optimization Theory and Applications, Springer, vol. 194(1), pages 1-24, July.
    12. Jun Xie & Chi Cao, 2017. "Non-Convex Economic Dispatch of a Virtual Power Plant via a Distributed Randomized Gradient-Free Algorithm," Energies, MDPI, vol. 10(7), pages 1-12, July.
    13. Michael R. Metel & Akiko Takeda, 2022. "Perturbed Iterate SGD for Lipschitz Continuous Loss Functions," Journal of Optimization Theory and Applications, Springer, vol. 195(2), pages 504-547, November.
    14. Zhongruo Wang & Krishnakumar Balasubramanian & Shiqian Ma & Meisam Razaviyayn, 2023. "Zeroth-order algorithms for nonconvex–strongly-concave minimax problems with improved complexities," Journal of Global Optimization, Springer, vol. 87(2), pages 709-740, November.
    15. Ryota Nozawa & Pierre-Louis Poirion & Akiko Takeda, 2025. "Zeroth-Order Random Subspace Algorithm for Non-smooth Convex Optimization," Journal of Optimization Theory and Applications, Springer, vol. 204(3), pages 1-31, March.
    16. Jingxu Xu & Zeyu Zheng, 2023. "Gradient-Based Simulation Optimization Algorithms via Multi-Resolution System Approximations," INFORMS Journal on Computing, INFORMS, vol. 35(3), pages 633-651, May.
    17. Rajeeva Laxman Karandikar & Mathukumalli Vidyasagar, 2024. "Convergence Rates for Stochastic Approximation: Biased Noise with Unbounded Variance, and Applications," Journal of Optimization Theory and Applications, Springer, vol. 203(3), pages 2412-2450, December.
    18. Ghaderi, Susan & Ahookhosh, Masoud & Arany, Adam & Skupin, Alexander & Patrinos, Panagiotis & Moreau, Yves, 2024. "Smoothing unadjusted Langevin algorithms for nonsmooth composite potential functions," Applied Mathematics and Computation, Elsevier, vol. 464(C).
    19. Geovani Nunes Grapiglia, 2023. "Quadratic regularization methods with finite-difference gradient approximations," Computational Optimization and Applications, Springer, vol. 85(3), pages 683-703, July.
    20. Flavia Chorobura & Ion Necoara, 2024. "Coordinate descent methods beyond smoothness and separability," Computational Optimization and Applications, Springer, vol. 88(1), pages 107-149, May.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:orijoc:v:34:y:2022:i:5:p:2384-2388. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.