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

asynchronous Broadcast-Based Convex Optimization Over a Network

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2011年第6期56卷 1337-1351页

作者： Nedic, Angelia Univ Illinois Ind & Enterprise Syst Engn Dept Urbana IL 61801 USA

We consider a distributed multi-agent network system where each agent has its own convex objective function, which can be evaluated with stochastic errors. The problem consists of minimizing the sum of the agent functions over a commonly known constraint set, but without a central coordinator and without agents sharing the explicit form of their objectives. We propose an asynchronous broadcast-based algorithm where the communications over the network are subject to random link failures. We investigate the convergence properties of the algorithm for a diminishing (random) stepsize and a constant stepsize, where each agent chooses its own stepsize independently of the other agents. Under some standard conditions on the gradient errors, we establish almost sure convergence of the method to an optimal point for diminishing stepsize. For constant stepsize, we establish some error bounds on the expected distance from the optimal point and the expected function value. We also provide numerical results.

关键词： asynchronous algorithms convex optimization distributed multi-agent system random broadcast network

来源：评论

学校读者我要写书评

暂无评论

asynchronous Distributed Optimization via Dual Decomposition and Block Coordinate Subgradient Methods

引用

IEEE TRANSACTIONS ON CONTROL OF NETWORK SYSTEMS 2021年第3期8卷 1348-1359页

作者： Lin, Yankai Shames, Iman Nesic, Dragan Univ Melbourne Dept Elect & Elect Engn Parkville Vic 3010 Australia Australian Natl Univ Sch Engn Acton ACT 0200 Australia

In this article, we study the problem of minimizing the sum of potentially nondifferentiable convex cost functions with partially overlapping dependences in an asynchronous manner, where communication in the network is not coordinated. We study the behavior of an asynchronous algorithm based on dual decomposition and block coordinate subgradient methods under assumptions weaker than those used in the literature. At the same time, we allow different agents to use local stepsizes with no global coordination. Sufficient conditions are provided for almost sure convergence to the solution of the optimization problem. Under additional assumptions, we establish a sublinear convergence rate that, in turn, can be strengthened to the linear convergence rate if the problem is strongly convex and has Lipschitz gradients. We also extend available results in the literature by allowing multiple and potentially overlapping blocks to be updated at the same time with nonuniform and potentially time-varying probabilities assigned to different blocks. A numerical example is provided to illustrate the effectiveness of the algorithm.

关键词： asynchronous algorithms distributed optimization networked control systems

来源：评论

学校读者我要写书评

暂无评论

SUFFICIENT CONDITIONS FOR THE CONVERGENCE OF asynchronous ITERATIONS

引用

PARALLEL COMPUTING 1989年第1期10卷 83-92页

作者： URESIN, A DUBOIS, M Department of Electrical Engineering-Systems University of Southern California Los Angeles CA 90089-0781 U.S.A.

asynchronous algorithms have the potential to be more efficient than synchronized algorithms in multiprocessors because the overheads associated with synchronization are removed. The sufficient conditions for the convergence of numerical asynchronous iterations have been established; however, relaxation procedures are also common in non-numerical applications. In this paper, we introduce sufficient conditions for the convergence of asynchronous iterations defined on any set of data, finite or infinite, countable or not. The sufficient conditions are then applied to the scene-labeling problem. A multitasked implementation of the scene-labeling algorithm in a distributed global memory system is detailed. In this implementation, no synchronization nor critical sections are necessary to enforce correctness of execution.

关键词： asynchronous algorithms implementation on a model architecture multiprocessors scene-labeling problem sufficient conditions for convergence

来源：评论

学校读者我要写书评

暂无评论

A Fast Distributed asynchronous Newton-Based Optimization Algorithm

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2020年第7期65卷 2769-2784页

作者： Mansoori, Fatemeh Wei, Ermin Northwestern Univ Dept Elect & Comp Engn Evanston IL 60208 USA

One of the most important problems in the field of distributed optimization is the problem of minimizing a sum of local convex objective functions over a networked system. Most of the existing work in this area focuses on developing distributed algorithms in a synchronous setting under the presence of a central clock, where the agents need to wait for the slowest one to finish the update, before proceeding to the next iterate. asynchronous distributed algorithms remove the need for a central coordinator, reduce the synchronization wait, and allow some agents to compute faster and execute more iterations. In the asynchronous setting, the only known algorithms for solving this problem could achieve an either linear or sublinear rate of convergence. In this paper, we build upon the existing literature to develop and analyze an asynchronous Newton-based method to solve a penalized version of the problem. We show that this algorithm guarantees almost sure convergence with a global linear and local quadratic rate in expectation. Numerical studies confirm the superior performance of our algorithm against other asynchronous methods.

关键词： Optimization Convergence Linear programming Approximation algorithms Delays Clocks Symmetric matrices Agents and autonomous systems asynchronous algorithms network analysis and control optimization algorithms

来源：评论

学校读者我要写书评

暂无评论

asynchronous Iterations in Optimization: New Sequence Results and Sharper Algorithmic Guarantees

引用

JOURNAL OF MACHINE LEARNING RESEARCH 2023年第1期24卷 1-75页

作者： Feyzmahdavian, Hamid Reza Johansson, Mikael ABB Corp Res Vasteras Sweden KTH Royal Inst Technol Div Decis & Control Syst Stockholm Sweden

We introduce novel convergence results for asynchronous iterations that appear in the analysis of parallel and distributed optimization algorithms. The results are simple to apply and give explicit estimates for how the degree of asynchrony impacts the convergence rates of the iterates. Our results shorten, streamline and strengthen existing convergence proofs for several asynchronous optimization methods and allow us to establish convergence guarantees for popular algorithms that were thus far lacking a complete theoretical under-standing. Specifically, we use our results to derive better iteration complexity bounds for proximal incremental aggregated gradient methods, to obtain tighter guarantees depending on the average rather than maximum delay for the asynchronous stochastic gradient descent method, to provide less conservative analyses of the speedup conditions for asynchronous block-co ordinate implementations of Krasnosel'skii-Mann iterations, and to quantify the convergence rates for totally asynchronous iterations under various assumptions on communication delays and update rates.

关键词： asynchronous algorithms parallel methods incremental methods coordinate descent stochastic gradient descent

来源：评论

学校读者我要写书评

暂无评论

PERTURBED ITERATE ANALYSIS FOR asynchronous STOCHASTIC OPTIMIZATION

引用

SIAM JOURNAL ON OPTIMIZATION 2017年第4期27卷 2202-2229页

作者： Mania, Horia Pan, Xinghao Papailiopoulos, Dimitris Recht, Benjamin Ramchandran, Kannan Jordan, Michael I. Univ Calif Berkeley AMPLab Berkeley CA 94720 USA Univ Calif Berkeley EECS Berkeley CA 94720 USA Univ Calif Berkeley Stat Berkeley CA 94720 USA

We introduce and analyze stochastic optimization methods where the input to each update is perturbed by bounded noise. We show that this framework forms the basis of a unified approach to analyzing asynchronous implementations of stochastic optimization algorithms, by viewing them as serial methods operating on noisy inputs. Using our perturbed iterate framework, we provide new analyses of the HOGWILD! algorithm and asynchronous stochastic coordinate descent that are simpler than earlier analyses, remove many assumptions of previous models, and in some cases yield improved upper bounds on the convergence rates. We proceed to apply our framework to develop and analyze KROMAGNON: a novel, parallel, sparse stochastic variance-reduced gradient (SVRG) algorithm. We demonstrate experimentally on a 16-core machine that the sparse and parallel version of SVRG is in some cases more than four orders of magnitude faster than the standard SVRG algorithm.

关键词： stochastic optimization asynchronous algorithms parallel machine learning

来源：评论

学校读者我要写书评

暂无评论

asynchronous stochastic approximations

引用

SIAM JOURNAL ON CONTROL AND OPTIMIZATION 1998年第3期36卷 840-851页

作者： Borkar, VS Indian Inst Sci Dept Comp Sci & Automat Bangalore 560012 Karnataka India

The asymptotic behavior of a distributed, asynchronous stochastic approximation scheme is analyzed in terms of a limiting nonautonomous differential equation. The relation between the latter and the relative values of... 详细信息

关键词： distributed algorithms asynchronous algorithms communication delays stochastic approximation ODE limit

来源：评论

学校读者我要写书评

暂无评论

Convergence of an asynchronous block-coordinate forward-backward algorithm for convex composite optimization

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2023年第1期86卷 303-344页

作者： Traore, Cheik Salzo, Saverio Villa, Silvia Univ Genoa Malga Ctr DIMA Genoa Italy Sapienza Univ Roma DIAG Rome Italy

In this paper, we study the convergence properties of a randomized block-coordinate descent algorithm for the minimization of a composite convex objective function, where the block-coordinates are updated asynchronously and randomly according to an arbitrary probability distribution. We prove that the iterates generated by the algorithm form a stochastic quasi-Fejer sequence and thus converge almost surely to a minimizer of the objective function. Moreover, we prove a general sublinear rate of convergence in expectation for the function values and a linear rate of convergence in expectation under an error bound condition of Tseng type. Under the same condition strong convergence of the iterates is provided as well as their linear convergence rate.

关键词： Convex optimization asynchronous algorithms Randomized block-coordinate descent Error bounds Stochastic quasi-Fejer sequences Forward-backward algorithm Convergence rates

来源：评论

学校读者我要写书评

暂无评论

Convergence of asynchronous Jacobi-Newton-iterations

引用

NUMERICAL LINEAR ALGEBRA WITH APPLICATIONS 1999年第2期6卷 157-165页

作者： Schrader, U TU chemnitz Fak Math D-09107 Chemnitz Germany

asynchronous iterations often converge under different conditions than their synchronous counterparts. In this paper we will study the global convergence of Jacobi-Newton-like methods for nonlinear equations Fx = 0. It is a known fact, that the synchronous algorithm converges monotonically, if F is a convex M-function and the starting values x(0) and y(0) meet the condition Fx(0) less than or equal to 0 less than or equal to Fy(0). In the paper it will be shown, which modifications are necessary to guarantee a similar convergence behavior for an asynchronous computation. Copyright (C) 1999 John Wiley & Sons, Ltd.

关键词： systems of nonlinear equations M-functions iterative methods parallel algorithms asynchronous algorithms chaotic relaxation

来源：评论

学校读者我要写书评

暂无评论

An asynchronous Algorithm for Optimal Vehicle Coordination at Traffic Intersections

引用

IFAC-PapersOnLine 2017年第1期50卷 12008-12014页

作者： Zanon, Mario Gros, Sébastien Wymeersch, Henk Falcone, Paolo The authors are with the Department of Signals and Systems Chalmers University of Technology Goteborg Sweden

In this paper we propose an algorithm for vehicle coordination at intersections in order to avoid collisions within the intersection area while optimising an objective given as the sum of individual costs associated with each agent. Extending the results presented in Hult et al. (2016), we develop an algorithm with asynchronous sensitivity updates in order to reduce the time spent in communication. We select which sensitivities to update in order to minimise an upper bound on the contraction of the inexact Newton iterates and introduce a projection of the inexact Newton steps in order to ensure feasibility of the local problems. We prove convergence of our algorithm and test it on a numerical example in order to validate its effectiveness. © 2017

关键词： Vehicles asynchronous algorithms asynchronous SQP Inexact newtons Intersection areas Local problems Optimal vehicles Traffic intersections Upper Bound

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：