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 Plus annual

Presents the access of premium content as premium feature

Premium Content

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 Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We provide a simple convergence proof for AdaGrad optimizing non-convexobjectives under only affine noise variance and bounded smoothness assumptions.The proof is essentially based on a novel auxiliary function $\xi$ that helpseliminate the complexity of handling the correlation between the numerator anddenominator of AdaGrad's update. Leveraging simple proofs, we are able toobtain tighter results than existing results \citep{faw2022power} and extendthe analysis to several new and important cases. Specifically, for theover-parameterized regime, we show that AdaGrad needs only$\mathcal{O}(\frac{1}{\varepsilon^2})$ iterations to ensure the gradient normsmaller than $\varepsilon$, which matches the rate of SGD and significantlytighter than existing rates $\mathcal{O}(\frac{1}{\varepsilon^4})$ for AdaGrad.We then discard the bounded smoothness assumption and consider a realisticassumption on smoothness called $(L_0,L_1)$-smooth condition, which allowslocal smoothness to grow with the gradient norm. Again based on the auxiliaryfunction $\xi$, we prove that AdaGrad succeeds in converging under$(L_0,L_1)$-smooth condition as long as the learning rate is lower than athreshold. Interestingly, we further show that the requirement on learning rateunder the $(L_0,L_1)$-smooth condition is necessary via proof by contradiction,in contrast with the case of uniform smoothness conditions where convergence isguaranteed regardless of learning rate choices. Together, our analyses broadenthe understanding of AdaGrad and demonstrate the power of the new auxiliaryfunction in the investigations of AdaGrad.

Convergence of AdaGrad for Non-convex Objectives: Simple Proofs and Relaxed Assumptions