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

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

CONSISTENT algorithms FOR MULTI-LABEL CLASSIFICATION WITH MACRO-AT-k METRICS

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Schultheis, Erik Kotlowski, Wojciech Wydmuch, Marek Babbar, Rohit Borman, Strom Dembczyński, Krzysztof Aalto University Helsinki Finland Poznan University of Technology Poznan Poland University of Bath Bath United Kingdom Yahoo Research Champaign United States Yahoo Research New York United States

We consider the optimization of complex performance metrics in multi-label classification under the population utility framework. We mainly focus on metrics linearly decomposable into a sum of binary classification utilities applied separately to each label with an additional requirement of exactly k labels predicted for each instance. These "macro-at-k" metrics possess desired properties for extreme classification problems with long tail labels. Unfortunately, the at-k constraint couples the otherwise independent binary classification tasks, leading to a much more challenging optimization problem than standard macro-averages. We provide a statistical framework to study this problem, prove the existence and the form of the optimal classifier, and propose a statistically consistent and practical learning algorithm based on the Frank-Wolfe method. Interestingly, our main results concern even more general metrics being non-linear functions of label-wise confusion matrices. Empirical results provide evidence for the competitive performance of the proposed approach. Copyright © 2024, The Authors. All rights reserved.

关键词： optimization algorithms

A survey on pioneering metaheuristic algorithms between 2019 and 2024

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Dokeroglu, Tansel Canturk, Deniz Kucukyilmaz, Tayfun TED University Software Engineering Department Ankara Turkey Department of Technology and Operations Management Erasmus University Netherlands

This review examines over 150 new metaheuristics of the last six years (between 2019-2024), underscoring their profound influence and performance. Over the past three decades, more than 500 new metaheuristic algorithms have been proposed, with no slowdown in sight—an overwhelming abundance that complicates the process of selecting and assessing the most effective solutions for complex optimization challenges. Our evaluation centers on pivotal criteria, including annual citation metrics, the breadth of addressed problem types, source code availability, user-friendly parameter configurations, innovative mechanisms and operators, and approaches designed to mitigate traditional metaheuristic issues such as stagnation and premature convergence. We further explore recent high-impact applications of the past six years’ most influential 23 metaheuristic algorithms, shedding light on their advantages and limitations, while identifying challenges and potential avenues for future research. © 2024, CC BY.

关键词： optimization algorithms

Faster Adaptive Decentralized Learning algorithms

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Huang, Feihu Zhao, Jianyu College of Computer Science and Technology Nanjing University of Aeronautics and Astronautics Nanjing China MIIT Key Laboratory of Pattern Analysis and Machine Intelligence Nanjing China

Decentralized learning recently has received increasing attention in machine learning due to its advantages in implementation simplicity and system robustness, data privacy. Meanwhile, the adaptive gradient methods show superior performances in many machine learning tasks such as training neural networks. Although some works focus on studying decentralized optimization algorithms with adaptive learning rates, these adaptive decentralized algorithms still suffer from high sample complexity. To fill these gaps, we propose a class of faster adaptive decentralized algorithms (i.e., AdaMDOS and AdaMDOF) for distributed nonconvex stochastic and finite-sum optimization, respectively. Moreover, we provide a solid convergence analysis framework for our methods. In particular, we prove that our AdaMDOS obtains a near-optimal sample complexity of Õ(ϵ−3) for finding an ϵ-stationary solution of nonconvex stochastic optimization. Meanwhile, our AdaMDOF obtains a near-optimal sample complexity of O(√nϵ−2) for finding an ϵ-stationary solution of nonconvex finite-sum optimization, where n denotes the sample size. To the best of our knowledge, our AdaMDOF algorithm is the first adaptive decentralized algorithm for nonconvex finite-sum optimization. Some experimental results demonstrate efficiency of our algorithms. © 2024, CC BY-NC-ND.

关键词： optimization algorithms

Submodular Information Selection for Hypothesis Testing with Misclassification Penalties

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Bhargav, Jayanth Ghasemi, Mahsa Sundaram, Shreyas Elmore Family School of Electrical & Computer Engineering Purdue University IN47907 United States

We consider the problem of selecting an optimal subset of information sources for a hypothesis testing/classification task where the goal is to identify the true state of the world from a finite set of hypotheses, based on finite observation samples from the sources. In order to characterize the learning performance, we propose a misclassification penalty framework, which enables nonuniform treatment of different misclassification errors. In a centralized Bayesian learning setting, we study two variants of the subset selection problem: (i) selecting a minimum cost information set to ensure that the maximum penalty of misclassifying the true hypothesis is below a desired bound and (ii) selecting an optimal information set under a limited budget to minimize the maximum penalty of misclassifying the true hypothesis. Under certain assumptions, we prove that the objective (or constraints) of these combinatorial optimization problems are weak (or approximate) submodular, and establish high-probability performance guarantees for greedy algorithms. Further, we propose an alternate metric for information set selection which is based on the total penalty of misclassification. We prove that this metric is submodular and establish near-optimal guarantees for the greedy algorithms for both the information set selection problems. Finally, we present numerical simulations to validate our theoretical results over several randomly generated instances. © 2024, CC BY.

关键词： optimization algorithms

Bayesian Optimisation with Unknown Hyperparameters: Regret Bounds Logarithmically Closer to Optimal

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Ziomek, Juliusz Adachi, Masaki Osborne, Michael A. Machine Learning Research Group University of Oxford United Kingdom Toyota Motor Corporation Japan

Bayesian optimization (BO) is widely used for optimising black-box functions but requires us to specify the length scale hyperparameter, which defines the smoothness of the functions the optimizer will consider. Most current BO algorithms choose this hyperparameter by maximizing the marginal likelihood of the observed data, albeit risking misspecification if the objective function is less smooth in regions we have not yet explored. The only prior solution addressing this problem with theoretical guarantees was A-GP-UCB, proposed by Berkenkamp et al. (2019). This algorithm progressively decreases the length scale, expanding the class of functions considered by the optimizer. However, A-GP-UCB lacks a stopping mechanism, leading to over-exploration and slow convergence. To overcome this, we introduce Length scale Balancing (LB)—a novel approach, aggregating multiple base surrogate models with varying length scales. LB intermittently adds smaller length scale candidate values while retaining longer scales, balancing exploration and exploitation. We formally derive a cumulative regret bound of LB and compare it with the regret of an oracle BO algorithm using the optimal length scale. Denoting the factor by which the regret bound of A-GP-UCB was away from oracle as g(T), we show that LB is only log g(T) away from oracle regret. We also empirically evaluate our algorithm on synthetic and real-world benchmarks and show it outperforms A-GP-UCB, maximum likelihood estimation and MCMC. © 2024, CC BY.

关键词： optimization algorithms

On Uncertainty Quantification for Near-Bayes Optimal algorithms

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Wang, Ziyu Holmes, Chris University of Oxford United Kingdom

Bayesian modelling allows for the quantification of predictive uncertainty which is crucial in safety-critical applications. Yet for many machine learning algorithms, it is difficult to construct or implement their Bayesian counterpart. In this work we present a promising approach to address this challenge, based on the hypothesis that commonly used ML algorithms are efficient across a wide variety of tasks and may thus be near Bayes-optimal w.r.t. an unknown task distribution. We prove that it is possible to recover the Bayesian posterior defined by the task distribution, which is unknown but optimal in this setting, by building a martingale posterior using the algorithm. We further propose a practical uncertainty quantification method that apply to general ML algorithms. Experiments based on a variety of neural network (NN) and non-NN algorithms demonstrate the efficacy of our method. © 2024, CC BY.

关键词： optimization algorithms

Complexities of Armijo-like algorithms in Deep Learning context

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Bilel, Bensaid Université de Bordeaux 351 cours de la Libération TalenceF 33 405 France

The classical Armijo backtracking algorithm [4] achieves the optimal complexity for smooth functions like gradient descent but without any hyperparameter tuning. However, the smoothness assumption is not suitable for Deep Learning optimization. In this work, we show that some variants of the Armijo optimizer achieves acceleration and optimal complexities under assumptions more suited for Deep Learning: the (L0, L1) smoothness condition [26] and analyticity [5]. New dependences on the smoothness constants and the initial gap are established. The results theoretically highlight the powerful efficiency of Armijo-like conditions for highly non-convex problems. Copyright © 2024, The Authors. All rights reserved.

关键词： optimization algorithms

Towards Sharper Risk Bounds for Minimax Problems

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Zhu, Bowei Li, Shaojie Liu, Yong Gaoling School of Artificial Intelligence Renmin University of China Beijing China Beijing Key Laboratory of Big Data Management and Analysis Methods Beijing China

Minimax problems have achieved success in machine learning such as adversarial training, robust optimization, reinforcement learning. For theoretical analysis, current optimal excess risk bounds, which are composed by generalization error and optimization error, present 1/n-rates in strongly-convex-strongly-concave (SC-SC) settings. Existing studies mainly focus on minimax problems with specific algorithms for optimization error, with only a few studies on generalization performance, which limit better excess risk bounds. In this paper, we study the generalization bounds measured by the gradients of primal functions using uniform localized convergence. We obtain a sharper high probability generalization error bound for nonconvex-strongly-concave (NC-SC) stochastic minimax problems. Furthermore, we provide dimension-independent results under Polyak-Lojasiewicz condition for the outer layer. Based on our generalization error bound, we analyze some popular algorithms such as empirical saddle point (ESP), gradient descent ascent (GDA) and stochastic gradient descent ascent (SGDA). We derive better excess primal risk bounds with further reasonable assumptions, which, to the best of our knowledge, are n times faster than exist results in minimax problems. © 2024, CC BY.

关键词： optimization algorithms