Random Gradient-Free Minimization of Convex Functions

By Yurii E. Nesterov, Vladimir Spokoiny. 2015

1,386 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Statistics and Probability

In Optimization & Training

Citations in the corpus

On the Complexity of Bandit and Derivative-Free Stochastic Convex Optimization (2012, methodology): “Derivative-free methods were among the earliest algorithms to numerically solve unconstrained optimization problems, and have recently enjoyed increasing interest, being especial useful in black-box situations where gradient information is hard to compute or does not exist [15, 18].”
ZOO: Zeroth Order Optimization Based Black-box Attacks to Deep Neural Networks without Training Substitute Models (2017, methodology): “The convergence of these zeroth order methods has been proved in optimization literature [10, 24, 31].”
Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming (2013, methodology): “For example, he established the O ( n/ǫ ) complexity, in terms of E [ f (¯ x ) − f ∗ ] ≤ ǫ , for a zeroth-order method applied to smooth convex programming problems (see in p.19 of [28]) along with some possible acceleration schemes.”
Evolution Strategies as a Scalable Alternative to Reinforcement Learning (2017, background): “Theoretical analysis indeed shows that for general non-smooth optimization problems, the required number of optimization steps scales linearly with the dimension [Nesterov and Spokoiny, 2011].”
Simple random search provides a competitive approach to reinforcement learning (2018, methodology): “Our method is based on ﬁnite diﬀerences along uniformly distributed directions; inspired by the derivative free optimization methods analyzed by Nesterov and Spokoiny [24], and similar to the Evolution Strategies algorithm [28].”
Evolved Policy Gradients (2018, neutral): “Similar formulations also appear in prior works including (36; 32; 16).”
Stochastic Convex Optimization with Bandit Feedback (2011, background): “[1] and Nesterov [15] do not apply to our setting as noted in the full-length version of this paper [2].”
On Evaluating Adversarial Robustness of Large Vision-Language Models (2023, methodology): “To estimate the gradients, we employ the random gradient-free (RGF) method [54].”
A Tour of Reinforcement Learning: The View from Continuous Control (2018, methodology): “A rigorous analysis using contemporary techniques was provided by Nesterov and Spokoiny [54].”
A Primer on Zeroth-Order Optimization in Signal Processing and Machine Learning: Principals, Recent Advances, and Applications (2020, methodology): “The unbiasedness of (1) with respect to ∇fμ(x) is assured by [19], [31]: Eu∼p [ ∇̂f(x) ] = ∇fμ(x).”
Contrasting Exploration in Parameter and Action Space: A Zeroth-Order Optimization Perspective (2019, methodology): “…assume that J ( θ ) is G -lipschitz and L -smooth, i.e. for all Note that these assumptions are similar to the assumptions made in other zeroth-order analysis works, (Flaxman et al., 2005; Agarwal et al., 2010; Duchi et al., 2015; Shamir, 2013; Ghadimi and Lan, 2013; Nesterov and Spokoiny, 2017).”
Square Attack: a query-efficient black-box adversarial attack via random search (2019, result): “We obtain the following result, similar to existing convergence rates for zeroth-order methods [42,43,24]:”
Multi-Step Model-Agnostic Meta-Learning: Convergence and Improved Algorithms (2020, neutral): “…(i) follows from the mean value theorem, (ii) follows from the inequality that ‖ ∑n i=1 bi‖2 ≤ n ∑n i=1 ‖bi‖2 for any vector bi, (iii) follows by combining Assumption 1, the inequality that ‖ ∑n i=1 bi‖ ≤ ∑n i=1 ‖bi‖ and rt, at ∈ (0, 1), ∑d t=1 rt = 1, and the last inequality follows from…”
SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator (2018, methodology): “4 SPIDER for Stochastic Zeroth-Order Method For SZO algorithms, (2.3) can be solved only from the Incremental Zeroth-Order Oracle (IZO)(Nesterov & Spokoiny, 2011), which is defined as: 11One of the results not included in this table is Carmon et al. (2017a), which finds an -approximate first-order…”
Learning Optimal Resource Allocations in Wireless Systems (2018, methodology): “To study another key aspect of the parameters of the DNN— namely the output distribution π θ , h —we make a comparison against the performance achieved using two natural choices for distribution in the power allocation problem in (34).”
Query-Efficient Hard-label Black-box Attack: An Optimization-based Approach (2018, methodology): “Here we propose to solve (1) using Randomized Gradient-Free (RGF) method proposed in [2, 18].”
Smoothing and worst-case complexity for direct-search methods in nonsmooth optimization (2013, methodology): “Note that the bound O(n 2 ǫ −2 ) for direct search is worse in terms of the power of ǫ. Nesterov [30], using Gaussian smoothing, proposes a random derivative-free approach for which he proves that the number of function evaluations needed for bringing the expected norm of the gradient of the smoothi”
Boundary Attack++: Query-Efficient Decision-Based Adversarial Attack (2019, background): “Agarwal et al. [1] and Nesterov and Spokoiny [23] observed a faster convergence rate by using two function evaluations for estimating gradient.”