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

Distributed Online Convex Optimization with Adversarial Constraints: Reduced Cumulative Constraint Violation Bounds under Slater’s Condition

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Yi, Xinlei Li, Xiuxian Yang, Tao Xie, Lihua Hong, Yiguang Chai, Tianyou Johansson, Karl H. Lab for Information & Decision Systems Massachusetts Institute of Technology CambridgeMA02139 United States Department of Control Science and Engineering College of Electronics and Information Engineering Tongji University Shanghai201804 China Shanghai Research Institute for Intelligent Autonomous Systems China The State Key Laboratory of Synthetical Automation for Process Industries Northeastern University Shenyang110819 China School of Electrical and Electronic Engineering Nanyang Technological University 50 Nanyang Avenue Singapore639798 Singapore Division of Decision and Control Systems School of Electrical Engineering and Computer Science KTH Royal Institute of Technology Sweden Digital Futures Stockholm10044 Sweden

This paper considers distributed online convex optimization with adversarial constraints. In this setting, a network of agents makes decisions at each round, and then only a portion of the loss function and a coordinate block of the constraint function are privately revealed to each agent. The loss and constraint functions are convex and can vary arbitrarily across rounds. The agents collaborate to minimize network regret and cumulative constraint violation. A novel distributed online algorithm is proposed and it achieves an O(T max{c,1−c}) network regret bound and an O(T 1−c/2) network cumulative constraint violation bound, where T is the number of rounds and c ∈ (0, 1) is a user-defined trade-off parameter. When Slater’s condition holds (i.e, there is a point that strictly satisfies the inequality constraints), the network cumulative constraint violation bound is reduced to O(T 1−c). Moreover, if the loss functions are strongly convex, then the network regret bound is reduced to O(log(T)), and the network cumulative constraint violation bound is reduced to O(√log(T)T) and O(log(T)) without and with Slater’s condition, respectively. To the best of our knowledge, this paper is the first to achieve reduced (network) cumulative constraint violation bounds for (distributed) online convex optimization with adversarial constraints under Slater’s condition. Finally, the theoretical results are verified through numerical simulations. Copyright © 2023, The Authors. All rights reserved.

关键词： Economic and social effects

Compressed Gradient Tracking Algorithms for Distributed Nonconvex Optimization

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Xu, Lei Yi, Xinlei Wen, Guanghui Shi, Yang Johansson, Karl H. Yang, Tao The State Key Laboratory of Synthetical Automation for Process Industries Northeastern University Shenyang110819 China The Lab for Information & Decision Systems Massachusetts Institute of Technology CambridgeMA02139 United States The Department of Systems Science School of Mathematics Southeast University Nanjing210096 China The Department of Mechanical Engineering University of Victoria VictoriaBCV8W 2Y2 Canada The Division of Decision and Control Systems School of Electrical Engineering and Computer Science KTH Royal Institute of Technology Stockholm100 44 Sweden

In this paper, we study the distributed nonconvex optimization problem, aiming to minimize the average value of the local nonconvex cost functions using local information exchange. To reduce the communication overhead, we introduce three general classes of compressors, i.e., compressors with bounded relative compression error, compressors with globally bounded absolute compression error, and compressors with locally bounded absolute compression error. By integrating them, respectively, with the distributed gradient tracking algorithm, we then propose three corresponding compressed distributed nonconvex optimization algorithms. Motivated by the state-of-the-art BEER algorithm proposed in [1], which is an efficient compressed algorithm integrating gradient tracking with biased and contractive compressors, our first proposed algorithm extends this algorithm to accommodate both biased and non-contractive compressors. For each algorithm, we design a novel Lyapunov function to demonstrate its sublinear convergence to a stationary point if the local cost functions are smooth. Furthermore, when the global cost function satisfies the Polyak–Lojasiewicz (P–L) condition, we show that our proposed algorithms linearly converge to a global optimal point. It is worth noting that, for compressors with bounded relative compression error and globally bounded absolute compression error, our proposed algorithms’ parameters do not require prior knowledge of the P–L constant. The theoretical results are illustrated by numerical examples, demonstrating the effectiveness of the proposed algorithms in significantly reducing the communication burden while maintaining the convergence performance. Moreover, simulation results show that the proposed algorithms outperform the state-of-the-art compressed distributed nonconvex optimization algorithms. Copyright © 2023, The Authors. All rights reserved.

关键词： Cost functions

Recursive Weighted Null-Space Fitting Method for Identification of Multivariate Systems ⁎

学校读者我要写书评

暂无评论

IFAC-PapersOnLine 2021年第7期54卷 345-350页

作者： Mengyuan Fang Miguel Galrinho Håkan Hjalmarsson Zhejiang Engineering Laboratory of Industrial Internet Communication Technology Zhejiang Sci-Tech University Hangzhou China. State Key Laboratory of Synthetical Automation for Process Industries Northeastern University Shenyang China OHB Sweden AB Kista Sweden Centre for Advanced Bio Production and Division of Decision and Control Systems School of Electrical Engineering and Computer Science KTH Royal Institute of Technology Sweden

Recursive identification of structured multivariate models is known to be difficult due to the general non-convexity of the likelihood function. In this work, we propose a recursive multivariate weighted null-space fitting method for identification of structured multivariate models. The proposed method first uses recursive least squares to estimate a high order non-parametric model, then a parametric model is obtained through weighted least squares from the non-parametric model. In this way, the method avoids directly optimizing a non-convex likelihood function and has guaranteed global convergency. Moreover, the proposed method is flexible in model structures and has the same finite sample performance as its off-line counterpart. We use simulation examples to illustrate the performance.

关键词： Recursive system identification multivariate systems weighted null-space fitting

Zeroth-order algorithms for stochastic distributed nonconvex optimization

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Yi, Xinlei Zhang, Shengjun Yang, Tao Johansson, Karl H. Division of Decision and Control Systems School of Electrical Engineering and Computer Science KTH Royal Institute of Technology Stockholm10044 Sweden Department of Electrical Engineering University of North Texas DentonTX76203 United States State Key Laboratory of Synthetical Automation for Process Industries Northeastern University Shenyang110819 China

In this paper, we consider a stochastic distributed nonconvex optimization problem with the cost function being distributed over n agents having access only to zeroth-order (ZO) information of the cost. This problem has various machine learning applications. As a solution, we propose two distributed ZO algorithms, in which at each iteration each agent samples the local stochastic ZO oracle at two points with a time-varying smoothing parameter. We show that the proposed algorithms achieve the linear speedup convergence rate O(√p=(nT)) for smooth cost functions under the state-dependent variance assumptions which are more general than the commonly used bounded variance and Lipschitz assumptions, and O(p=(nT)) convergence rate when the global cost function additionally satisfies the Polyak-Lojasiewicz (P-L) condition in addition, where p and T are the dimension of the decision variable and the total number of iterations, respectively. To the best of our knowledge, this is the first linear speedup result for distributed ZO algorithms, which enables systematic processing performance improvements by adding more agents. We also show that the proposed algorithms converge linearly under the relative bounded second moment assumptions and the P-L condition. We demonstrate through numerical experiments the efficiency of our algorithms on generating adversarial examples from deep neural networks in comparison with baseline and recently proposed centralized and distributed ZO algorithms. Copyright © 2021, The Authors. All rights reserved.

关键词： Cost functions

Regret and Cumulative Constraint Violation Analysis for Distributed Online Constrained Convex Optimization

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Yi, Xinlei Li, Xiuxian Yang, Tao Xie, Lihua Chai, Tianyou Johansson, Karl H. The Division of Decision and Control Systems School of Electrical Engineering and Computer Science KTH Royal Institute of Technology Stockholm10044 Sweden The Digital Futures Stockholm10044 Sweden The Department of Control Science and Engineering College of Electronics and Information Engineering The Shanghai Research Institute for Intelligent Autonomous Systems Tongji University Shanghai China The State Key Laboratory of Synthetical Automation for Process Industries Northeastern University Shenyang110819 China School of Electrical and Electronic Engineering Nanyang Technological University 50 Nanyang Avenue Singapore639798 Singapore

This paper considers the distributed online convex optimization problem with time-varying constraints over a network of agents. This is a sequential decision making problem with two sequences of arbitrarily varying convex loss and constraint functions. At each round, each agent selects a decision from the decision set, and then only a portion of the loss function and a coordinate block of the constraint function at this round are privately revealed to this agent. The goal of the network is to minimize the network-wide loss accumulated over time. Two distributed online algorithms with full-information and bandit feedback are proposed. Both dynamic and static network regret bounds are analyzed for the proposed algorithms, and network cumulative constraint violation is used to measure constraint violation, which excludes the situation that strictly feasible constraints can compensate the effects of violated constraints. In particular, we show that the proposed algorithms achieve O(T max{κ,1-κ}) static network regret and O(T 1-κ/2) network cumulative constraint violation, where T is the time horizon and κ ∈ (0, 1) is a user-defined trade-off parameter. Moreover, if the loss functions are strongly convex, then the static network regret bound can be reduced to O(T κ). Finally, numerical simulations are provided to illustrate the effectiveness of the theoretical results. Copyright © 2021, The Authors. All rights reserved.

关键词： Economic and social effects

A Primal-Dual SGD Algorithm for Distributed Nonconvex Optimization

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Yi, Xinlei Zhang, Shengjun Yang, Tao Chai, Tianyou Johansson, Karl H. The Division of Decision and Control Systems School of Electrical Engineering and Computer Science KTH Royal Institute of Technology Stockholm100 44 Sweden The Department of Electrical Engineering University of North Texas DentonTX76203 United States The State Key Laboratory of Synthetical Automation for Process Industries Northeastern University Shenyang110819 China

The distributed nonconvex optimization problem of minimizing a global cost function formed by a sum of n local cost functions by using local information exchange is considered. This problem is an important component of many machine learning techniques with data parallelism, such as deep learning and federated learning. We propose a distributed primal–dual stochastic gradient descent (SGD) algorithm, suitable for arbitrarily connected communication networks and any smooth (possibly nonconvex) cost functions. We show that the proposed algorithm achieves the linear speedup convergence rate O(1/√nT) for general nonconvex cost functions and the linear speedup convergence rate O(1/(nT)) when the global cost function satisfies the Polyak–Lojasiewicz (P–L) condition, where T is the total number of iterations. We also show that the output of the proposed algorithm with constant parameters linearly converges to a neighborhood of a global optimum. We demonstrate through numerical experiments the efficiency of our algorithm in comparison with the baseline centralized SGD and recently proposed distributed SGD algorithms. Copyright © 2020, The Authors. All rights reserved.

关键词： Cost functions

Exponential convergence for distributed smooth optimization under the restricted secant inequality condition

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Yi, Xinlei Zhang, Shengjun Yang, Tao Johansson, Karl H. Chai, Tianyou Division of Decision and Control Systems School of Electrical Engineering and Computer Science KTH Royal Institute of Technology Stockholm100 44 Sweden Department of Electrical Engineering University of North Texas DentonTX76203 United States State Key Laboratory of Synthetical Automation for Process Industries Northeastern University Shenyang110819 China

This paper considers the distributed smooth optimization problem in which the objective is to minimize a global cost function formed by a sum of local smooth cost functions, by using local information exchange. The standard assumption for proving exponential/linear convergence of first-order methods is the strong convexity of the cost functions, which does not hold for many practical applications. In this paper, we first show that the continuous-time distributed primal-dual gradient algorithm converges to one global minimizer exponentially under the assumption that the global cost function satisfies the restricted secant inequality condition. This condition is weaker than the strong convexity condition since it does not require convexity and the global minimizers are not necessary to be unique. We then show that the discrete-time distributed primal-dual algorithm constructed by using the Euler's approximation method converges to one global minimizer linearly under the same condition. The theoretical results are illustrated by numerical simulations. Copyright © 2019, The Authors. All rights reserved.

关键词： Continuous time systems

Linear convergence of first- And zeroth-order primal-dual algorithms for distributed nonconvex optimization

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Yi, Xinlei Zhang, Shengjun Yang, Tao Chai, Tianyou Johansson, Karl H. Division of Decision and Control Systems School of Electrical Engineering and Computer Science Kth Royal Institute of Technology Digital Futures Stockholm100 44 Sweden Department of Electrical Engineering University of North Texas DentonTX76203 United States State Key Laboratory of Synthetical Automation for Process Industries Northeastern University Shenyang110819 China

This paper considers the distributed nonconvex optimization problem of minimizing a global cost function formed by a sum of local cost functions by using local information *** first propose a distributed first-order primal-dual algorithm. We show that it converges sublinearly to a stationary point if each local cost function is smooth and linearly to a global optimum under an additional condition that the global cost function satisfies the Polyak-Lojasiewicz condition. This condition is weaker than strong convexity, which is a standard condition for proving linear convergence of distributed optimization algorithms, and the global minimizer is not necessarily unique. Motivated by the situations where the gradients are unavailable, we then propose a distributed zeroth-order algorithm, derived from the proposed distributed first-order algorithm by using a deterministic gradient estimator, and show that it has the same convergence properties as the proposed first-order algorithm under the same conditions. The theoretical results are illustrated by numerical simulations. Copyright © 2019, The Authors. All rights reserved.

关键词： Cost functions

Distributed bandit online convex optimization with time-varying coupled inequality constraints

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Yi, Xinlei Li, Xiuxian Yang, Tao Xie, Lihua Johansson, Karl H. Chai, Tianyou Division of Decision and Control Systems School of Electrical Engineering and Computer Science KTH Royal Institute of Technology Stockholm100 44 Sweden School of Electrical and Electronic Engineering Nanyang Technological University 50 Nanyang Avenue Singapore639798 Singapore State Key Laboratory of Synthetical Automation for Process Industries Northeastern University Shenyang110819 China

This paper considers the problem of distributed bandit online convex optimization with time-varying coupled inequality constraints. This problem can be defined as a repeated game between a group of learners and an adversary. The learners attempt to minimize a sequence of global loss functions and at the same time satisfy a sequence of coupled constraint functions. The global loss and the coupled constraint functions are the sum of local convex loss and constraint functions, respectively, which are adaptively generated by the adversary. The local loss and constraint functions are revealed in a bandit manner, i.e., only the values of loss and constraint functions at sampled points are revealed to the learners, and the revealed function values are held privately by each learner. We consider two scenarios, one- and two-point bandit feedback, and propose two corresponding distributed bandit online algorithms used by the learners. We show that sublinear expected regret and constraint violation are achieved by these two algorithms, if the accumulated variation of the comparator sequence also grows sublinearly. In particular, we show that O(T θ1 ) expected static regret and O(T 7/4−θ1 ) constraint violation are achieved in the one-point bandit feedback setting, and O(T max{κ,1−κ}) expected static regret and O(T 1−κ/2) constraint violation in the two-point bandit feedback setting, where θ1 ∈ (3/4, 5/6] and κ ∈ (0, 1) are user-defined trade-off parameters. Finally, these theoretical results are illustrated by numerical simulations of a simple power grid example. Copyright © 2019, The Authors. All rights reserved.

关键词： Convex optimization