Problemet med stokastisk konvex optimering med bandit feedback (i inlärningsgemenskapen) eller utan kunskap om gradienter (i optimeringsgemenskapen) har fått mycket uppmärksamhet under de senaste åren, i form av algoritmer och prestanda övre gränser. Men mycket mindre är känt om den inneboende komplexiteten i dessa problem, och det finns få lägre gränser i litteraturen, särskilt för ickelinjära funktioner. I detta dokument undersöker vi det uppnåeliga felet/regret i bandit och derivatfria inställningar, som en funktion av dimension d och det tillgängliga antalet frågor T. Vi ger en exakt karakterisering av uppnåelig prestanda för starkt konvexa och smidiga funktioner, vilket också innebär en icke-trivial lägre gräns för mer allmänna problem. Dessutom bevisar vi att i både bandit och derivatfri inställning, det antal frågor som krävs måste skala minst kvadratiskt med dimensionen. Slutligen visar vi att på den naturliga klassen av kvadratiska funktioner, är det möjligt att få en "snabb" O(1/T ) felfrekvens i termer av T, under milda antaganden, även utan att ha tillgång till gradienter. Såvitt vi vet är detta den första sådana hastighet i en derivatfri stokastisk inställning, och innehar trots tidigare resultat som verkar antyda motsatsen.
Även om ett dokument nyligen av REF visar att den lägre gränsen för ånger måste vara  och även med de starkt konvexa och smidiga antagandena.
On the Complexity of Bandit and Derivative-Free Stochastic Convex Optimization
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}