【论文考古】分布式优化|【论文考古】分布式优化 Communication Complexity of Convex Optimization
J. N. Tsitsiklis and Z.-Q. Luo, “Communication complexity of convex optimization,” Journal of Complexity, vol. 3, no. 3, pp. 231–243, Sep. 1987, doi: 10.1016/0885-064x(87)90013-6.
问题描述
两个用户各自有一个凸函数\(f_i\),相互交互最少的二进制消息,从而找到\(f_i+f_2\)的最优点
基本定义
- \(\mathscr{F}\):定义域\([0,1]^n\)上凸函数的一个集合
- \(I(f;
\epsilon)\in[0,1]^n\):定义域上,给定误差\(\epsilon\)后\(f\)最小值对应的自变量集合(\(f(x) \leq f(y)+\varepsilon, \forall y \in[0,1]^{n}\))
- \(C(f_1,f_2;
\epsilon,\pi)\):在协议\(\pi\)和精度\(\epsilon\)下,两个函数通过交换信息找到集合\(I\left(f_{1}+f_{2} ;
\varepsilon\right)\)中元素所需的消息数目
- \(C(\mathscr{F} ;
\varepsilon, \pi)\):该协议在最坏情况下找到目标所需交换的消息数量
\[C(\mathscr{F} ; \varepsilon, \pi)=\sup _{f_{1}, f_{2} \in \mathscr{F}} C\left(f_{1}, f_{2} ; \varepsilon, \pi\right) \]
- \(C(\mathscr{F} ;
\varepsilon)\):最优协议下所需的交换消息的数量,又称为\(\epsilon\)-communication complexity
\[C(\mathscr{F} ; \varepsilon)=\inf _{\pi \in \mathrm{I}(\varepsilon)} C(\mathscr{F} ; \varepsilon, \pi) \]
- 消息传输的模式,通信\(T\)次
- 每次传播信息的计算
\[m_{i}(t)=M_{i, t}\left(f_{i}, m_{j}(0), \ldots, m_{j}(t-1)\right) \]
- 最终最优点的确定
\[x=Q\left(f_{1}, m_{2}(0), \ldots ., m_{2}(T-1)\right) \]
- 每次传播信息的计算
Lemma 1:\(\text { If } \mathscr{F} \subset \mathscr{G} \mathscr{\text { then }} C(\mathscr{F} ; \varepsilon) \leq C(\mathscr{G}; \varepsilon)\) 简单函数所需传输的消息数量更少
Proposition:\(C\left(\mathcal{F}_{Q} ; \varepsilon\right) \geq O(n(\log n+\log (1 / \varepsilon)))\) 【【论文考古】分布式优化|【论文考古】分布式优化 Communication Complexity of Convex Optimization】其中\(\mathcal{F}_{Q}\)表示带有\(f(x)=\|x-x^\star\|^2\)形式的二次函数的集合,其中\(x^\star\in [0,1]^n\)。根据Lemma知道,选择最简单的函数能找到下界。考虑\(f_1=0\),所以\(f_2\)的最小值需要控制在\(\epsilon^{1/2}\)的精度内,因此至少需要\(\left(A n / \varepsilon^{1 / 2}\right)^{B n}\)个半径为\(\epsilon^{1/2}\)Euclidean ball来覆盖中\([0,1]^n\)。因此最终\(Q\)的解集的势至少就是\(\left(A n / \varepsilon^{1 / 2}\right)^{B n}\)。由于函数的值域的势不会超过定义域的势,所以\(Q\)的解集的势不超过\(2^T\),也就有\(T \geq O(n(\log n+\log (1 / \varepsilon))\)。
Naive Upper Bounds
The method of the centers of gravity (MCG) 在求解凸函数势需要最小次数的梯度计算。将MCG方法扩展到了分布式的场景,得到上界。
一维下的最优算法
算法核心在于用消息指示不同的计算步骤,而不是传递数据。
算法首先定义两个区间,分别表示
- \([a,b]\):\(f_1+f_2\)最优点所在的区间,\(x^\star \in [a,b]\)
- \([c,d]\):\(f'(x^{\star})\),\(f'_1(\frac{a+b}{2})\),\(f'_2(\frac{a+b}{2})\)所在的区间
- \(f'_1(\frac{a+b}{2})\in [c,\frac{c+d}{2}]\)则\(m_1=0\),否则\(m_1=1\)
- \(-f'_2(\frac{a+b}{2})\in[c,\frac{c+d}{2}]\)则\(m_2=0\),否则\(m_2=1\)
- \((f_1+f_2)'=f'_1+f'_2\),导值的正负性来找最小值
- 通过压缩\((f_1+f_2)'(\frac{a+b}{2})\)趋于零,从而确定\(\frac{a+b}{2}\)就是最小值
import numpy as np
import matplotlib.pyplot as pltdef f1(x):
return (x - 2) ** 2def df1(x):
return 2 * (x - 2)def f2(x):
return (x + 1) ** 2def df2(x):
return 2 * (x + 1)a, b, c, d = -1, 1, -3, 3
eps = 0.1while b - a > eps and d - c > eps:
if df1((a + b) / 2) <= (c + d) / 2:
m1 = 0
else:
m1 = 1if -df2((a + b) / 2) <= (c + d) / 2:
m2 = 0
else:
m2 = 1if m1 == 0 and m2 == 1:
a = (a + b) / 2
elif m1 == 1 and m2 == 0:
b = (a + b) / 2
elif m1 == 1 and m2 == 1:
c = (c + d) / 2
elif m1 == 0 and m2 == 0:
d = (c + d) / 2print('传输消息+2')
print(a, b, c, d)if b - a <= eps:
optimum = a + eps
else:
optimum = f1((a + b) / 2) + f2((a + b) / 2)print(optimum)
print(f1(0.5) + f2(0.5))
# 直观画图结果
x = np.linspace(-1, 2, 100)
y = f1(x) + f2(x)
plt.plot(x, y)
plt.show()
推荐阅读
- Python3+PyMysql
- 程序员|【大牛疯狂教学】2020最全的BAT大厂面试题整理改版
- C语言可重入函数和不可重入函数
- C++ Primer Plus(预备知识)
- 微信小程序开发|微信小程序周报(第七期)
- Vue可左右滑动按钮组组件使用详解
- hive|hive(导入CSV文件)
- #|美团外卖——物流论文小笔记(Python实现)
- 【面试题】实现文件夹中文件的遍历输出
- 【职业规划】该如何选择职业方向(性能?自动化?测开?,学习选择python、java?)