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

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

Understand the Effectiveness of Shortcuts through the Lens of DCA

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Sun, Youran Liu, Yihua Niu, Yi-Shuai Tsinghua University Beijing China Beijing China

Difference-of-Convex Algorithm (DCA) is a well-known nonconvex optimization algorithm for minimizing a nonconvex function that can be expressed as the difference of two convex ones. Many famous existing optimization algorithms, such as SGD and proximal point methods, can be viewed as special DCAs with specific DC decompositions, making it a powerful framework for optimization. On the other hand, shortcuts are a key architectural feature in modern deep neural networks, facilitating both training and optimization. We showed that the shortcut neural network gradient can be obtained by applying DCA to vanilla neural networks, networks without shortcut connections. Therefore, from the perspective of DCA, we can better understand the effectiveness of networks with shortcuts. Moreover, we proposed a new architecture called NegNet that does not fit the previous interpretation but performs on par with ResNet and can be included in the DCA framework. Copyright © 2024, The Authors. All rights reserved.

关键词： optimization algorithms

Gradient Descent Efficiency Index

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Dhingra, Aviral

Gradient descent is a widely used iterative algorithm for finding local minima in multivariate functions. However, the final iterations often either overshoot the minima or make minimal progress, making it challenging to determine an optimal stopping point. This study introduces a new efficiency metric, Ek, designed to quantify the effectiveness of each iteration. The proposed metric accounts for both the relative change in error and the stability of the loss function across iterations. This measure is particularly valuable in resource-constrained environments, where costs are closely tied to training time. Experimental validation across multiple datasets and models demonstrates that Ek provides valuable insights into the convergence behavior of gradient descent, complementing traditional performance metrics. The index has the potential to guide more informed decisions in the selection and tuning of optimization algorithms in machine learning applications and be used to compare the "effectiveness" of models relative to each other. 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

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

Taxicab distance based best-worst method for multi-criteria decision-making: An analytical approach

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Ratandhara, Harshit M. Kumar, Mohit Department of Basic Sciences Institute of Infrastructure Technology Research And Management Gujarat Ahmedabad380026 India

The Best-Worst Method (BWM) is a well-known distance based multi-criteria decision-making method used for computing the weights of decision criteria. This article examines a taxicab distance based model of the BWM, with the objective of developing a framework for deriving the model’s optimal weights by solving its associated optimization problem analytically. To achieve this, an optimal modification based optimization problem, equivalent to the original one, is first formulated. This reformulated problem is then solved analytically, and the optimal weight sets are derived from its solutions. Contrary to existing literature that asserts the uniqueness of optimal weight sets based on numerical examples, our findings reveal that, in some cases, the taxicab BWM leads to multiple optimal weight sets. This framework provides a solid mathematical foundation that enhances understanding of the model. It also eliminates the requirement for optimization software, improving the model’s precision and efficiency. Finally, the effectiveness of the proposed framework is demonstrated through numerical examples. © 2024, CC BY-NC-SA.

关键词： optimization algorithms