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

Robustness of Accelerated First-Order Algorithms for Strongly Convex optimization Problems

IEEE TRANSACTIONS ON AUTOMATIC control 2021年第6期66卷 2480-2495页

作者： Mohammadi, Hesameddin Razaviyayn, Meisam Jovanovic, Mihailo R. Univ Southern Calif Dept Elect & Comp Engn Los Angeles CA 90007 USA Univ Southern Calif Daniel J Epstein Dept Ind & Syst Engn Los Angeles CA 90007 USA

We study the robustness of accelerated first-order algorithms to stochastic uncertainties in gradient evaluation. Specifically, for unconstrained, smooth, strongly convex optimization problems, we examine the mean-squared error in the optimization variable when the iterates are perturbed by additive white noise. This type of uncertainty may arise in situations where an approximation of the gradient is sought through measurements of a real system or in a distributed computation over a network. Even though the underlying dynamics of first-order algorithms for this class of problems are nonlinear, we establish upper bounds on the mean-squared deviation from the optimal solution that are tight up to constant factors. Our analysis quantifies fundamental tradeoffs between noise amplification and convergence rates obtained via any acceleration scheme similar to Nesterov's or heavy-ball methods. To gain additional analytical insight, for strongly convex quadratic problems, we explicitly evaluate the steady-state variance of the optimization variable in terms of the eigenvalues of the Hessian of the objective function. We demonstrate that the entire spectrum of the Hessian, rather than just the extreme eigenvalues, influences robustness of noisy algorithms. We specialize this result to the problem of distributed averaging over undirected networks and examine the role of network size and topology on the robustness of noisy accelerated algorithms.

关键词： Acceleration Convergence optimization Robustness Noise measurement Heuristic algorithms Upper bound Accelerated first-order algorithms consensus networks control for optimization convex optimization integral quadratic constraints linear matrix inequalities (LMIs) noise amplification second-order moments semidefinite programming

来源：评论

学校读者我要写书评

暂无评论

The Gradient Tracking Is a Distributed Integral Action

引用

IEEE TRANSACTIONS ON AUTOMATIC control 2023年第12期68卷 7911-7918页

作者： Notarnicola, Ivano Bin, Michelangelo Marconi, Lorenzo Notarstefano, Giuseppe Alma Mater Studiorum Univ Bologna Dept Elect Elect & Informat Engn I-40136 Bologna Italy

We revisit the recent gradient tracking algorithm for distributed consensus optimization from a control theoretic viewpoint. We show that the algorithm can be constructed by solving a servomechanism control problem stemming from the distributed implementation of a centralized gradient method. Moreover, we show that, if expressed in proper coordinates, the gradient tracking embeds an integral action fed by a signal related to the consensus error. Finally, we provide an alternative convergence analysis based on Lyapunov arguments that also proves exponential asymptotic stability of the optimal equilibrium.

关键词： control for optimization distributed optimization gradient tracking integral control

来源：评论

学校读者我要写书评

暂无评论

The Proximal Augmented Lagrangian Method for Nonsmooth Composite optimization

引用

IEEE TRANSACTIONS ON AUTOMATIC control 2019年第7期64卷 2861-2868页

作者： Dhingra, Neil K. Khong, Sei Zhen Jovanovic, Mihailo R. Numerica Corp Ft Collins CO 80528 USA Univ Hong Kong Dept Elect & Elect Engn Pokfulam Hong Kong Peoples R China Univ Southern Calif Dept Elect Engn Los Angeles CA 90089 USA

We study a class of optimization problems in which the objective function is given by the sum of a differentiable but possibly nonconvex component and a nondifferentiable convex regularization term. We introduce an auxiliary variable to separate the objective function components and utilize the Moreau envelope of the regularization term to derive the proximal augmented Lagrangian- a continuously differentiable function obtained by constraining the augmented Lagrangian to the manifold that corresponds to the explicit minimization over the variable in the nonsmooth term. The continuous differentiability of this function with respect to both primal and dual variables allows us to leverage the method of multipliers (MM) to compute optimal primal-dual pairs by solving a sequence of differentiable problems. The MM algorithm is applicable to a broader class of problems than proximal gradient methods and it has stronger convergence guarantees and a more refined step-size update rules than the alternating direction method of multipliers (ADMM). These features make it an attractive option for solving structured optimal control problems. We also develop an algorithm based on the primal-descent dual-ascent gradient method and prove global (exponential) asymptotic stability when the differentiable component of the objective function is (strongly) convex and the regularization term is convex. Finally, we identify classes of problems for which the primal-dual gradient flow dynamics are convenient for distributed implementation and compare/contrast our framework to the existing approaches.

关键词： Augmented Lagrangian control for optimization global exponential stability method of multipliers non-smooth optimization primal-dual dynamics proximal algorithms proximal augmented Lagrangian regularization for design structured optimal control

来源：评论

学校读者我要写书评

暂无评论

Performance of noisy Nesterov's accelerated method for strongly convex optimization problems

Performance of noisy Nesterov's accelerated method for stron...

引用

American control Conference (ACC)

作者： Mohammadi, Hesameddin Razaviyayn, Meisam Jovanovic, Mihailo R. Univ Southern Calif Dept Elect & Comp Engn Los Angeles CA 90089 USA Univ Southern Calif Dept Ind & Syst Engn Los Angeles CA 90089 USA

ISBN: (纸本)9781538679265

We study the performance of noisy gradient descent and Nesterov's accelerated methods for strongly convex objective functions with Lipschitz continuous gradients. The steady-state second -order moment of the error in the iterates is analyzed when the gradient is perturbed by an additive white noise with zero mean and identity covariance. For any given condition number kappa, we derive explicit upper bounds on noise amplification that only depend on kappa and the problem size. We use quadratic objective functions to derive lower bounds and to demonstrate that the upper bounds are tight up to a constant factor. The established upper bound for Nesterov's accelerated method is larger than the upper bound for gradient descent by a factor of root kappa. This gap identifies a fundamental tradeoff that comes with acceleration in the presence of stochastic uncertainties in the gradient evaluation.

来源：评论

学校读者我要写书评

暂无评论

Global exponential stability of the Douglas-Rachford splitting dynamics 21st

Global exponential stability of the Douglas-Rachford splitti...

引用

21st IFAC World Congress on Automatic control - Meeting Societal Challenges

作者： Hassan-Moghaddam, Sepideh Jovanovic, Mihailo R. Univ Southern Calif Ming Hsieh Dept Elect & Comp Engn Los Angeles CA 90089 USA

Many modern optimization problems admit a composite form in which the objective function is given by the sum of a smooth term and a nonsmooth regularizer. Such problems can be solved via proximal methods and their variants, including the Douglas-Rachford (DR) splitting algorithm. In this paper, we view the DR splitting flow as a dynamical system and leverage techniques from control theory to study its global stability properties. In particular, for problems with strongly convex objective functions, we utilize the theory of integral quadratic constraints to prove global exponential stability of the ordinary differential equation that governs the evolution of the DR splitting flow. In our analysis, we use the fact that this algorithm can be interpreted as a variable-metric gradient method on the DR envelope and exploit structural properties of nonlinear terms that arise from composition of reflected proximal operators. Copyright (C) 2020 The Authors.

关键词： control for optimization Douglas-Rachford splitting global exponential stability integral quadratic constraints nonlinear dynamics nonsmooth optimization proximal algorithms

来源：评论

学校读者我要写书评

暂无评论

Proximal gradient flow and Douglas-Rachford splitting dynamics: Global exponential stability via integral quadratic constraints

引用

AUTOMATICA 2021年 123卷 109311-109311页

作者： Hassan-Moghaddam, Sepideh Jovanovic, Mihailo R. Univ Southern Calif Ming Hsieh Dept Elect & Comp Engn Los Angeles CA 90089 USA

Many large-scale and distributed optimization problems can be brought into a composite form in which the objective function is given by the sum of a smooth term and a nonsmooth regularizer. Such problems can be solved via a proximal gradient method and its variants, thereby generalizing gradient descent to a nonsmooth setup. In this paper, we view proximal algorithms as dynamical systems and leverage techniques from control theory to study their global properties. In particular, for problems with strongly convex objective functions, we utilize the theory of integral quadratic constraints to prove the global exponential stability of the equilibrium points of the differential equations that govern the evolution of proximal gradient and Douglas-Rachford splitting flows. In our analysis, we use the fact that these algorithms can be interpreted as variable-metric gradient methods on the suitable envelopes and exploit structural properties of the nonlinear terms that arise from the gradient of the smooth part of the objective function and the proximal operator associated with the nonsmooth regularizer. We also demonstrate that these envelopes can be obtained from the augmented Lagrangian associated with the original nonsmooth problem and establish conditions for global exponential convergence even in the absence of strong convexity. (c) 2020 Elsevier Ltd. All rights reserved.

关键词： control for optimization Forward-backward envelope Douglas-Rachford splitting Global exponential stability Integral quadratic constraints (IQCs) Nonlinear dynamics Nonsmooth optimization Proximal algorithms Primal-dual methods Proximal augmented lagrangian

来源：评论

学校读者我要写书评

暂无评论

Passivity-based Analysis of the ADMM Algorithm for Constraint-Coupled optimization

引用

AUTOMATICA 2022年 146卷

作者： Notarnicola, Ivano Falsone, Alessandro Alma Mater Studiorum Univ Bologna Dept Elect Elect & Informat Engn Bologna Italy Politecn Milan Dipartimento Elettron Informaz & Bioingn Milan Italy

We propose a novel, system theoretic analysis of the Alternating Direction Method of Multipliers (ADMM) applied to a convex constraint-coupled optimization problem. The resulting algorithm can be interpreted as a linear, discrete-time dynamical system (modeling the multiplier ascent update) in closed loop with a static nonlinearity (representing the minimization of the augmented Lagrangian). When expressed in suitable coordinates, we prove that the discrete-time linear dynamical system has a discrete positive-real transfer function and is interconnected in closed loop with a static, passive nonlinearity. This readily shows that the origin is a stable equilibrium for the feedback interconnection. Finally, we also show global asymptotic stability of the origin for the closed-loop system and, thus, global asymptotic convergence of ADMM to the optimal solution of the optimization problem.(c) 2022 Elsevier Ltd. All rights reserved.

关键词： ADMM Constraint-coupled optimization Passivity theory Nonsmooth optimization control for optimization

来源：评论

学校读者我要写书评

暂无评论

Global exponential stability of the Douglas-Rachford splitting dynamics ⁎

引用

IFAC-PapersOnLine 2020年第2期53卷 7350-7354页

作者： Sepideh Hassan-Moghaddam Mihailo R. Jovanović Ming Hsieh Department of Electrical and Computer Engineering University of Southern California Los Angeles CA 90089

关键词： control for optimization Douglas-Rachford splitting global exponential stability integral quadratic constraints nonlinear dynamics nonsmooth optimization proximal algorithms

来源：评论

学校读者我要写书评

暂无评论

Performance of noisy Nesterov's accelerated method for strongly convex optimization problems

Performance of noisy Nesterov's accelerated method for stron...

引用

American control Conference

作者： Hesameddin Mohammadi Meisam Razaviyayn Mihailo R. Jovanovic Department of Electrical and Computer Engineering University of Southern California Los Angeles CA 90089

ISBN: (纸本)9781538679012;9781538679265

We study the performance of noisy gradient descent and Nesterov's accelerated methods for strongly convex objective functions with Lipschitz continuous gradients. The steady-state second-order moment of the error in the iterates is analyzed when the gradient is perturbed by an additive white noise with zero mean and identity covariance. For any given condition number κ, we derive explicit upper bounds on noise amplification that only depend on κ and the problem size. We use quadratic objective functions to derive lower bounds and to demonstrate that the upper bounds are tight up to a constant factor. The established upper bound for Nesterov's accelerated method is larger than the upper bound for gradient descent by a factor of √κ. This gap identifies a fundamental tradeoff that comes with acceleration in the presence of stochastic uncertainties in the gradient evaluation.

关键词： Accelerated first-order algorithms control for optimization convex optimization integral quadratic constraints linear matrix inequalities Nesterov's method noise amplification second-order moments semidefinite programming Upper bound linear matrix inequalities second moment Convex function control optimization Objective function Additive white noise zero mean descent Gradient

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：