2023-04-11-chen23i.md

title	abstract	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
HeteRSGD: Tackling Heterogeneous Sampling Costs via Optimal Reweighted Stochastic Gradient Descent	One implicit assumption in current stochastic gradient descent (SGD) algorithms is the identical cost for sampling each component function of the finite-sum objective. However, there are applications where the costs differ substantially, for which SGD schemes with uniform sampling invoke a high sampling load. We investigate the use of importance sampling (IS) as a cost saver in this setting, in contrast to its traditional use for variance reduction. The key ingredient is a novel efficiency metric for IS that advocates low sampling costs while penalizing high gradient variances. We then propose HeteRSGD, an SGD scheme that performs gradient sampling according to optimal probability weights stipulated by the metric, and establish theories on its optimal asymptotic and finite-time convergence rates among all possible IS-based SGD schemes. We show that the relative efficiency gain of HeteRSGD can be arbitrarily large regardless of the problem dimension and number of components. Our theoretical results are validated numerically for both convex and nonconvex problems.	Regular Papers	inproceedings	Proceedings of Machine Learning Research	PMLR	2640-3498	chen23i	0	HeteRSGD: Tackling Heterogeneous Sampling Costs via Optimal Reweighted Stochastic Gradient Descent	10732	10781	10732-10781	10732	false	Chen, Ziang and Lu, Jianfeng and Qian, Huajie and Wang, Xinshang and Yin, Wotao	given family Ziang Chen given family Jianfeng Lu given family Huajie Qian given family Xinshang Wang given family Wotao Yin	2023-04-11		Proceedings of The 26th International Conference on Artificial Intelligence and Statistics	206	inproceedings	date-parts 2023 4 11	https://proceedings.mlr.press/v206/chen23i/chen23i.pdf