nach oben

Erschienen in:

2024 | OriginalPaper | Buchkapitel

Projection-Free Bandit Convex Optimization over Strongly Convex Sets

verfasst von : Chenxu Zhang, Yibo Wang, Peng Tian, Xiao Cheng, Yuanyu Wan, Mingli Song

Erschienen in: Advances in Knowledge Discovery and Data Mining

Verlag: Springer Nature Singapore

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Projection-free algorithms for bandit convex optimization have received increasing attention, due to the ability to deal with the bandit feedback and complicated constraints simultaneously. The state-of-the-art ones can achieve an expected regret bound of \(O(T^{3/4})\). However, they need to utilize a blocking technique, which is unsatisfying in practice due to the delayed reaction to the change of functions, and results in a logarithmically worse high-probability regret bound of \(O(T^{3/4}\sqrt{\log T})\). In this paper, we study the special case of bandit convex optimization over strongly convex sets, and present a projection-free algorithm, which keeps the \(O(T^{3/4})\) expected regret bound without employing the blocking technique. More importantly, we prove that it can enjoy an \(O(T^{3/4})\) high-probability regret bound, which removes the logarithmical factor in the previous high-probability regret bound. Furthermore, empirical results on synthetic and real-world datasets have demonstrated the better performance of our algorithm.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Streaming Fair k-Center Clustering over Massive Dataset with Performance Guarantee

Nächstes Kapitel Adaptive Prediction Interval for Data Stream Regression

Although Wan et al. [29] originally establish such bound for a decentralized variant of BBCG, it is easy to extend this result for BBCG.

https://github.com/zcx-xxx/PAKDD-2024/blob/main/PAKDD-2024-Zhang-S.pdf.

Abernethy, J., Hazan, E., Rakhlin, A.: Competing in the dark: an efficient algorithm for bandit linear optimization. In: Proceedings of the 21st Conference on Learning Theory, pp. 263–274 (2008)

Agarwal, A., Dekel, O., Xiao, L.: Optimal algorithms for online convex optimization with multi-point bandit feedback. In: Proceedings of the 23rd Conference on Learning Theory, pp. 28–40 (2010)

Awerbuch, B., Kleinberg, R.: Online linear optimization and adaptive routing. J. Comput. Syst. Sci. 74(1), 97–114 (2008)MathSciNetCrossRef

Bubeck, S., Cesa-Bianchi, N., Kakade, S.M.: Towards minimax policies for online linear optimization with bandit feedback. In: Proceedings of the 25th Conference on Learning Theory, pp. 41.1–41.14 (2012)

Bubeck, S., Dekel, O., Koren, T., Peres, Y.: Bandit convex optimization: \(\sqrt{t}\) regret in one dimension. In: Proceedings of the 28th Conference on Learning Theory, pp. 266–278 (2015)

Bubeck, S., Eldan, R., Lee, Y.T.: Kernel-based methods for bandit convex optimization. In: Proceedings of the 49th Annual ACM Symposium on Theory of Computing, pp. 72–85 (2019)

Chang, C.C., Lin, C.J.: Libsvm: a library for support vector machines. ACM Trans. Intell. Syst. Technol. 2(27), 1–27 (2011)CrossRef

Chen, L., Harshaw, C., Hassani, H., Karbasi, A.: Projection-free online optimization with stochastic gradient: from convexity to submodularity. In: Proceedings of the 35th International Conference on Machine Learning, pp. 814–823 (2018)

Chen, L., Zhang, M., Karbasi, A.: Projection-free bandit convex optimization. In: Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, pp. 2047–2056 (2019)

10.

Dekel, O., Eldan, R., Koren, T.: Bandit smooth convex optimization: Improving the bias-variance tradeoff. In: Advances in Neural Information Processing Systems 28, pp. 2926–2934 (2015)

11.

Flaxman, A.D., Kalai, A.T., McMahan, H.B.: Online convex optimization in the bandit setting: gradient descent without a gradient. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 385–394 (2005)

12.

Frank, M., Wolfe, P.: An algorithm for quadratic programming. Naval Res. Logistics Quart. 3(1–2), 95–110 (1956)MathSciNetCrossRef

13.

Garber, D., Hazan, E.: Faster rates for the frank-wolfe method over strongly-convex sets. In: Proceedings of the 32nd International Conference on Machine Learning, pp. 541–549 (2015)

14.

Garber, D., Hazan, E.: A linearly convergent conditional gradient algorithm with applications to online and stochastic optimization. SIAM J. Optim. 26(3), 1493–1528 (2016)MathSciNetCrossRef

15.

Garber, D., Kretzu, B.: Improved regret bounds for projection-free bandit convex optimization. In: Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, pp. 2196–2206 (2020)

16.

Garber, D., Kretzu, B.: New projection-free algorithms for online convex optimization with adaptive regret guarantees. In: Proceedings of the 35th Conference on Learning Theory, pp. 2326–2359 (2022)

17.

Garber, D., Kretzu, B.: Projection-free online exp-concave optimization. In: Proceedings of the 36th Conference on Learning Theory (2023)

18.

Hazan, E.: Introduction to online convex optimization. Found. Trends Optim. 2(3–4), 157–325 (2016)CrossRef

19.

Hazan, E., Kale, S.: Projection-free online learning. In: Proceedings of the 29th International Conference on Machine Learning, pp. 1843–1850 (2012)

20.

Hazan, E., Levy, K.Y.: Bandit convex optimization: towards tight bounds. In: Advances in Neural Information Processing Systems 27, pp. 784–792 (2014)

21.

Hazan, E., Minasyan, E.: Faster projection-free online learning. In: Proceedings of the 33rd Conference on Learning Theory, pp. 1877–1893 (2020)

22.

Ito, S.: An optimal algorithm for bandit convex optimization with strongly-convex and smooth loss. In: Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, pp. 2229–2239 (2020)

23.

Jaggi, M.: Revisiting Frank-Wolfe: projection-free sparse convex optimization. In: Proceedings of the 30th International Conference on Machine Learning, pp. 427–435 (2013)

24.

Kalhan, D.S., et al.: Dynamic online learning via frank-wolfe algorithm. IEEE Trans. Signal Process. 69, 932–947 (2021)MathSciNetCrossRef

25.

Kretzu, B., Garber, D.: Revisiting projection-free online learning: the strongly convex case. In: Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, pp. 3592–3600 (2021)

26.

McMahan, H.B., et al.: Ad click prediction: a view from the trenches. In: Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1222–1230 (2013)

27.

Saha, A., Tewari, A.: Improved regret guarantees for online smooth convex optimization with bandit feedback. In: Proceedings of the 14th International Conference on Artificial Intelligence and Statistics, pp. 636–642 (2011)

28.

Shalev-Shwartz, S., Singer, Y.: A primal-dual perspective of online learning algorithm. Mach. Learn. 69(2–3), 115–142 (2007)CrossRef

29.

Wan, Y., Tu, W.W., Zhang, L.: Projection-free distributed online convex optimization with \(\cal{O}(\sqrt{T})\) communication complexity. In: Proceedings of the 37th International Conference on Machine Learning, pp. 9818–9828 (2020)

30.

Wan, Y., Wang, G., Tu, W.W., Zhang, L.: Projection-free distributed online learning with sublinear communication complexity. J. Mach. Learn. Res. 23(172), 1–53 (2022)MathSciNet

31.

Wan, Y., Xue, B., Zhang, L.: Projection-free online learning in dynamic environments. In: Proceedings of the 35th AAAI Conference on Artificial Intelligence Advances, pp. 10067–10075 (2021)

32.

Wan, Y., Zhang, L.: Projection-free online learning over strongly convex set. In: Proceedings of the 35th AAAI Conference on Artificial Intelligence Advances, pp. 10076–10084 (2021)

33.

Wan, Y., Zhang, L., Song, M.: Improved dynamic regret for online frank-wolfe. In: Proceedings of the 36th Conference on Learning Theory (2023)

34.

Wang, Y., Wan, Y., Zhang, S., Zhang, L.: Distributed projection-free online learning for smooth and convex losses. In: Proceedings of the 37th AAAI Conference on Artificial Intelligence, pp. 10226–10234 (2023)

35.

Wang, Y., et al.: Non-stationary projection-free online learning with dynamic and adaptive regret guarantees. ArXiv e-prints arXiv:2305.11726 (2023)

36.

Zinkevich, M.: Online convex programming and generalized infinitesimal gradient ascent. In: Proceedings of the 20th International Conference on Machine Learning, pp. 928–936 (2003)

Titel: Projection-Free Bandit Convex Optimization over Strongly Convex Sets
verfasst von: Chenxu Zhang
Yibo Wang
Peng Tian
Xiao Cheng
Yuanyu Wan
Mingli Song
Verlag: Springer Nature Singapore
Buch: Advances in Knowledge Discovery and Data Mining
Print ISBN: 978-981-9722-61-7

Electronic ISBN: 978-981-9722-59-4

Copyright-Jahr: 2024
DOI: https://doi.org/10.1007/978-981-97-2259-4_9

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner