2 problems

0 votes0 replies0 views
The optimal-runtime conjecture for stochastic exp-concave optimization
Stochastic exp-concave optimization (SXO) concerns minimizing the population objective from stochastic gradient-oracle queries in dimension $d$ , to accuracy $\epsilon$ . Optimal-run…
Conjectureopenexp-concave-optimization online-optimization stochastic-optimizationarXiv posted 2 days ago
0 votes0 replies0 views
The arithmetic-complexity lower-bound conjecture for stochastic exp-concave optimization
Arithmetic-complexity conjecture. Without additional assumptions on the data-generating distribution, it is not possible to find an $varepsilon$ -optimal point using fewer than…
Conjectureopencomputational-complexity exp-concave-optimization online-optimizationarXiv posted 2 days ago

The optimal-runtime conjecture for stochastic exp-concave optimization