Stochastic Zeroth-order Optimization in High Dimensions

1 INTRODUCTION

• High-dimensional zeroth-order optimization is challenging when d exceeds the query budget: lower bounds show polynomial dimension dependence, while classical local averaging has variance scaling linearly with d.The paper introduces sparsity assumptions to make optimization tractable in this setting.Source: §1 · p. 1
• The paper proposes selecting a small subset of important variables before applying low-dimensional methods, and a separate stochastic mirror descent method using de-biased Lasso gradient estimates.The mirror descent method is described as requiring weaker assumptions than the variable-selection method.Source: §1 · p. 1
• In simulations, the mirror-descent-based method outperforms the variable-selection-based method.Source: §1 · p. 2

1.1 Related work

• Unlike zeroth-order methods, first-order sparse optimization typically assumes gradient estimates are unbiased for the original function's gradient, which is generally not possible in zeroth-order settings.Source: §1.1 · p. 2
• Prior compressed-sensing approaches estimate gradients and Hessians for trust-region methods, whereas this paper uses gradient-based algorithms and notes that those prior works established no explicit finite-sample convergence rates.The paper says Hessian recovery may be computationally undesirable in high dimensions.Source: §1.1 · p. 2

2.1 Additional notation

• The paper defines ℓp vector norms, inner products, and sub-Gaussian and sub-exponential random variables for its analysis.Source: §2.1 · p. 2

2.2 Assumptions and evaluation measures

• The setup assumes unconstrained convexity and that a minimizer exists with ℓ1 norm at most B.The minimizer need not be unique.Source: §2.2 · p. 2
• The key structural assumptions require sparse gradients and impose a weaker ℓ1-norm sparsity condition on Hessians.The gradient support may vary with the point; the paper notes that bounded gradient and Hessian coordinates can make function sparsity imply these assumptions.Source: §2.2 · p. 3
• Sparsity can permit gradient estimation with n ≪ d noisy zeroth-order queries, and the paper gives hyperparameter tuning and experimental optimization as motivating examples.The authors describe performance insensitivity to some hyperparameters as implying gradient and Hessian sparsity in such applications.Source: §2.2 · p. 3
• The evaluation uses final-point optimization error and cumulative regret, which also reflects the quality of intermediate query points.For convex problems, the passage states that simple regret is upper bounded by cumulative regret.Source: §2.2 · p. 3

3 LASSO GRADIENT ESTIMATION

• The estimator uses n ≪ d random samples near a query point to estimate its unknown gradient through a biased linear regression model.The design consists of random perturbations, and the regression bias tends to zero as δ tends to zero, at the expense of increasing variance.Source: §3 · pp. 3–4
• Because the gradient is sparse, Lasso is applied to the regression to estimate both the gradient and an intercept.The algorithm uses noisy function values under random perturbations of the query point.Source: §3 · pp. 3–4
• The estimator's regularization parameter λ is chosen to support gradient estimates measured in both ℓ∞ and ℓ1 norms.The passage gives a lemma under assumptions A1 through A4 and a sample-size condition, but the displayed bound is not included in the supplied text.Source: §3 · p. 4
• The probing scale δ controls a bias–variance tradeoff: smaller δ reduces approximation bias but increases the variance from stochastic noise.Larger δ reduces stochastic variance but increases bias from the first-order approximation.Source: §3 · p. 4

4 COMPONENT SELECTION

• Thresholding the Lasso estimate yields no false positives and detects relevant components whose partial derivatives are sufficiently large.The threshold is η = ωλ for a sufficiently large constant ω > 1.Source: §4 · pp. 4–5
• The successive algorithm repeatedly selects components, then applies classical low-dimensional zeroth-order optimization on the selected subset.The selection procedure is motivated by the thresholding guarantee.Source: §4 · pp. 4–5
• Theorem 1 bounds simple regret only; the algorithm cannot achieve consistent cumulative regret, and its failure probability does not vanish as d or T grows.The stated failure probability is at a constant level.Source: §4 · p. 5
• The cited low-dimensional zeroth-order regret bound holds only in expectation; exponential tail bounds remain open.The passage attributes the open question to.Source: §4 · p. 5

5.1 De-biased Lasso estimation

• Directly using biased Lasso gradients yields poor convergence; de-biasing addresses that bias, but inflates stochastic error so the estimate is not good in ℓ1 or ℓ2.The de-biased estimate is used with stochastic mirror descent to handle entrywise error.Source: §5 · p. 5, §5.1 · p. 5

5 MIRROR DESCENT

• Stochastic mirror descent with estimated gradients is proposed because directly substituting Lasso estimates for true gradients leads to poor convergence properties.The method applies de-biased estimates to address the estimation bias.Source: §5 · p. 5

5.2 Bregman divergence and stochastic mirror descent

• Using an ℓ_a-based 1-strongly convex Bregman divergence, mirror descent replaces inaccessible gradients with de-biased Lasso estimates in its updates.The updates are over a subset of the objective's domain.Source: §5.2 · p. 6

5.3 Rates of convergence

• Algorithm 3 has a convergence rate similar to successive component selection without function-sparsity assumption (A5), and its cumulative-regret bound holds with probability 1−O(d^-1).The successive component selection result instead bounds simple regret and holds with constant probability.Source: §5.3 · p. 6

5.4 Improved rates with Hessian smoothness

• O(T^-1/3) simple-regret convergence improves on O(T^-1/4), assuming Hessian smoothness and without requiring second-order information at runtime.Theorem 3 bounds simple regret only; a similar cumulative-regret bound for its parameter choices is not established.Source: §5.4 · p. 8

6 SIMULATIONS

• The simulations compare the methods on sparse quadratic and degree-4 polynomial functions constructed from a uniformly chosen subset of variables.The plots report cumulative regret at selected time epochs and begin after 1,000 oracle evaluations to avoid volatile burn-in phases.Source: §6 · p. 8
• In all simulation settings, vanilla zeroth-order gradient descent is dominated by both proposed algorithms, while mirror descent is superior to successive component selection.The authors recommend mirror descent for practical use.Source: §6 · p. 8
• Mirror descent is easier to use in practice because it has fewer parameters than successive component selection.Source: §6 · p. 8

7 CONCLUDING REMARKS

• The proposed algorithms achieve convergence bounds with only logarithmic dependence on ambient dimension under sparsity assumptions on gradients, Hessians, or functions.Source: §7 · p. 8
• Both algorithms require exact sparsity; whether similar dimension dependence holds under weaker sparsity, such as bounded ℓ1 norms of gradients and Hessians, remains open.The authors note that few practical functions are exactly sparse.Source: §7 · p. 8
• The algorithms have O(T^-1/4) convergence, while mirror descent reaches O(T^-1/3) with additional Hessian smoothness; achieving O(poly log(d)T^-1/2) remains an open question.Source: §7 · p. 8

Proof of Lemma 1

• With probability 1−O(d^-3), the proof bounds the relevant noise term using sub-Gaussian concentration and the boundedness of the perturbation vectors.A separate term is bounded by O(Hδ) almost surely.Source: Proof of Lemma 1 · p. 11
• The Lasso estimator is analyzed through its basic inequality, yielding a cone condition that bounds off-support error by on-support error.Source: Proof of Lemma 1 · pp. 11–12
• Combining the resulting inequalities with n=Ω(s^2 log d) completes the lemma’s proof and gives the stated ℓ1 error consequence.Source: Proof of Lemma 1 · p. 12

Proof of Theorem 1

• The proof starts from the finite-difference analysis for low-dimensional strongly smooth functions and applies it at each epoch.Source: Proof of Theorem 1 · p. 12
• The epochwise bound used in the proof scales with T^-1/3 and a polynomial factor in the stated quantities.Source: Proof of Theorem 1 · p. 12
• The proof combines the preliminary corollary and lemma, which hold with probability 1−O(d^-1), with the case analysis for whether the selected support omits true support components.When support components are omitted, the argument uses first-order optimality on the restricted set and a gradient bound.Source: Proof of Theorem 1 · p. 12

• The observation model writes eYt=Z̄tθ0t+εt, where θ0t=∇f(xt) and εt is defined in Eq. (2).Source: Proof of Lemma 2 · p. 13
• The proof splits bgt−gt into ζt and a second term; ζt has conditional mean zero given xt.Source: Proof of Lemma 2 · p. 13
• Under Assumption (A3), ∥b∥∞≤δH, which supports a Hölder bound on a term involving bΣ−I and bθt−θ0t.Source: Proof of Lemma 2 · p. 13
• The second inequality holds with probability 1−O(d^-2), by Lemma 1.Source: Proof of Lemma 2 · p. 13

Proof of Theorem 2

• The initial Bregman divergence is at most B² log d when the comparator satisfies ∥x*∥1≤B, and the proof uses an approximate-gradient mirror-descent regret bound from.Source: Proof of Theorem 2 · pp. 13–14
• With probability 1−O(d^-1), the squared dual-norm gradient-estimation error is ≲σ² log d uniformly over epochs when n=Ω(s² log d).Source: Proof of Theorem 2 · p. 14
• Theorem 2’s proof combines the intermediate bounds for a minimizer with ∥x*∥1≤B, under η<1/(2H), n=Ω(s² log d), and n=O(T).Source: Proof of Theorem 2 · pp. 14–15

Proof of Lemma 3

• For any a∈R^d, the estimator component ⟨eβt(δ),a⟩ is sub-Gaussian with parameter δH∥a∥1/√n.Source: Proof of Lemma 3 · p. 15

Proof of Theorem 3

• For convex f, the proof bounds cumulative suboptimality by controlling noisy-gradient errors and combining Eqs. (22,23) with Eq. (17).Source: Proof of Theorem 3 · pp. 15–16
• Theorem 3’s argument uses n=Ω(s² log d), n≤T/10, and η<1/(2H), and bounds ∥x*−xt∥2 by 2B when ∥x*∥1≤B.Source: Proof of Theorem 3 · pp. 15–16

Additional tail inequalities

• The appendix derives that the product of independent centered sub-Gaussian variables is centered sub-exponential.Source: Additional tail inequalities · p. 17
• The appendix also states Bernstein inequalities for sub-exponential variables and martingale differences, including a two-sided version related to.Source: Additional tail inequalities · p. 17