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

Stability-based Generalization Bounds for Variational Inference

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Wei, Yadi Khardon, Roni Department of Computer Science Indiana University Bloomington United States

Variational inference (VI) is widely used for approximate inference in Bayesian machine learning. In addition to this practical success, generalization bounds for variational inference and related algorithms have been developed, mostly through the connection to PAC-Bayes analysis. A second line of work has provided algorithm-specific generalization bounds through stability arguments or using mutual information bounds, and has shown that the bounds are tight in practice, but unfortunately these bounds do not directly apply to approximate Bayesian algorithms. This paper fills this gap by developing algorithm-specific stability based generalization bounds for a class of approximate Bayesian algorithms that includes VI, specifically when using stochastic gradient descent to optimize their objective. As in the non-Bayesian case, the generalization error is bounded by by expected parameter differences on a perturbed dataset. The new approach complements PAC-Bayes analysis and can provide tighter bounds in some cases. An experimental illustration shows that the new approach yields non-vacuous bounds on modern neural network architectures and datasets and that it can shed light on performance differences between variant approximate Bayesian algorithms. Copyright © 2025, The Authors. All rights reserved.

关键词： approximation algorithms

Machine Learning algorithms Based on Variations of the Least Squares Method for Power Amplifier Distortion Compensation

学校读者我要写书评

暂无评论

Machine Learning Algorithms Based on Variations of the Least...

Systems of Signals Generating and Processing in the Field of on Board Communications

作者： Igor V. Komarov Svetlana F. Gorgadze Moscow Technical University of Communications and Informatics Moscow Russia

ISBN: (数字)9798331532635

ISBN: (纸本)9798331532642

Variants of indirect learning based on the Least Squares Method (LSM) and the Recursive Least Squares Method (RLSM) are considered for digital predistortion of nonlinear distortions in complex composite signals with high peak-toaverage power ratios in power amplifiers. The advantage of the recursive algorithm is identified, providing approximately 9 dB lower levels of spurious out-of-band emissions for the amplified complex signal compared to the simple least squares algorithm. It is shown that for the polynomial model of the power amplifier used in the study, the recursive algorithm requires approximately 700 times more elementary mathematical operations to achieve the most efficient compensation of signal nonlinearities than the least squares algorithm.

关键词： Machine learning algorithms Nonlinear distortion Computer architecture approximation algorithms Predistortion Polynomials Mathematical models Hardware Least mean squares methods Convergence

Meta-Heuristic Approaches to Parallel Processing in Signal Representation and Real-Time Analysis

学校读者我要写书评

暂无评论

Meta-Heuristic Approaches to Parallel Processing in Signal R...

Automation and Computation (AUTOCOM), International Conference on

作者： Harisha Naik N T Sudhanshu Dev Aniket Shivam Neelesh Singh Shreenidhi H S Awakash Mishra Department of Computer Applications (DCA) Presidency College Bengaluru India Centre of Research Impact and Outcome Chitkara University Rajpura Punjab India Department of Computer Science and Engineering Siksha ‘O’ Anusandhan (Deemed to be University) Bhubaneswar Odisha India Chitkara Centre for Research and Development Chitkara University Baddi Himachal Pradesh India School of Engineering and Technology Computer Science and Engineering JAIN (Deemed to be University) Bangalore Karnataka Maharishi School of Engineering & Technology Maharishi University of Information Technology Uttar Pradesh India

ISBN: (数字)9798331542375

ISBN: (纸本)9798331542382

Meta-heuristic techniques have been popular in solving highly complex optimization problems. Parallel processing is very important in signal representation and real-time analysis, as it helps lower the time required for the data process so that algorithms can perform faster. The biggest challenge with the traditional parallel processing techniques is load balancing and higher communication overhead, which may need to scale up to a larger extent. Meta-heuristic techniques reduce the complexity of problems that are NP-complete or NP-hard by providing satisfactory solutions and approximate answers to difficult ones. This has helped in parallel processing for signal representation and real-time analysis. Parallel processing has also been useful in using meta-heuristic algorithms like genetic algorithms, ant colony optimization, and particle swarm optimization. Meta-heuristic algorithms produce flexible, adaptive mechanisms for solving complex problems.

关键词： Heuristic algorithms Metaheuristics Signal processing algorithms Parallel processing Signal processing approximation algorithms Load management Real-time systems Signal representation Particle swarm optimization

All-Subsets Important Separators with Applications to Sample Sets, Balanced Separators and Vertex Sparsifiers in Directed Graphs

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Anand, Aditya Lee, Euiwoong Li, Jason Saranurak, Thatchaphol University of Michigan Ann Arbor United States Carnegie Mellon University United States University of Michigan United States

Given a directed graph $G$ with $n$ vertices and $m$ edges, a parameter $k$ and two disjoint subsets $S,T \subseteq V(G)$, we show that the number of all-subsets important separators, which is the number of $A$-$B$ important vertex separators of size at most $k$ over all $A \subseteq S$ and $B \subseteq T$, is at most $\beta(|S|, |T|, k) = 4^k {|S| \choose \leq k} {|T| \choose \leq 2k}$, where ${x \choose \leq c} = \sum_{i = 1}^c {x \choose i}$, and that they can be enumerated in time $O(\beta(|S|,|T|,k)k^2(m+n))$. This is a generalization of the folklore result stating that the number of $A$-$B$ important separators for two fixed sets $A$ and $B$ is at most $4^k$ (first implicitly shown by Chen, Liu and Lu Algorithmica '09). From this result, we obtain the following applications: We give a construction for detection sets and sample sets in directed graphs, generalizing the results of Kleinberg (Internet Mathematics' 03) and Feige and Mahdian (STOC' 06) to directed graphs. Via our new sample sets, we give the first FPT algorithm for finding balanced separators in directed graphs parameterized by $k$, the size of the separator. Our algorithm runs in time $2^{O(k)} (m + n)$. We also give a $O({\sqrt{\log k}})$ approximation algorithm for the same problem. Finally, we present new results on vertex sparsifiers for preserving small cuts. Copyright © 2025, The Authors. All rights reserved.

关键词： approximation algorithms

Variational Quantum Circuits for Molecular Classification Using Graph Neural Network

学校读者我要写书评

暂无评论

Variational Quantum Circuits for Molecular Classification Us...

Quantum Communications, Networking, and Computing (QCNC), International Conference on

作者： Don Roosan Md Rahatul Ashakin Rubayat Khan Hasiba Mashed Khan Tiffany Khou Maria-Isabel Carnasciali Mohammad Rifat Haider School of Engineering and Computational Sciences Merrimack College USA Tekurai LLC San Antonio USA University of Nebraska Medical Center Omaha USA College of Pharmacy Western University of Health Sciences Pomona USA College of Public Health University of Georgia Athens USA

ISBN: (数字)9798331531591

ISBN: (纸本)9798331531607

The study explores the integration of quantum-enhanced feature mapping and optimization within Graph Neural Networks (GNNs) for molecular classification tasks. Utilizing IBM's Qiskit platform, we implement Variational Quantum Circuits (VQCs) to transform classical molecular features into quantum states, capturing complex correlations through quantum entanglement. Additionally, the Quantum Approximate Optimization Algorithm (QAOA) is employed for hyperparameter tuning to enhance model convergence and performance. Comparative analyses against traditional machine learning models demonstrate the superiority of the quantum-enhanced GNN, highlighting the potential of quantum computing in advancing molecular property prediction.

关键词： Quantum entanglement Computational modeling Transforms Quantum state approximation algorithms Graph neural networks Integrated circuit modeling Quantum circuit Optimization Tuning

OneBatchPAM: A Fast and Frugal K-Medoids Algorithm 39

学校读者我要写书评

暂无评论

OneBatchPAM: A Fast and Frugal K-Medoids Algorithm

39th Annual AAAI Conference on Artificial Intelligence, AAAI 2025

作者： de Mathelin, Antoine Cecchi, Nicolas Enrique Deheeger, François Mougeot, Mathilde Vayatis, Nicolas Centre Borelli Université Paris-Saclay CNRS ENS Paris-Saclay France Michelin France

ISBN: (纸本)157735897X

This paper proposes a novel k-medoids approximation algorithm to handle large-scale datasets with reasonable computational time and memory complexity. We develop a local-search algorithm that iteratively improves the medoid selection based on the estimation of the k-medoids objective. A single batch of size m n provides the estimation, which reduces the required memory size and the number of pairwise dissimilarities computations to O(mn), instead of O(n2) compared to most k-medoids baselines. We obtain theoretical results highlighting that a batch of size m = O(log(n)) is sufficient to guarantee, with strong probability, the same performance as the original local-search algorithm. Multiple experiments conducted on real datasets of various sizes and dimensions show that our algorithm provides similar performances as state-of-the-art methods such as FasterPAM and BanditPAM++ with a drastically reduced running time. Copyright © 2025, Association for the Advancement of Artificial Intelligence (***). All rights reserved.

关键词： approximation algorithms

A New DAPO Algorithm for Stock Trading

学校读者我要写书评

暂无评论

A New DAPO Algorithm for Stock Trading

Intelligent Data and Security (IDS), IEEE International Conference on

作者： Ruijian Zha Bojun Liu Department of Computer Science Columbia University New York NY USA

ISBN: (数字)9798331596613

ISBN: (纸本)9798331596620

Recent advances in reinforcement learning, like Dynamic sAmpling Policy Optimization (DAPO) algorithm, have demonstrated strong performance when combined with Large Language Models (LLMs). Motivated by this, we investigate whether similar benefits can be achieved in financial trading. We develop a novel trading agent that integrates an improved Group Relative Policy Optimization (GRPO) algorithm, enhanced with insights from DAPO, and incorporates LLM-based signals of risk and sentiment from financial news. We evaluate our method on the NASDAQ-100 index using the FNSPID dataset. Our improved DAPO algorithm achieves a cumulative return of 230.49% and an Information Ratio of 0.37, outperforming the CPPO-DeepSeek baseline. Additionally, our approach reduces training time from approximately 8 hours to 2.5 hours over 100 epochs, while significantly decreasing RAM usage. Our approach addresses limitations of existing RL-LLM frameworks, offering a scalable solution for building financial trading agents. Code is available at: https://***/Ruijian-Zha/FinRL-DAPO-SR/

关键词： Training Sentiment analysis Heuristic algorithms Large language models Random access memory Reinforcement learning approximation algorithms Security Risk management Optimization

Static to Dynamic Correlation Clustering

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Cao, Nairen Cohen-Addad, Vincent Lee, Euiwoong Li, Shi Lolck, David Rasmussen Newman, Alantha Thorup, Mikkel Vogl, Lukas Yan, Shuyi Zhang, Hanwen New York University United States Google Research United States University of Michigan United States Nanjing University China School of Computer Science Nanjing University China University of Copenhagen Denmark Université Grenoble Alpes France EPFL Switzerland

Correlation clustering is a well-studied problem, first proposed by Bansal, Blum, and Chawla [BBC04]. The input is an unweighted, undirected graph. The problem is to cluster the vertices so as to minimizing the number of edges between vertices in different clusters and missing edges between vertices inside the same cluster. This problem has a wide application in data mining and machine learning. We introduce a general framework that transforms existing static correlation clustering algorithms into fully-dynamic ones that work against an adaptive adversary. We show how to apply our framework to known efficient correlation clustering algorithms, starting from the classic 3-approximate Pivot algorithm from [ACN08]. Applied to the most recent near-linear 1.437-approximation algorithm from [CCL+25], we get a 1.437-approximation fully-dynamic algorithm that works with worst-case constant update time. The original static algorithm gets its approximation factor with constant probability, and we get the same against an adaptive adversary in the sense that for any given update step not known to our algorithm, our solution is a 1.437-approximation with constant probability when we reach this update. Previous dynamic algorithms had approximation factors around 3 in expectation, and they could only handle an oblivious adversary. © 2025, CC BY.

关键词： approximation algorithms

Approximately EFX and PO Allocations for Bivalued Chores

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Lin, Zehan Wu, Xiaowei Zhou, Shengwei IOTSC University of Macau China

We consider the computation for allocations of indivisible chores that are approximately EFX and Pareto optimal (PO). Recently, Garg et al. (2024) show the existence of 3-EFX and PO allocations for bi-valued instances, where the cost of an item to an agent is either 1 or k (where k > 1) by rounding the (fractional) earning restricted equilibrium. In this work, we improve the approximation ratio to (2 − 1/k), while preserving the Pareto optimality. Instead of rounding fractional equilibrium, our algorithm starts with the integral EF1 equilibrium for bi-valued chores, introduced by Garg et al. (AAAI 2022) and Wu et al. (EC 2023), and reallocates items until approximate EFX is achieved. We further improve our result for the case when k = 2 and devise an algorithm that computes EFX and PO allocations. Copyright © 2025, The Authors. All rights reserved.

关键词： approximation algorithms