分布式随机双层优化：复杂度改进与异构性分析

本文研究一类具有个性化内层目标的非凸-强凸分布式随机双层优化（DSBO）问题。现有算法大多需要超梯度估计的计算循环，导致效率低下，且尚未明确量化数据异构性对双层问题收敛的影响。

针对这些问题，提出LoPA算法——一种无循环的个性化分布式方法，通过跟踪机制迭代逼近内层解和Hessian逆矩阵，无需额外计算循环。理论分析明确量化了节点间异构性（记为b），在无需局部超梯度有界假设下，建立了O(1/((1-ρ)K) + (b/√m)^(2/3)/((1-ρ)^(2/3)K^(2/3)) + 1/√K(σ_p+1/√m σ_c))的次线性收敛率，其中σ_p和σ_c分别表示内外层变量的梯度采样方差。进一步结合梯度跟踪方案消除数据异构性影响，获得改进的O(1/((1-ρ)^2K) + 1/√K(σ_p+1/√m σ_c))收敛率。

LoPA达到O(ϵ⁻²)的计算复杂度（与通信复杂度匹配），优于现有DSBO算法。数值实验验证了算法的有效性。