Optimal Sample Complexity Bounds for Non-convex Optimization under Kurdyka-Lojasiewicz Condition

Qian Yu, Yining Wang, Baihe Huang, Qi Lei, Jason D. Lee
Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, PMLR 206:6806-6821, 2023.

Abstract

Optimization of smooth reward functions under bandit feedback is a long-standing problem in online learning. This paper approaches this problem by studying the convergence under smoothness and Kurdyka-Lojasiewicz conditions. We designed a search-based algorithm that achieves an improved rate compared to the standard gradient-based method. In conjunction with a matching lower bound, this algorithm shows optimality in the dependence on precision for the low-dimension regime.

Cite this Paper

BibTeX
@InProceedings{pmlr-v206-yu23a, title = {Optimal Sample Complexity Bounds for Non-convex Optimization under Kurdyka-Lojasiewicz Condition}, author = {Yu, Qian and Wang, Yining and Huang, Baihe and Lei, Qi and Lee, Jason D.}, booktitle = {Proceedings of The 26th International Conference on Artificial Intelligence and Statistics}, pages = {6806--6821}, year = {2023}, editor = {Ruiz, Francisco and Dy, Jennifer and van de Meent, Jan-Willem}, volume = {206}, series = {Proceedings of Machine Learning Research}, month = {25--27 Apr}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v206/yu23a/yu23a.pdf}, url = {https://proceedings.mlr.press/v206/yu23a.html}, abstract = {Optimization of smooth reward functions under bandit feedback is a long-standing problem in online learning. This paper approaches this problem by studying the convergence under smoothness and Kurdyka-Lojasiewicz conditions. We designed a search-based algorithm that achieves an improved rate compared to the standard gradient-based method. In conjunction with a matching lower bound, this algorithm shows optimality in the dependence on precision for the low-dimension regime.} }
Endnote
%0 Conference Paper %T Optimal Sample Complexity Bounds for Non-convex Optimization under Kurdyka-Lojasiewicz Condition %A Qian Yu %A Yining Wang %A Baihe Huang %A Qi Lei %A Jason D. Lee %B Proceedings of The 26th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2023 %E Francisco Ruiz %E Jennifer Dy %E Jan-Willem van de Meent %F pmlr-v206-yu23a %I PMLR %P 6806--6821 %U https://proceedings.mlr.press/v206/yu23a.html %V 206 %X Optimization of smooth reward functions under bandit feedback is a long-standing problem in online learning. This paper approaches this problem by studying the convergence under smoothness and Kurdyka-Lojasiewicz conditions. We designed a search-based algorithm that achieves an improved rate compared to the standard gradient-based method. In conjunction with a matching lower bound, this algorithm shows optimality in the dependence on precision for the low-dimension regime.
APA
Yu, Q., Wang, Y., Huang, B., Lei, Q. & Lee, J.D.. (2023). Optimal Sample Complexity Bounds for Non-convex Optimization under Kurdyka-Lojasiewicz Condition. Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 206:6806-6821 Available from https://proceedings.mlr.press/v206/yu23a.html.

Related Material