A Note on Zeroth-Order Optimization on the Simplex
This work addresses optimization challenges for functions defined on the simplex, but it is incremental as it adapts existing methods with a new estimator.
The paper tackles the problem of zeroth-order optimization on the probability simplex by constructing a gradient estimator that queries only the simplex, and proves that projected gradient descent and exponential weights algorithms converge at a rate of O(T^{-1/4}) when using this estimator.
We construct a zeroth-order gradient estimator for a smooth function defined on the probability simplex. The proposed estimator queries the simplex only. We prove that projected gradient descent and the exponential weights algorithm, when run with this estimator instead of exact gradients, converge at a $\mathcal O(T^{-1/4})$ rate.