Abstract-Vi anser derivatfria algoritmer för stokastiska och nonstokastiska konvexa optimeringsproblem som endast använder funktionsvärden snarare än gradienter. Med fokus på icke-asymptotiska gränser på konvergenshastigheter, visar vi att om par av funktionsvärden finns tillgängliga, algoritmer för d-dimensionell optimering som använder gradient uppskattningar baserade på slumpmässiga perturbationer lider en faktor på högst ε d i konvergenshastighet över traditionella stokastiska gradientmetoder. Vi etablerar sådana resultat för både smidiga och smidiga fall, skärper tidigare analyser som tyder på ett sämre dimensionsberoende, och utvidgar våra resultat till flera (m ≥ 2) utvärderingar. Vi kompletterar vår algoritmiska utveckling med informationsteoretiska lägre gränser på minimax-konvergensen av sådana problem och fastställer skärpan i våra uppnåeliga resultat upp till konstanta (ibland logaritmiska) faktorer.
Nyligen gav REF optimala garantier för stokastisk konvex optimering upp till logaritmiska faktorer.
Optimal Rates for Zero-Order Convex Optimization: The Power of Two Function Evaluations
{'venue': 'IEEE Transactions on Information Theory', 'journal': 'IEEE Transactions on Information Theory', 'mag_field_of_study': ['Mathematics', 'Computer Science']}