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

AN ACCELERATED randomized PROXIMAL COORDINATE GRADIENT METHOD AND ITS APPLICATION TO REGULARIZED EMPIRICAL RISK MINIMIZATION

引用

SIAM JOURNAL ON OPTIMIZATION 2015年第4期25卷 2244-2273页

作者： Lin, Qihang Lu, Zhaosong Xiao, Lin Univ Iowa Tippie Coll Business Iowa City IA 52242 USA Simon Fraser Univ Dept Math Burnaby BC V5A 1S6 Canada Microsoft Res Machine Learning Grp Redmond WA 98052 USA

We consider the problem of minimizing the sum of two convex functions: one is smooth and given by a gradient oracle, and the other is separable over blocks of coordinates and has a simple known structure over each block. We develop an accelerated randomized proximal coordinate gradient (APCG) method for minimizing such convex composite functions. For strongly convex functions, our method achieves faster linear convergence rates than existing randomized proximal coordinate gradient methods. Without strong convexity, our method enjoys accelerated sublinear convergence rates. We show how to apply the APCG method to solve the regularized empirical risk minimization (ERM) problem and devise efficient implementations that avoid full-dimensional vector operations. For ill-conditioned ERM problems, our method obtains improved convergence rates than the state-of-the-art stochastic dual coordinate ascent method.

关键词： convex optimization coordinate descent method randomized algorithm accelerated proximal gradient method empirical risk minimization

来源：评论

学校读者我要写书评

暂无评论

Distributed Frequency Control via randomized Response of Electric Vehicles in Power Grid

引用

IEEE TRANSACTIONS ON SUSTAINABLE ENERGY 2016年第1期7卷 312-324页

作者： Moghadam, Mohammad R. Vedady Zhang, Rui Ma, Richard T. B. Natl Univ Singapore Dept Elect & Comp Engn Singapore 117576 Singapore Natl Univ Singapore Dept Elect & Comp Engn Singapore 117583 Singapore ASTAR Inst Infocomm Res Singapore 138632 Singapore Natl Univ Singapore Dept Comp Sci Singapore 117418 Singapore Adv Digital Sci Ctr Singapore 138632 Singapore

In this paper, we propose a new distributed frequency control scheme for electric vehicles (EVs) to help restore the power grid frequency upon a contingency of supply-demand imbalance. Under our scheme, each EV independently monitors the grid frequency at discrete times and responds by switching among its charging, idle, and discharging operational modes according to a simple threshold-based switching algorithm. To recover the grid frequency smoothly and prevent an undesired frequency overshoot/undershoot due to simultaneous response of EVs, we design the inter-response times of any EV to follow an exponentially distributed random variable with a certain mean value at each operational mode. To draw insights into the performance of our scheme, we characterize its impacts on the grid frequency in various aspects, including the mean and variance of the resulting grid frequency over time, the mean frequency recovery time, the average number of EV switching their modes, and the probability of frequency overshoot/undershoot. Accordingly, we formulate an optimization problem for the grid operator to minimize the expected cost of implementing our frequency control scheme by designing EVs' response rates subject to their requested incentive prices and the given grid performance guarantees. Finally, we validate our analysis via simulations on the IEEE 9-Bus test system and the Ireland power system, where it is observed that our frequency control scheme can be used as a reliable and cost-efficient alternative for the conventional primary reserve service.

关键词： Electric vehicle renewable energy sources distributed frequency control randomized algorithm optimization

来源：评论

学校读者我要写书评

暂无评论

randomized Monte Carlo algorithms for Problems with Random Parameters ("Double Randomization" Method)

引用

NUMERICAL ANALYSIS AND APPLICATIONS 2019年第2期12卷 155-165页

作者： Mikhailov, G. A. Russian Acad Sci Inst Computat Math & Math Geophys Siberian Branch Pr Akad Laurenteva 6 Novosibirsk 630090 Russia Novosibirsk State Univ Ul Pirogova 2 Novosibirsk 630090 Russia

randomized Monte Carlo algorithms are constructed by a combination of a basic probabilistic model and its random parameters to investigate parametric distributions of linear functionals. An optimization of the algorithms with a statistical kernel estimator for the probability density is presented. A randomized projection algorithm for estimating a nonlinear functional distribution is formulated and applied to the investigation of the criticality fluctuations of a particle multiplication process in a random medium.

关键词： probabilistic model statistical modeling random parameter randomized algorithm double randomization method random medium splitting method statistical kernel estimator

来源：评论

学校读者我要写书评

暂无评论

The method of randomized Bregman projections for stochastic feasibility problems

引用

NUMERICAL algorithmS 2023年第3期93卷 1269-1307页

作者： Kostic, Vladimir R. Salzo, Saverio Ist Italiano Tecnol Via Melen83 I-16152 Genoa Italy Univ Novi Sad Fac Sci Dept Math & Informat Trg Dositeja Obradovica 4 Novi Sad 21000 Serbia

In this work, we study the method of randomized Bregman projections for stochastic convex feasibility problems, possibly with an infinite number of sets, in Euclidean spaces. Under very general assumptions, we prove almost sure convergence of the iterates to a random almost common point of the sets. We then analyze in depth the case of affine sets showing that the iterates converge Q-linearly and providing also global and local rates of convergence. This work generalizes recent developments in randomized methods for the solution of linear systems based on orthogonal projection methods. We provided several applications: sketch & project methods for solving linear systems of equations, positive definite matrix completion problem, gossip algorithms for networks consensus, the assessment of robust stability of dynamical systems, and computational solutions for multimarginal optimal transport.

关键词： Stochastic convex feasibility problem Bregman projection method Linear convergence randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Practical sketching-based randomized tensor ring decomposition

引用

NUMERICAL LINEAR ALGEBRA WITH APPLICATIONS 2024年第4期31卷 e2548-e2548页

作者： Yu, Yajie Li, Hanyu Chongqing Univ Coll Math & Stat Chongqing 401331 Peoples R China

Based on sketching techniques, we propose two practical randomized algorithms for tensor ring (TR) decomposition. Specifically, on the basis of defining new tensor products and investigating their properties, the two algorithms are devised by applying the Kronecker sub-sampled randomized Fourier transform and TensorSketch to the alternating least squares subproblems derived from the minimization problem of TR decomposition. From the former, we find an algorithmic framework based on random projection for randomized TR decomposition. We compare our proposals with the existing methods using both synthetic and real data. Numerical results show that they have quite decent performance in accuracy and computing time.

关键词： alternating least squares problem Kronecker sub-sampled randomized Fourier transform randomized algorithm sketching tensor ring decomposition TensorSketch

来源：评论

学校读者我要写书评

暂无评论

On the randomized multiple row-action methods for solving linear least-squares problems

引用

NUMERICAL algorithmS 2024年 1-28页

作者： Zuo, Qian Wu, Nian-Ci Liu, Chengzhi Wang, Yatian Peking Univ Ctr Frontiers Comp Studies Beijing 100871 Peoples R China Peking Univ Sch Comp Sci Beijing 10087 Peoples R China South Cent Minzu Univ Sch Math & Stat Wuhan 430074 Peoples R China Hunan Univ Humanities Sci & Technol Sch Math & Finance Loudi 417000 Peoples R China Wuhan Univ Sch Math & Stat Wuhan 430072 Peoples R China

The randomized row-action method is a popular representative of the iterative algorithm because of its efficiency in solving the overdetermined and consistent systems of linear equations. In this paper, we present an extended randomized multiple row-action method to solve a given overdetermined and inconsistent linear system and analyze its computational complexities at each iteration. We prove that the proposed method can linearly converge in the mean square to the least-squares solution with a minimum Euclidean norm. Several numerical studies are presented to corroborate our theoretical findings. The real-world applications, such as image reconstruction and large noisy data fitting in computer-aided geometric design, are also presented for illustration purposes.

关键词： randomized algorithm Row-action method Convergence analysis Real-world application

来源：评论

学校读者我要写书评

暂无评论

Efficiency of randomized parallel backtrack search

引用

algorithmICA 1999年第1期24卷 14-28页

作者： Zhang, YJ Ortynski, A SABRE Grp Southlake TX 76092 USA No Telecom Richardson TX 75082 USA So Methodist Univ Dallas TX 75275 USA

This paper presents an improved analysis of a randomized parallel backtrack search algorithm (RPBS). Our analysis uses the single-node-donation model that each donation contains a single tree node. It is shown that with high probability the total number of messages generated by RPBS is O (phd) where p is the number of processors, and h and d are the height and degree of the backtrack search tree. Under the assumption of unit-time message delivery, it is shown that with high probability the execution time of RPBS is n/p + O (hd) where it is the number of nodes of the backtrack search tree and the leading term n/p has no constant factor. As the result of limited communication requirement, RPBS can be efficiently implemented in message-passing or shared-memory multiprocessor systems. A general analysis of network implementation of RPBS is presented. The concept of total routing time, the sum of routing times of all messages, is introduced as a measure of communication cost. It is shown that the overall effect of message delay to the execution time of RPBS is small if the total routing time is small. Some experimental data on a shared-memory machine are reported.

关键词： backtrack parallel computation randomized algorithm distributed computing combinatorial search problem

来源：评论

学校读者我要写书评

暂无评论

Explicit error bounds for randomized Smolyak algorithms and an application to infinite-dimensional integration

引用

JOURNAL OF APPROXIMATION THEORY 2020年 251卷 105342-105342页

作者： Gnewuch, M. Wnuk, M. Univ Osnabruck Inst Math Albrechtstr 28 A D-49076 Osnabruck Germany

Smolyak's method, also known as sparse grid method, is a powerful tool to tackle multivariate tensor product problems solely with the help of efficient algorithms for the corresponding univariate problem. In this paper we study the randomized setting, i.e., we randomize Smolyak's method. We provide upper and lower error bounds for randomized Smolyak algorithms with explicitly given dependence on the number of variables and the number of information evaluations used. The error criteria we consider are the worst case root mean square error (the typical error criterion for randomized algorithms, sometimes referred to as "randomized error",) and the root mean square worst case error (sometimes referred to as "worst-case error"). randomized Smolyak algorithms can be used as building blocks for efficient methods such as multilevel algorithms, multivariate decomposition methods or dimension-wise quadrature methods to tackle successfully high-dimensional or even infinite-dimensional problems. As an example, we provide a very general and sharp result on the convergence rate of Nth minimal errors of infinite-dimensional integration on weighted reproducing kernel Hilbert spaces. Moreover, we are able to characterize the spaces for which randomized algorithms for infinite-dimensional integration are superior to deterministic ones. We illustrate our findings for the special instance of weighted Korobov spaces. We indicate how these results can be extended, e.g., to spaces of functions whose smooth dependence on successive variables increases ("spaces of increasing smoothness") and to the problem of L-2-approximation (function recovery). (C) 2019 Elsevier Inc. All rights reserved.

关键词： Tensor product problem Sparse grid randomized algorithm Infinite-dimensional approximation Multivariate decomposition method Changing dimension algorithm

来源：评论

学校读者我要写书评

暂无评论

Improvement of Multidimensional randomized Monte Carlo algorithms with "Splitting"

引用

COMPUTATIONAL MATHEMATICS AND MATHEMATICAL PHYSICS 2019年第5期59卷 775-781页

作者： Mikhailov, G. A. Russian Acad Sci Inst Computat Math & Math Geophys Siberian Branch Novosibirsk 630090 Russia Novosibirsk State Univ Novosibirsk 630090 Russia

randomized Monte Carlo algorithms are constructed by jointly realizing a baseline probabilistic model of the problem and its random parameters (random medium) in order to study a parametric distribution of linear functionals. This work relies on statistical kernel estimation of the multidimensional distribution density with a homogeneous kernel and on a splitting method, according to which a certain number of baseline trajectories are modeled for each medium realization. The optimal value of is estimated using a criterion for computational complexity formulated in this work. Analytical estimates of the corresponding computational efficiency are obtained with the help of rather complicated calculations.

关键词： probabilistic model Monte Carlo method statistical modeling randomized algorithm double randomization method random medium splitting method statistical kernel estimate complexity of functional estimate

来源：评论

学校读者我要写书评

暂无评论

randomized Primal–Dual Proximal Block Coordinate Updates

引用

Journal of the Operations Research Society of China 2019年第2期7卷 205-250页

作者： Xiang Gao Yang-Yang Xu Shu-Zhong Zhang Department of Industrial and Systems Engineering University of MinnesotaMinneapolisUSA Department of Mathematical Sciences Rensselaer Polytechnic InstituteTroyUSA

In this paper,we propose a randomized primal–dual proximal block coordinate updating framework for a general multi-block convex optimization model with coupled objective function and linear *** mere convexity,we establish its O(1/t)convergence rate in terms of the objective value and feasibility *** framework includes several existing algorithms as special cases such as a primal–dual method for bilinear saddle-point problems(PD-S),the proximal Jacobian alternating direction method of multipliers(Prox-JADMM)and a randomized variant of the ADMM for multi-block convex *** analysis recovers and/or strengthens the convergence properties of several existing *** example,for PD-S our result leads to the same order of convergence rate without the previously assumed boundedness condition on the constraint sets,and for Prox-JADMM the new result provides convergence rate in terms of the objective value and the feasibility *** is well known that the original ADMM may fail to converge when the number of blocks exceeds *** result shows that if an appropriate randomization procedure is invoked to select the updating blocks,then a sublinear rate of convergence in expectation can be guaranteed for multi-block ADMM,without assuming any strong *** new approach is also extended to solve problems where only a stochastic approximation of the subgradient of the objective is available,and we establish an O(1/√t)convergence rate of the extended approach for solving stochastic programming.

关键词： Primal-dual method Alternating direction method of multipliers(ADMM) randomized algorithm Iteration complexity·First-order stochastic approximation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：