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

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 Bias-Correction Decentralized Stochastic Gradient Algorithm with Momentum Acceleration

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Hu, Yuchen Chen, Xi Liu, Weidong Mao, Xiaojun School of Mathematical Sciences Shanghai Jiao Tong University Shanghai200240 China New York University New YorkNY10012 United States

Distributed stochastic optimization algorithms can handle large-scale data simultaneously and accelerate model training. However, the sparsity of distributed networks and the heterogeneity of data limit these advantages. This paper proposes a momentum-accelerated distributed stochastic gradient algorithm, referred to as Exact-Diffusion with Momentum (EDM), which can correct the bias caused by data heterogeneity and introduces the momentum method commonly used in deep learning to accelerate the convergence of the algorithm. We theoretically demonstrate that this algorithm converges to the neighborhood of the optimum sub-linearly irrelevant to data heterogeneity when applied to non-convex objective functions and linearly under the Polyak-Lojasiewicz condition (a weaker assumption than µ-strongly convexity). Finally, we evaluate the performance of the proposed algorithm by simulation, comparing it with a range of existing decentralized optimization algorithms to demonstrate its effectiveness in addressing data heterogeneity and network sparsity. Copyright © 2025, The Authors. All rights reserved.

关键词： optimization algorithms

Near-Optimal Decision Trees in a SPLIT Second

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Babbar, Varun McTavish, Hayden Rudin, Cynthia Seltzer, Margo Department of Computer Science Duke University Durham United States Department of Computer Science University of British Columbia Vancouver Canada

Decision tree optimization is fundamental to interpretable machine learning. The most popular approach is to greedily search for the best feature at every decision point, which is fast but provably suboptimal. Recent approaches find the global optimum using branch and bound with dynamic programming, showing substantial improvements in accuracy and sparsity at great cost to scalability. An ideal solution would have the accuracy of an optimal method and the scalability of a greedy method. We introduce a family of algorithms called SPLIT (SParse Lookahead for Interpretable Trees) that moves us significantly forward in achieving this ideal balance. We demonstrate that not all sub-problems need to be solved to optimality to find high quality trees;greediness suffices near the leaves. Since each depth adds an exponential number of possible trees, this change makes our algorithms orders of magnitude faster than existing optimal methods, with negligible loss in performance. We extend this algorithm to allow scalable computation of sets of near-optimal trees (i.e., the Rashomon set). © 2025, CC BY.

关键词： optimization algorithms

Mechanical Properties Estimation Of Ultra Great Workability Concrete By Developing Hybrid algorithms

学校读者我要写书评

暂无评论

淡江理工学刊 2023年第9期26卷 1303-1318页

作者： Lijun Wang Pengcheng Yang

The compressive strength of ultra great workability concrete (UGWC) is a function of the kind, characteristics and quantities of its material components. Empirically gaining this relation sometimes needs the usage of intelligent algorithms to receive a simulative model that fits into experimental data records. In this study, the usefulness of developing hybridized regression analysis on UGWC was analyzed with the aim of reducing the consumed time and experimental efforts. To this aim, a dataset including 170 samples collected from published papers different hybridized support vector regression (SVR) analyses were produced, where the optimal values of determinant attributes of SVR were explored by metaheuristic optimization algorithms named particle swarm optimization (PSO), Cuckoo optimization algorithm (COA), and Bat algorithm (BAT). The performance evaluators demonstrate that all three hybridized SVR models have remarkable potential in compressive strength estimation of UGWC. The first rank belonged to the SVR-COA model, where it could gain the highest value of R^2 and variance account factor (VAF) in both training (R^2=0.9056 and VAF=90.17%) and validating section (R^2=0.9208 and VAF=91.81%), and the lowest value of root mean square error, and mean absolute error in both training and validating sections. Therefore, the hybridized SVR-COA model could receive the proper accuracy in comparison with other models as well as literature.

关键词： Ultra great workability concrete Compressive strength Prediction SVR analysis optimization algorithms

The Performance Of The Unadjusted Langevin Algorithm Without Smoothness Assumptions

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Johnston, Tim Lytras, Iosif Makras, Nikolaos Sabanis, Sotirios School of Mathematics University of Edinburgh United Kingdom National Technical University of Athens Greece Université Paris Dauphine-PSL Ceremade France Archimedes/Athena Research Centre Greece

In this article, we study the problem of sampling from distributions whose densities are not necessarily smooth nor logconcave. We propose a simple Langevin-based algorithm that does not rely on popular but computationally challenging techniques, such as the Moreau-Yosida envelope or Gaussian smoothing. We derive non-asymptotic guarantees for the convergence of the algorithm to the target distribution in Wasserstein distances. Non-asymptotic bounds are also provided for the performance of the algorithm as an optimizer, specifically for the solution of associated excess risk optimization problems. © 2025, CC BY.

关键词： optimization algorithms

Algorithmic approaches to avoiding bad local minima in nonconvex inconsistent feasibility

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Dinh, Thi Lan Bennecke, Wiebke Jansen, G.S. Matthijs Luke, D. Russell Mathias, Stefan Institut für Numerische und Angewandte Mathematik Georg-August-Universität Göttingen Göttingen Germany I. Physikalisches Institut Georg-August-Universität Göttingen Göttingen Germany

The main challenge of nonconvex optimization is to find a global optimum, or at least to avoid "bad" local minima and meaningless stationary points. We study here the extent to which algorithms, as opposed to optimization models and regularization, can be tuned to accomplish this goal. The model we consider is a nonconvex, inconsistent feasibility problem with many local minima, where these are points at which the gaps between the sets are smallest on neighborhoods of these points. The algorithms that we compare are all projection-based algorithms, specifically cyclic projections, the cyclic relaxed Douglas-Rachford algorithm, and relaxed Douglas-Rachford splitting on the product space. The local convergence and fixed points of these algorithms have already been characterized in pervious theoretical studies. We demonstrate the theory for these algorithms in the context of orbital tomographic imaging from angle-resolved photon emission spectroscopy (ARPES) measurements, both synthetically generated and experimental. Our results show that, while the cyclic projections and cyclic relaxed Douglas-Rachford algorithms generally converge the fastest, the method of relaxed Douglas-Rachford splitting on the product space does move away from bad local minima of the other two algorithms, settling eventually on clusters of local minima corresponding to globally optimal critical *** Codes 65K10, 65K05, 90C26, 49M27, 49J53, 49K40, 49M05 © 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

GRADIENT SAMPLING ALGORITHM FOR SUBSMOOTH FUNCTIONS

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Boskos, Dimitris Cortés, Jorge Martínez, Sonia Delft Center for Systems and Control TU Delft Netherlands Department of Mechanical and Aerospace Engineering UC San Diego United States

This paper considers non-smooth optimization problems where we seek to minimize the pointwise maximum of a continuously parameterized family of functions. Since the objective function is given as the solution to a maximization problem, neither its values nor its gradients are available in closed form, which calls for approximation. Our approach hinges upon extending the so-called gradient sampling algorithm, which approximates the Clarke generalized gradient of the objective function at a point by sampling its derivative at nearby locations. This allows us to select descent directions around points where the function may fail to be differentiable and establish algorithm convergence to a stationary point from any initial condition. Our key contribution is to prove this convergence by alleviating the requirement on continuous differentiability of the objective function on an open set of full measure. We further provide assumptions under which a desired convex subset of the decision space is rendered attractive for the iterates of the algorithm. Copyright © 2025, The Authors. All rights reserved.

关键词： optimization algorithms