Research map / Learning theory and algorithms / Sample complexity
Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothness
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the new softmax-based, randomized-smoothed hard function construction instead of the prior randomized-smoothing lower-bound construction | Randomized p-th-order smooth convex optimization · p-th-order smooth convex optimization | oracle-query lower-bound exponent: \Omega_p\left(\left({L_pR^{p+1}}/{\epsilon}\right)^{2/(5p+1)}\right) -> \Omega_p\left(\left( {L_pR^{p+1}}/{\epsilon} \ri | Helped |
| Extend the information-hiding lower-bound construction to quantum oracle queries | Quantum p-th-order smooth convex optimization · p-th-order smooth convex optimization | oracle-query lower bound: k queries | Helped |
| Extend the information-hiding lower-bound construction to polynomially many parallel queries per round | Parallel randomized p-th-order smooth convex optimization · p-th-order smooth convex optimization | query rounds lower bound: k rounds | Helped |
Closest papers by meaning
- Tight Lower Bounds under Asymmetric High-Order Hölder Smoothness and Uniform Convexity (ICLR 2025 · similarity 0.90)
- Near-Optimal Quantum Algorithm for Minimizing the Maximal Loss (ICLR 2024 · similarity 0.90)
- Quantum Algorithms and Lower Bounds for Finite-Sum Optimization (ICML 2024 · similarity 0.89)
- Complexity Lower Bounds of Adaptive Gradient Algorithms for Non-convex Stochastic Optimization under Relaxed Smoothness (ICLR 2025 · similarity 0.89)
- Isotropic Noise in Stochastic and Quantum Convex Optimization (NeurIPS 2025 · similarity 0.88)
- Quantum Algorithms for Non-smooth Non-convex Optimization (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.