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

Analysis of Target Data-Dependent greedy Kernel algorithms: Convergence Rates for f-, f . P- and f/P-greedy

CONSTRUCTIVE APPROXIMATION 2023年第1期57卷 45-74页

作者： Wenzel, Tizian Santin, Gabriele Haasdonk, Bernard Univ Stuttgart Inst Appl Anal & Numer Simulat Stuttgart Germany Bruno Kessler Fdn Digital Soc Ctr Trento Italy

Data-dependent greedy algorithms in kernel spaces are known to provide fast converging interpolants, while being extremely easy to implement and efficient to run. Despite this experimental evidence, no detailed theory has yet been presented. This situation is unsatisfactory, especially when compared to the case of the data-independent P-greedy algorithm, for which optimal convergence rates are available, despite its performances being usually inferior to the ones of target data-dependent algorithms. In this work, we fill this gap by first defining a new scale of greedy algorithms for interpolation that comprises all the existing ones in a unique analysis, where the degree of dependency of the selection criterion on the functional data is quantified by a real parameter. We then prove new convergence rates where this degree is taken into account, and we show that, possibly up to a logarithmic factor, target data-dependent selection strategies provide faster convergence. In particular, for the first time we obtain convergence rates for target data adaptive interpolation that are faster than the ones given by uniform points, without the need of any special assumption on the target function. These results are made possible by refining an earlier analysis of greedy algorithms in general Hilbert spaces. The rates are confirmed by a number of numerical examples.

关键词： Kernel methods greedy algorithms Convergence rates Target data-dependent algorithms

来源：评论

学校读者我要写书评

暂无评论

A Family of Fast Parallel greedy algorithms for the Steiner Forest Problem

A Family of Fast Parallel Greedy Algorithms for the Steiner ...

引用

IEEE International Symposium on Parallel and Distributed Processing Workshops and Phd Forum (IPDPSW)

作者： Laleh Ghalami Daniel Grosu Department of Computer Science Wayne State University Detroit USA

ISBN: (数字)9781665497473

ISBN: (纸本)9781665497480

We introduce a family of fast parallel greedy algorithms for the Steiner Forest Problem, a fundamental combinatorial optimization problem in graphs. Given an undirected graph with non-negative weights for edges and a set of pairs of vertices called terminals, the Steiner Forest Problem is to find the minimum cost subgraph that connects each of the terminal pairs together. We design a family of parallel algorithms based on a sequential heuristic greedy algorithm called Paired greedy which iteratively connects the terminal pairs that have the minimum distance. The family of parallel algorithms consists of a set of algorithms exhibiting various degrees of parallelism determined by the number of pairs that are connected in parallel in each iteration of the algorithms. We implement and run the algorithms on a multi-core system and perform an extensive experimental analysis. The results show that our proposed parallel algorithms achieve significant speedup with respect to the sequential Paired greedy algorithm and provide solutions with costs that are very close to those of the solutions obtained by the sequential Paired greedy algorithm.

关键词： greedy algorithms Measurement Concurrent computing Distributed processing Costs Conferences Forestry

来源：评论

学校读者我要写书评

暂无评论

Online Learning via Offline greedy algorithms: Applications in Market Design and Optimization 21

Online Learning via Offline Greedy Algorithms: Applications ...

引用

Proceedings of the 22nd ACM Conference on Economics and Computation

作者： Rad Niazadeh Negin Golrezaei Joshua R. Wang Fransisca Susan Ashwinkumar Badanidiyuru The University of Chicago Chicago IL USA Massachusetts Institute of Technology Cambridge MA USA Google Research Mountain View CA USA

ISBN: (纸本)9781450385541

Motivated by online decision-making in time-varying combinatorial environments, we study the problem of transforming offline algorithms to their online counterparts. We focus on offline combinatorial problems that are amenable to a constant factor approximation using a greedy algorithm that is robust to local errors. For such problems, we provide a general framework that efficiently transforms offline robust greedy algorithms to online ones using Blackwell *** show that the resulting online algorithms have O(T1/2) (approximate) regret under the full information setting. We further introduce a bandit extension of Blackwell approachability that we call Bandit Blackwell approachability. We leverage this notion to transform greedy robust offline algorithms into a O(T2/3) (approximate) regret in the bandit setting. Demonstrating the flexibility of our framework, we apply our offline-to-online transformation to several problems at the intersection of revenue management, market design, and online optimization, including product ranking optimization in online platforms, reserve price optimization in auctions, and submodular maximization. We show that our transformation, when applied to these applications, leads to new regret bounds or improves the current known bounds.

关键词： blackwell approachability greedy algorithms online combinatorial optimization online learning

来源：评论

学校读者我要写书评

暂无评论

Non-Negative Orthogonal greedy algorithms

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2019年第21期67卷 5643-5658页

作者： Thanh Thi Nguyen Idier, Jerome Soussen, Charles Djermoune, El-Hadi Univ Lorraine F-54506 Vandceuvre Les Nancy France CNRS Ctr Rech Automat Nancy F-54506 Vandceuvre Les Nancy France CNRS Lab Sci Numer Nantes F-44321 Nantes France Univ Paris Saclay Univ Paris Sud CNRS Cent SupelecLab Signaux & Syst F-91192 Gif Sur Yvette France

Orthogonal greedy algorithms are popular sparse signal reconstruction algorithms. Their principle is to select atoms one by one. A series of unconstrained least-square subproblems of gradually increasing size is solved to compute the approximation coefficients, which is efficiently performed using a fast recursive update scheme. When dealing with non-negative sparse signal reconstruction, a series of non-negative least-squares subproblems have to be solved. Fast implementation becomes tricky since each subproblem does not have a closed-form solution anymore. Recently, non-negative extensions of the classical orthogonal matching pursuit and orthogonal least squares algorithms were proposed, using slow (i.e., non-recursive) or recursive but inexact implementations. In this paper, we revisit these algorithms in a unified way. We define a class of non-negative orthogonal greedy algorithms and exhibit their structural properties. We propose a fast and exact implementation based on the active-set resolution of non-negative least-squares and exploiting warm start initializations. The algorithms are assessed in terms of accuracy and computational complexity for a sparse spike deconvolution problem. We also present an application to near-infrared spectra decomposition.

关键词： greedy algorithms Signal processing algorithms Matching pursuit algorithms Sparse representation Approximation algorithms Dictionaries Acceleration Orthogonal greedy algorithms sparse reconstru-ction non-negativity non-negative least-squares active-set algorithms

来源：评论

学校读者我要写书评

暂无评论

Some greedy algorithms for sparse polynomial chaos expansions

引用

JOURNAL OF COMPUTATIONAL PHYSICS 2019年第0期387卷 303-325页

作者： Baptista, Ricardo Stolbunov, Valentin Nair, Prasanth B. Univ Toronto Inst Aerosp Studies Toronto ON M3H 5T6 Canada MIT 77 Massachusetts Ave Cambridge MA 02139 USA

Compressed sensing algorithms approximate functions using limited evaluations by searching for a sparse representation among a dictionary of basis functions. Orthogonal matching pursuit (OMP) is a greedy algorithm for selecting basis functions whose computational cost scales with the size of the dictionary. For polynomial chaos (PC) approximations, the size of the dictionary grows quickly with the number of model inputs and the maximum polynomial degree, making them often prohibitive to use with greedy methods. We propose two new algorithms for efficiently constructing sparse PC expansions for problems with high-dimensional inputs. The first algorithm is a parallel OMP method coupled with an incremental QR factorization scheme, wherein the model construction step is interleaved with a nu-fold cross-validation procedure. The second approach is a randomized greedy algorithm that leverages a probabilistic argument to only evaluate a subset of basis functions from the dictionary at each iteration of the incremental algorithm. The randomized algorithm is demonstrated to recover model outputs with a similar level of sparsity and accuracy as OMP, but with a cost that is independent of the dictionary size. Both algorithms are validated with a numerical comparison of their performance on a series of algebraic test problems and PDEs with high-dimensional inputs. (C) 2019 Elsevier Inc. All rights reserved.

关键词： Polynomial chaos greedy algorithms Uncertainty quantification Compressed sensing Stochastic models

来源：评论

学校读者我要写书评

暂无评论

The statistical properties analysis of reconstruction error in greedy pursuit algorithms: Taking OMP as an example

引用

ELECTRONICS LETTERS 2023年第22期59卷 e13023-e13023页

作者： Xiao, Lei Han, Yubing Ma, Xiaofeng Dai, Minghui Nanjing Univ Sci & Technol Sch Elect & Opt Engn Nanjing Jiangsu Peoples R China

greedy pursuit algorithms are widely used in sparse signal processing for their computational efficiency. However, research on the reconstruction error properties is far from comprehensive. This paper derives the statistical properties of reconstruction error in greedy pursuit algorithms, including probability density function (PDF), expectation, and covariance. The reconstruction error follows a mixture distribution, which is composed of multiple multivariate random variables and weighted by the probability of support sets. The multivariate random variable obeys a truncated distribution that results from restricting the noise domain. The validity of the derivations is verified by using the orthogonal matching pursuit (OMP) algorithm as an example. This paper delves into the statistical properties of the reconstruction error in greedy pursuit algorithms. It establishes that the reconstruction error follows a mixture multivariate truncated Gaussian distribution. The OMP algorithm is taken as an example to derive the PDF, expectation, and covariance matrix of the reconstruction ***

关键词： compressed sensing greedy algorithms signal reconstruction statistical distributions

来源：评论

学校读者我要写书评

暂无评论

greedy training algorithms for neural networks and applications to PDEs

引用

JOURNAL OF COMPUTATIONAL PHYSICS 2023年第1期484卷

作者： Siegel, Jonathan W. Hong, Qingguo Jin, Xianlin Hao, Wenrui Xu, Jinchao Penn State Univ Dept Math University Pk PA 16802 USA Peking Univ Sch Math Sci Beijing Peoples R China

Recently, neural networks have been widely applied for solving partial differential equations (PDEs). Although such methods have been proven remarkably successful on practical engineering problems, they have not been shown, theoretically or empirically, to converge to the underlying PDE solution with arbitrarily high accuracy. The primary difficulty lies in solving the highly non-convex optimization problems resulting from the neural network discretization, which are difficult to treat both theoretically and practically. It is our goal in this work to take a step toward remedying this. For this purpose, we develop a novel greedy training algorithm for shallow neural networks. Our method is applicable to both the variational formulation of the PDE and also to the residual minimization formulation pioneered by physics informed neural networks (PINNs). We analyze the method and obtain a priori error bounds when solving PDEs from the function class defined by shallow networks, which rigorously establishes the convergence of the method as the network size increases. Finally, we test the algorithm on several benchmark examples, including high dimensional PDEs, to confirm the theoretical convergence rate. Although the method is expensive relative to traditional approaches such as finite element methods, we view this work as a proof of concept for neural network-based methods, which shows that numerical methods based upon neural networks can be shown to rigorously converge.(c) 2023 Elsevier Inc. All rights reserved.

关键词： Neural networks Partial differential equations greedy algorithms Generalization accuracy

来源：评论

学校读者我要写书评

暂无评论

Hybrid optimisation method of sparse FIR DFEs based on reweighted l1-norm minimisation and greedy algorithms

引用

ELECTRONICS LETTERS 2019年第8期55卷 491-492页

作者： Yu, Lihong Zhao, Jiaxiang Nankai Univ Coll Artificial Intelligence Tianjin 300350 Peoples R China Nankai Univ Coll Elect Informat & Opt Engn Tianjin 300350 Peoples R China

The finite-impulse-response (FIR) decision feedback equalisers (DFEs) with a large number of taps are used to eliminate the intersymbol interference. In this Letter, a hybrid optimisation approach based on reweighted l(1)-norm minimisation and the greedy algorithm is proposed to get a better estimation of the non-zero taps. First, the authors transform the problem of designing sparse FIR multiple-input multiple-output DFEs into an l(0)-norm minimisation problem, then use the proposed approach, which involves two stages as the preliminary selection of non-zero tap positions and re-optimisation with non-zero taps, to determine the positions and values of the non-zero taps for the FIR DFEs. The simulation results demonstrate the effectiveness of the proposed hybrid optimisation approach.

关键词： intersymbol interference decision feedback equalisers transient response minimisation FIR filters optimisation greedy algorithms MIMO communication hybrid optimisation method sparse FIR DFEs greedy algorithm finite-impulse-response decision feedback equalisers intersymbol interference hybrid optimisation approach nonzero taps sparse FIR multiple-input multiple-output DFEs norm minimisation problem nonzero tap positions

来源：评论

学校读者我要写书评

暂无评论

Duality Gap Estimates for Weak Chebyshev greedy algorithms in Banach Spaces

引用

COMPUTATIONAL MATHEMATICS AND MATHEMATICAL PHYSICS 2019年第6期59卷 904-914页

作者： Mironov, S. V. Sidorov, S. P. Saratov NG Chernyshevskii State Univ Saratov 410012 Russia

The paper studies weak greedy algorithms for finding sparse solutions of convex optimization problems in Banach spaces. We consider the concept of duality gap, the values of which are implicitly calculated at the step of choosing the direction of the fastest descent at each iteration of the greedy algorithm. We show that these values give upper bounds for the difference between the values of the objective function in the current state and the optimal point. Since the value of the objective function at the optimal point is not known in advance, the current values of the duality gap can be used, for example, in the stopping criteria for the greedy algorithm. In the paper, we find estimates of the duality gap values depending on the number of iterations for the weak greedy algorithms under consideration.

关键词： nonlinear optimization greedy algorithms sparse solution

来源：评论

学校读者我要写书评

暂无评论

Multi-AGV Motion Planning Using greedy Search algorithms and Learned Heuristics

Multi-AGV Motion Planning Using Greedy Search Algorithms and...

引用

IEEE/ASME (AIM) International Conference on Advanced Intelligent Mechatronics

作者： Sohta Kawawaki Ayumu Goto Kosuke Taneda Takeshi Muranaka Yuji Enoki Toyokazu Kobayashi Tomoya Hattori Ryota Takamido Jun Ota Department of Precision Engineering School of Engineering The University of Tokyo Tokyo Japan Logistics & Automation Division Murata Machinery Ltd. Kyoto Japan Research into Artifacts Center for Engineering (RACE) School of Engineering The University of Tokyo Tokyo Japan

ISBN: (数字)9798350355369

ISBN: (纸本)9798350355376

For productive operations involving multiple Automated Guided Vehicles (AGVs), it is essential to plan motions quickly that minimize the total sum of costs required for each AGV to perform transport tasks (Sum-of-Costs). However, calculating motions that achieve a superior Sum-of-Costs within a short period is challenging. This study introduces a strategy to accelerate motion planning for multiple AGVs utilizing Conflict-based Search (CBS). It incorporates two methodologies: (a) employing greedy search algorithms, and (b) integrating learned heuristics into the A* search algorithm. After implementing and simulating each method, the proposed integrated methodology showed significant efficiency for 15 AGVs. It achieved a 96% reduction in computation time and limited the deterioration of the Sum-of-Costs to 8%, compared to the CBS-based method. Furthermore, even with a strict CPU time limit of 60 seconds, the proposed method successfully planned motions for 20 AGVs, tasks that the baseline method failed to accomplish.

关键词： greedy algorithms Machine learning algorithms Remotely guided vehicles Mechatronics Costs Heuristic algorithms Machine learning

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：