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

Robust Information Selection for Hypothesis Testing with Misclassification Penalties

学校读者我要写书评

暂无评论

arXiv 2025年

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

We study the problem of robust information selection for a Bayesian hypothesis testing / classification task, where the goal is to identify the true state of the world from a finite set of hypotheses based on observations from the selected information sources. We introduce a novel misclassification penalty framework, which enables non-uniform treatment of different misclassification events. Extending the classical subset selection framework, we study the problem of selecting a subset of sources that minimize the maximum penalty of misclassification under a limited budget, despite deletions or failures of a subset of the selected sources. We characterize the curvature properties of the objective function and propose an efficient greedy algorithm with performance guarantees. Next, we highlight certain limitations of optimizing for the maximum penalty metric and propose a submodular surrogate metric to guide the selection of the information set. We propose a greedy algorithm with near-optimality guarantees for optimizing the surrogate metric. Finally, we empirically demonstrate the performance of our proposed algorithms in several instances of the information set selection problem. © 2025, CC BY.

关键词： optimization algorithms

A double-layer placement algorithm for integrated circuit-based modules on printed circuit board

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Li, Hangyuan Yang, Zhaoyang Pang, Haotian Xu, Ning Chen, Yu School of Computer Science and Artificial Intelligence Wuhan University of Technology Wuhan430070 China School of Information Engineering Wuhan University of Technology Wuhan430070 China School of Mathematics and Statistics Wuhan University of Technology Wuhan430070 China

Considering that the physical design of printed circuit board (PCB) follows the principle of modularized design, this paper proposes an automatic placement algorithm for functional modules. We first model the placement problem as a mixed-variable optimization problem, and then, developed tailored algorithms of global placement and legalization for the top-layer centralized placement subproblem and the bottom-layer pin-oriented placement subproblem. Numerical comparison demonstrates that the proposed mixed-variable optimization scheme can get optimized total wirelength of placement. Meanwhile, experimental results on several industrial PCB cases show that the developed centralized strategies can well accommodate the requirement of top-layer placement, and the pin-oriented global placement based on bin clustering contributes to optimized placement results meeting the requirement of pin-oriented design. © 2025, CC BY.

关键词： optimization algorithms

Implicit bias of Normalized Steepest Descent in Multiclass Classification: Sign Descent, Spectral Descent, and Adam

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Fan, Chen Schmidt, Mark Thrampoulidis, Christos University of British Columbia Canada Canada

In the optimization of overparameterized models, different gradient-based methods can achieve zero training error yet converge to distinctly different solutions inducing different generalization properties. Despite a decade of research on implicit optimization bias, important questions remain open even in the foundational case of linear classification with separable data. We address this gap by characterizing the implicit bias of both Adam and Sign gradient descent (SignGD) in multi-class cross-entropy minimization: we prove that their iterates converge to solutions maximizing the margin with respect to the classifier matrix’s max-norm, and we establish the corresponding convergence rates. We then generalize our analysis to p-norm normalized steepest descent (NSD) algorithms. This includes Spectral Descent, which we show converges to the max-margin solution with respect to the spectral norm. A key insight is that the analysis of general entrywise and Schatten p-norms can be reduced to the analysis of NSD with max-norm (i.e., SignGD) by exploiting a natural ordering property between all p-norms relative to the max-norm and its dual sum-norm. Our results demonstrate that the multiclass linear setting, which is inherently richer than the binary counterpart, provides the most transparent playground for studying implicit biases of matrix-parameter optimization algorithms. © 2025, CC BY.

关键词： optimization algorithms

Selective Use of Yannakakis’ Algorithm to Improve Query Performance: Machine Learning to the Rescue

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Böhm, Daniela Gottlob, Georg Lanzinger, Matthias Longo, Davide Mario Okulmus, Cem Pichler, Reinhard Selzer, Alexander TU Wien Vienna Austria University of Calabria Rende Italy University Paderborn Paderborn Germany

Query optimization has played a central role in database research for decades. However, more often than not, the proposed optimization techniques lead to a performance improvement in some, but not in all, situations. Therefore, we urgently need a methodology for designing a decision procedure that decides for a given query whether the optimization technique should be applied or not. In this work, we propose such a methodology with a focus on Yannakakis-style query evaluation as our optimization technique of interest. More specifically, we formulate this decision problem as an algorithm selection problem and we present a Machine Learning based approach for its solution. Empirical results with several benchmarks on a variety of database systems show that our approach indeed leads to a statistically significant performance improvement. © 2025, CC BY-NC-ND.

关键词： optimization algorithms

The Performance Of The Unadjusted Langevin Algorithm Without Smoothness Assumptions

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Johnston, Tim Lytras, Iosif Makras, Nikolaos Sabanis, Sotirios School of Mathematics University of Edinburgh United Kingdom National Technical University of Athens Greece Université Paris Dauphine-PSL Ceremade France Athena/Archimedes Research Centre Greece

In this article, we study the problem of sampling from distributions whose densities are not necessarily smooth nor log-concave. We propose a simple Langevin-based algorithm that does not rely on popular but computationally challenging techniques, such as the Moreau Yosida envelope or Gaussian smoothing. We derive non-asymptotic guarantees for the convergence of the algorithm to the target distribution in Wasserstein distances. Non asymptotic bounds are also provided for the performance of the algorithm as an optimizer, specifically for the solution of associated excess risk optimization problems. © 2025, CC BY.

关键词： optimization algorithms

RL-finetuning LLMs from on- and off-policy data with a single algorithm

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Tang, Yunhao Cohen, Taco Zhang, David W. Valko, Michal Munos, Rémi Meta GenAI United States Meta FAIR United States Meta United States

We introduce a novel reinforcement learning algorithm (AGRO, for Any-Generation Reward optimization) for fine-tuning large-language models. AGRO leverages the concept of generation consistency, which states that the optimal policy satisfies the notion of consistency across any possible generation of the model. We derive algorithms that find optimal solutions via the sample-based policy gradient and provide theoretical guarantees on their convergence. Our experiments demonstrate the effectiveness of AGRO in both on-policy and off-policy settings, showing improved performance on the mathematical reasoning dataset over baseline algorithms. Copyright © 2025, The Authors. All rights reserved.

关键词： optimization algorithms

Near-Optimal Decision Trees in a SPLIT Second

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Babbar, Varun McTavish, Hayden Rudin, Cynthia Seltzer, Margo Department of Computer Science Duke University Durham United States Department of Computer Science University of British Columbia Vancouver Canada

Decision tree optimization is fundamental to interpretable machine learning. The most popular approach is to greedily search for the best feature at every decision point, which is fast but provably suboptimal. Recent approaches find the global optimum using branch and bound with dynamic programming, showing substantial improvements in accuracy and sparsity at great cost to scalability. An ideal solution would have the accuracy of an optimal method and the scalability of a greedy method. We introduce a family of algorithms called SPLIT (SParse Lookahead for Interpretable Trees) that moves us significantly forward in achieving this ideal balance. We demonstrate that not all sub-problems need to be solved to optimality to find high quality trees;greediness suffices near the leaves. Since each depth adds an exponential number of possible trees, this change makes our algorithms orders of magnitude faster than existing optimal methods, with negligible loss in performance. We extend this algorithm to allow scalable computation of sets of near-optimal trees (i.e., the Rashomon set). © 2025, CC BY.

关键词： optimization algorithms

eagle: early approximated gradient based learning rate estimator

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Fujimoto, Takumi Nishi, Hiroaki Faculty of Science and Technology Japan Center for Information and Computer Science School of Science for Open and Environmental Systems Keio University Japan

We propose EAGLE update rule, a novel optimization method that accelerates loss convergence during the early stages of training by leveraging both current and previous step parameter and gradient values. The update algorithm estimates optimal parameters by computing the changes in parameters and gradients between consecutive training steps and leveraging the local curvature of the loss landscape derived from these changes. However, this update rule has potential instability, and to address that, we introduce an adaptive switching mechanism that dynamically selects between Adam and EAGLE update rules to enhance training stability. Experiments on standard benchmark datasets demonstrate that EAGLE optimizer, which combines this novel update rule with the switching mechanism achieves rapid training loss convergence with fewer epochs, compared to conventional optimization methods. Copyright © 2025, The Authors. All rights reserved.

关键词： optimization algorithms

PAC Learnability of Scenario Decision-Making algorithms: Necessary and Sufficient Conditions

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Berger, Guillaume O. Jungers, Raphaël M. Department of Applied Mathematics UCLouvain Louvain-la-Neuve1348 Belgium

We study the PAC property of scenario decision-making algorithms, that is, the ability to make a decision that has an arbitrarily low risk of violating an unknown safety constraint, provided sufficiently many realizations (called scenarios) of the safety constraint are sampled. Sufficient conditions for scenario decision-making algorithms to be PAC are available in the literature, such as finiteness of the VC dimension of its associated classifier and existence of a compression scheme. We study the question of whether these sufficient conditions are also necessary. We show with counterexamples that this is not the case in general. This contrasts with binary classification learning, for which the analogous conditions are sufficient and necessary. Popular scenario decision-making algorithms, such as scenario optimization, enjoy additional properties, such as stability and consistency. We show that even under these additional assumptions the above conclusions hold. Finally, we derive a necessary condition for scenario decision-making algorithms to be PAC, inspired by the VC dimension and the so-called no-free-lunch theorem. Copyright © 2025, The Authors. All rights reserved.

关键词： optimization algorithms