2023-04-11-chen23g.md

title	software	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
Reducing Discretization Error in the Frank-Wolfe Method	https://github.com/zoechen369/Reducing-Discretization-Error-in-the-Frank-Wolfe-Method	The Frank-Wolfe algorithm is a popular method in structurally constrained machine learning applications, due to its fast per-iteration complexity. However, one major limitation of the method is a slow rate of convergence that is difficult to accelerate due to erratic, zig-zagging step directions, even asymptotically close to the solution. We view this as an artifact of discretization; that is to say, the Frank-Wolfe flow, which is its trajectory at asymptotically small step sizes, does not zig-zag, and reducing discretization error will go hand-in-hand in producing a more stabilized method, with better convergence properties. We propose two improvements: a multistep Frank-Wolfe method that directly applies optimized higher-order discretization schemes; and an LMO-averaging scheme with reduced discretization error, and whose local convergence rate over general convex sets accelerates from a rate of $O(1/k)$ to up to $O(1/k^{3/2})$.	Regular Papers	inproceedings	Proceedings of Machine Learning Research	PMLR	2640-3498	chen23g	0	Reducing Discretization Error in the Frank-Wolfe Method	9697	9727	9697-9727	9697	false	Chen, Zhaoyue and Sun, Yifan	given family Zhaoyue Chen given family Yifan Sun	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/chen23g/chen23g.pdf