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

A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noise

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Diakonikolas, Ilias Zarifis, Nikos UW-Madison United States

We study the problem of PAC learning γ-margin halfspaces in the presence of Massart noise. Without computational considerations, the sample complexity of this learning problem is known to be Θ(1 e /(γ2ǫ)). Prior computationally efficient algorithms for the problem incur sample complexity Õ(1/(γ4ǫ3)) and achieve 0-1 error of η + ǫ, where η e /(γ2ǫ2)), nearly matching this lower bound. In addition, our algorithm is simple and practical, relying on online SGD on a carefully selected sequence of convex losses. Copyright © 2025, The Authors. All rights reserved.

关键词： optimization algorithms

A new tail bound for the sum of bounded independent random variables

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Loper, Jackson Regier, Jeffrey Department of Statistics University of Michigan United States

We construct a new tail bound for the sum of independent random variables for situations in which the expected value of the sum is known and each random variable lies within a specified interval, which may be different for each variable. This new bound can be computed by solving a two-dimensional convex optimization problem. Simulations demonstrate that the new bound is often substantially tighter than Hoeffding’s inequality for cases in which both bounds are applicable. Copyright © 2025, The Authors. All rights reserved.

关键词： optimization algorithms

On the non-submodularity of the problem of adding links to minimize the effective graph resistance

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Achterberg, Massimo A. Kooij, Robert E. Faculty of Electrical Engineering Mathematics and Computer Science Delft University of Technology P.O. Box 5031 Delft2600 GA Netherlands P.O. Box 96800 Den Haag2509 JE Netherlands

We consider the optimisation problem of adding k links to a given network, such that the resulting effective graph resistance is as small as possible. The problem was recently proven to be NP-hard, such that optimal solutions obtained with brute-force methods require exponentially many computation steps and thus are infeasible for any graph of realistic size. Therefore, it is common in such cases to use a simple greedy algorithm to obtain an approximation of the optimal solution. It is known that if the considered problem is submodular, the quality of the greedy solution can be guaranteed. However, it is known that the optimisation problem we are facing, is not submodular. For such cases one can use the notion of generalized submodularity, which is captured by the submodularity ratio γ. A performance bound, which is a function of γ, also exists in case of generalized submodularity. In this paper we give an example of a family of graphs where the submodularity ratio approaches zero, implying that the solution quality of the greedy algorithm cannot be guaranteed. Furthermore, we show that the greedy algorithm does not always yield the optimal solution and demonstrate that even for a small graph with 10 nodes, the ratio between the optimal and the greedy solution can be as small as 0.878. © 2025, CC BY.

关键词： optimization algorithms

A non-parametric optimal design algorithm for population pharmacokinetics

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Hovd, Markus Kryshchenko, Alona Neely, Michael N. Otalvaro, Julian Schumitzky, Alan Yamada, Walter M. Oslo University Hospital University of Oslo Norway California State University Channel Islands United States Children’s Hospital Los Angeles University of Southern California United States Children’s Hospital Los Angeles United States University of Southern California United States

This paper introduces a non-parametric estimation algorithm designed to effectively estimate the joint distribution of model parameters with application to population pharmacokinetics. Our research group has previously developed the non-parametric adaptive grid (NPAG) algorithm, which while accurate, explores parameter space using an ad-hoc method to suggest new support points. In contrast, the non-parametric optimal design (NPOD) algorithm uses a gradient approach to suggest new support points, which reduces the amount of time spent evaluating non-relevant points and by this the overall number of cycles required to reach convergence. In this paper, we demonstrate that the NPOD algorithm achieves similar solutions to NPAG across two datasets, while being significantly more efficient in both the number of cycles required and overall runtime. Given the importance of developing robust and efficient algorithms for determining drug doses quickly in pharmacokinetics, the NPOD algorithm represents a valuable advancement in nonparametric modeling. Further analysis is needed to determine which algorithm performs better under specific conditions. © 2025, CC BY.

关键词： optimization algorithms

Optimal Criteria for Best Subset Selection

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Zhu, Zhihan Zhang, Yanhao Xia, Yong The School of Mathematical Sciences Beihang University Beijing100191 China

This paper introduces two novel criteria: one for feature selection and another for feature elimination in the context of best subset selection, which is a benchmark problem in statistics and machine learning. From the perspective of optimization, we revisit the classical selection and elimination criteria in traditional best subset selection algorithms, revealing that these classical criteria capture only partial variations of the objective function after the entry or exit of features. By formulating and solving optimization subproblems for feature entry and exit exactly, new selection and elimination criteria are proposed, proved as the optimal decisions for the current entry-and-exit process compared to classical criteria. Replacing the classical selection and elimination criteria with the proposed ones generates a series of enhanced best subset selection algorithms. These generated algorithms not only preserve the theoretical properties of the original algorithms but also achieve significant meta-gains without increasing computational cost across various scenarios and evaluation metrics on multiple tasks such as compressed sensing and sparse regression. © 2025, CC BY.

关键词： optimization algorithms

A New and Robust ABC-K-Means Hybrid Approach for Improved Image Clustering

学校读者我要写书评

暂无评论

SSRN

SSRN 2025年

作者： El Haouari, Oussama Mourad, Hana Khrissi, Lahbib El Akkad, Nabil LASET Laboratory of Applied Sciences and Emerging Technologies National School of Applied Sciences of Fez Sidi Mohamed Ben Abdellah University Fez Morocco LIPI Laboratory of Interdisciplinary Computer Science and Physics Normal Superior School of Fez Sidi Mohamed Ben Abdellah University Fez Morocco

Clustering remains a critical task in image analysis, yet traditional K-means methods frequently suffer from local optima issues, leading to suboptimal clustering, particularly in complex datasets. In this study, we present a novel hybrid approach that integrates the Artificial Bee Colony (ABC) algorithm with K-means to optimize initial centroid placement and improve clustering accuracy. By leveraging ABC's global optimization capabilities, our approach enhances K-means’ robustness and convergence, providing more accurate clustering results. Comparative experiments demonstrate that our ABC-K-means method consistently outperforms other K-means-based hybrid algorithms, including those incorporating Particle Swarm optimization (PSO), Simulated Annealing (SA), and Genetic algorithms (GA). This enhanced method addresses critical limitations in traditional clustering algorithms, establishing a promising solution for high-quality image clustering tasks. © 2025, The Authors. All rights reserved.

关键词： optimization algorithms

A Geometric Framework for Stochastic Iterations

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Combettes, Patrick L. Madariaga, Javier I. North Carolina State University Department of Mathematics RaleighNC27695 United States

This paper concerns models and convergence principles for dealing with stochasticity in a wide range of algorithms arising in nonlinear analysis and optimization in Hilbert spaces. It proposes a flexible geometric framework within which existing solution methods can be recast and improved, and new ones can be designed. Almost sure weak, strong, and linear convergence results are established in particular for fixed point and feasibility problems. In these areas, the proposed algorithms exceed the features of the state of the art in several respects. Numerical applications to signal and image recovery are provided. Copyright © 2025, The Authors. All rights reserved.

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

Learning Is a Kan Extension

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Pugh, Matthew Grundy, Jo Cirstea, Corina Harris, Nick

Previous work has demonstrated that efficient algorithms exist for computing Kan extensions and that some Kan extensions have interesting similarities to various machine learning algorithms. This paper closes the gap by proving that all error minimisation algorithms may be presented as a Kan extension. This result provides a foundation for future work to investigate the optimisation of machine learning algorithms through their presentation as Kan extensions. A corollary of this representation of error-minimising algorithms is a presentation of error from the perspective of lossy and lossless transformations of data. © 2025, CC BY.

关键词： optimization algorithms