Na Li, Zhaolin Ren, Yujie Tang
We have not lifted any functions out of this paper's repositories yet, so there is nothing we have run. If it links a repository, it is listed below.
Some links come from the archived Papers with Code dataset (CC BY-SA 4.0): attribution and licence.
Two-point zeroth order methods are important in many applications of zeroth-order optimization, such as robotics, wind farms, power systems, online optimization, and adversarial robustness to black-box attacks in deep neural networks, where the problem may be high-dimensional and/or timevarying. Most problems in these applications are nonconvex and contain saddle points. While existing works have shown that zeroth-order methods utilizing Ω(d) function valuations per iteration (with d denoting the problem dimension) can escape saddle points efficiently, it remains an open question if zeroth-order methods based on two-point estimators can escape saddle points. In this paper, we show that by adding an appropriate isotropic perturbation at each iteration, a zeroth-order algorithm based on 2m (for any 1 ≤ m ≤ d) function evaluations per iteration can not only find -second order stationary points polynomially fast, but do so using only Õ( d /m 2 ψ) function evaluations, where ψ ≥ Ω( √ ) is a parameter capturing the extent to which the function of interest exhibits the strict saddle property.
The same record, over MCP at https://syntology.ai/mcp:
get_harvested_code_for_paper("2209.13555")
get_code_for_paper("2209.13555")
have("2209.13555")
Connect an agent — have() is free.