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

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

Mining Potentially Explanatory Patterns via Partial Solutions

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Catalano, GianCarlo A.P.I. Brownlee, Alexander E.I. Cairns, David McCall, John Ainslie, Russell University of Stirling Computing Science and Mathematics Stirling United Kingdom Robert Gordon University National Subsea Centre Aberdeen United Kingdom BT Technology Applied Research Ipswich United Kingdom

Genetic algorithms have established their capability for solving many complex optimization problems. Even as good solutions are produced, the user’s understanding of a problem is not necessarily improved, which can lead to a lack of confidence in the results. To mitigate this issue, explainability aims to give insight to the user by presenting them with the knowledge obtained by the algorithm. In this paper we introduce Partial Solutions in order to improve the explainability of solutions to combinatorial optimization problems. Partial Solutions represent beneficial traits found by analyzing a population, and are presented to the user for explainability, but also provide an explicit model from which new solutions can be generated. We present an algorithm that assembles a collection of Partial Solutions chosen to strike a balance between high fitness, simplicity and atomicity. Experiments with standard benchmarks show that the proposed algorithm is able to find Partial Solutions which improve explainability at reasonable computational cost without affecting search performance. © 2024, CC BY.

关键词： optimization algorithms

Revisiting Local PageRank Estimation on Undirected Graphs: Simple and Optimal

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Wang, Hanzhi Renmin University of China Beijing China

We propose a simple and optimal algorithm, BackMC, for local PageRank estimation in undirected graphs: given an arbitrary target node t in an undirected graph G comprising n nodes and m edges, BackMC accurately estimates the PageRank score of node t while assuring a small relative error and a high success probability. The worst-case computational complexity of BackMC is upper bounded by (formula presented) , where dmin denotes the minimum degree of G, and dt denotes the degree of t, respectively. Compared to the previously best upper bound of (formula presented) (VLDB’23), which is derived from a significantly more complex algorithm and analysis, our BackMC improves the computational complexity for this problem by a factor of (formula presented) with a much simpler algorithm. Furthermore, we establish a matching lower bound of (formula presented) for any algorithm that attempts to solve the problem of local PageRank estimation, demonstrating the theoretical optimality of our BackMC. We conduct extensive experiments on various large-scale real-world and synthetic graphs, where BackMC consistently shows superior performance. Copyright © 2024, The Authors. All rights reserved.

关键词： 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

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

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

Complexity order of multiple resource algorithms

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Teh, Run Yan Thenabadu, Manushan Drummond, Peter D. Centre for Quantum Science and Technology Theory Swinburne University of Technology Melbourne3122 Australia

Algorithmic efficiency is essential to reducing energy use and time taken for computational problems. Optimizing efficiency is important for tasks involving multiple resources, for example in stochastic calculations where the size of the random ensemble competes with the time-step. We define the complexity order of an algorithm needing multiple resources as the exponent of inverse total error with respect to the total resources used. The optimum order c is predicted for cases involving competing, factorable resources. As an illustration, this is applied to computing averages in a stochastic differential equation, with numerical examples that agree with earlier literature, as well as with the more general analytic theory that is obtained here. Copyright © 2024, The Authors. All rights reserved.

关键词： optimization algorithms

A preconditioned second-order convex splitting algorithm with a difference of varying convex functions and line search

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Shen, Xinhua Shang, Zaijiu Sun, Hongpeng School of Mathematics Renmin University of China China Academy of Mathematics and Systems Science Chinese Academy of Sciences Beijing100190 China Shanghai Institute for Mathematics and Interdisciplinary Sciences Shanghai200092 China

This paper introduces a preconditioned convex splitting algorithm enhanced with line search techniques for nonconvex optimization problems. The algorithm utilizes second-order backward differentiation formulas (BDF) for the implicit and linear components and the Adams-Bashforth scheme for the nonlinear and explicit parts of the gradient flow in variational functions. The proposed algorithm, resembling a generalized difference-of-convex-function approach, involves a changing set of convex functions in each iteration. It integrates the Armijo line search strategy to improve performance. The study also discusses classical preconditioners such as symmetric Gauss-Seidel, Jacobi, and Richardson within this context. The global convergence of the algorithm is established through the Kurdyka-Lojasiewicz properties, ensuring convergence within a finite number of preconditioned iterations. Numerical experiments demonstrate the superiority of the proposed second-order convex splitting with line search over conventional difference-of-convex-function algorithms. © 2024, CC BY-NC-ND.

关键词： optimization algorithms

TERIME: An improved RIME algorithm with enhanced exploration and exploitation for robust parameter extraction of photovoltaic models

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Chen, Shi-Shun Jiang, Yu-Tong Chen, Wen-Bin Li, Xiao-Yang School of Reliability and Systems Engineering Beihang University Beijing100191 China

Parameter extraction of photovoltaic (PV) models is crucial for the planning, optimization, and control of PV systems. Although some methods using meta-heuristic algorithms have been proposed to determine these parameters, the robustness of solutions obtained by these methods faces great challenges when the complexity of the PV model increases. The unstable results will affect the reliable operation and maintenance strategies of PV systems. In response to this challenge, an improved RIME algorithm with enhanced exploration and exploitation is proposed for robust and accurate parameter identification for various PV models. Specifically, the differential evolution mutation operator is integrated in the exploration phase to enhance the population diversity. Meanwhile, a new exploitation strategy incorporating randomization and neighborhood strategies simultaneously is developed to maintain the balance of exploitation width and depth. The improved RIME algorithm is applied to estimate the optimal parameters of the single-diode model (SDM), double-diode model (DDM), and triple-diode model (TDM) combined with the Lambert-W function for three PV cell and module types including RTC France, Photo Watt-PWP 201 and S75. According to the statistical analysis in 100 runs, the TEIMRE achieves more accurate and robust parameter estimations than other techniques to various PV models in varying environmental conditions. All of our source codes are publicly available at https://***/dirge1/TERIME. © 2024, CC BY.

关键词： optimization algorithms