The Price of Adaptivity in Stochastic Convex Optimization

Autor:	Carmon, Yair, Hinder, Oliver
Rok vydání:	2024
Předmět:	Mathematics - Optimization and Control Computer Science - Machine Learning Statistics - Machine Learning
Druh dokumentu:	Working Paper
Popis:	We prove impossibility results for adaptivity in non-smooth stochastic convex optimization. Given a set of problem parameters we wish to adapt to, we define a "price of adaptivity" (PoA) that, roughly speaking, measures the multiplicative increase in suboptimality due to uncertainty in these parameters. When the initial distance to the optimum is unknown but a gradient norm bound is known, we show that the PoA is at least logarithmic for expected suboptimality, and double-logarithmic for median suboptimality. When there is uncertainty in both distance and gradient norm, we show that the PoA must be polynomial in the level of uncertainty. Our lower bounds nearly match existing upper bounds, and establish that there is no parameter-free lunch. En route, we also establish tight upper and lower bounds for (known-parameter) high-probability stochastic convex optimization with heavy-tailed and bounded noise, respectively. Comment: Accepted for presentation at the Conference on Learning Theory (COLT) 2024; to appear in proceedings as an extended abstract
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2402.10898 Zobrazit plný text záznamu View this record from Arxiv