AISTATS 2023poster2 citations
Optimal Sample Complexity Bounds for Non-convex Optimization under Kurdyka-Lojasiewicz Condition
Qian Yu, Yining Wang, Baihe Huang, Qi Lei, Jason D. Lee
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.
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.}
}