Fetching the paper…
Reading the bibliography…
In this paper, we study the black box optimization problem under the Polyak--Lojasiewicz (PL) condition, assuming that the objective function is not just smooth, but has higher smoothness.
‘‘An automatic method for finding the greatest or least value of a function’’
HoHo Rosenbrock · 1960
Earlier work this paper cites.
‘‘Gradient methods for the minimisation of functionals’’
Boris Polyak · 1963
Earlier work this paper cites.
‘‘Une propriété topologique des sous-ensembles analytiques réels’’
Stanislaw Lojasiewicz · 1963
Earlier work this paper cites.
‘‘Optimal order of accuracy of search algorithms in stochastic optimization’’
Boris Polyak and Aleksandr Tsybakov · 1990
Earlier work this paper cites.
‘‘Stochastic approximation’’
Madanlal Wasan · 2004
Earlier work this paper cites.
‘‘Solving large scale linear prediction problems using stochastic gradient descent algorithms’’
Tong Zhang · 2004
Earlier work this paper cites.
‘‘Cubic regularization of Newton method and its global performance’’
Yurii Nesterov and Boris Polyak · 2006
Earlier work this paper cites.
‘‘Introduction to derivative-free optimization’’
Andrew Conn, Katya Scheinberg and Luis Vicente · 2009
Earlier work this paper cites.
‘‘Optimal Algorithms for Online Convex Optimization with Multi-Point Bandit Feedback.’’
Alekh Agarwal, Ofer Dekel and Lin Xiao · 2010
Earlier work this paper cites.
‘‘Large-scale machine learning with stochastic gradient descent’’
L\’eon Bottou · 2010
Earlier work this paper cites.
‘‘An optimal method for stochastic composite optimization’’
Guanghui Lan · 2012
Earlier work this paper cites.
‘‘Stochastic first-and zeroth-order methods for nonconvex stochastic programming’’
Saeed Ghadimi and Guanghui Lan · 2013
Earlier work this paper cites.
‘‘Predictive entropy search for efficient global optimization of black-box functions’’
Jos\’e Hern\’andez-Lobato, Matthew Hoffman and Zoubin Ghahramani · 2014
Earlier work this paper cites.
‘‘Convex optimization: Algorithms and complexity’’
S\’ebastien Bubeck · 2015
Earlier work this paper cites.
‘‘Optimal rates for zero-order convex optimization: The power of two function evaluations’’
John Duchi, Michael Jordan, Martin Wainwright and Andre Wibisono · 2015
Earlier work this paper cites.
‘‘Modern efficient numerical approaches to regularized regression problems in application to traffic demands matrix calculation from link loads’’
A Anikin et al · 2015
Earlier work this paper cites.
‘‘Highly-smooth zero-th order online optimization’’
Francis Bach and Vianney Perchet · 2016
Earlier work this paper cites.
‘‘Learning supervised pagerank with gradient-based and gradient-free optimization methods’’
Lev Bogolubsky et al · 2016
Earlier work this paper cites.
‘‘Linear convergence of gradient and proximal-gradient methods under the polyak-łojasiewicz condition’’
Hamed Karimi, Julie Nutini and Mark Schmidt · 2016
Earlier work this paper cites.
‘‘Algorithms and matching lower bounds for approximately-convex optimization’’
Andrej Risteski and Yuanzhi Li · 2016
Earlier work this paper cites.
‘‘Zoo: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models’’
Pin-Yu Chen et al · 2017
Earlier work this paper cites.
‘‘An optimal algorithm for bandit and zero-order convex optimization with two-point feedback’’
Ohad Shamir · 2017
Earlier work this paper cites.
‘‘Random gradient-free minimization of convex functions’’
Yurii Nesterov and Vladimir Spokoiny · 2017
Earlier work this paper cites.
‘‘Zeroth order nonconvex multi-agent optimization over networks’’
Davood Hajinezhad, Mingyi Hong and Alfredo Garcia · 2017
Cited alongside, same era.
‘‘Stochastic online optimization. Single-point and multi-point non-linear multi-armed bandits. Convex and strongly-convex case’’
Alexander Gasnikov et al · 2017
Cited alongside, same era.
‘‘Structured evolution with compact architectures for scalable policy optimization’’
Krzysztof Choromanski et al · 2018
Cited alongside, same era.
‘‘Simple random search of static linear policies is competitive for reinforcement learning’’
Horia Mania, Aurelia Guy and Benjamin Recht · 2018
Cited alongside, same era.
‘‘Black-box generation of adversarial text sequences to evade deep learning classifiers’’
Ji Gao, Jack Lanchantin, Mary Soffa and Yanjun Qi · 2018
Cited alongside, same era.
‘‘Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation’’
Mikhail Belkin · 2021
Later among the works it cites.
‘‘Stopping rules for accelerated gradient methods with additive noise in gradient’’
Artem Vasin, Alexander Gasnikov and Vladimir Spokoiny · 2021
Later among the works it cites.
Ivan Stepanov, Artyom Voronov, Aleksandr Beznosikov and Alexander Gasnikov · 2021
Later among the works it cites.
‘‘Last iterate convergence of SGD for Least-Squares in the Interpolation regime.’’
Aditya Varre, Loucas Pillaud-Vivien and Nicolas Flammarion · 2021
Later among the works it cites.
‘‘The min-max complexity of distributed stochastic convex optimization with intermittent communication’’
Blake Woodworth, Brian Bullins, Ohad Shamir and Nathan Srebro · 2021
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
‘‘Adaptive balancing of gradient and update computation times using global geometry and approximate subproblems’’
Sai Karimireddy, Sebastian Stich and Martin Jaggi · 2018
Cited alongside, same era.
‘‘Zeroth-order stochastic variance reduction for nonconvex optimization’’
Sijia Liu et al · 2018
Cited alongside, same era.
‘‘The convergence of sparsified gradient methods’’
Dan Alistarh et al · 2018
Cited alongside, same era.
‘‘Gradient sparsification for communication-efficient distributed optimization’’
Jianqiao Wangni, Jialei Wang, Ji Liu and Tong Zhang · 2018
Cited alongside, same era.
Matthias Ehrhardt, Erlend Riis, Torbjrn Ringholm and Carola-Bibiane Sch\"onlieb · 2018
Cited alongside, same era.
‘‘Unified optimal analysis of the (stochastic) gradient method’’
Sebastian Stich · 2019
Cited alongside, same era.
‘‘Derivative-free methods for policy optimization: Guarantees for linear quadratic systems’’
Dhruv Malik et al · 2019
Cited alongside, same era.
Later among the works it cites.
‘‘Asynchronous Stochastic Optimization Robust to Arbitrary Delays’’
Alon Cohen et al · 2021
Later among the works it cites.
Eduard Gorbunov et al · 2021
Later among the works it cites.
‘‘Analysis of biased stochastic gradient descent using sequential semidefinite programs’’
Bin Hu, Peter Seiler and Laurent Lessard · 2021
Later among the works it cites.
‘‘Distributed Online and Bandit Convex Optimization’’
Kumar Patel, Aadirupa Saha, Lingxiao Wang and Nathan Srebro · 2022
Later among the works it cites.
Aleksandr Lobanov, Belal Alashqar, Darina Dvinskikh and Alexander Gasnikov · 2022
Later among the works it cites.
‘‘A gradient estimator via L1-randomization for online zero-order optimization with two point feedback’’
Arya Akhavan, Evgenii Chzhen, Massimiliano Pontil and Alexandre Tsybakov · 2022
Later among the works it cites.
‘‘Stochastic Zeroth-Order Functional Constrained Optimization: Oracle Complexity and Applications’’
Anthony Nguyen and Krishnakumar Balasubramanian · 2022
Later among the works it cites.
‘‘Randomized gradient-free methods in convex optimization’’
Alexander Gasnikov et al · 2022
Later among the works it cites.
‘‘The power of first-order smooth optimization for black-box non-smooth problems’’
Alexander Gasnikov et al · 2022
Later among the works it cites.
‘‘Stopping Rules for Gradient Methods for Non-Convex Problems with Additive Noise in Gradient’’
Boris Polyak, Ilia Kuruzov and Fedor Stonyakin · 2022
Later among the works it cites.
‘‘On the Lower Bound of Minimizing Polyak-L_2(Γ)ojasiewicz functions’’
Pengyun Yue, Cong Fang and Zhouchen Lin · 2022
Later among the works it cites.
‘‘Finite Difference Gradient Approximation: To Randomize or Not?’’
Katya Scheinberg · 2022
Later among the works it cites.
‘‘Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noise’’
Eduard Gorbunov et al · 2022
Later among the works it cites.
‘‘Noisy Zeroth-Order Optimization for Non-smooth Saddle Point Problems’’
Darina Dvinskikh, Vladislav Tominin, Iaroslav Tominin and Alexander Gasnikov · 2022
Later among the works it cites.
‘‘Gradient-Type Methods for Optimization Problems with Polyak-L_2(Γ)ojasiewicz Condition: Early Stopping and Adaptivity to Inexactness Parameter’’
Ilya Kuruzov, Fedor Stonyakin and Mohammad Alkousa · 2023
Closest in time.
‘‘Gradient-free optimization of highly smooth functions: improved analysis and a new algorithm’’
Arya Akhavan, Evgenii Chzhen, Massimiliano Pontil and Alexandre Tsybakov · 2023
Closest in time.
‘‘Gradient-free proximal methods with inexact oracle for convex stochastic nonsmooth optimization problems on the simplex’’
Alexander Gasnikov, Anastasia Lagunovskaya, Ilnura Usmanova and Fedor Fedorenko · 2034
Closest in time.