-
摘要: 机器学习中的诸多非凸优化问题, 如鲁棒相位恢复、低秩矩阵补全以及稀疏字典学习等, 本质上可归结为弱凸优化问题. 然而, 弱凸优化问题固有的非凸特性使得此类问题的求解极具挑战. 此外, 由于系统复杂度和问题规模的增加以及相关参数的分布式存储需求, 传统的基于单个个体的集中式计算框架难以高效求解此类问题. 针对上述挑战, 设计一种分布式镜像下降算法, 并从Bregman-Moreau包络的角度分析其收敛性, 证明算法的收敛速度为$ \mathrm{O}(\ln K/\sqrt{K}) $, 其中$K$为算法的迭代步数. 进一步地, 考虑目标函数梯度信息难以精确获取的情形, 采用正交随机方向矩阵法进行梯度估计. 相较于传统的基于随机向量的方法, 该方法利用多维方向信息进行估计, 从而显著提高梯度信息的估计精度和效率. 基于高效的梯度信息估计, 提出一种分布式零阶镜像下降算法, 并获得与已知精确梯度信息情形下相一致的收敛速度. 最后, 通过基于相位恢复问题的数值仿真和实验验证了所提出的两种算法的有效性.
-
关键词:
- 分布式优化 /
- 弱凸 /
- 镜像下降 /
- Bregman-Moreau包络 /
- 零阶梯度
Abstract: Many non-convex optimization problems in machine learning, such as robust phase retrieval, low-rank matrix recovery, and sparse dictionary learning, can be fundamentally modeled as weakly convex optimization problems. However, the inherent non-convex property of weakly convex optimization makes solving such problems particularly challenging. Besides, with the increase of systems＇ complexity and problem scale, as well as distributed storage of related parameters, traditional centralized computing frameworks based on a single node are difficult to solve such problems efficiently. To address these challenges, we design a distributed mirror descent algorithm and analyze its convergence from the perspective of the Bregman-Moreau envelope. It has been proven that the convergence rate of the algorithm is $ \mathrm{O}(\ln K/\sqrt{K}) $, where $K$ is the number of iterations of the algorithm. Moreover, considering that exact gradient information of the objective function is difficult to obtain, we propose a gradient estimation scheme based on orthogonal random direction matrices. Compared to conventional methods based on random vectors, this method utilizes multi-dimensional directional information for estimation, significantly improving the accuracy and efficiency of gradient information estimation. Furthermore, we propose a distributed zeroth-order mirror descent algorithm based on the effective gradient information estimation result, and achieve a comparable convergence to the algorithm designed based on known exact gradient information. Finally, we validate the effectiveness of the two proposed algorithms by numerical simulations and experiments based on the phase retrieval problem.1)1 1 考虑非光滑凸函数$ h(\cdot):{\bf R}_{}^{m}\rightarrow {\bf R} $, $ {{\mathit{\boldsymbol{u}}}} $为其定义域$ {\rm dom} h $中一点. 若向量$ {{\mathit{\boldsymbol{g}}}}\in{\bf R}^{m} $满足$ h({{\mathit{\boldsymbol{v}}}})\ge h({{\mathit{\boldsymbol{u}}}})+ \langle {{\mathit{\boldsymbol{g}}}}, {{\mathit{\boldsymbol{v}}}}-{{\mathit{\boldsymbol{u}}}} \rangle $, $ \forall {{\mathit{\boldsymbol{v}}}}\in {\rm dom} h $, 则称$ {{\mathit{\boldsymbol{g}}}} $为函数$ h(\cdot) $在点$ {{\mathit{\boldsymbol{u}}}} $处的一个次梯度; 此外, 记$ \partial h({{\mathit{\boldsymbol{u}}}})=\{{{\mathit{\boldsymbol{g}}}}|{{\mathit{\boldsymbol{g}}}}\in{\bf R}^{m}, \;h({{\mathit{\boldsymbol{v}}}})\ge $$ h({{\mathit{\boldsymbol{u}}}})+ \langle {{\mathit{\boldsymbol{g}}}}, \;{{\mathit{\boldsymbol{v}}}}-{{\mathit{\boldsymbol{u}}}} \rangle, \forall {{\mathit{\boldsymbol{v}}}} \in {\rm dom} h\} $为函数$ h(\cdot) $在点$ {{\mathit{\boldsymbol{u}}}} $处的次梯度集合[29]. -
-
[1] 衣鹏, 洪奕光. 分布式合作优化及其应用. 中国科学: 数学, 2016, 46(10): 1547−1564Yi Peng, Hong Yi-Guang. Distributed cooperative optimization and its applications. Scientia Sinica Mathematica, 2016, 46(10): 1547−1564 [2] 谢佩, 游科友, 洪奕光, 谢立华. 网络化分布式凸优化算法研究进展. 控制理论与应用, 2018, 35(7): 918−927 doi: 10.7641/CTA.2018.80205Xie Pei, You Ke-You, Hong Yi-Guang, Xie Li-Hua. A survey of distributed convex optimization algorithms over networks. Control Theory and Applications, 2018, 35(7): 918−927 doi: 10.7641/CTA.2018.80205 [3] Nedić A, Liu J. Distributed optimization for control. Annual Review of Control, Robotics, and Autonomous Systems, 2018, 1(1): 77−103 [4] Yang T, Yi X L, Wu J F, Yuan Y, Wu D, Meng Z Y, et al. A survey of distributed optimization. Annual Reviews in Control, 2019, 47: 278−305 doi: 10.1016/j.arcontrol.2019.05.006 [5] 杨涛, 柴天佑. 分布式协同优化的研究现状与展望. 中国科学: 技术科学, 2020, 50(11): 1414−1425 doi: 10.1360/SST-2020-0040Yang Tao, Chai Tian-You. Research status and prospects of distributed collaborative optimization. Scientia Sinica Technologica, 2020, 50(11): 1414−1425 doi: 10.1360/SST-2020-0040 [6] 邓文, 李伟健, 曾宪琳, 洪奕光. 矩阵方程的分布式求解算法研究概述. 控制理论与应用, 2021, 38(11): 1695−1706 doi: 10.7641/CTA.2021.10671Deng Wen, Li Wei-Jian, Zeng Xian-Lin, Hong Yi-Guang. A survey of distributed algorithms for solving matrix equations. Control Theory and Applications, 2021, 38(11): 1695−1706 doi: 10.7641/CTA.2021.10671 [7] 杨涛, 徐磊, 易新蕾, 张圣军, 陈蕊娟, 李渝哲. 基于事件触发的分布式优化算法. 自动化学报, 2022, 48(1): 133−143Yang Tao, Xu Lei, Yi Xin-Lei, Zhang Sheng-Jun, Chen Rui-Juan, Li Yu-Zhe. Event-triggered distributed optimization algorithms. Acta Automatica Sinica, 2022, 48(1): 133−143 [8] Yang S F, Liu Q S, Wang J. A multi-agent system with a proportional-integral protocol for distributed constrained optimization. IEEE Transactions on Automatic Control, 2016, 62(7): 3461−3467 [9] Zhu Y N, Yu W W, Wen G H, Chen G R. Projected primal-dual dynamics for distributed constrained nonsmooth convex optimization. IEEE Transactions on Cybernetics, 2018, 50(4): 1776−1782 [10] Yuan K, Ling Q, Yin W T. On the convergence of decentralized gradient descent. SIAM Journal on Optimization, 2016, 26(3): 1835−1854 doi: 10.1137/130943170 [11] Pu S, Shi W, Xu J M, Nedić A. Push-pull gradient methods for distributed optimization in networks. IEEE Transactions on Automatic Control, 2021, 66(1): 1−16 doi: 10.1109/TAC.2020.2972824 [12] Nedić A, Ozdaglar A, Parrilo P A. Constrained consensus and optimization in multi-agent networks. IEEE Transactions on Automatic Control, 2010, 55(4): 922−938 doi: 10.1109/TAC.2010.2041686 [13] Lei J L, Chen H F, Fang H T. Primal-dual algorithm for distributed constrained optimization. Systems and Control Letters, 2016, 96: 110−117 [14] Cheng S S, Liang S, Fan Y, Hong Y G. Distributed gradient tracking for unbalanced optimization with different constraint sets. IEEE Transactions on Automatic Control, 2023, 68(6): 3633−3640 [15] Beck A, Teboulle M. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 2003, 31(3): 167−175 doi: 10.1016/S0167-6377(02)00231-6 [16] Yuan D M, Hong Y G, Ho D W, Jiang G P. Optimal distributed stochastic mirror descent for strongly convex optimization. Automatica, 2018, 90: 196−203 doi: 10.1016/j.automatica.2017.12.053 [17] Yang Y, Jia Q S, Xu Z B, Guan X H, Spanos C J. Proximal ADMM for nonconvex and nonsmooth optimization. Automatica, 2022, 146: Article No. 110551 [18] Hou J, Zeng X L, Wang G, Sun J, Chen J. Distributed momentum-based Frank-Wolfe algorithm for stochastic optimization. IEEE/CAA Journal of Automatica Sinica, 2022, 10(3): 685−699 [19] Chen S X, Garcia A, Shahrampour S. On distributed nonconvex optimization: Projected subgradient method for weakly convex problems in networks. IEEE Transactions on Automatic Control, 2021, 67(2): 662−675 [20] Wei M L, Yu W W, Liu H Z, Xu Q. Distributed weakly convex optimization under random time-delay interference. IEEE Transactions on Network Science and Engineering, 2024, 11(1): 212−224 doi: 10.1109/TNSE.2023.3294414 [21] Wang Y H, Zhao W X, Hong Y G, Zamani M. Distributed subgradient-free stochastic optimization algorithm for nonsmooth convex functions over time-varying networks. SIAM Journal on Control and Optimization, 2019, 57(4): 2821−2842 doi: 10.1137/18M119046X [22] Pang Y P, Hu G Q. Randomized gradient-free distributed optimization methods for a multiagent system with unknown cost function. IEEE Transactions on Automatic Control, 2019, 65(1): 333−340 [23] Pang Y P, Hu G Q. Gradient-free distributed optimization with exact convergence. Automatica, 2022, 144: Article No. 110474 [24] Yi X L, Zhang S J, Yang T, Johansson K H. Zeroth-order algorithms for stochastic distributed nonconvex optimization. Automatica, 2022, 142: Article No. 110353 doi: 10.1016/j.automatica.2022.110353 [25] Xu L, Yi X L, Deng C, Shi Y, Chai T Y, Yang T. Quantized zeroth-order gradient tracking algorithm for distributed nonconvex optimization under Polyak-Łojasiewicz condition. IEEE Transactions on Cybernetics, 2024, 54(10): 5746−5758 doi: 10.1109/TCYB.2024.3384924 [26] Wang R Y, Fan Y, Cheng S S. Zeroth-order algorithm design with orthogonal direction for distributed weakly convex optimization. In: Proceedings of the 63rd IEEE Conference on Decision and Control (CDC2024). Milan, Italy: IEEE, 2024. [27] Juditsky A, Kwon J, Moulines É. Unifying mirror descent and dual averaging. Mathematical Programming, 2023, 199: 793−830 [28] Moreau J J. Proximitè et dualitè dans un espace hilbertien. Bull. De La Sociètè Mathèmatique De France, 1965, 93: 273−299 [29] 刘浩洋, 户将, 李勇锋, 文再文. 最优化: 建模、算法与理论. 北京: 高等教育出版社, 2020.Liu Hao-Yang, Hu Jiang, Li Yong-Feng, Wen Zai-Wen. Optimization: Modeling, Algorithm and Theory. Beijing: Higher Education Press, 2020. [30] Zhou W X, Zhou Y, Chen X L, Ning T T, Chen H Y, Guo Q, et al. Pancreatic cancer-targeting exosomes for enhancing immunotherapy and reprogramming tumor microenvironment. Biomaterials, 2021, 268: Article No. 120546 doi: 10.1016/j.biomaterials.2020.120546 [31] Ram S S, Nedić A, Veeravalli V V. Distributed stochastic subgradient projection algorithms for convex optimization. Journal of Optimization Theory and Applications, 2010, 147: 516−545 doi: 10.1007/s10957-010-9737-7 -
下载:
图(5)
计量
- 文章访问数: 341
- HTML全文浏览量: 117
- PDF下载量: 85
- 被引次数: 0
