  In many real-world problems, first-order (FO) derivative evaluations are too
expensive or even inaccessible. For solving these problems, zeroth-order (ZO)
methods that only need function evaluations are often more efficient than FO
methods or sometimes the only options. In this paper, we propose a novel
zeroth-order inexact augmented Lagrangian method (ZO-iALM) to solve black-box
optimization problems, which involve a composite (i.e., smooth+nonsmooth)
objective and functional constraints. Under a certain regularity condition
(also assumed by several existing works on FO methods), the query complexity of
our ZO-iALM is $\tilde{O}(d\varepsilon^{-3})$ to find an $\varepsilon$-KKT
point for problems with a nonconvex objective and nonconvex constraints, and
$\tilde{O}(d\varepsilon^{-2.5})$ for nonconvex problems with convex
constraints, where $d$ is the variable dimension. This appears to be the first
work that develops an iALM-based ZO method for functional constrained
optimization and meanwhile achieves query complexity results matching the
best-known FO complexity results up to a factor of $d$. With an extensive
experimental study, we show the effectiveness of our method. The applications
of our method span from classical optimization problems to practical machine
learning examples such as resource allocation in sensor networks and
adversarial example generation.
