In this paper, we study and analyze zeroth-order stochastic approximation
algorithms for solving bilvel problems, when neither the upper/lower objective
values, nor their unbiased gradient estimates are available. In particular,
exploiting Stein's identity, we first use Gaussian smoothing to estimate first-
and second-order partial derivatives of functions with two independent block of
variables. We then used these estimates in the framework of a stochastic
approximation algorithm for solving bilevel optimization problems and establish
its non-asymptotic convergence analysis. To the best of our knowledge, this is
the first time that sample complexity bounds are established for a fully
stochastic zeroth-order bilevel optimization algorithm.

本文研究使用零阶随机逼近算法解决双层问题，无论是上 / 下目标值还是它们的无偏梯度估计都不可用。通过利用斯坦恩恒等式，首先使用高斯平滑估计具有两个独立块变量的函数的一阶和二阶偏导数。然后，在随机逼近算法框架中使用这些估计来解决双层优化问题，并建立其非渐近收敛分析。据我们所知，这是第一次为完全随机零阶双层优化算法建立样本复杂度界限。

经由高斯平滑的全零阶双层规划

Fully Zeroth-Order Bilevel Programming via Gaussian Smoothing

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.

本文提出了针对非凸和凸优化的零阶随机逼近算法，并关注解决约束优化、高维设置和避免鞍点等问题。我们探索了结构稀疏假设的优点，并提出了一种使用零阶信息的被截断随机梯度算法和一种避免鞍点的算法，并讨论了它们的收敛率。