REVIEW 1 cited by
The exact information-based complexity of smooth convex minimization
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
read the original abstract
We obtain a new lower bound on the information-based complexity of first-order minimization of smooth and convex functions. We show that the bound matches the worst-case performance of the recently introduced Optimized Gradient Method, thereby establishing that the bound is tight and can be realized by an efficient algorithm. The proof is based on a novel construction technique of smooth and convex functions.
Forward citations
Cited by 1 Pith paper
-
A lower bound for stepsize-based acceleration of gradient descent
Gradient descent with arbitrary predetermined nonnegative step size schedules has worst-case last-iterate convergence rate at least Omega(T^{-p}) for every p > sqrt(2+sqrt(3)) approximately 1.9319.
Discussion (0). Continue with ORCID to comment.