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

Qian Yu; Yining Wang; Baihe Huang; Qi Lei; Jason D. Lee

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

Qian Yu, Yining Wang, Baihe Huang, Qi Lei, Jason D. Lee

Research output: Contribution to journal › Conference article › peer-review

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 design 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.

Original language	English (US)
Pages (from-to)	6806-6821
Number of pages	16
Journal	Proceedings of Machine Learning Research
Volume	206
State	Published - 2023
Event	26th International Conference on Artificial Intelligence and Statistics, AISTATS 2023 - Valencia, Spain Duration: Apr 25 2023 → Apr 27 2023

All Science Journal Classification (ASJC) codes

Artificial Intelligence
Software
Control and Systems Engineering
Statistics and Probability

Cite this

@article{a30c2c53ed204f9e9eaafc3c4520a6f2,

title = "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 design 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.",

author = "Qian Yu and Yining Wang and Baihe Huang and Qi Lei and Lee, {Jason D.}",

note = "Publisher Copyright: Copyright {\textcopyright} 2023 by the author(s); 26th International Conference on Artificial Intelligence and Statistics, AISTATS 2023 ; Conference date: 25-04-2023 Through 27-04-2023",

year = "2023",

language = "English (US)",

volume = "206",

pages = "6806--6821",

journal = "Proceedings of Machine Learning Research",

issn = "2640-3498",

}

TY - JOUR

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

AU - Yu, Qian

AU - Wang, Yining

AU - Huang, Baihe

AU - Lei, Qi

AU - Lee, Jason D.

PY - 2023

Y1 - 2023

N2 - 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 design 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.

AB - 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 design 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.

UR - http://www.scopus.com/inward/record.url?scp=85165144722&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85165144722&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:85165144722

SN - 2640-3498

VL - 206

SP - 6806

EP - 6821

JO - Proceedings of Machine Learning Research

JF - Proceedings of Machine Learning Research

T2 - 26th International Conference on Artificial Intelligence and Statistics, AISTATS 2023

Y2 - 25 April 2023 through 27 April 2023

ER -

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

Abstract

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this