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

A Performance Bound for the Greedy Algorithm in a Generalized Class of String optimization Problems

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Van Over, Brandon Li, Bowen Chong, Edwin K.P. Pezeshki, Ali The Department of Electrical and Computer Engineering Colorado State University Fort CollinsCO80523 United States

We present a simple performance bound for the greedy scheme in string optimization problems that obtains strong results. Our approach vastly generalizes the group of previously established greedy curvature bounds by Conforti and Cornuéjols (1984). We consider three constants, αG, αG′ , and αG′′ introduced by Conforti and Cornuéjols (1984), that are used in performance bounds of greedy schemes in submodular set optimization. We first generalize both of the αG and αG′′ bounds to string optimization problems in a manner that includes maximizing submodular set functions over matroids as a special case. We then derive a much simpler and computable bound that allows for applications to a far more general class of functions with string domains. We prove that our bound is superior to both the αG and αG′′ bounds and provide a counterexample to show that the αG′ bound is incorrect under the assumptions in Conforti and Cornuéjols (1984). We conclude with two applications. The first is an application of our result to sensor coverage problems. We demonstrate our performance bound in cases where the objective function is set submodular and string submodular. The second is an application to a social welfare maximization problem with black-box utility functions. © 2024, CC BY.

关键词： optimization algorithms

HIGHER DEGREE INEXACT MODEL FOR optimization PROBLEMS

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Alkousa, Mohammad S. Stonyakin, Fedor S. Gasnikov, Alexander V. Abdo, Asmaa M. Alcheikh, Mohammad M. Moscow Institute of Physics and Technology Russia Moscow Institute of Physics and Technology V. I. Vernadsky Crimean Federal University Russia Moscow Institute of Physics and Technology Innopolis University Caucasus Mathematical Center of Adygh State University Russia Mathematics Department Faculty of Science Damascus University Damascus Syria

In this paper, it was proposed a new concept of the inexact higher degree (δ, L, q)-model of a function that is a generalization of the inexact (δ, L)-model [24], (δ, L)-oracle [14] and (δ, L)-oracle of degree q ∈ [0, 2) [29]. Some examples were provided to illustrate the proposed new model. Adaptive inexact gradient and fast gradient methods for convex and strongly convex functions were constructed and analyzed using the new proposed inexact model. A universal fast gradient method that allows solving optimization problems with a weaker level of smoothness, among them non-smooth problems was proposed. For convex optimization problems it was proved that the proposed gradient and fast gradient methods could be converged with rates (formula presented) and (formula presented) , respectively. For the gradient method, the coefficient of δ diminishes with k, and for the fast gradient method, there is no error accumulation for q ≥ 2/3. It proposed a definition of an inexact higher degree oracle for strongly convex functions and a projected gradient method using this inexact oracle. For variational inequalities and saddle point problems, a higher degree inexact model and an adaptive method called Generalized Mirror Prox to solve such class of problems using the proposed inexact model were proposed. Some numerical experiments were conducted to demonstrate the effectiveness of the proposed inexact model, we tested the universal fast gradient method to solve some non-smooth problems with a geometrical nature. © 2024, CC BY.

关键词： optimization algorithms

A Stochastic Quasi-Newton Method for Non-convex optimization with Non-uniform Smoothness

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Sun, Zhenyu Wei, Ermin ECE Northwestern University United States IEMS Northwestern University United States

Classical convergence analyses for optimization algorithms rely on the widely-adopted uniform smoothness assumption. However, recent experimental studies have demonstrated that many machine learning problems exhibit non-uniform smoothness, meaning the smoothness factor is a function of the model parameter instead of a universal constant. In particular, it has been observed that the smoothness grows with respect to the gradient norm along the training trajectory. Motivated by this phenomenon, the recently introduced (L0, L1)-smoothness is a more general notion, compared to traditional L-smoothness, that captures such positive relationship between smoothness and gradient norm. Under this type of non-uniform smoothness, existing literature has designed stochastic first-order algorithms by utilizing gradient clipping techniques to obtain the optimal O(ϵ−3) sample complexity for finding an ϵ-approximate first-order stationary solution. Nevertheless, the studies of quasi-Newton methods are still lacking. Considering higher accuracy and more robustness for quasi-Newton methods, in this paper we propose a fast stochastic quasi-Newton method when there exists non-uniformity in smoothness. Leveraging gradient clipping and variance reduction, our algorithm can achieve the best-known O(ϵ−3) sample complexity and enjoys convergence speedup with simple hyperparameter tuning. Our numerical experiments show that our proposed algorithm outperforms the state-of-the-art approaches. Copyright © 2024, The Authors. All rights reserved.

关键词： optimization algorithms

q-EXPONENTIAL FAMILY FOR POLICY optimization

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Zhu, Lingwei Shah, Haseeb Wang, Han Nagai, Yukie White, Martha University of Tokyo Japan University of Alberta Canada

Policy optimization methods benefit from a simple and tractable policy parametrization, usually the Gaussian for continuous action spaces. In this paper, we consider a broader policy family that remains tractable: the q-exponential family. This family of policies is flexible, allowing the specification of both heavy-tailed policies (q > 1) and light-tailed policies (q © 2024, CC BY.

关键词： optimization algorithms

A Primal-Dual-Assisted Penalty Approach to Bilevel optimization with Coupled Constraints

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Jiang, Liuyuan Xiao, Quan Tenorio, Victor M. Real-Rojas, Fernando Marques, Antonio G. Chen, Tianyi Rensselaer Polytechnic Institute TroyNY United States King Juan Carlos University Madrid Spain

Interest in bilevel optimization has grown in recent years, partially due to its applications to tackle challenging machine-learning problems. Several exciting recent works have been centered around developing efficient gradient-based algorithms that can solve bilevel optimization problems with provable guarantees. However, the existing literature mainly focuses on bilevel problems either without constraints, or featuring only simple constraints that do not couple variables across the upper and lower-levels, excluding a range of complex applications. Our paper studies this challenging but less explored scenario and develops a (fully) first-order algorithm, which we term BLOCC, to tackle BiLevel optimization problems with Coupled Constraints. We establish rigorous convergence theory for the proposed algorithm and demonstrate its effectiveness on two well-known real-world applications - hyperparameter selection in support vector machine (SVM) and infrastructure planning in transportation networks using the real data from the city of Seville. © 2024, CC BY.

关键词： optimization algorithms

From Exponential to Finite/Fixed-Time Stability: Applications to optimization

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Ozaslan, Ibrahim K. Jovanović, Mihailo R. The Ming Hsieh Department of Electrical and Computer Engineering University of Southern California Los AngelesCA90089 United States

The development of finite/fixed-time stable optimization algorithms typically involves study of specific problem instances. The lack of a unified framework hinders understanding of more sophisticated algorithms, e.g., primal-dual gradient flow dynamics. The purpose of this paper is to address the following question: Given an exponentially stable optimization algorithm, can it be modified to obtain a finite/fixed-time stable algorithm? We provide an affirmative answer, demonstrate how the solution can be computed on a finite-time interval via a simple scaling of the right-hand-side of the original dynamics, and certify the desired properties of the modified algorithm using the Lyapunov function that proves exponential stability of the original system. Finally, we examine nonsmooth composite optimization problems and smooth problems with linear constraints to demonstrate the merits of our approach. © 2024, CC BY.

关键词： optimization algorithms

COMPUTING OPTIMAL REGULARIZERS FOR ONLINE LINEAR optimization

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Gatmiry, Khashayar Schneider, Jon Jegelka, Stefanie MIT United States Google Research United States

Follow-the-Regularized-Leader (FTRL) algorithms are a popular class of learning algorithms for online linear optimization (OLO) that guarantee sub-linear regret, but the choice of regularizer can significantly impact dimension-dependent factors in the regret bound. We present an algorithm that takes as input convex and symmetric action sets and loss sets for a specific OLO instance, and outputs a regularizer such that running FTRL with this regularizer guarantees regret within a universal constant factor of the best possible regret bound. In particular, for any choice of (convex, symmetric) action set and loss set we prove that there exists an instantiation of FTRL which achieves regret within a constant factor of the best possible learning algorithm, strengthening the universality result of Srebro et al., 2011. Our algorithm requires preprocessing time and space exponential in the dimension d of the OLO instance, but can be run efficiently online assuming a membership and linear optimization oracle for the action and loss sets, respectively (and is fully polynomial time for the case of constant dimension d). We complement this with a lower bound showing that even deciding whether a given regularizer is α-strongly-convex with respect to a given norm is NP-hard. Copyright © 2024, The Authors. All rights reserved.

关键词： optimization algorithms

Higher-Order Stochastic Dominance Constraints in optimization

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Lakshmanan, Rajmadan Pichler, Alois Kopa, Miloš Faculty of Mathematics University of Technology Chemnitz Germany Charles University Prague Czech Republic

This contribution examines optimization problems that involve stochastic dominance constraints. These problems have uncountably many constraints. We develop methods to solve the optimization problem by reducing the constraints to a finite set of test points needed to verify stochastic dominance. This improves both theoretical understanding and computational efficiency. Our approach introduces two formulations of stochastic dominance—one employs expectation operators and another based on risk measures—allowing for efficient verification processes. Additionally, we develop an optimization framework incorporating these stochastic dominance constraints. Numerical results validate the robustness of our method, showcasing its effectiveness for solving higher-order stochastic dominance problems, with applications to fields such as portfolio *** Codes 90C15, 91B06, 60E15 © 2025, CC BY.

关键词： optimization algorithms

An Improved Chicken Swarm optimization Algorithm for Handwritten Document Image Enhancement

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Stanley, Mugisha Gutu, Janet Lynn Tar Nagabhushan, P. Department Of Studies Computer Science Mysore University India

Chicken swarm optimization is a new meta-heuristic algorithm which mimics the foraging hierarchical behavior of chicken. In this paper, we describe the preprocessing of handwritten document by contrast enhancement while preserving detail with an improved chicken swarm optimization algorithm. The results of the algorithm are compared with other existing meta-heuristic algorithms like Cuckoo Search(CS), Firefly Algorithm(FA) and Artificial Bee Colony(ABC). The proposed algorithm considerably outperforms all the above by giving good results. © 2024, CC0.

关键词： optimization algorithms