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

Model-Free Learning for Massive MIMO Systems: Stochastic Approximation Adjoint Iterative Learning Control

IEEE CONTROL SYSTEMS LETTERS 2021年第6期5卷 1946-1951页

作者： Aarnoudse, Leontine Oomen, Tom Eindhoven Univ Technol Dept Mech Engn Control Syst Technol NL-5600 MB Eindhoven Netherlands

Learning can substantially increase the performance of control systems that perform repeating tasks. The aim of this letter is to develop an efficient iterative learning control algorithm for MIMO systems with a large number of inputs and outputs that does not require model knowledge. The gradient of the control criterion is obtained through dedicated experiments on the system. Using a judiciously selected randomization technique, an unbiased estimate of the gradient is obtained from a single dedicated experiment, resulting in fast convergence of a Robbins-Monro type stochastic gradient descent algorithm. Analysis shows that the approach is superior to earlier deterministic approaches and to related SPSA-type algorithms. The approach is illustrated on a multivariable example.

关键词： Approximation algorithms Stochastic processes Data models Convergence Analytical models Optimization Noise measurement Iterative learning control large-scale systems optimization randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Online two-way trading: Randomization and advice

引用

THEORETICAL COMPUTER SCIENCE 2021年 856卷 41-50页

作者： Fung, Stanley P. Y. Univ Leicester Sch Informat Leicester LE1 7RH Leics England

We consider the following online two-way trading problem: given some amount of money and a stock (security) of fluctuating prices, we want to perform a bounded number of speculative trades so as to make the most money. We assume a global fluctuation model, where global limits on the minimum and maximum possible prices are given. Previously, optimal algorithms were established in the deterministic case. In this paper we consider two models that improve the competitiveness: randomized algorithms, and algorithms with advice. In most cases we give close to optimal upper and lower bounds on the competitive ratios. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Online algorithms Stock market trading randomized algorithms Advice complexity

来源：评论

学校读者我要写书评

暂无评论

Lower Bounds for Parallel and randomized Convex Optimization

引用

JOURNAL OF MACHINE LEARNING RESEARCH 2020年第1期21卷 1-31页

作者： Diakonikolas, Jelena Guzman, Cristobal Univ Wisconsin Madison Dept Comp Sci 1210 W Dayton St Madison WI 53706 USA Pontificia Univ Catolica Chile Inst Math & Computat Engn Fac Math Vicunna Mackenna 4860 Santiago 7820436 Chile Pontificia Univ Catolica Chile Sch Engn Millennium Nucleus Ctr Discovery Structures Compl Vicunna Mackenna 4860 Santiago 7820436 Chile

We study the question of whether parallelization in the exploration of the feasible set can be used to speed up convex optimization, in the local oracle model of computation and in the high-dimensional regime. We show that the answer is negative for both deterministic and randomized algorithms applied to essentially any of the interesting geometries and nonsmooth, weakly-smooth, or smooth objective functions. In particular, we show that it is not possible to obtain a polylogarithmic (in the sequential complexity of the problem) number of parallel rounds with a polynomial (in the dimension) number of queries per round. In the majority of these settings and when the dimension of the space is polynomial in the inverse target accuracy, our lower bounds match the oracle complexity of sequential convex optimization, up to at most a logarithmic factor in the dimension, which makes them (nearly) tight. Another conceptual contribution of our work is in providing a general and streamlined framework for proving lower bounds in the setting of parallel convex optimization. Prior to our work, lower bounds for parallel convex optimization algorithms were only known in a small fraction of the settings considered in this paper, mainly applying to Euclidean (l(2)) and l(infinity) spaces.

关键词： lower bounds convex optimization parallel algorithms randomized algorithms non-Euclidean optimization

来源：评论

学校读者我要写书评

暂无评论

randomized DISCRETE EMPIRICAL INTERPOLATION METHOD FOR NONLINEAR MODEL REDUCTION

引用

SIAM JOURNAL ON SCIENTIFIC COMPUTING 2020年第3期42卷 A1582-A1608页

作者： Saibaba, Arvind K. North Carolina State Univ Dept Math Raleigh NC 27695 USA

The discrete empirical interpolation method (DEIM) is a popular technique for nonlinear model reduction, and it has two main ingredients: an interpolating basis that is computed from a collection of snapshots of the solution, and a set of indices which determine the nonlinear components to be simulated. The computation of these two ingredients dominates the overall cost of the DEIM algorithm. To specifically address these two issues, we present randomized versions of the DEIM algorithm. There are three main contributions of this paper. First, we use randomized range finding algorithms to efficiently find an approximate DEIM basis. Second, we develop randomized subset selection tools, based on leverage scores, to efficiently select the nonlinear components. Third, we develop several theoretical results that quantify the accuracy of the randomization on the DEIM approximation. We also present numerical experiments that demonstrate the benefits of the proposed algorithms.

关键词： model reduction randomized algorithms discrete empirical interpolation method subset selection subspace iteration

来源：评论

学校读者我要写书评

暂无评论

Relatively Complete Verification of Probabilistic Programs

引用

PROCEEDINGS OF THE ACM ON PROGRAMMING LANGUAGES-PACMPL 2021年第POPL期5卷 1–30页

作者： Batz, Kevin Kaminski, Benjamin Lucien Katoen, Joost-Pieter Matheja, Christoph Rhein Westfal TH Aachen Aachen Germany UCL London England Swiss Fed Inst Technol Zurich Switzerland

We study a syntax for specifying quantitative "assertions"-functions mapping program states to numbers-for probabilistic program verification. We prove that our syntax is expressive in the following sense: Given any probabilistic program C, if a function f is expressible in our syntax, then the function mapping each initial state sigma to the expected value of f evaluated in the final states reached after termination of C on sigma (also called the weakest preexpectation wp[C] (f)) is also expressible in our syntax. As a consequence, we obtain a relatively complete verification system for reasoning about expected values and probabilities in the sense of Cook: Apart from proving a single inequality between two functions given by syntactic expressions in our language, given f, g, and C, we can check whether g <= wp[C] (f).

关键词： probabilistic programs randomized algorithms formal verification quantitative verification completeness weakest precondition weakest preexpectation

来源：评论

学校读者我要写书评

暂无评论

2-D Stochastic Configuration Networks for Image Data Analytics

引用

IEEE TRANSACTIONS ON CYBERNETICS 2021年第1期51卷 359-372页

作者： Li, Ming Wang, Dianhui South China Normal Univ Sch Informat Technol Educ Guangzhou 510631 Peoples R China La Trobe Univ Dept Comp Sci & Informat Technol Melbourne Vic 3086 Australia Northeastern Univ State Key Lab Synthet Automat Proc Ind Shenyang 110819 Peoples R China

Stochastic configuration networks (SCNs) as a class of randomized learner model have been successfully employed in data analytics due to its universal approximation capability and fast modeling property. The technical essence lies in stochastically configuring the hidden nodes (or basis functions) based on a supervisory mechanism rather than data-independent randomization as usually adopted for building randomized neural networks. Given image data modeling tasks, the use of 1-D SCNs potentially demolishes the spatial information of images, and may result in undesirable performance. This paper extends the original SCNs to a 2-D version, called 2DSCNs, for fast building randomized learners with matrix inputs. Some theoretical analysis on the goodness of 2DSCNs against SCNs, including the complexity of the random parameter space and the superiority of generalization, are presented. Empirical results over one regression example, four benchmark handwritten digit classification tasks, two human face recognition datasets, as well as one natural image database, demonstrate that the proposed 2DSCNs perform favorably and show good potential for image data analytics.

关键词： Data models Data analysis Computational modeling Analytical models Approximation algorithms Neural networks Buildings Image data analytics randomized algorithms 2-D stochastic configuration networks (2DSCNs)

来源：评论

学校读者我要写书评

暂无评论

Population Protocols for Exact Plurality Consensus 41

Population Protocols for Exact Plurality Consensus

引用

41st ACM Symposium on Principles of Distributed Computing, PODC 2022

作者： Bankhamer, Gregor Berenbrink, Petra Biermeier, Felix Elsässer, Robert Hosseinpour, Hamed Kaaser, Dominik Kling, Peter University of Salzburg Salzburg Austria Universität Hamburg Hamburg Germany Tu Hamburg Hamburg Germany

ISBN: (纸本)9781450392624

We consider the plurality consensus problem for population protocols. Here, n anonymous agents start each with one of k opinions. Their goal is to agree on the initially most frequent opinion (the plurality opinion) via random, pairwise interactions. Exact plurality consensus refers to the requirement that the plurality opinion must be identified even if the bias (difference between the most and second most frequent opinion) is only 1. The case of k = 2 opinions is known as the majority problem. Recent breakthroughs led to an always correct, exact majority population protocol that is both time- and space-optimal, needing O(logn) states per agent and, with high probability, O(logn) time [Doty, Eftekhari, Gasieniec, Severson, Uznanski, and Stachowiak;2021]. Meanwhile, results for general plurality consensus are rare and far from optimal. We know that any always correct protocol requires ω(k2) states, while the currently best protocol needs O(k11) states [Natale and Ramezani;2019]. For ordered opinions, this can be improved to O(k6) [Gasieniec, Hamilton, Martin, Spirakis, and Stachowiak;2016]. © 2022 ACM.

关键词： plurality consensus population protocols randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

A randomized COORDINATE DESCENT METHOD WITH VOLUME SAMPLING

引用

SIAM JOURNAL ON OPTIMIZATION 2020年第3期30卷 1878-1904页

作者： Rodomanov, Anton Kropotov, Dmitry Natl Res Univ Higher Sch Econ Samsung HSE Lab Moscow 109028 Russia Lomonosov Moscow State Univ Moscow 119991 Russia

We analyze the coordinate descent method with a new coordinate selection strategy, called volume sampling. This strategy prescribes selecting subsets of variables of certain size proportionally to the determinants of principal submatrices of the matrix, which bounds the curvature of the objective function. In the particular case when the size of the subsets equals one, volume sampling coincides with the well-known strategy of sampling coordinates proportionally to their Lipschitz constants. For the coordinate descent with volume sampling, we establish the convergence rates for both convex and strongly convex problems. Our theoretical results show that, by increasing the size of the subsets, it is possible to accelerate the method up to the factor which depends on the spectral gap between the corresponding largest eigenvalues of the curvature matrix. Several numerical experiments confirm our theoretical conclusions.

关键词： convex optimization unconstrained minimization coordinate descent methods randomized algorithms volume sampling convergence rate

来源：评论

学校读者我要写书评

暂无评论

Quadratically Tight Relations for randomized Query Complexity

引用

THEORY OF COMPUTING SYSTEMS 2020年第1期64卷 101-119页

作者： Jain, Rahul Klauck, Hartmut Kundu, Srijita Lee, Troy Santha, Miklos Sanyal, Swagato Vihrovs, Jevgenijs Natl Univ Singapore Ctr Quantum Technol Block S153 Sci Dr 2 Singapore 117543 Singapore MajuLab UMI 3654 Singapore Singapore Nanyang Technol Univ SPMS 21 Nanyang Link Singapore 637371 Singapore Univ Paris Diderot IRIF CNRS F-75205 Paris France Univ Latvia Fac Comp Ctr Quantum Comp Sci Raina 19 LV-1586 Riga Latvia

In this work we investigate the problem of quadratically tightly approximating the randomized query complexity of Boolean functions R(f). The certificate complexity C(f) is such a complexity measure for the zero-error randomized query complexity R0(f): C(f) = R0(f) = C(f)2. In the first part of the paper we introduce a new complexity measure, expectational certificate complexity EC(f), which is also a quadratically tight bound on R0(f): EC(f) = R0(f) = O(EC(f)2). For R(f), we prove that EC2/3 = R(f). We then prove that EC(f) = C(f) = EC(f)2 and show that there is a quadratic separation between the two, thus EC(f) gives a tighter upper bound for R0(f). The measure is also related to the fractional certificate complexity FC(f) as follows: FC(f) = EC(f) = O(FC(f)3/2). This also connects to an open question by Aaronson whether FC(f) is a quadratically tight bound for R0(f), as EC(f) is in fact a relaxation of FC(f). In the second part of the work, we investigate whether the corruption bound corr (f) quadratically approximates R(f). By Yao's theorem, it is enough to prove that the square of the corruption bound upper bounds the distributed query complexity D mu (f) for all input distributions mu. Here, we show that this statement holds for input distributions in which the various bits of the input are distributed independently. This is a natural and interesting subclass of distributions, and is also in the spirit of the input distributions studied in communication complexity in which the inputs to the two communicating parties are statistically independent. Our result also improves upon a result of Harsha et al. (2016), who proved a similar weaker statement. We also note that a similar statement in the communication complexity is open.

关键词： Query complexity randomized algorithms Certificate complexity Fractional block sensitivity Corruption bound

来源：评论

学校读者我要写书评

暂无评论

randomized core reduction for discrete ill-posed problem

引用

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS 2020年 375卷 112797-000页

作者： Zhang, Liping Wei, Yimin Zhejiang Univ Technol Dept Math Hangzhou 310023 Peoples R China Fudan Univ Sch Math Sci Shanghai 200433 Peoples R China Fudan Univ Shanghai Key Lab Contemporary Appl Math Shanghai 200433 Peoples R China

In this paper, we apply randomized algorithms to approximate the total least squares (TLS) solution of the problem Ax approximate to b in the large-scale discrete ill-posed problems. A regularization technique, based on the multiplicative randomization and the subspace iteration, is proposed to obtain the approximate core problem. In the error analysis, we provide upper bounds for the errors of the solution and the residual of the randomized core reduction. Illustrative numerical examples and comparisons are presented. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Core problem TLS problem randomized algorithms SVD III-posed

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：