English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We study the statistical and computational complexities of the Polyak stepsize gradient descent algorithm under generalized smoothness and Lojasiewiczconditions of the population loss function, namely, the limit of the empiricalloss function when the sample size goes to infinity, and the stability betweenthe gradients of the empirical and population loss functions, namely, thepolynomial growth on the concentration bound between the gradients of sampleand population loss functions. We demonstrate that the Polyak step sizegradient descent iterates reach a final statistical radius of convergencearound the true parameter after logarithmic number of iterations in terms ofthe sample size. It is computationally cheaper than the polynomial number ofiterations on the sample size of the fixed-step size gradient descent algorithmto reach the same final statistical radius when the population loss function isnot locally strongly convex. Finally, we illustrate our general theory underthree statistical examples: generalized linear model, mixture model, and mixedlinear regression model.

Towards Statistical and Computational Complexities of Polyak Step Size Gradient Descent