检索结果-内蒙古大学图书馆

Linear convergence for distributed stochastic optimization with coupled inequality constraints

JOURNAL OF THE FRANKLIN INSTITUTE 2025年第1期362卷

作者： Du, Kaixin Meng, Min Li, Xiuxian Tongji Univ Shanghai Res Inst Intelligent Autonomous Syst Shanghai 201210 Peoples R China Tongji Univ Coll Elect & Informat Engn Dept Control Sci & Engn Shanghai 201804 Peoples R China Natl Key Lab Autonomous Intelligent Unmanned Syst Shanghai Peoples R China Minist Educ Frontiers Sci Ctr Intelligent Autonomous Syst Shanghai Peoples R China

This paper considers the distributed stochastic optimization problem over time-varying networks, in which agents aim to cooperatively minimize the expected value of the sum of their cost functions subject to coupled affine inequalities. Considering various stochastic factors and constraints on decisions inherent in physical environments, this problem has wide applications such as in smart grids, resource allocation and distributed machine learning. To solve this problem, a novel distributed stochastic primal-dual algorithm is devised by applying variance reduction and distributed tracking techniques. A complete and rigorous analysis shows that the developed algorithm linearly converges to the optimal solution in the mean square sense, and an explicit upper bound on the required constant stepsize is presented. Finally, a numerical example is conducted to illustrate the theoretical findings.

关键词： distributed stochastic optimization Coupled affine inequality constraints Primal-dual algorithm Variance reduction Linear convergence

来源：评论

学校读者我要写书评

暂无评论

distributed stochastic optimization with Compression for Non-Strongly Convex Objectives

引用

Computer Modeling in Engineering & Sciences 2024年第4期139卷 459-481页

作者： Xuanjie Li Yuedong Xu School of Information Science and Technology Fudan UniversityShanghaiChina

We are investigating the distributed optimization problem,where a network of nodes works together to minimize a global objective that is a finite sum of their stored local *** nodes exchange optimization parameters through the wireless network,large-scale training models can create communication bottlenecks,resulting in slower training *** address this issue,CHOCO-SGD was proposed,which allows compressing information with arbitrary precision without reducing the convergence rate for strongly convex objective ***,most convex functions are not strongly convex(such as logistic regression or Lasso),which raises the question of whether this algorithm can be applied to non-strongly convex *** this paper,we provide the first theoretical analysis of the convergence rate of CHOCO-SGD on non-strongly convex *** derive a sufficient condition,which limits the fidelity of compression,to guarantee ***,our analysis demonstrates that within the fidelity threshold,this algorithm can significantly reduce transmission burden while maintaining the same convergence rate order as its no-compression *** experiments further validate the theoretical findings by demonstrating that CHOCO-SGD improves communication efficiency and keeps the same convergence rate order *** experiments also show that the algorithm fails to converge with low compression fidelity and in time-varying ***,our study offers valuable insights into the potential applicability of CHOCO-SGD for non-strongly convex ***,we provide practical guidelines for researchers seeking to utilize this algorithm in real-world scenarios.

关键词： distributed stochastic optimization arbitrary compression fidelity non-strongly convex objective function

来源：评论

学校读者我要写书评

暂无评论

distributed stochastic optimization algorithm with non-consistent constraints in time-varying unbalanced networks

引用

JOURNAL OF THE FRANKLIN INSTITUTE-ENGINEERING AND APPLIED MATHEMATICS 2024年第14期361卷

作者： Zhu, Yanan Zhou, Zhipeng Miao, Guoying Nanjing Univ Informat Sci & Technol Sch Automat Nanjing 210044 Peoples R China

This study focuses on a class of distributed optimization problems with non-consistent local set constraints in time-varying unbalanced networks. Considering that each agent only has access to local gradient information with random errors, this paper proposes a distributed stochastic gradient projection algorithm. Under some conditions of random errors and a uniformly joint strongly connected topology, it is shown that the local decision states of all agents converge to a common optimal solution with a probability of one, achieving a sublinear convergence root rate of O (ln k / k ). Notably, under the condition that at least one local function exhibits strong convexity, the algorithm achieves a faster sublinear convergence rate of O (1/ k ). These theoretical results are validated through numerical simulations. Furthermore, this paper applies the proposed algorithm to solve for the unknown parameters in distributed linear regression problems with incomplete data. Numerical results indicate that the algorithm not only aligns with the convergence properties reported in existing literature but also demonstrates significant superiority in convergence speed. This important discovery not only lays a solid theoretical foundation for the further application and extension of the algorithm but also reveals its immense potential in solving practical problems.

关键词： distributed stochastic optimization Time-varying unbalanced networks Sublinear convergence rate Incomplete data

来源：评论

学校读者我要写书评

暂无评论

Differentially Private distributed stochastic optimization with Time-Varying Sample Sizes

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2024年第9期69卷 6341-6348页

作者： Wang, Jimin Zhang, Ji-Feng Univ Sci & Technol Beijing Sch Automat & Elect Engn Beijing 100083 Peoples R China Univ Sci & Technol Beijing Key Lab Knowledge Automat Ind Proc Minist Educ Beijing 100083 Peoples R China Chinese Acad Sci Inst Syst Sci Acad Math & Syst Sci Key Lab Syst & Control Beijing 100190 Peoples R China Univ Chinese Acad Sci Sch Math Sci Beijing 100049 Peoples R China

Differentially private distributed stochastic optimization has become a hot topic due to the need for privacy protection in distributed stochastic optimization. In this article, two-time scale stochastic approximation-type algorithms for differentially private distributed stochastic optimization with time-varying sample sizes are proposed using gradient- and output-perturbation methods. For both gradient- and output-perturbation cases, the convergence of the algorithm and differential privacy with a finite cumulative privacy budget $\varepsilon$ for an infinite number of iterations are simultaneously established, which is substantially different from the existing works. By a time-varying sample size method, the privacy level is enhanced, and differential privacy with a finite cumulative privacy budget $\varepsilon$ for an infinite number of iterations is established. By properly choosing a Lyapunov function, the algorithm achieves almost sure and mean square convergence even when the added privacy noise has an increasing variance. Furthermore, we rigorously provide the mean square convergence rates of the algorithm and show how the added privacy noise affects the convergence rate of the algorithm. Finally, numerical examples, including distributed training on a benchmark machine learning dataset, are presented to demonstrate the efficiency and advantages of the algorithms.

关键词： optimization Privacy Convergence Differential privacy Machine learning algorithms Approximation algorithms Standards Convergence rate differential privacy distributed stochastic optimization privacy-preserving stochastic approximation

来源：评论

学校读者我要写书评

暂无评论

ASYMPTOTIC PROPERTIES OF PRIMAL-DUAL ALGORITHM FOR distributed stochastic optimization OVER RANDOM NETWORKS WITH IMPERFECT COMMUNICATIONS

引用

SIAM JOURNAL ON CONTROL AND optimization 2018年第3期56卷 2159-2188页

作者： Lei, Jinlong Chen, Han-Fu Fang, Hai-Tao Chinese Acad Sci Acad Math & Syst Sci Key Lab Syst & Control Beijing 100080 Peoples R China

This paper studies a distributed stochastic optimization problem over random networks with imperfect communications subject to a global constraint, which is the intersection of local constraint sets assigned to agents. The global cost function is the sum of local expectation-valued convex cost functions. By incorporating the augmented Lagrangian technique with the projection method, a stochastic approximatio-based distributed primal-dual algorithm is proposed to solve the problem. Each agent updates its estimate by using the local noisy observations of its gradient function and the imperfect information derived from its neighbors. For the constrained problem, the estimates are first shown to be bounded almost surely (a.s.) and then are proved to converge to the optimal solution set a.s. Furthermore, the asymptotic normality and efficiency of the algorithm are addressed for the unconstrained case. The results demonstrate the influence of random networks, communication noises, and gradient errors on the performance of the algorithm. Finally, numerical simulations are presented to demonstrate the theoretic results.

关键词： distributed stochastic optimization random networks primal-dual algorithm stochastic approximation asymptotic normality asymptotic efficiency

来源：评论

学校读者我要写书评

暂无评论

Time Complexity Analysis of distributed stochastic optimization in a Non-Stationary Environment 15

Time Complexity Analysis of Distributed Stochastic Optimizat...

引用

15th International Symposium on Modeling and optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt)

作者： Bharath, B. N. Vaishali, P. Dept ECE PESIT Bangalore South Campus Bangalore 560100 Karnataka India

ISBN: (纸本)9783901882906

In this paper, we consider a distributed stochastic optimization problem where the goal is to minimize the time average of a cost function subject to a set of constraints on the time averages of related stochastic processes called penalties. We assume that the state of the system is evolving in an independent and non- stationary fashion and the " common information" available at each node is distributed and delayed. Such stochastic optimization is an integral part of many important problems in wireless networks such as scheduling, routing, resource allocation and crowd sensing. We propose an approximate distributed DriftPlus- Penalty (DPP) algorithm, and show that it achieves a time average cost (and penalties) that is within epsilon > 0 of the optimal cost (and constraints) with high probability. Also, we provide a condition on the convergence time t for this result to hold. In particular, for any delay D >= 0 in the common information, we use a coupling argument to prove that the proposed algorithm converges almost surely to the optimal solution. We use an application from wireless sensor network to corroborate our theoretical findings through simulation results.

关键词： Drift-plus-penalty Lyapunov function wireless networks online learning distributed stochastic optimization

来源：评论

学校读者我要写书评

暂无评论

A Primal-Dual Algorithm for distributed stochastic optimization with Equality Constraints 40

A Primal-Dual Algorithm for Distributed Stochastic Optimizat...

引用

40th Chinese Control Conference (CCC)

作者： Du, Kai-Xin Chen, Xing-Min Dalian Univ Technol Sch Math Sci Dalian 116024 Peoples R China

ISBN: (纸本)9789881563804

distributed stochastic optimization problem with equality constraints over a random network with imperfect communications is considered, where the measurements of all functions to be used are subject to noises. The goal of the network is to minimize a global cost function subject to a global constraint set, where the global objective is a sum of objective functions, the global constraint set is the intersection of local constraint sets with equality constraints, and each agent only has access to information on its cost function and constraint function. A primal-dual projection-free distributed algorithm is proposed to solve the problem, where each agent updates its estimates by using the local observations and local information on its neighbors' broadcast state values. Almost sure convergence of the algorithm is proven under mild conditions.

关键词： distributed stochastic optimization equality constrained optimization distributed primal-dual algorithm almost sure convergence stochastic approximation

来源：评论

学校读者我要写书评

暂无评论

Confidence region for distributed stochastic optimization problem via stochastic gradient tracking method

引用

AUTOMATICA 2024年 159卷

作者： Zhao, Shengchao Liu, Yongchao Dalian Univ Technol Sch Math Sci Dalian 116024 Peoples R China

Since stochastic approximation (SA) based algorithms are easy to implement and need less memory, they are very popular in distributed stochastic optimization problems. Many works have focused on the consistency of the objective values and the iterates returned by the SA based algorithms. It is of fundamental interest to know how to quantify the uncertainty associated with SA solutions via the confidence regions of a prescribed level of significance for the true solution. In this paper, we discuss the framework of constructing the asymptotic confidence regions of the optimal solution to distributed stochastic optimization problem with a focus on the distributed stochastic gradient tracking method. To attain this goal, we first present the asymptotic normality of Polyak-Ruppert averaged distributed stochastic gradient tracking method. We then estimate the corresponding covariance matrix through online estimators. Finally, we provide a practical procedure to build the asymptotic confidence regions for the optimal solution. Numerical tests are also conducted to show the efficiency of the proposed methods.(c) 2023 Elsevier Ltd. All rights reserved.

关键词： Confidence regions distributed stochastic optimization Plug-in method Batch-means method stochastic gradient tracking method

来源：评论

学校读者我要写书评

暂无评论

A Primal-Dual Algorithm for distributed stochastic optimization with Equality Constraints

A Primal-Dual Algorithm for Distributed Stochastic Optimizat...

引用

第40届中国控制会议

作者： Kai-Xin Du Xing-Min Chen School of Mathematical Sciences Dalian University of Technology

关键词： distributed stochastic optimization equality constrained optimization distributed primal-dual algorithm almost sure convergence stochastic approximation

来源：评论

学校读者我要写书评

暂无评论

distributed Heterogeneous Multi-Agent optimization with stochastic Sub-Gradient

引用

Journal of Systems Science & Complexity 2024年第4期37卷 1470-1487页

作者： HU Haokun MO Lipo CAO Xianbing School of Mathematics and Statistics Central South UniversityChangsha 410083China School of Mathematics and Statistics Beijing Technology and Business UniversityBeijing 100048China Research Centre for Agri-Product Quality Traceability Beijing Technology and Business UniversityBeijing 100048China School of Computer and Artificial Intelligence Beijing Technology and Business UniversityBeijing 100048China China Food Flavor and Nutrition Health Innovation Center Beijing Technology and Business UniversityBeijing 100048China

This paper studies the optimization problem of heterogeneous networks under a timevarying *** agent only accesses to one local objective function,which is *** improved algorithm with noisy measurement of local objective functions' sub-gradients and additive noises among information exchanging between each pair of agents is designed to minimize the sum of objective functions of all *** weaken the effect of these noises,two step sizes are introduced in the control *** graph theory,stochastic analysis and martingale convergence theory,it is proved that if the sub-gradients are uniformly bounded,the sequence of digraphs is balanced and the union graph of all digraphs is joint strongly connected,then the designed control protocol can force all agents to find the global optimal point almost *** last,the authors give some numerical examples to verify the effectiveness of the stochastic sub-gradient algorithms.

关键词： Communication noises distributed stochastic optimization heterogeneous networks subgradient measurement noises

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：