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

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

Sliding Window Bi-Objective Evolutionary algorithms for Optimizing Chance-Constrained Monotone Submodular Functions

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Yan, Xiankun Neumann, Aneta Neumann, Frank Optimisation and Logistics School of Computer and Mathematical Sciences The University of Adelaide Adelaide Australia

Variants of the GSEMO algorithm using multi-objective formulations have been successfully analyzed and applied to optimize chance-constrained submodular functions. However, due to the effect of the increasing population size of the GSEMO algorithm considered in these studies from the algorithms, the approach becomes ineffective if the number of trade-offs obtained grows quickly during the optimization run. In this paper, we apply the sliding-selection approach introduced in [21] to the optimization of chance-constrained monotone submodular functions. We theoretically analyze the resulting SW-GSEMO algorithm which successfully limits the population size as a key factor that impacts the runtime and show that this allows it to obtain better runtime guarantees than the best ones currently known for the GSEMO. In our experimental study, we compare the performance of the SW-GSEMO to the GSEMO and NSGA-II on the maximum coverage problem under the chance constraint and show that the SW-GSEMO outperforms the other two approaches in most cases. In order to get additional insights into the optimization behavior of SW-GSEMO, we visualize the selection behavior of SW-GSEMO during its optimization process and show it beats other algorithms to obtain the highest quality of solution in variable instances. 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

A Framework for Decentralized Equilibrium Seeking in Networked Sampled-Data Games using Hybrid Control Tools*

学校读者我要写书评

暂无评论

IFAC-PapersOnLine 2023年第2期56卷 5095-5100页

作者： Vishal Shenoy Jorge I. Poveda Department of Electrical and Computer Engineering University of California San Diego CA 92093 USA

We study the steady-state Nash equilibrium-seeking problem for sampled-data games with LTI dynamics and quadratic costs. The key challenge is to guarantee the robust stability and convergence properties of the closed-loop system in the presence of local individual sampling mechanisms assigned to each of the players in the game. This problem is non-trivial due to the unstable behaviors that can arise when sequential control updates (rather than parallel) emerge in the closed-loop system because of the existence of local control triggering mechanisms in each node of the network. To address this issue, we introduce a controls framework based on tools from hybrid dynamical systems theory. Our results are illustrated via numerical examples.

关键词： Equilibrium-Seeking Network Systems Hybrid Control optimization algorithms Cyber-Physical Systems

Pandora with Inaccurate Priors

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Banihashem, Kiarash Chen, Xiang Hajiaghayi, MohammadTaghi Kim, Sungchul Mahadik, Kanak Rossi, Ryan Yu, Tong University of Maryland United States Adobe Research United States Adobe Systems United States

We investigate the role of inaccurate priors for the classical Pandora’s box problem. In the classical Pandora’s box problem we are given a set of boxes each with a known cost and an unknown value sampled from a known distribution. We investigate how inaccuracies in the beliefs can affect existing algorithms. Specifically, we assume that the knowledge of the underlying distribution has a small error in the Kolmogorov distance, and study how this affects the utility obtained by the optimal algorithm. Copyright © 2025, 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