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

Mirror and Preconditioned Gradient Descent in Wasserstein Space

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Bonet, Clément Uscidda, Théo David, Adam Aubin-Frankowski, Pierre-Cyril Korba, Anna CREST ENSAE IP Paris France Institute of Mathematics Technische Universität Berlin Germany TU Wien Austria

As the problem of minimizing functionals on the Wasserstein space encompasses many applications in machine learning, different optimization algorithms on d have received their counterpart analog on the Wasserstein space. We focus here on lifting two explicit algorithms: mirror descent and preconditioned gradient descent. These algorithms have been introduced to better capture the geometry of the function to minimize and are provably convergent under appropriate (namely relative) smoothness and convexity conditions. Adapting these notions to the Wasserstein space, we prove guarantees of convergence of some Wasserstein-gradient-based discrete-time schemes for new pairings of objective functionals and regularizers. The difficulty here is to carefully select along which curves the functionals should be smooth and convex. We illustrate the advantages of adapting the geometry induced by the regularizer on ill-conditioned optimization tasks, and showcase the improvement of choosing different discrepancies and geometries in a computational biology task of aligning single-cells. © 2024, CC BY.

关键词： optimization algorithms

THEORETICAL ANALYSIS OF QUALITY DIVERSITY algorithms FOR A CLASSICAL PATH PLANNING PROBLEM

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Dang, Duc-Cuong Neumann, Aneta Neumann, Frank Opris, Andre Sudholt, Dirk Algorithms for Intelligent Systems University of Passau Passau Germany Optimisation and Logistics School of Computer and Mathematical Sciences The University of Adelaide Adelaide Australia

Quality diversity (QD) algorithms have shown to provide sets of high quality solutions for challenging problems in robotics, games, and combinatorial optimisation. So far, theoretical foundational explaining their good behaviour in practice lack far behind their practical success. We contribute to the theoretical understanding of these algorithms and study the behaviour of QD algorithms for a classical planning problem seeking several solutions. We study the all-pairs-shortest-paths (APSP) problem which gives a natural formulation of the behavioural space based on all pairs of nodes of the given input graph that can be used by Map-Elites QD algorithms. Our results show that Map-Elites QD algorithms are able to compute a shortest path for each pair of nodes efficiently in parallel. Furthermore, we examine parent selection techniques for crossover that exhibit significant speed ups compared to the standard QD approach. Copyright © 2024, The Authors. All rights reserved.

关键词： optimization algorithms

MINIMAX ASPECTS OF optimizationS IN ERGODIC THEORY

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Motonaga, Shoya Department of Mathematical Sciences Ritsumeikan University 1-1-1 Nojihigashi Shiga Kusatsu525-8577 Japan

We study optimization problems in ergodic theory from the view point of minimax problems. We give minimax characterizations of maximum ergodic averages involving time averages. Our approach also works for the abstract variational principle of generalized pressure functions which is proved by Biś et al. (2022). We also describe the relationship between our minimax results and the Fenchel-Rockafellar *** Codes 37A05, 37A50 Copyright © 2024, The Authors. All rights reserved.

关键词： optimization algorithms

Performance of Parity QAOA for the Signed Max-Cut Problem

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Weidinger, Anita Mbeng, Glen Bigan Fellner, Michael Khachatryan, Davit 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

The practical implementation of quantum optimization algorithms on noisy intermediate-scale quantum devices requires accounting for their limited connectivity. As such, the Parity architecture was introduced to overcome this limitation by encoding binary optimization problems onto planar quantum chips. We investigate the performance of the Quantum Approximate optimization Algorithm on the Parity architecture (Parity QAOA) for solving instances of the signed Max-Cut problem on complete and regular graphs. By comparing the algorithms at fixed circuit depth, we demonstrate that Parity QAOA outperforms conventional QAOA implementations based on SWAP networks. Our analysis utilizes Clifford circuits to estimate lower performance bounds for Parity QAOA for problem sizes that would be otherwise inaccessible on classical computers. For single layer circuits we additionally benchmark the recursive variant of the two algorithms, showing that their performance is equal. Copyright © 2024, The Authors. All rights reserved.

关键词： optimization algorithms

NEAR OPTIMAL PURE EXPLORATION IN LOGISTIC BANDITS

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Rivera, Eduardo Ochoa Tewari, Ambuj University of Michigan Ann Arbor United States

Bandit algorithms have garnered significant attention due to their practical applications in real-world scenarios. However, beyond simple settings such as multi-arm or linear bandits, optimal algorithms remain scarce. Notably, no optimal solution exists for pure exploration problems in the context of generalized linear model (GLM) bandits. In this paper, we narrow this gap and develop the first track-and-stop algorithm for general pure exploration problems under the logistic bandit called logistic track-and-stop (Log-TS). Log-TS is an efficient algorithm that asymptotically matches an approximation for the instance-specific lower bound of the expected sample complexity up to a logarithmic factor. © 2024, CC BY.

关键词： optimization algorithms

An Efficient Global optimization Algorithm with Adaptive Estimates of the Local Lipschitz Constants

学校读者我要写书评

暂无评论

arXiv 2022年

作者： D’Agostino, Danny Department of Industrial Systems Engineering and Management National University of Singapore Singapore

In this work, we present a new deterministic partition-based Global optimization (GO) algorithm that uses estimates of the local Lipschitz constants associated with different sub-regions of the domain of the objective function. The estimates of the local Lipschitz constants associated with each partition are the result of adaptively balancing the global and local information obtained so far from the algorithm, given in terms of absolute slopes. We motivate a coupling strategy with local optimization algorithms (both gradient-based and derivative-free) to accelerate the convergence speed of the proposed approach. In the end, we compare our approach HALO (Hybrid Adaptive Lipschitzian optimization) with respect to popular GO algorithms using hundreds of test functions. From the numerical results, the performance of HALO is very promising and can extend our arsenal of efficient procedures for attacking challenging real-world GO problems. The Python code of HALO is publicly available on GitHub. Copyright © 2022, The Authors. All rights reserved.

关键词： optimization algorithms

Picard Iteration for Parameter Estimation in Nonlinear Ordinary Differential Equations

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Talitckii, Aleksandr Peet, Matthew M. School for the Engineering of Matter Transport and Energy Arizona State University TempeAZ85298 United States

We consider the problem of using experimental time-series data for parameter estimation in nonlinear ordinary differential equations, focusing on the case where the data is noisy, sparse, irregularly sampled, includes multiple experiments, and does not directly measure the system state or its time-derivative. To account for such low-quality data, we propose a new framework for gradient-based parameter estimation which uses the Picard operator to reformulate the problem as constrained optimization with infinite-dimensional variables and constraints. We then use the contractive properties of the Picard operator to propose a class of gradient-contractive algorithms and provide conditions under which such algorithms are guaranteed to converge to a local optima. The algorithms are then tested on a battery of models and variety of datasets in order to demonstrate robustness and improvement over alternative approaches. Copyright © 2024, The Authors. All rights reserved.

关键词： optimization algorithms

The Competition Complexity of Prophet Inequalities with Correlations

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Ezra, Tomer Garbuz, Tamar Harvard University Cambridge United States Tel Aviv University Tel Aviv Israel

We initiate the study of the prophet inequality problem through the resource augmentation framework in scenarios when the values of the rewards are correlated. Our goal is to determine the number of additional rewards an online algorithm requires to approximate the maximum value of the original instance. While the independent reward case is well understood, we extend this research to account for correlations among rewards. Our results demonstrate that, unlike in the independent case, the required number of additional rewards for approximation depends on the number of original rewards, and that block-threshold algorithms, which are optimal in the independent case, may require an infinite number of additional rewards when correlations are present. We develop asymptotically optimal algorithms for the following three scenarios: (1) where rewards arrive in blocks corresponding to the different copies of the original instance;(2) where rewards across all copies are arbitrarily shuffled;and (3) where rewards arrive in blocks corresponding to the different copies of the original instance, and values within each block are pairwise independent rather than fully correlated. Copyright © 2024, The Authors. All rights reserved.

关键词： optimization algorithms

The Better Solution Probability Metric: Optimizing QAOA to Outperform its Warm-Start Solution

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Feeney, Sean Tate, Reuben Eidenbenz, Stephan CCS-3 Information Sciences Los Alamos National Laboratory Los AlamosNM87544 United States

This paper presents a numerical simulation investigation of the Warm-Start Quantum Approximate optimization Algorithm (QAOA) as proposed by Tate et al. [1], focusing on its application to 3-regular Max-Cut problems. Our study demonstrates that Warm-Start QAOA consistently outperforms theoretical lower bounds on approximation ratios across various tilt angles, highlighting its potential in practical scenarios beyond worst-case predictions. Despite these improvements, Warm-Start QAOA with traditional parameters optimized for expectation value does not exceed the performance of the initial classical solution. To address this, we introduce an alternative parameter optimization objective, the Better Solution Probability (BSP) metric. Our results show that BSP-optimized Warm-Start QAOA identifies solutions at non-trivial tilt angles that are better than even the best classically found warm-start solutions with non-vanishing probabilities. These findings underscore the importance of both theoretical and empirical analyses in refining QAOA and exploring its potential for quantum advantage. Copyright © 2024, The Authors. All rights reserved.

关键词： optimization algorithms