PaperlayerView exact revision on arXiv

Source-linked AI summary

Zeroth-order Nonconvex Stochastic Optimization: Handling Constraints, High-Dimensionality and Saddle-Points

Krishnakumar Balasubramanian, Saeed Ghadimi

arXiv:1809.06474v2math.OCcs.DScs.LGmath.STstat.MLstat.TH

TL;DR

The paper studies convex and nonconvex stochastic optimization when only noisy function evaluations are available, including constraints, dimensionality, and saddle-point avoidance. It develops zeroth-order algorithms for these settings, reporting improved conditional-gradient rates, poly-logarithmic dimensional dependence for gradient methods, and an approach to second-order stationarity.

  • Problem

    The paper asks how to optimize convex and nonconvex objectives using only noisy function evaluations, where constraints can make projection costly, zeroth-order methods can depend linearly on dimension, and saddle-point avoidance is challenging.

    Source: §1 · pp. 2–3

  • Method

    The paper analyzes zeroth-order conditional-gradient methods, studies standard and truncated stochastic-gradient methods under structural sparsity, and uses Stein identities for Hessian estimation in a cubic-regularized Newton method.

    Source: §1 · p. 4, §4.2 · p. 26

  • Results

    The proposed methods attain improved rates for convex conditional gradient, poly-logarithmic dimensional dependence for specified gradient methods, and efficient convergence to second-order stationary points with the cubic-regularized Newton approach.

    Source: §1 · p. 4

  • Takeaways & Limitations

    In the stated settings, zeroth-order methods can address constraints and exploit sparsity while extending function-query optimization to saddle-point avoidance.

    Source: §1 · pp. 2, 4

    Spectral truncation makes the Hessian estimator robust to heavy tails, but removes the vanilla estimator’s computational advantage.

    Source: §4.1 · p. 26

Abstract

from arXiv · show

In this paper, we propose and analyze zeroth-order stochastic approximation algorithms for nonconvex and convex optimization, with a focus on addressing constrained optimization, high-dimensional setting and saddle-point avoiding. To handle constrained optimization, we first propose generalizations of the conditional gradient algorithm achieving rates similar to the standard stochastic gradient algorithm using only zeroth-order information. To facilitate zeroth-order optimization in high-dimensions, we explore the advantages of structural sparsity assumptions. Specifically, (i) we highlight an implicit regularization phenomenon where the standard stochastic gradient algorithm with zeroth-order information adapts to the sparsity of the problem at hand by just varying the step-size and (ii) propose a truncated stochastic gradient algorithm with zeroth-order information, whose rate of convergence depends only poly-logarithmically on the dimensionality. We next focus on avoiding saddle-points in non-convex setting. Towards that, we interpret the Gaussian smoothing technique for estimating gradient based on zeroth-order information as an instantiation of first-order Stein's identity. Based on this, we provide a novel linear-(in dimension) time estimator of the Hessian matrix of a function using only zeroth-order information, which is based on second-order Stein's identity. We then provide an algorithm for avoiding saddle-points, which is based on a zeroth-order cubic regularization Newton's method and discuss its convergence rates.

1 Introduction

The paper develops zeroth-order stochastic optimization methods for settings where constraints, high dimensionality, or nonconvex saddle points pose challenges. It uses noisy function evaluations and analyzes conditional-gradient, sparse-optimization, and cubic-regularized Newton approaches.

1 Introduction

  • The motivating gap is that most existing zeroth-order algorithms are analyzed in low-dimensional unconstrained settings, with limited nonconvex theory beyond first-order stationarity.The paper assumes access to noisy function evaluations rather than gradient or Hessian queries.Source: §1 · p. 2
  • Zeroth-order conditional-gradient methods address constrained problems where projection can be costly, with complexity depending linearly on dimension, like zeroth-order gradient methods.The paper also proposes a modified method with improved rates for convex objectives.Source: §1 · p. 2
  • Under a sparsity assumption, zeroth-order stochastic gradient methods achieve poly-logarithmic dimensional dependence for first-order stationarity, while a truncated convex method improves dependence on error tolerance.The standard method exhibits implicit regularization; the truncated method is less expensive than the approach of [WDBS18].Source: §1 · pp. 3–4
  • A zeroth-order cubic-regularized Newton method uses a Hessian estimator based on second-order Stein identities to avoid saddle points and reach second-order stationary points.The estimator uses inner-product evaluations and has runtime linear in dimension.Source: §1 · pp. 3–4

1.1 Preliminaries

  • Gaussian smoothing for estimating gradients from function queries is an instance of first-order Stein identity, motivating the paper’s higher-order Hessian estimation approach.The preliminaries also define expectation-based optimality criteria for convex and nonconvex problems.Source: §1.1 · p. 6
  • The stated performance measures are expectation-based; high-probability counterparts require sub-Gaussian oracle tails, while bandit regret may behave differently.The authors do not elaborate on the high-probability analysis.Source: §1.1 · p. 6

2 Handling Constraints: Zeroth-order Stochastic Conditional Gradient Type Method

This section develops and analyzes zeroth-order stochastic conditional-gradient methods for constrained nonconvex and convex optimization under boundedness assumptions, including inexact updates for convex problems. It also qualifies the complexity comparison, noting improved target-accuracy dependence but no improvement in order when measured by the Frank–Wolfe gap alone.

2.1 Zeroth-order Stochastic Conditional Gradient Method

  • For nonconvex objectives, ZSCG returns a random iterate and provides complexity bounds matching first-order stochastic conditional-gradient methods in epsilon under the Frank-Wolfe-gap measure.Its analysis uses the Frank-Wolfe gap to characterize approximate stationarity.Source: §2.1 · pp. 7, 8, 11

2.2 Improved Rates for Convex Problems

  • For convex objectives, an accelerated inexact-update variant skips some gradient evaluations, reducing zeroth-order oracle calls while retaining the same number of linear subproblems as the basic method.The method applies conditional gradient to inexactly solve subproblems of a stochastic accelerated-gradient method.Source: §2.2 · pp. 11, 14

2.3 Zeroth-order Stochastic Gradient Method with Inexact Updates-Nonconvex case

  • For nonconvex problems, the inexact-update method has better complexity bounds than the convex accelerated variant, but the bounds are the same when measured by the same criterion.Its analysis uses a gradient-mapping criterion as an alternative to the Frank-Wolfe gap.Source: §2.3 · pp. 14–15
  • Bounds (2.35) improve on (2.9) in target-accuracy ǫ dependence, but for the Frank–Wolfe gap alone both have the same order of magnitude.The comparison uses different performance measures; the same-order result follows from part c of Lemma 2.2.Source: §2.3 · p. 16

3 Handling High-Dimensionality: Zeroth-order Stochastic Gradient Methods

The section studies zeroth-order stochastic gradient methods for high-dimensional optimization under structural sparsity assumptions. It analyzes standard and truncated methods for nonconvex and convex objectives.

3 Handling High-Dimensionality: Zeroth-order Stochastic Gradient Methods

  • The section assumes s-sparse gradients, with s much smaller than d, to study unconstrained zeroth-order optimization.It considers nonconvex and convex objectives under this structural sparsity setting.Source: §3 · p. 17

3.2 Zeroth-order Stochastic Gradient Method for Convex Problems

  • The truncated variant keeps the ˆs largest-magnitude gradient components and zeros out the rest.The paper analyzes it for convex objectives using function-value optimality gap, assuming a sparse optimal solution as well as sparse gradients.Source: §3.1 · p. 20, §3.2 · p. 20

3.1 Zeroth-order Stochastic Gradient Method for Nonconvex Problems

  • With sparse gradients, the standard method’s convergence rate depends only poly-logarithmically on d when the step size is selected appropriately.This improves on the linear dimensionality dependence reported for the general nonconvex method.Source: §3.1 · pp. 17, 18, 20
  • The standard method needs no special sparsity operation: under the dual-norm performance measure, it implicitly adapts to gradient sparsity.The paper also states that the result applies to convex objectives under the same performance measure.Source: §3.1 · p. 20

3.2 Zeroth-order Stochastic Gradient Method for Convex Problems

  • For convex problems, the truncated method’s complexity depends poly-logarithmically on d and linearly on ˆs.The stated guarantee also assumes a sparse optimal solution; its iteration bound is given in the theorem passage.Source: §3.2 · pp. 20–22
  • Compared with [WDBS18], the paper’s sparsity assumptions are weaker than requiring dependence on only s coordinates, and it assumes no second-derivative sparsity or smoothness.It also contrasts one function query per iteration and simple thresholding with [WDBS18]’s multiple queries and debiased Lasso estimators.Source: §3.2 · p. 22

4 Handling Saddle-Points: Zeroth-Order Cubic Regularization Method

The section develops zeroth-order Hessian estimation from second-order Stein’s identity and uses estimated gradients and Hessians in a stochastic cubic-regularized Newton method. It establishes convergence and sample-complexity results, while noting that robustness and dimension-related improvements have limits.

4.1 Estimating Hessian with Zeroth-Order Information

  • Second-order Gaussian Stein’s identity relates function queries to Hessians, yielding an estimator whose Hessian-vector products take time linear in dimension.The estimator approximates the Hessian of the smoothed function from Gaussian samples, which is then used to approximate the Hessian of the original function.Source: §4.1 · pp. 23–24
  • The Hessian approximation bound improves in its dependence on dimension under the more restrictive interchangeability assumption, but that improvement does not reduce oracle calls for the cubic-regularized method.The paper also notes that the two estimators are not robust to ν approaching zero because their variances blow up, and focuses on the estimator in (4.4).Source: §4.1 · pp. 23, 25
  • Spectral truncation makes the Hessian estimator robust to heavy-tailed function values, but loses the vanilla estimator’s computational advantage.The paper does not provide the detailed estimation-error analysis for the robust Hessian and gradient estimators.Source: §4.1 · p. 26

4.2 Zeroth-Order Stochastic Cubic Regularized Newton Method

  • Algorithm 7 presents a zeroth-order stochastic cubic-regularized Newton method using gradient and Hessian estimates based on Stein’s identities; its output is a random index from the generated trajectory.Source: §4.2 · p. 26
  • For the cubic-regularized Newton method, the paper reports a zeroth-order oracle-call advantage for high-accuracy second-order stationarity, with linear dependence on dimension as the cost of zeroth-order access.The discussion specifies this advantage when ε ≈ d^-3 and notes that intermediate complexity results are possible depending on solution quality.Source: §4.2 · p. 30

5 Discussion

The discussion summarizes the paper’s zeroth-order algorithms for constraints, dimensionality, and saddle-point avoidance, and identifies several directions for extending the results.

5 Discussion

  • The paper proposes and analyzes zeroth-order stochastic approximation algorithms for convex and nonconvex problems motivated by modern machine-learning challenges.The algorithms address constraints, dimensionality, and saddle-points in nonconvex stochastic optimization.Source: §5 · pp. 30–31
  • Finite-sum problems may admit better rates through variance-reduction techniques, while high-dimensional constrained conditional-gradient performance remains unexplored.The authors also identify lower bounds for the nonconvex settings and regret bounds as open directions.Source: §5 · p. 31
  • The authors identify second-order stationarity results in constrained settings as a challenging future extension.They state that they plan to extend the results to this setting.Source: §5 · p. 31

Related papers

Loading 1809.06474v2…