Optimal Sample Complexity Bounds for Non-Convex Optimization Under Kurdyka-Lojasiewicz Condition
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
Text
Yu et al. "Optimal Sample Complexity Bounds for Non-Convex Optimization Under Kurdyka-Lojasiewicz Condition." Artificial Intelligence and Statistics, 2023.Markdown
[Yu et al. "Optimal Sample Complexity Bounds for Non-Convex Optimization Under Kurdyka-Lojasiewicz Condition." Artificial Intelligence and Statistics, 2023.](https://mlanthology.org/aistats/2023/yu2023aistats-optimal/)BibTeX
@inproceedings{yu2023aistats-optimal,
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 = {Artificial Intelligence and Statistics},
year = {2023},
pages = {6806-6821},
volume = {206},
url = {https://mlanthology.org/aistats/2023/yu2023aistats-optimal/}
}