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

Sample-Based Neural approximation Approach for Probabilistic Constrained Programs

IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS 2023年第2期34卷 1058-1065页

作者： Shen, Xun Ouyang, Tinghui Yang, Nan Zhuang, Jiancang Grad Univ Adv Studies Dept Stat Sci SOKENDAI Tokyo 1068569 Japan Natl Inst Adv Ind Sci & Technol Tokyo 1350064 Japan China Three Gorges Univ Dept Hubei Prov Collaborat Innovat Ctr New Energy Yichang 443002 Peoples R China Inst Stat Math Tokyo 1908562 Japan

This article introduces a neural approximation-based method for solving continuous optimization problems with probabilistic constraints. After reformulating the probabilistic constraints as the quantile function, a sample-based neural network model is used to approximate the quantile function. The statistical guarantees of the neural approximation are discussed by showing the convergence and feasibility analysis. Then, by introducing the neural approximation, a simulated annealing-based algorithm is revised to solve the probabilistic constrained programs. An interval predictor model (IPM) of wind power is investigated to validate the proposed method.

关键词： Probabilistic logic Random variables Convergence approximation algorithms Wind power generation Optimization Neural networks Neural network model nonlinear optimization probabilistic constraints quantile function sample average approximation

来源：评论

学校读者我要写书评

暂无评论

Leveraging Sparse approximation for Monaural Overlapped Speech Separation From Auditory Perspective

引用

IEEE ACCESS 2023年 11卷 124748-124759页

作者： Sekiguchi, Hiroshi Narusue, Yoshiaki Morikawa, Hiroyuki Univ Tokyo Grad Sch Engn Bunkyo Ku Tokyo 1138656 Japan

Neuroscience suggests that the sparse behavior of a neural population underlies the mechanisms of the auditory system for monaural overlapped speech separation. This study investigates leveraging sparse approximation to improve speech separation in a conventional deep learning algorithm. We develop a combined model that embeds a sparse approximation algorithm, a multilayered iterative soft thresholding algorithm (ML-ISTA), into a conventional time-domain-based speech separation algorithm, Conv-TasNet. Adopting ML-ISTA is a crucial enabler for the embedding process and helps avoid solving a bi-level optimization problem comprising sparse approximation and speech separation. ML-ISTA performs sparse approximation through forward calculations, thereby eliminating the optimization of sparse approximation. The combined model is trained with WSJ0-2mix, the Wall Street Journal English corpus for two-speaker mixed speech without noisy or reverberant interference, to clarify the proposed method's performance. The model demonstrates that sparse approximation improves separation performance regardless of the approximation setting. The peak performance of the model exceeds that of Conv-TasNet by 1.1% to 4.7% in four speech quality criteria. Moreover, sparse approximation accelerates the combined model performance gain at the early stages of learning relative to Conv-TasNet. The primary novelty of the study is embedding the sparse approximation algorithm, ML-ISTA, into a deep-learning-based speech separation framework and the experimental proof of improved separation performance in the proposed algorithm.

关键词： Sparse representation approximation algorithms Behavioral sciences Auditory system Speech enhancement Optimization Neurons Neuroscience Deep learning Speech processing sparse approximation sparsity speech separation

来源：评论

学校读者我要写书评

暂无评论

Fully polynomial time approximation scheme for the pagination problem with hierarchical structure of tiles

引用

RAIRO-OPERATIONS RESEARCH 2023年第1期57卷 1-16页

作者： Grange, Aristide Kacem, Imed Martin, Sebastien Minich, Sarah Univ Lorraine LCOMS Metz France

The pagination problem is described as follows. We have a set of symbols, a collection of subsets over these symbols (we call these subsets the tiles) and an integer capacity C. The objective is to find the minimal number of pages (a type of container) on which we can schedule all the tiles while following two fundamental rules. We cannot assign more than C symbols on each page and a tile cannot be broken into several pieces, all of its symbols must be assigned to at least one of the pages. The difference from the Bin Packing Problem is that tiles can merge. If two tiles share a subset of symbols and if they are assigned to the same page, this subset will be assigned only once to the page (and not several times). In this paper, as this problem is NP-complete, we will consider a particular case of the dual problem, where we have exactly two pages for which the capacity must be minimized. We will present a fully polynomial time approximation scheme (FPTAS) to solve it. This approximation scheme is based on the simplification of a dynamic programming algorithm and it has a strongly polynomial time complexity. The conducted numerical experiments show its practical effectiveness.

关键词： approximation algorithms scheduling FPTAS dynamic programming

来源：评论

学校读者我要写书评

暂无评论

A fast approximation algorithm for the maximum 2-packing set problem on planar graphs

引用

OPTIMIZATION LETTERS 2023年第6期17卷 1435-1454页

作者： Trejo-Sanchez, Joel Antonio Madera-Ramirez, Francisco A. Alberto Fernandez-Zepeda, Jose Luis Lopez-Martinez, Jose Flores-Lamas, Alejandro CONACYT Ctr Res Math Dept Comp Sci Merida Yucatan Mexico Univ Autonoma Yucatan Dept Comp Sci Merida Yucatan Mexico Ctr Sci Res & Higher Educ Ensenada CICESE Dept Comp Sci Ensenada Baja California Mexico Royal Holloway Univ London Dept Comp Sci Egham Hill Egham Surrey England

Given an undirected graph G = (V, E), a subset S subset of V is a 2-packing set if, for any pair of vertices u, v is an element of S, the shortest path between them is at least three-edge long. Finding a 2-packing set of maximum cardinality is an NP-hard problem for arbitrary graphs. This paper proposes an approximation algorithm for the maximum 2-packing set problem for planar graphs. We show that our algorithm is at least lambda-2/lambda of the optimal (i.e. the approximation ratio is lambda/lambda-2), where lambda is a constant related to how the proposed algorithm decomposes the input graph into smaller subgraphs. Then, we improve the solution given by our approximation algorithm by adding some vertices to the solution. Experimentally, we show that our improved algorithm computes a near-optimal 2-packing set. This algorithm is the first approximation algorithm for the maximum 2-packing set to the best of our knowledge.

关键词： approximation algorithms Maximum 2-packing set Linear programming Planar graphs

来源：评论

学校读者我要写书评

暂无评论

Online approximation Scheme for Scheduling Heterogeneous Utility Jobs in Edge Computing

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2023年第1期31卷 352-365页

作者： Zhang, Chi Tan, Haisheng Huang, Haoqiang Han, Zhenhua Jiang, Shaofeng H-C Li, Guopeng Li, Xiang-Yang Univ Sci & Technol China LINKE Lab Hefei 230027 Peoples R China Univ Sci & Technol China CAS Key Lab Wireless Opt Commun Hefei 230027 Peoples R China Hong Kong Univ Sci & Technol Dept Comp Sci & Engn Hong Kong Peoples R China Microsoft Res Asia MSRA Shanghai 200232 Peoples R China Peking Univ Ctr Frontiers Comp Studies Beijing 100871 Peoples R China

Edge computing systems typically handle a wide variety of applications that exhibit diverse degrees of sensitivity to job latency. Therefore, a multitude of utility functions of the job response time need to be considered by the underlying job dispatching and scheduling mechanism. Nonetheless, previous studies in edge computing mainly focused on optimizing a single utility function across all jobs, e.g., linear, sigmoid, or the hard deadline. In this paper, we design online job dispatching and scheduling strategies in which different jobs can be categorized by different non-increasing utility functions. Our goal is to maximize the total utility of all scheduled jobs. We first prove that no online deterministic algorithm could achieve a competitive ratio better than the lower bound Omega(1/root epsilon) under the (1 + epsilon)-speed augmentation model. We proceed to propose an online algorithm, named as O4A, for handling jobs with heterogeneous utilities. We prove that O4A is O(1/epsilon(2))-competitive. We also design its distributed version, i.e., DO4A. We implement O4A and DO4A on an edge computing testbed running deep learning inference jobs. With the production trace from Google Cluster, our experimental and large-scale simulation results indicate that O4A can increase the total utility by up to 50% compared with state-of-the-art methods. Besides, the performance loss of DO4A is only 2% com pared with O4A with a small communication overhead involved. Moreover, both of our algorithms are robust to estimation errors in job processing time and transmission delay.

关键词： approximation algorithms scheduling edge computing

来源：评论

学校读者我要写书评

暂无评论

High Dimensional Origin Destination Calibration Using Metamodel Assisted Simultaneous Perturbation Stochastic approximation

引用

IEEE TRANSACTIONS ON INTELLIGENT TRANSPORTATION SYSTEMS 2023年第4期24卷 3845-3854页

作者： Ho, Mun Chon Lim, Joanne Mun-Yee Chong, Chun Yong Chua, Kah Keong Siah, Alvin Kuok Lim Monash Univ Malaysia Sch Engn Subang Jaya 47500 Malaysia Monash Univ Malaysia Sch Informat Technol Subang Jaya 47500 Malaysia Recogine Technol SDN BHD Subang Jaya 47650 Malaysia

The huge traffic data generated by intelligent transportation system (ITS) leads to the development of many advanced traffic models. These traffic models consist of many adjustable parameters which need to be calibrated before they are used in practice. This paper focuses on the offline calibration of origin-destination (OD) input parameters of a simulation-based traffic model to match its output with sensor data. An improved Simultaneous Perturbation Stochastic approximation (SPSA) algorithm called Metamodel Assisted Simultaneous Perturbation Stochastic approximation (MSPSA) is proposed in this paper to calibrate high-dimensional OD parameters within a tight computational budget. The proposed MSPSA combines the gradient of SPSA with the gradient of a differentiable metamodel function to improve the calibration efficiency. An integer program is also used to fine-tune the OD estimates. The proposed MSPSA algorithm is tested on a simple synthetic toy network and complex road network of Kuala Lumpur (KL), Malaysia. The proposed MSPSA algorithm is compared against SPSA and state-of-the-art Weighted Simultaneous Perturbation Stochastic approximation (WSPSA) in both transportation networks. For KL network, synthetic and real-world sensor measurements are used as ground truth references to evaluate the performance of each approach. Based on the simulation results, the proposed MSPSA algorithm is able to gain at least 50% of improvement as compared to SPSA and WSPSA in both synthetic and real-world scenarios.

关键词： Calibration Roads Transportation Perturbation methods Stochastic processes approximation algorithms Data models Origin-destination calibration stochastic approximation simulation-based optimization metamodel SPSA

来源：评论

学校读者我要写书评

暂无评论

approximation algorithm for prize-collecting weighted set cover with fairness constraints

引用

Discrete Applied Mathematics 2025年 373卷 301-315页

作者： Zhou, Mingchao Zhang, Zhao School of Mathematical Sciences Zhejiang Normal University Jinhua Zhejiang321004 China

Fairness has become one of the hottest concerns in recent research. This paper introduces the prize-collecting weighted set cover problem with fairness constraint (FPCWSC). It is a variant of the minimum weight set cover problem, in which every uncovered element incurs a penalty and the elements are divided into several groups, each group having a minimum number of elements required to be covered. The goal is to minimize the cost of selected sets plus the penalties on those uncovered elements, subject to the constraint that every group has its coverage requirement satisfied. We propose a four-phase algorithm using deterministic rounding twice, followed by a randomized rounding method and a greedy method. In polynomial time, the algorithm computes a feasible solution with an expected approximation ratio O(f+lnΔ), where f is the maximum number of sets containing a common element and Δ is the maximum number of groups having nonempty intersection with a set. © 2025 Elsevier B.V.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

BREACHING THE 2-approximation BARRIER FOR CONNECTIVITY AUGMENTATION: A REDUCTION TO STEINER TREE

引用

SIAM JOURNAL ON COMPUTING 2023年第3期52卷 718-739页

作者： Byrka, Jaroslaw Grandoni, Fabrizio Ameli, Afrouz Jabal Univ Wroclaw Wroclaw Poland USI SUPSI IDSIA Lugano Viganello Switzerland Eindhoven Univ Technol Eindhoven Netherlands

The basic goal of survivable network design is to build a cheap network that maintains the connectivity between given sets of nodes despite the failure of a few edges/nodes. The connectivity augmentation problem (CAP) is arguably one of the most basic problems in this area: given a k(-edge)-connected graph G and a set of extra edges (links), select a minimum cardinality subset A of links such that adding A to G increases its edge connectivity to k+ 1. Intuitively, one wants to make an existing network more reliable by augmenting it with extra edges. The best known approximation factor for this NP-hard problem is 2, and this can be achieved with multiple approaches (the first such result is in [G. N. Frederickson and J\'aj\'a, SIAM J. Comput., 10 (1981), pp. 270--283]. It is known [E. A. Dinitz, A. V. Karzanov, and M. V. Lomonosov, Studies in Discrete Optimization, Nauka, Moscow, 1976, pp. 290--306] that CAP can be reduced to the case k = 1, also known as the tree augmentation problem (TAP) for odd k, and to the case k = 2, also known as the cactus augmentation problem (CacAP) for even k. Prior to the conference version of this paper [J. Byrka, F. Grandoni, and A. Jabal Ameli, STOC'20, ACM, New York, 2020, pp. 815--825], several better than 2 approximation algorithms were known for TAP, culminating with a recent 1.458 approximation [F. Grandoni, C. Kalaitzis, and R. Zenklusen, STOC'18, ACM, New York, 1918, pp. 632--645]. However, for CacAP the best known approximation was 2. In this paper we breach the 2 approximation barrier for CacAP, hence, for CAP, by presenting a polynomial-time 2 ln(4) -967 1120 + \varepsilon < 1.91 approximation. From a technical point of view, our approach deviates quite substantially from previous work. In particular, the better-than-2 approximation algorithms for TAP either exploit greedy-style algorithms or are based on rounding carefully designed LPs. We instead use a reduction to the Steiner tree problem which was previously used in para

关键词： approximation algorithms connectivity augmentation Steiner tree

来源：评论

学校读者我要写书评

暂无评论

Machine Unlearning: Taxonomy, Metrics, Applications, Challenges, and Prospects

引用

IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS 2025年 PP卷 PP页

作者： Li, Na Zhou, Chunyi Gao, Yansong Chen, Hui Zhang, Zhi Kuang, Boyu Fu, Anmin Nanjing Univ Sci & Technol Sch Cyber Sci & Engn Nanjing 210094 Peoples R China Xidian Univ State Key Lab Integrated Serv Networks Xian 710071 Peoples R China Zhejiang Univ Coll Comp Sci & Technol Hangzhou 310058 Peoples R China Univ Western Australia Dept Comp Sci & Software Engn Perth WA 6009 Australia Nanjing Univ Sci & Technol Sch Comp Sci & Engn Nanjing 210094 Peoples R China

Personal digital data is a critical asset, and governments worldwide have enforced laws and regulations to protect data privacy. Data users have been endowed with the "right to be forgotten" (RTBF) of their data. In the course of machine learning (ML), the forgotten right requires a model provider to delete user data and its subsequent impact on ML models upon user requests. Machine unlearning (MU) emerges to address this, which has garnered ever-increasing attention from both industry and academia. Specifically, MU allows model providers to eliminate the influence of unlearned data without retraining the model from scratch, ensuring the model behaves as if it never encountered this data. While the area has developed rapidly, there is a lack of comprehensive surveys to capture the latest advancements. Recognizing this shortage, we conduct an extensive exploration to map the landscape of MU including the (fine-grained) taxonomy of unlearning algorithms under centralized and distributed settings, debate on approximate unlearning, verification and evaluation metrics, and challenges and solutions across various applications. We also focus on the motivations, challenges, and specific methods for deploying unlearning in large language models (LLMs), as well as the potential attacks targeting unlearning processes. The survey concludes by outlining potential directions for future research, hoping to serve as a beacon for interested scholars.

关键词： Data models Surveys Measurement Training Electronic mail Data privacy Taxonomy General Data Protection Regulation Computational modeling approximation algorithms federated learning (FL) large language model (LLM) machine learning (ML) machine unlearning (MU)

来源：评论

学校读者我要写书评

暂无评论

Stochastic approximation Beyond Gradient for Signal Processing and Machine Learning

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2023年 71卷 3117-3148页

作者： Dieuleveut, Aymeric Fort, Gersende Moulines, Eric Wai, Hoi-To Ecole Polytech CMAP UMR 7641 Palaiseau France Univ Toulouse Inst Math Toulouse CNRS UPS F-31062 Toulouse 9 France Chinese Univ Hong Kong Shatin Hong Kong Peoples R China

Stochastic approximation (SA) is a classical algorithm that has had since the early days a huge impact on signal processing, and nowadays on machine learning, due to the necessity to deal with a large amount of data observed with uncertainties. An exemplar special case of SA pertains to the popular stochastic (sub)gradient algorithm which is the working horse behind many important applications. A lesser-known fact is that the SA scheme also extends to non-stochastic-gradient algorithms such as compressed stochastic gradient, stochastic expectation-maximization, and a number of reinforcement learning algorithms. The aim of this article is to overview and introduce the non-stochastic-gradient perspectives of SA to the signal processing and machine learning audiences through presenting a design guideline of SA algorithms backed by theories. Our central theme is to propose a general framework that unifies existing theories of SA, including its non-asymptotic and asymptotic convergence results, and demonstrate their applications on popular non-stochastic-gradient algorithms. We build our analysis framework based on classes of Lyapunov functions that satisfy a variety of mild conditions. We draw connections between non-stochastic-gradient algorithms and scenarios when the Lyapunov function is smooth, convex, or strongly convex. Using the said framework, we illustrate the convergence properties of the non-stochastic-gradient algorithms using concrete examples. Extensions to the emerging variance reduction techniques for improved sample complexity will also be discussed.

关键词： Signal processing algorithms Convergence Machine learning algorithms approximation algorithms Random variables Lyapunov methods Monte Carlo methods Stochastic approximation convergence analysis compressed stochastic gradient expectation maximization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：