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

Lower bounds and accelerated algorithms for bilevel optimization

The Journal of Machine Learning Research 2023年第1期24卷 795-850页

作者： Kaiyi Ji Yingbin Liang Department of Computer Science and Engineering University at Buffalo Buffalo NY Department of Electrical and Computer Engineering The Ohio State University Columbus OH

Bilevel optimization has recently attracted growing interests due to its wide applications in modern machine learning problems. Although recent studies have characterized the convergence rate for several such popular algorithms, it is still unclear how much further these convergence rates can be improved. In this paper, we address this fundamental question from two perspectives. First, we provide the first-known lower complexity bounds of $\widetilde \Omega\bigg(\sqrt{\frac{L_y\widetilde L_{xy}^2}{\mu_x\mu_y^2}}\bigg)$ and $\widetilde \Omega\big(\frac{1}{\sqrt{\epsilon}}\min\{\kappa_y,\frac{1}{\sqrt{\epsilon^{3}}}\}\big)$ respectively for strongly-convex-strongly-convex and convex-strongly-convex bilevel optimizations. Second, we propose an accelerated bilevel optimizer named AccBiO, for which we provide the first-known complexity bounds without the gradient boundedness assumption (which was made in existing analyses) under the two aforementioned geometries. We also provide significantly tighter upper bounds than the existing complexity when the bounded gradient assumption does hold. We show that AccBiO achieves the optimal results (i.e., the upper and lower bounds match up to logarithmic factors) when the inner-level problem takes a quadratic form with a constant-level condition number. Interestingly, our lower bounds under both geometries are larger than the corresponding optimal complexities of minimax optimization, establishing that bilevel optimization is provably more challenging than minimax optimization. Our theoretical results are validated by numerical experiments.

关键词： bilevel optimization lower bounds accelerated algorithms computational complexity convergence rate optimality

来源：评论

学校读者我要写书评

暂无评论

accelerated Decentralized Load Balancing in Multi-Agent Networks

引用

IEEE ACCESS 2024年 12卷 161954-161967页

作者： Erofeeva, Victoria Granichin, Oleg Volodina, Elena St Petersburg State Univ Ctr Artificial Intelligence & Data Sci St Petersburg 199034 Russia St Petersburg State Univ Fac Math & Mech St Petersburg 199034 Russia

Decentralized load balancers are gaining in popularity because they offer scalability, resilience, and the ability to handle high-demand workloads in distributed network systems. In practice, decentralized algorithms face such network issues as connection losses, dropped packets during data transmission, network latency. They should also account for the physical limitations of real systems. Existing works primarily consider different meta-heuristic approaches to carry out load balancing. Nevertheless, theoretically grounded algorithms that work under non-stationary conditions are of interest. In this paper, we improve the convergence rate of an existing decentralized load balancing protocol based on Local Voting Protocol (LVP) to obtain a solution that tends towards the optimal load balancing strategy over time. We propose a new accelerated-LVP protocol and derive its parameters required to achieve the acceleration. The simulation demonstrates superiority of the proposed solution over the existing approaches in terms of convergence rate. In our experiments, we consider two scenarios: steady and bursty. In the first scenario, we observe that, on average, the proposed algorithm achieves the lowest error rate 15% faster than the nearest competitor. In the second scenario, on average, the proposed algorithm achieves an error rate that is 10% less than the nearest competitor.

关键词： Load management Protocols Peer-to-peer computing Convergence Symbols Productivity Prediction algorithms Network systems Load modeling Multi-agent systems Load balancing decentralized networks accelerated algorithms non-stationary optimization Local Voting Protocol network disruptions multi-agent systems

来源：评论

学校读者我要写书评

暂无评论

A Study on Accelerating Average Consensus algorithms Using Delayed Feedback

引用

IEEE TRANSACTIONS ON CONTROL OF NETWORK SYSTEMS 2023年第1期10卷 157-168页

作者： Moradian, Hossein Kia, Solmaz S. Univ Calif Irvine Dept Mech & Aerosp Engn Irvine CA 92697 USA

This article studies accelerating a Laplacian-based dynamic average consensus algorithm by splitting the conventional delay-free disagreement feedback into a weighted summation of current and outdated terms. When determining the weighted sum, there is a range of time delay that results in a higher convergence rate for the algorithm. For such weights, using the Lambert W function, we obtain the rate-increasing range of the time delay, obtain the maximum reachable rate, and characterize the value of the corresponding maximizer delay. We also study the effect of using the outdated feedback on the control effort of the agents. We show that only for some specific affine combination of the immediate and outdated feedback, the control effort of the agents does not go beyond that of the delay-free algorithm. In addition, we demonstrate that using outdated feedback does not increase the steady-state tracking error of the average consensus algorithm. Finally, we determine the optimum combination of the current and the outdated feedback weights to achieve the maximum increase in the rate of convergence without increasing the control effort of the agents. We demonstrate our results through a numerical example.

关键词： Convergence Delays Heuristic algorithms Consensus algorithm Laplace equations Delay effects Network topology accelerated algorithms average consensus distributed systems

来源：评论

学校读者我要写书评

暂无评论

HIGH-ORDER OPTIMIZATION METHODS FOR FULLY COMPOSITE PROBLEMS

引用

SIAM JOURNAL ON OPTIMIZATION 2022年第3期32卷 2402-2427页

作者： Doikov, Nikita Nesterov, Yurii Catholic Univ Louvain UCL Inst Informat & Commun Technol Elect & Appl Math B-1348 Louvain La Neuve Belgium Catholic Univ Louvain UCL CORE B-1348 Louvain La Neuve Belgium

In this paper, we study a fully composite formulation of convex optimization problems, which includes, as a particular case, the problems with functional constraints, max-type minimization problems, and problems with simple nondifferentiable components. We treat all these formulations in a unified way, highlighting the existence of very natural optimization schemes of different order p >= 1. As the result, we obtain new high-order (p >= 2) optimization methods for composite formulation. We prove the global convergence rates for them under the most general conditions. Assuming that the upper-level component of our objective function is subhomogeneous, we develop efficient modification of the basic fully composite first-order and second-order methods and propose their accelerated variants.

关键词： convex optimization constrained optimization nonsmooth optimization gradient methods high-order methods accelerated algorithms

来源：评论

学校读者我要写书评

暂无评论

Fast sparse optimization via adaptive shrinkage 22

Fast sparse optimization via adaptive shrinkage

引用

22nd World Congress of the International Federation of Automatic Control (IFAC)

作者： Cerone, Vito Fosson, Sophie M. Regruto, Diego Politecn Torino Dept Control & Comp Engn Turin Italy

ISBN: (纸本)9781713872344

The need for fast sparse optimization is emerging, e.g., to deal with large-dimensional data-driven problems and to track time-varying systems. In the framework of linear sparse optimization, the iterative shrinkage-thresholding algorithm is a valuable method to solve Lasso, which is particularly appreciated for its ease of implementation. Nevertheless, it converges slowly. In this paper, we develop a proximal method, based on logarithmic regularization, which turns out to be an iterative shrinkage-thresholding algorithm with adaptive shrinkage hyperparameter. This adaptivity substantially enhances the trajectory of the algorithm, in a way that yields faster convergence, while keeping the simplicity of the original method. Our contribution is twofold: on the one hand, we derive and analyze the proposed algorithm;on the other hand, we validate its fast convergence via numerical experiments and we discuss the performance with respect to state-of-the-art algorithms. Copyright (c) 2023 The Authors.

关键词： Sparse learning optimization estimation iterative/recursive algorithms proximal algorithms accelerated algorithms

来源：评论

学校读者我要写书评

暂无评论

Decentralized personalized federated learning: Lower bounds and optimal algorithm for all personalization modes

引用

EURO JOURNAL ON COMPUTATIONAL OPTIMIZATION 2022年 10卷

作者： Sadiev, Abdurakhmon Borodich, Ekaterina Beznosikov, Aleksandr Dvinskikh, Darina Chezhegov, Saveliy Tappenden, Rachael Takac, Martin Gasnikov, Alexander Moscow Inst Phys & Technol MIPT Moscow Russia Mohamed Bin Zayed Univ Artificial Intelligence MB Abu Dhabi U Arab Emirates HSE Univ Moscow Russia Univ Canterbury Christchurch New Zealand RAS Inst Informat Transmiss Problems Moscow Russia

This paper considers the problem of decentralized, personal-ized federated learning. For centralized personalized federated learning, a penalty that measures the deviation from the local model and its average, is often added to the objective function. However, in a decentralized setting this penalty is expensive in terms of communication costs, so here, a different penalty - one that is built to respect the structure of the underlying computational network - is used instead. We present lower bounds on the communication and local computation costs for this problem formulation and we also present provably optimal methods for decentralized personalized federated learning. Numerical experiments are presented to demonstrate the practical performance of our methods. (c) 2022 The Authors. Published by Elsevier Ltd on behalf of Association of European Operational Research Societies (EURO). This is an open access article under the CC BY-NC-ND license (http://***/licenses/by-nc-nd/4.0/).

关键词： Federated learning Decentralized optimization Distributed optimization Lower and upper bounds accelerated algorithms

来源：评论

学校读者我要写书评

暂无评论

accelerated variance-reduced methods for saddle-point problems

引用

EURO JOURNAL ON COMPUTATIONAL OPTIMIZATION 2022年 10卷

作者： Borodich, Ekaterina Tominin, Vladislav Tominin, Yaroslav Kovalev, Dmitry Gasnikov, Alexander Dvurechensky, Pavel Moscow Inst Phys & Technol Moscow Russia HSE Univ Moscow Russia Weierstrass Inst Appl Anal & Stochast Berlin Germany King Abdullah Univ Sci & Technol Thuwal Saudi Arabia RAS Inst Informat Transmiss Problems Moscow Russia

We consider composite minimax optimization problems where the goal is to find a saddle-point of a large sum of non -bilinear objective functions augmented by simple composite regularizers for the primal and dual variables. For such problems, under the average-smoothness assumption, we propose accelerated stochastic variance-reduced algorithms with optimal up to logarithmic factors complexity bounds. In particular, we consider strongly-convex-strongly-concave, convex-strongly-concave, and convex-concave objectives. To the best of our knowledge, these are the first nearly-optimal algorithms for this setting.(c) 2022 The Author(s). Published by Elsevier Ltd on behalf of Association of European Operational Research Societies (EURO). This is an open access article under the CC BY license (http://***/licenses/by/4.0/).

关键词： Saddle-point problem Minimax optimization Composite optimization Stochastic variance-reduced algorithms accelerated algorithms

来源：评论

学校读者我要写书评

暂无评论

Fast and safe: accelerated gradient methods with optimality certificates and underestimate sequences

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2021年第2期79卷 369-404页

作者： Jahani, Majid Gudapati, Naga Venkata C. Ma, Chenxin Tappenden, Rachael Takac, Martin Lehigh Univ Dept Syst & Ind Engn HS Mohler Lab 200 West Packer Ave Bethlehem PA 18015 USA Univ Bologna Dept Elect Elect & Informat Engn Viale Risorgimento 2 I-40136 Bologna Italy Univ Canterbury Sch Math & Stat Private Bag 4800 Christchurch 8140 New Zealand

In this work we introduce the concept of an Underestimate Sequence (UES), which is motivated by Nesterov's estimate sequence. Our definition of a UES utilizes three sequences, one of which is a lower bound (or under-estimator) of the objective function. The question of how to construct an appropriate sequence of lower bounds is addressed, and we present lower bounds for strongly convex smooth functions and for strongly convex composite functions, which adhere to the UES framework. Further, we propose several first order methods for minimizing strongly convex functions in both the smooth and composite cases. The algorithms, based on efficiently updating lower bounds on the objective functions, have natural stopping conditions that provide the user with a certificate of optimality. Convergence of all algorithms is guaranteed through the UES framework, and we show that all presented algorithms converge linearly, with the accelerated variants enjoying the optimal linear rate of convergence.

关键词： Underestimate sequence Estimate sequence Quadratic averaging Lower bounds Strongly convex Smooth minimization Composite minimization accelerated algorithms

来源：评论

学校读者我要写书评

暂无评论

Fast sparse optimization via adaptive shrinkage

引用

IFAC-PapersOnLine 2023年第2期56卷 10390-10395页

作者： Vito Cerone Sophie M. Fosson Diego Regruto

The need for fast sparse optimization is emerging, e.g., to deal with large-dimensional data-driven problems and to track time-varying systems. In the framework of linear sparse optimization, the iterative shrinkage-thresholding algorithm is a valuable method to solve Lasso, which is particularly appreciated for its ease of implementation. Nevertheless, it converges slowly. In this paper, we develop a proximal method, based on logarithmic regularization, which turns out to be an iterative shrinkage-thresholding algorithm with adaptive shrinkage hyperparameter. This adaptivity substantially enhances the trajectory of the algorithm, in a way that yields faster convergence, while keeping the simplicity of the original method. Our contribution is twofold: on the one hand, we derive and analyze the proposed algorithm; on the other hand, we validate its fast convergence via numerical experiments and we discuss the performance with respect to state-of-the-art algorithms.

关键词： Sparse learning optimization estimation iterative/recursive algorithms proximal algorithms accelerated algorithms

来源：评论

学校读者我要写书评

暂无评论

Computation-Aware Distributed Optimization over Networks: A Hybrid Dynamical Systems Approach

Computation-Aware Distributed Optimization over Networks: A ...

引用

2021 Workshop on Computation-Aware Algorithmic Design for Cyber-Physical Systems (CAADCPS)

作者： Ochoa, Daniel E. Poveda, Jorge, I Uribe, Cesar A. Univ Colorado Boulder CO 80309 USA Rice Univ Houston TX 77251 USA

ISBN: (纸本)9781450383998

The area of Cyber-Physical Systems (CPS) has emerged as a general discipline that studies complex dynamical systems that incorporate computation, control, and communication technologies [10]. The application of CPS spans several domains, from autonomous driving and intelligent transportation systems to deep-space exploration and quantum computing. However, traditionally, the algorithmic design and the implementation of CPS algorithms have been studied separately. While this approach facilitates the theoretical analysis of the system, it naturally poses critical issues when deploying the designed systems in their intended domain, i.e., the physical world. © 2021 Owner/Author.

关键词： Distributed Optimization accelerated algorithms Hybrid Dynamical Systems Computation-Aware algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：