Online convex optimization in the bandit setting: gradient descent without a gradient

ABSTRACT

We study a general online convex optimization problem. We have a convex set S and an unknown sequence of cost functions c1, c2,..., and in each period, we choose a feasible point xt in S, and learn the cost ct(xt). If the function ct is also revealed after each period then, as Zinkevich shows in [25], gradient descent can be used on these functions to get regret bounds of O(√n). That is, after n rounds, the total cost incurred will be O(√n) more than the cost of the best single feasible decision chosen with the benefit of hindsight, minx Σ ct(x).We extend this to the "bandit" setting, where, in each period, only the cost ct(xt) is revealed, and bound the expected regret as O(n^3/4).Our approach uses a simple approximation of the gradient that is computed from evaluating ct at a single (random) point. We show that this biased estimate is sufficient to approximate gradient descent on the sequence of functions. In other words, it is possible to use gradient descent without seeing anything more than the value of the functions at a single point. The guarantees hold even in the most general case: online against an adaptive adversary.For the online linear optimization problem [15], algorithms with low regrets in the bandit setting have recently been given against oblivious [1] and adaptive adversaries [19]. In contrast to these algorithms, which distinguish between explicit explore and exploit periods, our algorithm can be interpreted as doing a small amount of exploration in each period.

REFERENCES

• 1: Baruch Awerbuch , Robert D. Kleinberg, Adaptive routing with end-to-end feedback: distributed learning and geometric approaches, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007367]
• 2: P. Auer , N. Cesa-Bianchi , Y. Freund , R. E. Schapire, Gambling in a rigged casino: The adversarial multi-armed bandit problem, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.322, October 23-25, 1995
• 3: Dimitri P. Bertsekas , John N. Tsitsiklis, Neuro-Dynamic Programming, Athena Scientific, 1996
• 4: Dimitris Bertsimas , Santosh Vempala, Solving convex programs by random walks, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509926]
• 5: J. Birge and F. Loveaux. Introduction to Stochastic Programming. Springer Verlag, New York, 1997.
• 6: Thomas Cover. Universal Portfolios. In Mathematical Finance1, 1--29, 1991.
• 7: A. Frieze and R. Kannan. Log-Sobolev inequalities and sampling from log-concave distributions. Annals of Applied Probability, 9 (1999), 14--26.
• 8: O. N. Granichin. Stochastic approximation with input perturbation for dependent observation disturbances. Vestn. Leningrad. Gos Univ., 1989, Ser. 1, no. 4, 27--31.
• 9: O. N. Granichin, Randomized Algorithms for Stochastic Approximation under Arbitrary Disturbances, Automation and Remote Control, v.63 n.2, p.209-219, February 2002 [doi>10.1023/A:1014291407082]
• 10: David P. Helmbold, Robert E. Schapire, Yoram Singer, and Manfred K. Warmuth. On-line portfolio selection using multiplicative updates. In Mathematical Finance, 8(4):325--347, 1998.
• 11: L. Khachiyan. A polynomial algorithm in linear programming (in Russian). Doklady Akedamii Nauk SSSR, 244, 1093--1096, 1979.
• 12: R. Kleinberg. Nearly Tight Bounds for the Continuum Armed Bandit Problem. To appear in Proc. 18th Annual Conf. on Neural Information Processing Systems, 2004.
• 13: S. Kirkpatrick, C. D. Gelatt Jr., M. P. Vecchi. Optimization by Simulated Annealing. Science, 220, 4598, 671--680, 1983.
• 14: A. Kalai , S. Vempala, Efficient algorithms for universal portfolios, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.486, November 12-14, 2000
• 15: A. Kalai and S. Vempala. Efficient algorithms for the online decision problem. In Proceedings of the 16th Conference on Computational Learning Theory, 2003.
• 16: Jyrki Kivinen , Manfred K. Warmuth, Exponentiated gradient versus gradient descent for linear predictors, Information and Computation, v.132 n.1, p.1-63, Jan. 10, 1997 [doi>10.1006/inco.1996.2612]
• 17: Ravi Kannan , László Lovász , Miklós Simonovits, Random walks and an O*(n5) volume algorithm for convex bodies, Random Structures & Algorithms, v.11 n.1, p.1-50, Aug. 1997 [doi>10.1002/(SICI)1098-2418(199708)11:1<1::AID-RSA1>3.0.CO;2-X]
• 18: László Lovász , Santosh Vempala, Simulated Annealing in Convex Bodies and an 0*(n4) Volume Algorithm, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.650, October 11-14, 2003
• 19: H. Brendan McMahan and Avrim Blum. Online Geometric Optimization in the Bandit Setting Against an Adaptive Adversary. In Proceedings of the 17th Annual Conference on Learning Theory, COLT 2004.
• 20: N. Metropolis, A. Rosenbluth, M. Rosenbluth, A. Teller, E. Teller. Equation of State Calculations by Fast Computing Machines. J. Chem. Phys., 21, 6, 1087--1092. 1953.
• 21: V. D. Milman and A. Pajor. Isotropic position and inertia ellipsoids and zonoids of the unit ball of a normed n-dimensional space. Lecture Notes in Mathematics 1376, Springer, Berlin (1989), 64--104.
• 22: James C. Spall, A one-measurement form of simultaneous perturbation stochastic approximation, Automatica (Journal of IFAC), v.33 n.1, p.109-112, Jan. 1997 [doi>10.1016/S0005-1098(96)00149-5]
• 23: James C. Spall, Introduction to Stochastic Search and Optimization, John Wiley & Sons, Inc., New York, NY, 2003
• 24: Eiji Takimoto , Manfred K. Warmuth, Path Kernels and Multiplicative Updates, Proceedings of the 15th Annual Conference on Computational Learning Theory, p.74-89, July 08-10, 2002
• 25: M. Zinkevich. Online Convex Programming and Generalized Infinitesimal Gradient Ascent. In Proceedings of the Twentieth International Conference on Machine Learning, pp. 928--936, 2003.