Analysis of biased stochastic gradient descent using sequential semidefinite programs

• 成果类型: Article
• 署名作者: Hu, Bin; Seiler, Peter; Lessard, Laurent
• 署名单位: University of Illinois System; University of Illinois Urbana-Champaign; University of Michigan System; University of Michigan; University of Wisconsin System; University of Wisconsin Madison
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-020-01486-1
• 发表日期: 2021
• 页码: 383-408
• 关键词: worst-case performance; 1st-order methods; convex; optimization; complexity

摘要

We present a convergence rate analysis for biased stochastic gradient descent (SGD), where individual gradient updates are corrupted by computation errors. We develop stochastic quadratic constraints to formulate a small linear matrix inequality (LMI) whose feasible points lead to convergence bounds of biased SGD. Based on this LMI condition, we develop a sequential minimization approach to analyze the intricate trade-offs that couple stepsize selection, convergence rate, optimization accuracy, and robustness to gradient inaccuracy. We also provide feasible points for this LMI and obtain theoretical formulas that quantify the convergence properties of biased SGD under various assumptions on the loss functions.