Sharper Bounds for Proximal Gradient Algorithms with Errors
分析了凸复合问题中近端梯度算法在梯度与近端计算不精确时的收敛性，提出了更紧的概率界，用于验证带早停、低精度和近端误差的稀疏控制模型预测控制问题。
.We analyze the convergence of the proximal gradient algorithm for convex composite problems in the presence of gradient and proximal computational inaccuracies. We generalize the deterministic analysis to the quasi-Fejér case and quantify the uncertainty incurred from approximate computing and early termination errors. We propose new probabilistic tighter bounds that we use to verify a simulated Model Predictive Control (MPC) with sparse controls problem solved with early termination, reduced precision, and proximal errors. We also show how the probabilistic bounds are more suitable than the deterministic ones for algorithm verification and more accurate for application performance guarantees. Under mild statistical assumptions, we also prove that some cumulative error terms follow a martingale property. And conforming to observations, e.g., in [M. Schmidt, N. L. Roux, and F. R. Bach, Convergence rates of inexact proximal-gradient methods for convex optimization, in Advances in Neural Information Processing Systems, 2011, pp. 1458–1466], we also show how the acceleration of the algorithm amplifies the gradient and proximal computational errors.Keywordsconvex optimizationproximal gradient descentapproximate algorithmsMSC codes49M3765K0590C25