Silver Rate Is (Almost) Optimal for Gradient Descent Acceleration
The paper claims matching lower bounds that pin down the best possible polynomial rates for nonnegative preset GD step schedules.
Ye and Liu study smooth convex optimization under predetermined nonnegative stepsizes. They prove a non-anytime lower bound of roughly `n^-p_sil`, with `p_sil = log_2(1 + sqrt(2))`. For anytime schedules, they show every infinite schedule hits infinitely many horizons with a weaker lower-bound exponent. The abstract says these results, combined with prior upper bounds, determine the optimal convergence exponents in both settings. ArXiv · AI/CL/LG's note
Ye and Liu study smooth convex optimization under predetermined nonnegative stepsizes. They prove a non-anytime lower bound of roughly `n^-p_sil`, with `p_sil = log_2(1 + sqrt(2))`. For anytime schedules, they show every infinite schedule hits infinitely many horizons with a weaker lower-bound exponent. The abstract says these results, combined with prior upper bounds, determine the optimal convergence exponents in both settings. ArXiv · AI/CL/LG's note
score 4