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

Probabilistic Iterative Hard Thresholding for Sparse Learning

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Bergamaschi, Matteo Cristofari, Andrea Kungurtsev, Vyacheslav Rinaldi, Francesco Department of Mathematics "Tullio Levi-Civita" University of Padua Italy Department of Civil Engineering and Computer Science Engineering University of Rome "Tor Vergata" Italy Czech Technical University in Prague Czech Republic

For statistical modeling wherein the data regime is unfavorable in terms of dimensionality relative to the sample size, finding hidden sparsity in the ground truth can be critical in formulating an accurate statistical model. The so-called "0 norm", which counts the number of non-zero components in a vector, is a strong reliable mechanism of enforcing sparsity when incorporated into an optimization problem. However, in big data settings wherein noisy estimates of the gradient must be evaluated out of computational necessity, the literature is scant on methods that reliably converge. In this paper we present an approach towards solving expectation objective optimization problems with cardinality constraints. We prove convergence of the underlying stochastic process, and demonstrate the performance on two Machine Learning problems. © 2024, CC BY.

关键词： optimization algorithms

INCREASING THE VALUE OF INFORMATION DURING PLANNING IN UNCERTAIN ENVIRONMENTS

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Pokharel, Gaurab Department of Computer Science Oberlin College OberlinOH United States

Prior studies have demonstrated that for many real-world problems, POMDPs can be solved through online algorithms both quickly and with near optimality [10, 8, 6]. However, on an important set of problems where there is a large time delay between when the agent can gather information and when it needs to use that information, these solutions fail to adequately consider the value of information. As a result, information gathering actions, even when they are critical in the optimal policy, will be ignored by existing solutions, leading to sub-optimal decisions by the agent. In this research, we develop a novel solution that rectifies this problem by introducing a new algorithm that improves upon state-of-the-art online planning by better reflecting on the value of actions that gather information. We do this by adding Entropy to the UCB1 heuristic in the POMCP algorithm. We test this solution on the hallway problem. Results indicate that our new algorithm performs significantly better than POMCP. © 2024, CC BY.

关键词： optimization algorithms

Strategies for optimizing double-bracket quantum algorithms

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Xiaoyue, Li Robbiati, Matteo Pasquale, Andrea Pedicillo, Edoardo Wright, Andrew Carrazza, Stefano Gluza, Marek School of Physical and Mathematical Sciences Nanyang Technological University 21 Nanyang Link Singapore637371 Singapore Geneva1211 Switzerland TIF Lab Dipartimento di Fisica Università degli Studi diMilano Italy Quantum Research Centre Technology Innovation Institute Abu Dhabi United Arab Emirates INFN Sezione di Milano Milan Italy Lausanne Switzerland

Recently double-bracket quantum algorithms have been proposed as a way to compile circuits for approximating eigenstates. Physically, they consist of appropriately composing evolutions under an input Hamiltonian together with diagonal evolutions. Here, we present strategies to optimize the choice of the double-bracket evolutions to enhance the diagonalization efficiency. This can be done by finding optimal generators and durations of the evolutions. We present numerical results regarding the preparation of double-bracket iterations, both in ideal cases where the algorithm’s setup provides analytical convergence guarantees and in more heuristic cases, where we use an adaptive and variational approach to optimize the generators of the evolutions. As an example, we discuss the efficacy of these optimization strategies when considering a spin-chain Hamiltonian as the target. To propose algorithms that can be executed starting today, fully aware of the limitations of the quantum technologies at our disposal, we finally present a selection of diagonal evolution parametrizations that can be directly compiled into CNOTs and single-qubit rotation gates. We discuss the advantages and limitations of this compilation and propose a way to take advantage of this approach when used in synergy with other existing methods. © 2024, CC BY.

关键词： optimization algorithms

Turing in the shadows of Nobel and Abel: an algorithmic story behind two recent prizes

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Gamarnik, David Massachusetts Institute of Technology United States

The 2021 Nobel Prize in physics was awarded to Giorgio Parisi "for the discovery of the interplay of disorder and fluctuations in physical systems from atomic to planetary scales," and the 2024 Abel Prize in mathematics was awarded to Michel Talagrand "for his groundbreaking contributions to probability theory and functional analysis, with outstanding applications in mathematical physics and statistics." What remains largely absent in the popular descriptions of these prizes, however, is the profound contributions the works of both individuals have had to the field of algorithms and computation. The ideas first developed by Parisi and his collaborators relying on remarkably precise physics intuition, and later confirmed by Talagrand and others by no less remarkable mathematical techniques, have revolutionized the way we think algorithmically about optimization problems involving randomness. This is true both in terms of the existence of fast algorithms for some optimization problems, but also in terms of our persistent failures of finding such algorithms for some other optimization problems. © 2025, CC BY.

关键词： optimization algorithms

Distributed Alternating Direction Method of Multipliers for Linearly Constrained optimization Over a Network

学校读者我要写书评

暂无评论

IEEE CONTROL SYSTEMS LETTERS 2020年第1期4卷 247-252页

作者： Carli, Raffaele Dotoli, Mariagrazia Polytech Bari Dept Elect & Informat Engn I-70125 Bari Italy

In this letter we address the distributed optimization problem for a network of agents, which commonly occurs in several control engineering applications. Differently from the related literature, where only consensus constraints are typically addressed, we consider a challenging distributed optimization set-up where agents rely on local communication and computation to optimize a sum of local objective functions, each depending on individual variables subject to local constraints, while satisfying linear coupling constraints. Thanks to the distributed scheme, the resolution of the optimization problem turns into designing an iterative control procedure that steers the strategies of agents-whose dynamics is decouplednot only to be convergent to the optimal value but also to satisfy the coupling constraints. Based on duality and consensus theory, we develop a proximal Jacobian alternating direction method of multipliers (ADMM) for solving such a kind of linearly constrained convex optimization problems over a network. Using the monotone operator and fixed point mapping, we analyze the optimality of the proposed algorithm and establish its o(1/t) convergence rate. Finally, through numerical simulations we show that the proposed algorithm offers higher computational performances than recent distributed ADMM variants.

关键词： Distributed control distributed optimization optimization algorithms

Last Iterate Convergence of Incremental Methods and Applications in Continual Learning

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Cai, Xufeng Diakonikolas, Jelena Department of Computer Sciences University of Wisconsin-Madison United States

Incremental gradient and incremental proximal methods are a fundamental class of optimization algorithms used for solving finite sum problems, broadly studied in the literature. Yet, without strong convexity, their convergence guarantees have primarily been established for the ergodic (average) iterate. Motivated by applications in continual learning, we obtain the first convergence guarantees for the last iterate of both incremental gradient and incremental proximal methods, in general convex smooth (for both) and convex Lipschitz (for the proximal variants) settings. Our oracle complexity bounds for the last iterate nearly match (i.e., match up to a square-root-log or a log factor) the best known oracle complexity bounds for the average iterate, for both classes of methods. We further obtain generalizations of our results to weighted averaging of the iterates with increasing weights and for randomly permuted ordering of updates. We study incremental proximal methods as a model of continual learning with generalization and argue that large amount of regularization is crucial to preventing catastrophic forgetting. Our results generalize last iterate guarantees for incremental methods compared to state of the art, as such results were previously known only for overparameterized linear models, which correspond to convex quadratic problems with infinitely many solutions. Copyright © 2024, The Authors. All rights reserved.

关键词： optimization algorithms

Simmering: Sufficient is better than optimal for training neural networks

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Babayan, Irina Aliahmadi, Hazhir Anders, Greg van Department of Physics Engineering Physics and Astronomy Queen’s University KingstonONK7L 3N6 Canada

The broad range of neural network training techniques that invoke optimization but rely on ad hoc modification for validity [1? –4] suggests that optimization-based training is misguided. Shortcomings of optimization-based training are brought to particularly strong relief by the problem of overfitting, where naive optimization produces spurious outcomes.[5–7] The broad success of neural networks for modelling physical processes [8–12] has prompted advances that are based on inverting the direction of investigation and treating neural networks as if they were physical systems in their own right.[13–16] These successes raise the question of whether broader, physical perspectives could motivate the construction of improved training algorithms. Here, we introduce simmering, a physics-based method that trains neural networks to generate weights and biases that are merely "good enough", but which, paradoxically, outperforms leading optimization-based approaches. Using classification and regression examples we show that simmering corrects neural networks that are overfit by Adam [17], and show that simmering avoids overfitting if deployed from the outset. Our results question optimization as a paradigm for neural network training, and leverage information-geometric arguments to point to the existence of classes of sufficient training algorithms that do not take optimization as their starting point. Copyright © 2024, The Authors. All rights reserved.

关键词： optimization algorithms

EXADAM: THE POWER OF ADAPTIVE CROSS-MOMENTS

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Adly, Ahmed M. Egypt

This paper introduces EXAdam (EXtended Adam), a novel optimization algorithm that builds upon the widely-used Adam [1] optimizer. EXAdam incorporates three key enhancements: (1) new debiasing terms for improved moment estimation, (2) a gradient-based acceleration mechanism for increased responsiveness to the current loss landscape, and (3) a dynamic step size formula that allows for continuous growth of the learning rate throughout training. These innovations work synergistically to address limitations of the original Adam algorithm, potentially offering improved convergence properties, enhanced ability to escape saddle points, and greater robustness to hyperparameter choices. I provide a theoretical analysis of EXAdam’s components and their interactions, highlighting the algorithm’s potential advantages in navigating complex optimization landscapes. Empirical evaluations demonstrate EXAdam’s superiority over Adam, achieving 48.07% faster convergence and yielding improvements of 4.6%, 4.13%, and 2.39% in training, validation, and testing accuracies, respectively, when applied to a CNN trained on the CIFAR-10 dataset [2]. While these results are promising, further empirical validation across diverse tasks is essential to fully gauge EXAdam’s efficacy. Nevertheless, EXAdam represents a significant advancement in adaptive optimization techniques, with promising implications for a wide range of machine learning applications. This work aims to contribute to the ongoing development of more efficient, adaptive, and universally applicable optimization methods in the field of machine learning and artificial intelligence. Copyright © 2024, The Authors. All rights reserved.

关键词： optimization algorithms

Modified Recursive QAOA for Exact Max-Cut Solutions on Bipartite Graphs: Closing the Gap Beyond QAOA Limit

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Bae, Eunok Kwon, Hyukjoon Vijendran, V. Lee, Soojoon Seoul02455 Korea Republic of Department of Quantum Science and Technology Research School of Physics Australian National University Acton2601 Australia 2 Fusionopolis Way Innovis #08-03 Singapore138634 Singapore Department of Mathematics Research Institute for Basic Sciences Kyung Hee University Seoul02447 Korea Republic of

Quantum Approximate optimization Algorithm (QAOA) is a quantum-classical hybrid algorithm proposed with the goal of approximately solving combinatorial optimization problems such as the MAX-CUT problem. It has been considered a potential candidate for achieving quantum advantage in the Noisy Intermediate-Scale Quantum era and has been extensively studied. However, the performance limitations of low-level QAOA have also been demonstrated across various instances. In this work, we first analytically prove the performance limitations of level-1 QAOA in solving the MAX-CUT problem on bipartite graphs. To this end, we derive an upper bound for the approximation ratio based on the average degree of bipartite graphs. Second, we demonstrate that Recursive QAOA (RQAOA), which recursively reduces graph size using QAOA as a subroutine, outperforms the level-1 QAOA. However, the performance of RQAOA exhibits limitations as the graph size increases. Finally, we show that RQAOA with a restricted parameter regime can fully address these limitations. Surprisingly, this modified RQAOA always finds the exact maximum cut for any bipartite graphs and even for a more general graph with parity-signed weights. © 2024, CC BY.

关键词： optimization algorithms