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

Connectivity-aware Synthesis of Quantum algorithms

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Dreier, Florian Fleckenstein, Christoph Aigner, Gregor Fellner, Michael Stahn, Reinhard Lanthaler, Martin Lechner, Wolfgang Institute for Theoretical Physics University of Innsbruck InnsbruckA-6020 Austria Parity Quantum Computing GmbH InnsbruckA-6020 Austria Parity Quantum Computing Germany GmbH Hamburg20095 Germany

We present a general method for the implementation of quantum algorithms that optimizes both gate count and circuit depth. Our approach introduces connectivity-adapted CNOT-based building blocks called Parity Twine chains. It outperforms all known state-of-the art methods for implementing prominent quantum algorithms such as the quantum Fourier transform or the Quantum Approximate optimization Algorithm across a wide range of quantum hardware, including linear, square-grid, hexagonal, ladder and all-to-all connected devices. For specific cases, we rigorously prove the optimality of our approach. Copyright © 2025, The Authors. All rights reserved.

关键词： optimization algorithms

Online Allocation with Multi-Class Arrivals: Group Fairness vs Individual Welfare

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Zargari, Faraz Jazi, Hossein Nekouyan Sun, Bo Tan, Xiaoqi University of Alberta Canada University of Waterloo Canada

We introduce and study a multi-class online resource allocation problem with group fairness guarantees. The problem involves allocating a fixed amount of resources to a sequence of agents, each belonging to a specific group. The primary objective is to ensure fairness across different groups in an online setting. We focus on three fairness notions: one based on quantity and two based on utility. To achieve fair allocations, we develop two threshold-based online algorithms, proving their optimality under two fairness notions and near-optimality for the more challenging one. Additionally, we demonstrate a fundamental trade-off between group fairness and individual welfare using a novel representative function-based approach. To address this trade-off, we propose a set-aside multi-threshold algorithm that reserves a portion of the resource to ensure fairness across groups while utilizing the remaining resource to optimize efficiency under utility-based fairness notions. This algorithm is proven to achieve the Pareto-optimal trade-off. We also demonstrate that our problem can model a wide range of real-world applications, including network caching and cloud computing, and empirically evaluate our proposed algorithms in the network caching problem using real datasets. Copyright © 2025, The Authors. All rights reserved.

关键词： optimization algorithms

A Descent-based method on the Duality Gap for solving zero-sum games

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Fasoulakis, Michail Markakis, Evangelos Roussakis, Giorgos Santorinaios, Christodoulos Royal Holloway University of London United Kingdom Archimedes RC Athens Greece Athens University of Economics and Business Greece Foundation for Research and Technology–Hellas Greece

We focus on the design of algorithms for finding equilibria in 2-player zero-sum games. Although it is well known that such problems can be solved by a single linear program, there has been a surge of interest in recent years for simpler algorithms, motivated in part by applications in machine learning. Our work proposes such a method, inspired by the observation that the duality gap (a standard metric for evaluating convergence in min-max optimization problems) is a convex function for bilinear zero-sum games. To this end, we analyze a descent-based approach, variants of which have also been used as a subroutine in a series of algorithms for approximating Nash equilibria in general non-zero-sum games. In particular, we study a steepest descent approach, by finding the direction that minimises the directional derivative of the duality gap function. Our main theoretical result is that the derived algorithms achieve a geometric decrease in the duality gap and improved complexity bounds until we reach an approximate equilibrium. Finally, we complement this with an experimental evaluation, which provides promising findings. Our algorithm is comparable with (and in some cases outperforms) some of the standard approaches for solving 0-sum games, such as OGDA (Optimistic Gradient Descent/Ascent), even with thousands of available strategies per player. © 2025, CC BY.

关键词： optimization algorithms

A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noise

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Diakonikolas, Ilias Zarifis, Nikos UW-Madison United States

We study the problem of PAC learning γ-margin halfspaces in the presence of Massart noise. Without computational considerations, the sample complexity of this learning problem is known to be Θ(1 e /(γ2ǫ)). Prior computationally efficient algorithms for the problem incur sample complexity Õ(1/(γ4ǫ3)) and achieve 0-1 error of η + ǫ, where η e /(γ2ǫ2)), nearly matching this lower bound. In addition, our algorithm is simple and practical, relying on online SGD on a carefully selected sequence of convex losses. Copyright © 2025, The Authors. All rights reserved.

关键词： optimization algorithms

Robust Information Selection for Hypothesis Testing with Misclassification Penalties

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Bhargav, Jayanth Sundaram, Shreyas Ghasemi, Mahsa Elmore Family School of Electrical and Computer Engineering Purdue University West LafayetteIN47907 United States

We study the problem of robust information selection for a Bayesian hypothesis testing / classification task, where the goal is to identify the true state of the world from a finite set of hypotheses based on observations from the selected information sources. We introduce a novel misclassification penalty framework, which enables non-uniform treatment of different misclassification events. Extending the classical subset selection framework, we study the problem of selecting a subset of sources that minimize the maximum penalty of misclassification under a limited budget, despite deletions or failures of a subset of the selected sources. We characterize the curvature properties of the objective function and propose an efficient greedy algorithm with performance guarantees. Next, we highlight certain limitations of optimizing for the maximum penalty metric and propose a submodular surrogate metric to guide the selection of the information set. We propose a greedy algorithm with near-optimality guarantees for optimizing the surrogate metric. Finally, we empirically demonstrate the performance of our proposed algorithms in several instances of the information set selection problem. © 2025, CC BY.

关键词： optimization algorithms

A double-layer placement algorithm for integrated circuit-based modules on printed circuit board

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Li, Hangyuan Yang, Zhaoyang Pang, Haotian Xu, Ning Chen, Yu School of Computer Science and Artificial Intelligence Wuhan University of Technology Wuhan430070 China School of Information Engineering Wuhan University of Technology Wuhan430070 China School of Mathematics and Statistics Wuhan University of Technology Wuhan430070 China

Considering that the physical design of printed circuit board (PCB) follows the principle of modularized design, this paper proposes an automatic placement algorithm for functional modules. We first model the placement problem as a mixed-variable optimization problem, and then, developed tailored algorithms of global placement and legalization for the top-layer centralized placement subproblem and the bottom-layer pin-oriented placement subproblem. Numerical comparison demonstrates that the proposed mixed-variable optimization scheme can get optimized total wirelength of placement. Meanwhile, experimental results on several industrial PCB cases show that the developed centralized strategies can well accommodate the requirement of top-layer placement, and the pin-oriented global placement based on bin clustering contributes to optimized placement results meeting the requirement of pin-oriented design. © 2025, CC BY.

关键词： optimization algorithms

Parallel multi-objective metaheuristics for smart communications in vehicular networks

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Toutouh, Jamal Alba, Enrique University of Málaga Málaga Spain

This article analyzes the use of two parallel multi-objective soft computing algorithms to automatically search for high-quality settings of the Ad hoc On Demand Vector routing protocol for vehicular networks. These methods are based on an evolutionary algorithm and on a swarm intelligence approach. The experimental analysis demonstrates that the configurations computed by our optimization algorithms outperform other state-of-the-art optimized ones. In turn, the computational efficiency achieved by all the parallel versions is greater than 87 %. Therefore, the line of work presented in this article represents an efficient framework to improve vehicular communications. Copyright © 2025, The Authors. All rights reserved.

关键词： optimization algorithms

Implicit bias of Normalized Steepest Descent in Multiclass Classification: Sign Descent, Spectral Descent, and Adam

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Fan, Chen Schmidt, Mark Thrampoulidis, Christos University of British Columbia Canada Canada

In the optimization of overparameterized models, different gradient-based methods can achieve zero training error yet converge to distinctly different solutions inducing different generalization properties. Despite a decade of research on implicit optimization bias, important questions remain open even in the foundational case of linear classification with separable data. We address this gap by characterizing the implicit bias of both Adam and Sign gradient descent (SignGD) in multi-class cross-entropy minimization: we prove that their iterates converge to solutions maximizing the margin with respect to the classifier matrix’s max-norm, and we establish the corresponding convergence rates. We then generalize our analysis to p-norm normalized steepest descent (NSD) algorithms. This includes Spectral Descent, which we show converges to the max-margin solution with respect to the spectral norm. A key insight is that the analysis of general entrywise and Schatten p-norms can be reduced to the analysis of NSD with max-norm (i.e., SignGD) by exploiting a natural ordering property between all p-norms relative to the max-norm and its dual sum-norm. Our results demonstrate that the multiclass linear setting, which is inherently richer than the binary counterpart, provides the most transparent playground for studying implicit biases of matrix-parameter optimization algorithms. © 2025, CC BY.

关键词： optimization algorithms

Selective Use of Yannakakis’ Algorithm to Improve Query Performance: Machine Learning to the Rescue

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Böhm, Daniela Gottlob, Georg Lanzinger, Matthias Longo, Davide Mario Okulmus, Cem Pichler, Reinhard Selzer, Alexander TU Wien Vienna Austria University of Calabria Rende Italy University Paderborn Paderborn Germany

Query optimization has played a central role in database research for decades. However, more often than not, the proposed optimization techniques lead to a performance improvement in some, but not in all, situations. Therefore, we urgently need a methodology for designing a decision procedure that decides for a given query whether the optimization technique should be applied or not. In this work, we propose such a methodology with a focus on Yannakakis-style query evaluation as our optimization technique of interest. More specifically, we formulate this decision problem as an algorithm selection problem and we present a Machine Learning based approach for its solution. Empirical results with several benchmarks on a variety of database systems show that our approach indeed leads to a statistically significant performance improvement. © 2025, CC BY-NC-ND.

关键词： optimization algorithms