A Note on Zeroth-Order Optimization on the Simplex
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimization
In the paper, we propose a class of accelerated zeroth-order and first-order momentum methods for both nonconvex mini-optimization and minimax-optimization. Specifically, we propose a new accelerated zeroth-order momentu…
Adversarial AttackGradient Free Minimax Optimization: Variance Reduction and Faster Convergence
Many important machine learning applications amount to solving minimax optimization problems, and in many cases there is no access to the gradient information, but only the function values. In this paper, we focus on suc…
Stochastic OptimizationZeroth-Order Stochastic Alternating Direction Method of Multipliers for Nonconvex Nonsmooth Optimization
Alternating direction method of multipliers (ADMM) is a popular optimization tool for the composite and constrained problems in machine learning. However, in many machine learning problems such as black-box attacks and b…
Adversarial AttackBIG-bench Machine LearningBinary ClassificationZeroth-Order Nonconvex Nonsmooth Optimization with Heavy-Tailed Noise
This paper considers the nonconvex nonsmooth problem in which the objective function is Lipschitz continuous. We focus on the stochastic setting where the algorithm can access stochastic function value evaluations with h…
Faster Gradient-Free Proximal Stochastic Methods for Nonconvex Nonsmooth Optimization
Proximal gradient method has been playing an important role to solve many machine learning tasks, especially for the nonsmooth problems. However, in some machine learning problems such as the bandit model and the black-b…
BIG-bench Machine Learning