2024-09-12-hong24a.md

title	abstract	openreview	section	layout	series	publisher	issn	id	month	tex_title	firstpage	lastpage	page	order	cycles	bibtex_author	author	date	address	container-title	volume	genre	issued	pdf	extras
Revisiting Convergence of AdaGrad with Relaxed Assumptions	In this study, we revisit the convergence of AdaGrad with momentum (covering AdaGrad as a special case) on non-convex smooth optimization problems. We consider a general noise model where the noise magnitude is controlled by the function value gap together with the gradient magnitude. This model encompasses a broad range of noises including bounded noise, sub-Gaussian noise, affine variance noise and the expected smoothness, and it has been shown to be more realistic in many practical applications. Our analysis yields a probabilistic convergence rate which, under the general noise, could reach at $\tilde{\mathcal{O}}(1/\sqrt{T})$. This rate does not rely on prior knowledge of problem-parameters and could accelerate to $\tilde{\mathcal{O}}(1/T)$ where $T$ denotes the total number iterations, when the noise parameters related to the function value gap and noise level are sufficiently small. The convergence rate thus matches the lower rate for stochastic first-order methods over non-convex smooth landscape up to logarithm terms [Arjevani et al., 2023]. We further derive a convergence bound for AdaGrad with momentum, considering the generalized smoothness where the local smoothness is controlled by a first-order function of the gradient norm.	AlYO5cq1fG	Papers	inproceedings	Proceedings of Machine Learning Research	PMLR	2640-3498	hong24a	0	Revisiting Convergence of AdaGrad with Relaxed Assumptions	1727	1750	1727-1750	1727	false	Hong, Yusu and Lin, Junhong	given family Yusu Hong given family Junhong Lin	2024-09-12		Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence	244	inproceedings	date-parts 2024 9 12	https://raw.githubusercontent.com/mlresearch/v244/main/assets/hong24a/hong24a.pdf