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

An angle rounding parameter initialization technique for ma-QAOA

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Wilkie, Anthony Ostrowski, James Herrman, Rebekah Industrial and Systems Engineering University of Tennessee at Knoxville KnoxvilleTN United States

The multi-angle quantum approximate optimization algorithm (ma-QAOA) is a recently introduced algorithm that gives at least the same approximation ratio as the quantum approximate optimization algorithm (QAOA) and, in most cases, gives a significantly higher approximation ratio than QAOA. One drawback to ma-QAOA is that it uses significantly more classical parameters than QAOA, so the classical optimization component more complex. In this paper, we motivate a new parameter initialization strategy in which angles are initially randomly set to multiples of π/8 between -π and π and this vector is used to seed one round of BFGS. We find that this parameter initialization strategy gives average approximation ratios of 0.900, 0.982, and 0.997 for p = 1, 2, 3 layers of ma-QAOA. This is comparable to the average approximation ratios of ma-QAOA where the optimal parameters are found using BFGS with 1 random starting seed, which are 0.900, 0.982, and 0.996. We also test another parameter initialization strategy in which angles corresponding to maximal degree vertices in the graph are set to 0 while all other are randomly initialized to random multiples of π/8. Using this strategy, the average approximation ratios are 0.897, 0.984, and 0.997. © 2024, CC BY.

关键词： optimization algorithms

Computing Optima in Standard Quadratic Functions in Zero-Error Probabilistic Polynomial Time

学校读者我要写书评

暂无评论

SSRN

SSRN 2024年

作者： Gao, Lunshan Physics and Computer Science Wilfrid Laurier University 75 University Ave. W. WaterlooONN2L3C5 Canada

Fuzzy numbers are used to represent uncertainties arising from imprecision and vagueness. In this paper, we propose a novel randomized algorithm for computing local optima in standard quadratic optimization problems by using fuzzification, random number generators, and the first and second order conditions. This paper proves that: (1) the computational complexity of the new algorithm is in zero-error probabilistic polynomial time;(2) the transformation used in the new algorithm is polynomial time reduction. Examplesand numerical experiments show that the new algorithm outperforms both Gurobi optimizer and IBM CPLEX solvers and the new algorithm is faster than both Gurobi optimizer and IBM CPLEX solvers. © 2024, The Authors. All rights reserved.

关键词： optimization algorithms

Centralized Selection with Preferences in the Presence of Biases

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Celis, L. Elisa Kumar, Amit Vishnoi, Nisheeth K. Xu, Andrew Yale University United States IIT Delhi India

This paper considers the scenario in which there are multiple institutions, each with a limited capacity for candidates, and candidates, each with preferences over the institutions. A central entity evaluates the utility of each candidate to the institutions, and the goal is to select candidates for each institution in a way that maximizes utility while also considering the candidates’ preferences. The paper focuses on the setting in which candidates are divided into multiple groups and the observed utilities of candidates in some groups are biased–systematically lower than their true utilities. The first result is that, in these biased settings, prior algorithms can lead to selections with sub-optimal true utility and significant discrepancies in the fraction of candidates from each group that get their preferred choices. Subsequently, an algorithm is presented along with proof that it produces selections that achieve near-optimal group fairness with respect to preferences while also nearly maximizing the true utility under distributional assumptions. Further, extensive empirical validation of these results in real-world and synthetic settings, in which the distributional assumptions may not hold, are presented. © 2024, CC BY.

关键词： optimization algorithms

Parallelization of Gillespie algorithm based on binary words

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Lacoste, David Castellana, Michele Institut Curie PSL Research University CNRS UMR168 11 rue Pierre et Marie Curie Paris 75005 France Gulliver Laboratory UMR CNRS 7083 PSL Research University ESPCI 10 Rue Vauquelin Paris F-75231 France

We present an improvement of the Gillespie Exact Stochastic Simulation Algorithm, which leverages a bitwise representation of variables to perform independent simulations in parallel. We show that the subsequent gain in computational yield is significant, and it may allow to perform simulations of non-well mixed chemical systems. We illustrate this idea with simulations of Frank model, originally introduced to explain the emergence of homochirality in prebiotic systems. © 2024, CC BY.

关键词： optimization algorithms

Extended convexity and smoothness and their applications in deep learning

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Qi, Binchuan Gong, Wei Li, Li College of Electronics and Information Engineering Tongji University Shanghai201804 China National Key Laboratory of Autonomous Intelligent Unmanned Systems Tongji University Shanghai201210 China Shanghai Research Institute for Intelligent Autonomous Systems Tongji University Shanghai201210 China

This paper introduces an optimization framework aimed at providing a theoretical foundation for a class of composite optimization problems, particularly those encountered in deep learning. In this framework, we introduce H()-convexity and H(Φ)-smoothness to generalize the existing concepts of Lipschitz smoothness and strong convexity. Furthermore, we analyze and establish the convergence of both gradient descent and stochastic gradient descent methods for objective functions that are H(Φ)-smooth. We prove that the optimal convergence rates of these methods depend solely on the homogeneous degree of Φ. Based on these findings, we construct two types of non-convex and non-smooth optimization problems: deterministic composite and stochastic composite optimization problems, which encompass the majority of optimization problems in deep learning. To address these problems, we develop the gradient structure control algorithm and prove that it can locate approximate global optima. This marks a significant departure from traditional non-convex analysis framework, which typically settle for stationary points. Therefore, with the introduction of H()-convexity and H(Φ)-smoothness, along with the GSC algorithm, the non-convex optimization mechanisms in deep learning can be theoretically explained and supported. Finally, the effectiveness of the proposed framework is substantiated through empirical experimentation. Copyright © 2024, The Authors. All rights reserved.

关键词： optimization algorithms

GenJoin: Conditional Generative Plan-to-Plan Query Optimizer that Learns from Subplan Hints

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Sulimov, Pavel Lehmann, Claude Stockinger, Kurt Zurich University of Applied Sciences Switzerland

Query optimization has become a research area where classical algorithms are being challenged by machine learning algorithms. At the same time, recent trends in learned query optimizers have shown that it is prudent to take advantage of decades of database research and augment classical query optimizers by shrinking the plan search space through different types of hints (e.g. by specifying the join type, scan type or the order of joins) rather than completely replacing the classical query optimizer with machine learning models. It is especially relevant for cases when classical optimizers cannot fully enumerate all logical and physical plans and, as an alternative, need to rely on less robust approaches like genetic algorithms. However, even symbiotically learned query optimizers are hampered by the need for vast amounts of training data, slow plan generation during inference and unstable results across various workload conditions. In this paper, we present GenJoin - a novel learned query optimizer that considers the query optimization problem as a generative task and is capable of learning from a random set of subplan hints to produce query plans that outperform the classical optimizer. GenJoin is the first learned query optimizer that significantly and consistently outperforms PostgreSQL as well as state-of-the-art methods on two well-known real-world benchmarks across a variety of workloads using rigorous machine learning evaluations. © 2024, CC BY.

关键词： optimization algorithms

GD doesn’t make the cut: Three ways that non-differentiability affects neural network training

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Kumar, Siddharth Krishna Upwork inc. San Francisco United States

This paper critically examines the fundamental distinctions between gradient methods applied to non-differentiable functions (NGDMs) and classical gradient descents (GDs) for differentiable functions, revealing significant gaps in current deep learning optimization theory. We demonstrate that NGDMs exhibit markedly different convergence properties compared to GDs, strongly challenging the applicability of extensive neural network convergence literature based on L − smoothness to non-smooth neural networks. Our analysis reveals paradoxical behavior of NDGM solutions for L1-regularized problems, where increasing regularization counterintuitively leads to larger L1 norms of optimal solutions. This finding calls into question widely adopted L1 penalization techniques for network pruning. We further challenge the common assumption that optimization algorithms like RMSProp behave similarly in differentiable and non-differentiable contexts. Expanding on the Edge of Stability phenomenon, we demonstrate its occurrence in a broader class of functions, including Lipschitz continuous convex differentiable functions. This finding raises important questions about its relevance and interpretation in non-convex, nondifferentiable neural networks, particularly those using ReLU activations. Our work identifies critical misunderstandings of NDGMs in influential literature, stemming from an overreliance on strong smoothness assumptions. These findings necessitate a reevaluation of optimization dynamics in deep learning, emphasizing the crucial need for more nuanced theoretical foundations in analyzing these complex systems. © 2024, CC BY.

关键词： optimization algorithms

Learning-to-Optimize with PAC-Bayesian Guarantees: Theoretical Considerations and Practical Implementation

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Sucker, Michael Fadili, Jalal Ochs, Peter Department of Mathematics University of Tübingen Tübingen Germany ENSICAEN Normandie Université CNRS GREYC France Department of Mathematics and Computer Science Saarland University Saarbrücken Germany

We use the PAC-Bayesian theory for the setting of learning-to-optimize. To the best of our knowledge, we present the first framework to learn optimization algorithms with provable generalization guarantees (PAC-Bayesian bounds) and explicit trade-off between convergence guarantees and convergence speed, which contrasts with the typical worst-case analysis. Our learned optimization algorithms provably outperform related ones derived from a worst-case analysis. The results rely on PAC-Bayesian bounds for general, possibly unbounded loss-functions based on exponential families. Further, we provide a concrete algorithmic realization of the framework and new methodologies for learning-to-optimize. Finally, we conduct four practically relevant experiments to support our theory. With this, we showcase that the provided learning framework yields optimization algorithms that provably outperform the state-of-the-art by orders of magnitude. © 2024, CC BY.

关键词： optimization algorithms

A bilevel optiization based algorithm for solving a class of price equilibrium problems

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Hai, Nguyen Ngoc Muu, Le Dung van Quy, Nguyen Trade Union University Hanoi Viet Nam TIMAS Thang Long University Institute of Mathmatics VAST Hanoi Viet Nam Financial University Hanoi Viet Nam

We consider class of equilibrium models including the implicit Walras supply-demand and competitive models. Such a model in this class, in general, is ill-posed. We formulate such a model in the form a variational inequality having certain monotonicity property which allow us to describe a regularization algorithm avoiding the ill-posedness based upon the bilevel optimization for finding a point that is nearest to the given guessed or desired equilibrium price for the model. The obtained computational results with many randomly generated data show that the proposed algorithm works well for this class of the equilibrium models. © 2024, CC0.

关键词： optimization algorithms