<p>Distributed optimization problems usually face inexact communication issues induced by channel noise, communication quantization or differential privacy protection. Most existing algorithms need a two-timescale setting of the stepsize of gradient descent and the parameter of noise suppression to ensure the convergence to the optimal solution. In this paper, we propose two single-timescale algorithms, VRA-DGT and VRA-DSGT, for distributed deterministic and stochastic optimization problems with inexact communication respectively. VRA-DGT integrates the Variance-Reduced Aggregation (VRA) mechanism with the distributed gradient tracking framework, which achieves the convergence rate of <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\mathcal {O}\left( k^{-1}\right) $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mfenced close=")" open="("> <msup> <mi>k</mi> <mrow> <mo>-</mo> <mn>1</mn> </mrow> </msup> </mfenced> </mrow> </math></EquationSource> </InlineEquation> in the mean square sense and <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\mathcal {O}\left( \frac{\ln (k+1)}{k^b}\right) $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mfenced close=")" open="("> <mfrac> <mrow> <mo>ln</mo> <mo stretchy="false">(</mo> <mi>k</mi> <mo>+</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> <msup> <mi>k</mi> <mi>b</mi> </msup> </mfrac> </mfenced> </mrow> </math></EquationSource> </InlineEquation>, <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\forall b\in (0.5,1)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo>∀</mo> <mi>b</mi> <mo>∈</mo> <mo stretchy="false">(</mo> <mn>0.5</mn> <mo>,</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> in the almost sure sense when the objective function is strongly convex and smooth. For stochastic optimization problems, VRA-DSGT, where a hybrid variance-reduced technique has been introduced in VRA-DGT, maintains the convergence rate of <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\mathcal {O}\left( k^{-1}\right) $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mfenced close=")" open="("> <msup> <mi>k</mi> <mrow> <mo>-</mo> <mn>1</mn> </mrow> </msup> </mfenced> </mrow> </math></EquationSource> </InlineEquation> in the mean square sense and <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$\mathcal {O}\left( \frac{\ln (k+1)}{k^b}\right) $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mfenced close=")" open="("> <mfrac> <mrow> <mo>ln</mo> <mo stretchy="false">(</mo> <mi>k</mi> <mo>+</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> <msup> <mi>k</mi> <mi>b</mi> </msup> </mfrac> </mfenced> </mrow> </math></EquationSource> </InlineEquation>, <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$\forall b\in (0.5,1)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo>∀</mo> <mi>b</mi> <mo>∈</mo> <mo stretchy="false">(</mo> <mn>0.5</mn> <mo>,</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> in the almost sure sense. Simulated experiments on a logistic regression problem with real-world data verify the effectiveness of the proposed algorithms.</p>

Efficient gradient tracking algorithms for distributed optimization problems with inexact communication

期刊论文
发表日期：

2026年2月21日

查看全文

Shengchao Zhao,
Yongchao Liu

摘要

Distributed optimization problems usually face inexact communication issues induced by channel noise, communication quantization or differential privacy protection. Most existing algorithms need a two-timescale setting of the stepsize of gradient descent and the parameter of noise suppression to ensure the convergence to the optimal solution. In this paper, we propose two single-timescale algorithms, VRA-DGT and VRA-DSGT, for distributed deterministic and stochastic optimization problems with inexact communication respectively. VRA-DGT integrates the Variance-Reduced Aggregation (VRA) mechanism with the distributed gradient tracking framework, which achieves the convergence rate of $\mathcal {O}\left( k^{-1}\right) $ $O (k^{- 1})$ in the mean square sense and $\mathcal {O}\left( \frac{\ln (k+1)}{k^b}\right) $ $O (\frac{ln (k + 1)}{k^{b}})$ , $\forall b\in (0.5,1)$ $\forall b \in (0.5, 1)$ in the almost sure sense when the objective function is strongly convex and smooth. For stochastic optimization problems, VRA-DSGT, where a hybrid variance-reduced technique has been introduced in VRA-DGT, maintains the convergence rate of $\mathcal {O}\left( k^{-1}\right) $ $O (k^{- 1})$ in the mean square sense and $\mathcal {O}\left( \frac{\ln (k+1)}{k^b}\right) $ $O (\frac{ln (k + 1)}{k^{b}})$ , $\forall b\in (0.5,1)$ $\forall b \in (0.5, 1)$ in the almost sure sense. Simulated experiments on a logistic regression problem with real-world data verify the effectiveness of the proposed algorithms.