Bounded Oracle Error in Nonconvex Stochastic Optimization
Arjevani et al. asked whether almost-surely bounded oracle error permits a better rate than bounded variance for smooth nonconvex stochastic optimization. It does not: every randomized adaptive algorithm still needs Omega(dL/eps^2 + dL sigma^2/eps^4) queries, matching the standard upper bound.
- Result
- Proved
- Status
- Resolved
- AI contribution
- AI-discovered
- Method
- Argument
- Field
- Stochastic optimization
- Posed by
- Yossi Arjevani, Yair Carmon, John C. Duchi, Dylan J. Foster, Nathan Srebro, Blake Woodworth
- Year posed
- 2023
- Years open
- 3y
- Solved
- 2026-08-10
- Model
- GPT-5.6 Sol
- Vendor
- OpenAI
- Collaborators
- Jikai Jin
- Verification
- Unreviewed
- Publication
- Preprint
- Significance
- 12 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What the AI did
Stated in the abstract itself, not buried in an acknowledgment: "The proof was independently generated with GPT-5.6 Sol in Codex's Ultra mode during a two-hour session. The human author supplied the prompt and was responsible only for checking the proof and revising and polishing the manuscript."
Verification
A preprint days old, with no independent review.
Source
- PaperarXiv