Projection-Free Bandit Convex Optimization

2018/05/18 by Chen, Lin, Zhang, Mingrui, Karbasi, Amin · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.1805.07474

Abstract

In this paper, we propose the first computationally efficient projection-free algorithm for bandit convex optimization (BCO). We show that our algorithm achieves a sublinear regret of O(nT^4/5) (where T is the horizon and n is the dimension) for any bounded convex functions with uniformly bounded gradients. We also evaluate the performance of our algorithm against baselines on both synthetic and real data sets for quadratic programming, portfolio selection and matrix completion problems.

Cited by

• Data-Dependent Regret and Polyak Corrections for Constrained Online Convex Optimization

Related

• Improved Regret Bounds for Projection-free Bandit Convex Optimization
• Second Order Methods for Bandit Optimization and Control
• Bandit Convex Optimisation
• An optimal algorithm for bandit convex optimization
• Bandit Convex Optimization: sqrtT Regret in One Dimension