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

Archetypal Analysis for Binary Data

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Wedenborg, A. Emilie J. Mørup, Morten The Technical University of Denmark DTU Compute - Cognitive Systems Section Denmark

Archetypal analysis (AA) is a matrix decomposition method that identifies distinct patterns using convex combinations of the data points denoted archetypes with each data point in turn reconstructed as convex combinations of the archetypes. AA thereby forms a polytope representing trade-offs of the distinct aspects in the data. Most existing methods for AA are designed for continuous data and do not exploit the structure of the data distribution. In this paper, we propose two new optimization frameworks for archetypal analysis for binary data. i) A second order approximation of the AA likelihood based on the Bernoulli distribution with efficient closed-form updates using an active set procedure for learning the convex combinations defining the archetypes, and a sequential minimal optimization strategy for learning the observation specific reconstructions. ii) A Bernoulli likelihood based version of the principal convex hull analysis (PCHA) algorithm originally developed for least squares optimization. We compare these approaches with the only existing binary AA procedure relying on multiplicative updates and demonstrate their superiority on both synthetic and real binary data. Notably, the proposed optimization frameworks for AA can easily be extended to other data distributions providing generic efficient optimization frameworks for AA based on tailored likelihood functions reflecting the underlying data distribution. © 2025, CC BY.

关键词： optimization algorithms

GRADIENT SAMPLING ALGORITHM FOR SUBSMOOTH FUNCTIONS

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Boskos, Dimitris Cortés, Jorge Martínez, Sonia Delft Center for Systems and Control TU Delft Netherlands Department of Mechanical and Aerospace Engineering UC San Diego United States

This paper considers non-smooth optimization problems where we seek to minimize the pointwise maximum of a continuously parameterized family of functions. Since the objective function is given as the solution to a maximization problem, neither its values nor its gradients are available in closed form, which calls for approximation. Our approach hinges upon extending the so-called gradient sampling algorithm, which approximates the Clarke generalized gradient of the objective function at a point by sampling its derivative at nearby locations. This allows us to select descent directions around points where the function may fail to be differentiable and establish algorithm convergence to a stationary point from any initial condition. Our key contribution is to prove this convergence by alleviating the requirement on continuous differentiability of the objective function on an open set of full measure. We further provide assumptions under which a desired convex subset of the decision space is rendered attractive for the iterates of the algorithm. Copyright © 2025, The Authors. All rights reserved.

关键词： optimization algorithms

Blackwell’s Approachability with Approximation algorithms

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Garber, Dan Massalha, Mhna Faculty of Data and Decision Sciences Technion - Israel Institute of Technology Israel

We revisit Blackwell’s celebrated approachability problem which considers a repeated vector-valued game between a player and an adversary. Motivated by settings in which the action set of the player or adversary (or both) is difficult to optimize over, for instance when it corresponds to the set of all possible solutions to some NP-Hard optimization problem, we ask what can the player guarantee efficiently, when only having access to these sets via approximation algorithms with ratios αX ≥ 1 and 1 ≥ αY > 0, respectively. Assuming the player has monotone preferences, in the sense that he does not prefer a vector-valued loss 1 over 2 if 2 ≤ 1, we establish that given a Blackwell instance with an approachable target set S, the downward closure of the appropriately-scaled set αXαY−1S is efficiently approachable with optimal rate. In case only the player’s or adversary’s set is equipped with an approximation algorithm, we give simpler and more efficient algorithms. Copyright © 2025, The Authors. All rights reserved.

关键词： optimization algorithms

On the Low Weight Polynomial Multiple Problem

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Ţiplea, Ferucio Laurenţiu Lăzărescu, Simona-Maria Faculty of Computer Science "Alexandru Ioan Cuza" University of Iaşi Iaşi Romania "Simion Stoilow" Institute of Mathematics The Romanian Academy Bucharest Romania

Finding a low-weight multiple (LWPM) of a given polynomial is very useful in the cryptanalysis of stream ciphers and arithmetic in finite fields. There is no known deterministic polynomial time complexity algorithm for solving this problem, and the most efficient algorithms are based on a time/memory trade-off. The widespread perception is that this problem is difficult. In this paper, we establish a relationship between the LWPM problem and the MAX-SAT problem of determining an assignment that maximizes the number of valid clauses of a system of affine Boolean clauses. This relationship shows that any algorithm that can compute the optimum of a MAX-SAT instance can also compute the optimum of an equivalent LWPM instance. It also confirms the perception that the LWPM problem is *** Codes 68Q15, 68Q25, 14G50, 94A60 © 2024, CC BY-NC-ND.

关键词： optimization algorithms

Nesterov acceleration in benignly non-convex landscapes

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Gupta, Kanan Wojtowytsch, Stephan Department of Mathematics University of Pittsburgh United States

While momentum-based optimization algorithms are commonly used in the notoriously non-convex optimization problems of deep learning, their analysis has historically been restricted to the convex and strongly convex setting. In this article, we partially close this gap between theory and practice and demonstrate that virtually identical guarantees can be obtained in optimization problems with a ‘benign’ non-convexity. We show that these weaker geometric assumptions are well justified in overparametrized deep learning, at least locally. Variations of this result are obtained for a continuous time model of Nesterov’s accelerated gradient descent algorithm (NAG), the classical discrete time version of NAG, and versions of NAG with stochastic gradient estimates with purely additive noise and with noise that exhibits both additive and multiplicative scaling. Copyright © 2024, The Authors. All rights reserved.

关键词： optimization algorithms

Convergence towards a local minimum by direct search methods with a covering step

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Bouchet, Pierre-Yves Audet, Charles Bourdin, Loïc École Polytechnique de Montréal MontréalQCH3T 1J4 Canada GERAD MontréalQCH3T 1J4 Canada XLIM Research Institute University of Limoges France

This paper introduces a new step to the Direct Search Method (DSM) to strengthen its convergence analysis. By design, this so-called covering step may ensure that, for all refined points of the sequence of incumbent solutions generated by the resulting cDSM (covering DSM), the set of all evaluated trial points is dense in a neighborhood of that refined point. We prove that this additional property guarantees that all refined points are local solutions to the optimization problem. This new result holds true even for a discontinuous objective function, under a mild assumption that we discuss in details. We also provide a practical construction scheme for the covering step that works at low additional cost per iteration. Finally, we show that the covering step may be adapted to classes of algorithms differing from the DSM. © 2024, CC BY.

关键词： optimization algorithms

Tighter Analysis for Decentralized Stochastic Gradient Method: Impact of Data Homogeneity

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Li, Qiang Wai, Hoi-To Dept. of System Engineering & Engineering Management Faculty of Engineering The Chinese University of Hong Kong Shatin District Hong Kong

This paper studies the effect of data homogeneity on multi-agent stochastic optimization. We consider the decentralized stochastic gradient (DSGD) algorithm and perform a refined convergence analysis. Our analysis is explicit on the similarity between Hessian matrices of local objective functions which captures the degree of data homogeneity. We illustrate the impact of our analysis through studying the transient time, defined as the minimum number of iterations required for a distributed algorithm to achieve comparable performance as its centralized counterpart. When the local objective functions have similar Hessian, the transient time of DSGD can be as small as O(n2/3/ρ8/3) for smooth (possibly non-convex) objective functions, O(√n/ρ) for strongly convex objective functions, where n is the number of agents and ρ is the spectral gap of graph. These findings provide a theoretical justification for the empirical success of DSGD. Our analysis relies on a novel observation with higher-order Taylor approximation for gradient maps that can be of independent interest. Numerical simulations validate our findings. © 2024, CC BY.

关键词： optimization algorithms

LINEAR BANDITS ON ELLIPSOIDS: MINIMAX OPTIMAL algorithms

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Zhang, Raymond Hadiji, Hédi Combes, Richard Laboratoire des Signaux et Systèmes Univ. Paris-Saclay CNRS CentraleSupélec France

We consider linear stochastic bandits where the set of actions is an ellipsoid. We provide the first known minimax optimal algorithm for this problem. We first derive a novel information-theoretic lower bound on the regret of any algorithm, which must be at least Ω(min(dσ√T + dθA, θAT)) where d is the dimension, T the time horizon, σ2 the noise variance, A a matrix defining the set of actions and θ the vector of unknown parameters. We then provide an algorithm whose regret matches this bound to a multiplicative universal constant. The algorithm is non-classical in the sense that it is not optimistic, and it is not a sampling algorithm. The main idea is to combine a novel sequential procedure to estimate θ, followed by an explore-and-commit strategy informed by this estimate. The algorithm is highly computationally efficient, and a run requires only time O(dT + d2 log(T/d) + d3) and memory O(d2), in contrast with known optimistic algorithms, which are not implementable in polynomial time. We go beyond minimax optimality and show that our algorithm is locally asymptotically minimax optimal, a much stronger notion of optimality. We further provide numerical experiments to illustrate our theoretical findings. © 2025, CC BY.

关键词： optimization algorithms

Mechanical Properties Estimation Of Ultra Great Workability Concrete By Developing Hybrid algorithms

学校读者我要写书评

暂无评论

淡江理工学刊 2023年第9期26卷 1303-1318页

作者： Lijun Wang Pengcheng Yang

The compressive strength of ultra great workability concrete (UGWC) is a function of the kind, characteristics and quantities of its material components. Empirically gaining this relation sometimes needs the usage of intelligent algorithms to receive a simulative model that fits into experimental data records. In this study, the usefulness of developing hybridized regression analysis on UGWC was analyzed with the aim of reducing the consumed time and experimental efforts. To this aim, a dataset including 170 samples collected from published papers different hybridized support vector regression (SVR) analyses were produced, where the optimal values of determinant attributes of SVR were explored by metaheuristic optimization algorithms named particle swarm optimization (PSO), Cuckoo optimization algorithm (COA), and Bat algorithm (BAT). The performance evaluators demonstrate that all three hybridized SVR models have remarkable potential in compressive strength estimation of UGWC. The first rank belonged to the SVR-COA model, where it could gain the highest value of R^2 and variance account factor (VAF) in both training (R^2=0.9056 and VAF=90.17%) and validating section (R^2=0.9208 and VAF=91.81%), and the lowest value of root mean square error, and mean absolute error in both training and validating sections. Therefore, the hybridized SVR-COA model could receive the proper accuracy in comparison with other models as well as literature.

关键词： Ultra great workability concrete Compressive strength Prediction SVR analysis optimization algorithms