An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback
This provides an incremental improvement in optimization algorithms for machine learning and AI, benefiting researchers and practitioners in fields requiring efficient convex optimization with limited feedback.
The paper tackles the problem of bandit and zero-order convex optimization with two-point feedback, presenting a simple algorithm that achieves optimal performance for convex Lipschitz functions, improving upon prior work limited to smooth functions.
We consider the closely related problems of bandit convex optimization with two-point feedback, and zero-order stochastic convex optimization with two function evaluations per round. We provide a simple algorithm and analysis which is optimal for convex Lipschitz functions. This improves on \cite{dujww13}, which only provides an optimal result for smooth functions; Moreover, the algorithm and analysis are simpler, and readily extend to non-Euclidean problems. The algorithm is based on a small but surprisingly powerful modification of the gradient estimator.