Improved Gradient Descent Lower Bounds Beyond Nesterov
Predetermined stepsizes cannot push gradient descent as far as earlier bounds left open.
Ye and Liu prove new lower bounds for smooth convex optimization: $\Omega(n^{-1.6342})$ in the non-anytime setting and $\Omega(n^{-1.2408})$ in the anytime setting. The paper says these improve prior lower bounds from Ma and Chen and from Tsai et al. It also claims the anytime result, compared with known silver-schedule rates, separates what is achievable in anytime versus non-anytime regimes. ArXiv · AI/CL/LG's note
Ye and Liu prove new lower bounds for smooth convex optimization: $\Omega(n^{-1.6342})$ in the non-anytime setting and $\Omega(n^{-1.2408})$ in the anytime setting. The paper says these improve prior lower bounds from Ma and Chen and from Tsai et al. It also claims the anytime result, compared with known silver-schedule rates, separates what is achievable in anytime versus non-anytime regimes. ArXiv · AI/CL/LG's note
score 5