<p>The demand for decentralized data collection and distributed computing has surged across statistics, machine learning, and image science. In this landscape, the&#xa0;<i>alternating direction method of multipliers</i>&#xa0;(<Emphasis FontCategory="NonProportional">ADMM</Emphasis>) has emerged as a cornerstone for solving distributed convex optimization problems. Despite its widespread use, however, the precise iterative dynamics of&#xa0;<Emphasis FontCategory="NonProportional">ADMM</Emphasis> remain poorly understood. Using dimensional analysis, we derive high-resolution ordinary differential equations (ODEs) that capture a key phenomenon in&#xa0;<Emphasis FontCategory="NonProportional">ADMM</Emphasis>, which we term the <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\lambda \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>λ</mi> </math></EquationSource> </InlineEquation>-correction. This effect causes the trajectory of the discrete algorithm to deviate from the constrained hyperplane. We then employ Lyapunov analysis to study the convergence properties of the resulting high-resolution ODEs and extend these insights to the discrete&#xa0;<Emphasis FontCategory="NonProportional">ADMM</Emphasis> algorithm. Our analysis reveals that the numerical error introduced by the implicit discretization scheme plays a central role in determining both the convergence rate and the monotonicity of&#xa0;<Emphasis FontCategory="NonProportional">ADMM</Emphasis> iterations. In particular, when one component of the objective function is strongly convex, the ergodic average of&#xa0;<Emphasis FontCategory="NonProportional">ADMM</Emphasis> iterates achieves a convergence rate of <i>O</i>(1/<i>N</i>), where <i>N</i> denotes the number of iterations.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Understanding the ADMM Algorithm via High-Resolution Differential Equations

  • Bowen Li,
  • Bin Shi

摘要

The demand for decentralized data collection and distributed computing has surged across statistics, machine learning, and image science. In this landscape, the alternating direction method of multipliers (ADMM) has emerged as a cornerstone for solving distributed convex optimization problems. Despite its widespread use, however, the precise iterative dynamics of ADMM remain poorly understood. Using dimensional analysis, we derive high-resolution ordinary differential equations (ODEs) that capture a key phenomenon in ADMM, which we term the \(\lambda \) λ -correction. This effect causes the trajectory of the discrete algorithm to deviate from the constrained hyperplane. We then employ Lyapunov analysis to study the convergence properties of the resulting high-resolution ODEs and extend these insights to the discrete ADMM algorithm. Our analysis reveals that the numerical error introduced by the implicit discretization scheme plays a central role in determining both the convergence rate and the monotonicity of ADMM iterations. In particular, when one component of the objective function is strongly convex, the ergodic average of ADMM iterates achieves a convergence rate of O(1/N), where N denotes the number of iterations.