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

DADA: Dual Averaging with Distance Adaptation

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Moshtaghifar, Mohammad Rodomanov, Anton Vankov, Daniil Stich, Sebastian U. Sharif University of Technology Iran CISPA Helmholtz Center for Information Security Germany Arizona State University United States

We present a novel universal gradient method for solving convex optimization problems. Our algorithm—Dual Averaging with Distance Adaptation (DADA)—is based on the classical scheme of dual averaging and dynamically adjusts its coefficients based on observed gradients and the distance between iterates and the starting point, eliminating the need for problem-specific parameters. DADA is a universal algorithm that simultaneously works for a broad spectrum of problem classes, provided the local growth of the objective function around its minimizer can be bounded. Particular examples of such problem classes are nonsmooth Lipschitz functions, Lipschitz-smooth functions, Hölder-smooth functions, functions with high-order Lipschitz derivative, quasi-self-concordant functions, and (L0, L1)-smooth functions. Crucially, DADA is applicable to both unconstrained and constrained problems, even when the domain is unbounded, without requiring prior knowledge of the number of iterations or desired accuracy. Copyright © 2025, The Authors. All rights reserved.

关键词： optimization algorithms

PROVABLY EFFICIENT MULTI-OBJECTIVE BANDIT algorithms UNDER PREFERENCE-CENTRIC CUSTOMIZATION

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Cao, Linfeng Shi, Ming Shroff, Ness B. Department of CSE The Ohio State University United States Department of Electrical Engineering University at Buffalo United States Department of ECE The Ohio State University United States

Multi-objective multi-armed bandit (MO-MAB) problems traditionally aim to achieve Pareto optimality. However, real-world scenarios often involve users with varying preferences across objectives, resulting in a Pareto-optimal arm that may score high for one user but perform quite poorly for another. This highlights the need for customized learning, a factor often overlooked in prior research. To address this, we study a preference-aware MO-MAB framework in the presence of explicit user preference. It shifts the focus from achieving Pareto optimality to further optimizing within the Pareto front under preference-centric customization. To our knowledge, this is the first theoretical study of customized MO-MAB optimization with explicit user preferences. Motivated by practical applications, we explore two scenarios: unknown preference and hidden preference, each presenting unique challenges for algorithm design and analysis. At the core of our algorithms are preference estimation and preference-aware optimization mechanisms to adapt to user preferences effectively. We further develop novel analytical techniques to establish near-optimal regret of the proposed algorithms. Strong empirical performance confirm the effectiveness of our approach. © 2025, CC BY.

关键词： optimization algorithms

Algorithmic approaches to avoiding bad local minima in nonconvex inconsistent feasibility

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Dinh, Thi Lan Bennecke, Wiebke Jansen, G.S. Matthijs Luke, D. Russell Mathias, Stefan Institut für Numerische und Angewandte Mathematik Georg-August-Universität Göttingen Göttingen Germany I. Physikalisches Institut Georg-August-Universität Göttingen Göttingen Germany

The main challenge of nonconvex optimization is to find a global optimum, or at least to avoid "bad" local minima and meaningless stationary points. We study here the extent to which algorithms, as opposed to optimization models and regularization, can be tuned to accomplish this goal. The model we consider is a nonconvex, inconsistent feasibility problem with many local minima, where these are points at which the gaps between the sets are smallest on neighborhoods of these points. The algorithms that we compare are all projection-based algorithms, specifically cyclic projections, the cyclic relaxed Douglas-Rachford algorithm, and relaxed Douglas-Rachford splitting on the product space. The local convergence and fixed points of these algorithms have already been characterized in pervious theoretical studies. We demonstrate the theory for these algorithms in the context of orbital tomographic imaging from angle-resolved photon emission spectroscopy (ARPES) measurements, both synthetically generated and experimental. Our results show that, while the cyclic projections and cyclic relaxed Douglas-Rachford algorithms generally converge the fastest, the method of relaxed Douglas-Rachford splitting on the product space does move away from bad local minima of the other two algorithms, settling eventually on clusters of local minima corresponding to globally optimal critical *** Codes 65K10, 65K05, 90C26, 49M27, 49J53, 49K40, 49M05 © 2025, CC BY.

关键词： optimization algorithms

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

Riemannian Multiplicative Update for Sparse Simplex constraint using oblique rotation manifold

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Esposito, Flavia Ang, Andersen Department of Mathematics University of Bari Aldo Moro Italy School of Electronics and Computer Science University of Southampton United Kingdom

We propose a new manifold optimization method to solve low-rank problems with sparse simplex constraints (variables are simultaneous nonnegativity, sparsity, and sum-to-1) that are beneficial in applications. The proposed approach exploits oblique rotation manifolds, rewrite the problem, and introduce a new Riemannian optimization method. Experiments on synthetic datasets compared to the standard Euclidean method show the effectiveness of the proposed method. © 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

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

HIERARCHICAL MINIMUM VARIANCE PORTFOLIOS: A THEORETICAL AND ALGORITHMIC APPROACH

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Mograby, Gamal Department of Mathematical Sciences University of Cincinnati United States

We introduce a novel approach to portfolio optimization that leverages hierarchical graph structures and the Schur complement method to systematically reduce computational complexity while preserving full covariance information. Inspired by López de Prado’s hierarchical risk parity and Cotton’s Schur complement methods, our framework models the covariance matrix as an adjacency-like structure of a hierarchical graph. We demonstrate that portfolio optimization can be recursively reduced across hierarchical levels, allowing optimal weights to be computed efficiently by inverting only small submatrices regardless of portfolio size. Moreover, we translate our results into a recursive algorithm that constructs optimal portfolio allocations. Our results reveal a transparent and mathematically rigorous connection between classical Markowitz mean-variance optimization, hierarchical clustering, and the Schur complement *** Codes ***, ***, *** © 2025, CC BY-NC-ND.

关键词： optimization algorithms