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

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

来源：评论

学校读者我要写书评

暂无评论

An overview of spatial microscopic and accelerated kinetic Monte Carlo methods

引用

JOURNAL OF COMPUTER-AIDED MATERIALS DESIGN 2007年第2期14卷 253-308页

作者： Chatterjee, Abhijit Vlachos, Dionisios G. Univ Delaware Dept Chem Engn Newark DE 19716 USA Univ Delaware Ctr Catalyt Sci & Technol Newark DE 19716 USA

The microscopic spatial kinetic Monte Carlo (KMC) method has been employed extensively in materials modeling. In this review paper, we focus on different traditional and multiscale KMC algorithms, challenges associated with their implementation, and methods developed to overcome these challenges. In the first part of the paper, we compare the implementation and computational cost of the null-event and rejection-free microscopic KMC algorithms. A firmer and more general foundation of the null-event KMC algorithm is presented. Statistical equivalence between the null-event and rejection-free KMC algorithms is also demonstrated. Implementation and efficiency of various search and update algorithms, which are at the heart of all spatial KMC simulations, are outlined and compared via numerical examples. In the second half of the paper, we review various spatial and temporal multiscale KMC methods, namely, the coarse-grained Monte Carlo (CGMC), the stochastic singular perturbation approximation, and the tau-leap methods, introduced recently to overcome the disparity of length and time scales and the one-at-a time execution of events. The concepts of the CGMC and the tau-leap methods, stochastic closures, multigrid methods, error associated with coarse-graining, a posteriori error estimates for generating spatially adaptive coarse-grained lattices, and computational speed-up upon coarse-graining are illustrated through simple examples from crystal growth, defect dynamics, adsorption-desorption, surface diffusion, and phase transitions.

关键词： review multiscale simulation coarse-graining mesoscopic modeling Monte Carlo materials defects diffusion crystal growth phase transitions accelerated algorithms binary tree efficient update efficient search tau-leap stiff stochastic computational singular perturbation low-dimensional manifold

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

accelerated Monte Carlo method for calculation of sink strengths of absorbing surfaces for 3-D migrating particles in crystals of the cubic system

引用

JOURNAL OF NUCLEAR MATERIALS 2020年第0期531卷 152006-000页

作者： Sivak, A. B. Sivak, P. A. Chernov, V. M. Natl Res Ctr Kurchatov Inst 1 Akad Kurchatova Pl Moscow 123182 Russia JSC VNIINM Moscow Russia

An accelerated (compared to the standard "residence-time" algorithm) Monte Carlo method for the calculation of the sink strengths of absorbing surfaces for particles in crystals of the cubic system has been suggested. On its basis, several algorithms have been developed which allow one to calculate the sink strengths either without any systematic inaccuracy or with its low and controlled magnitude. These algorithms have been tested by calculating the sink strengths of absorbing surfaces of different geometry (spherical, toroidal, cylindrical and planar) for particles (self-interstitial atoms, vacancies) in a crystal with BCC lattice. The use of the developed algorithms accelerates the calculations for low volume fractions of absorbers by orders of magnitude. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Monte Carlo accelerated algorithms Sink strengths Diffusion Self-interstitial atom Vacancy

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Efficient Dynamic Parallel MRI Reconstruction for the Low-Rank Plus Sparse Model

引用

IEEE TRANSACTIONS ON COMPUTATIONAL IMAGING 2019年第1期5卷 17-26页

作者： Lin, Claire Yilin Fessler, Jeffrey A. Univ Michigan Dept Math Ann Arbor MI 48109 USA Univ Michigan Dept Elect Engn & Comp Sci Ann Arbor MI 48109 USA

The low-rank plus sparse (L+S) decomposition model enables the reconstruction of undersampled dynamic parallel magnetic resonance imaging data. Solving for the low rank and the sparse components involves nonsmooth composite convex optimization, and algorithms for this problem can he categorized into proximal gradient methods and variable splitting methods. This paper investigates new efficient algorithms for both schemes. While current proximal gradient techniques for the L+S model involve the classical iterative soft thresholding algorithm (ISTA), this paper considers two accelerated alternatives, one based on the fast iterative shrinkage-thresholding algorithm (FISTA) and the other with the recent proximal optimized gradient method (POGM). In the augmented Lagrangian (AL) framework, we propose an efficient variable splitting scheme based on the form of the data acquisition operator, leading to simpler computation than the conjugate gradient approach required by existing AL methods. Numerical results suggest faster convergence of the efficient implementations for both frameworks, with POGM providing the fastest convergence overall and the practical benefit of being free of algorithm tuning parameters.

关键词： Parallel magnetic resonance imaging (MRI) dynamic MRI low-rank sparsity accelerated algorithms proximal gradient method (PGM) augmented lagrangian (AL) variable splitting

来源：评论

学校读者我要写书评

暂无评论

CONSTRAINED AGGLOMERATIVE HIERARCHICAL-CLASSIFICATION

引用

PATTERN RECOGNITION 1983年第2期16卷 213-217页

作者： PERRUCHET, C Issy les Moulineaux France

This paper presents a method of classification taking account of a contiguity constraint. This procedure is applicable to all data sets represented in two distinct spaces, one of which is defined by the introduction of a relation of contiguity. The basic idea is to favour the pairs of clusters which are close in this space (i.e. contiguous). In practice, the hierarchy depends on the choice of a contiguity threshold equal to the maximal distance beyond which two points are not contiguous. Following the description of the algorithm, one will find results dealing with the influence of the constraint and with the estimation of the contiguity threshold. To illustrate this paper, classifications of ground points distributed on a plane area and characterized by geochemical descriptors are given.

关键词： Cluster analysis Constrained classification Contiguity constraint accelerated algorithms Geochemical application

来源：评论

学校读者我要写书评

暂无评论

accelerated STOCHASTIC APPROXIMATION

引用

SIAM JOURNAL ON OPTIMIZATION 1993年第4期3卷 868-881页

作者： Delyon, Bernard Juditsky, Anatoli Inst Natl Rech Informat & Automat Inst Rech Informat & Syst Aleatoires F-35042 Rennes France

A technique to accelerate convergence of stochastic approximation algorithms is studied. It is based on Kesten's idea of equalization of the gain coefficient for the Robbins-Monro algorithm. Convergence with probability is proved for the multidimensional analog of the Kesten accelerated stochastic approximation algorithm. Asymptotic normality of the delivered estimates is also shown. Results of numerical simulations are presented that demonstrate the efficiency of the acceleration procedure.

关键词： stochastic approximation accelerated algorithms optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：