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

Acceleration Exists! optimization Problems When Oracle Can Only Compare Objective Function Values

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Lobanov, Aleksandr Gasnikov, Alexander Krasnov, Andrei MIPT Skoltech ISP RAS Russia Innopolis MIPT MI RAS Russia MIPT Innopolis Russia

Frequently, the burgeoning field of black-box optimization encounters challenges due to a limited understanding of the mechanisms of the objective function. To address such problems, in this work we focus on the deterministic concept of Order Oracle, which only utilizes order access between function values (possibly with some bounded noise), but without assuming access to their values. As theoretical results, we propose a new approach to create non-accelerated optimization algorithms (obtained by integrating Order Oracle into existing optimization "tools") in non-convex, convex, and strongly convex settings that are as good as both SOTA coordinate algorithms with first-order oracle and SOTA algorithms with Order Oracle up to logarithm factor. Moreover, using the proposed approach, we provide the first accelerated optimization algorithm using the Order Oracle. And also, using an already different approach we provide the asymptotic convergence of the first algorithm with the stochastic Order Oracle concept. Finally, our theoretical results demonstrate effectiveness of proposed algorithms through numerical experiments. Copyright © 2024, The Authors. All rights reserved.

关键词： optimization algorithms

A Smooth Gradient Approximation Neural Network for General Constrained Nonsmooth Nonconvex optimization Problems

学校读者我要写书评

暂无评论

SSRN

SSRN 2024年

作者： Liu, Na Jia, Wenwen Qin, Sitian School of Mathematical Sciences Tianjin Normal University Tianjin China Institute of Mathematics and Interdisciplinary Sciences Tianjin Normal University Tianjin China Department of Mathematics Southeast University Nanjing China Department of Mathematics Harbin Institute of Technology Weihai China

Many optimization problems in engineering practice are nonsmooth nonconvex in nature. The nonsmoothness and nonconvexity of objective and constraint functions brings great challenges to the design and convergence analysis of optimization algorithms. This paper designs a smooth gradient approximation neural network for such optimization problems. Any accumulation point of the neural network's state solution is a stationary point of the nonconvex optimization under consideration. Furthermore, the neural network demonstrates the ability to find optimal solutions for some generalized convex optimization problems. The algorithm herein offers several key advantages over some related algorithms. Firstly, the smoothing approximation technique simplifies the implementation of the presented algorithm. In addition, the results of this paper do not rely on the following conditions that are often required in the relevant literature: 1) the constraint functions are convex and satisfies the Slater's condition;2) the objective function is coercive;3) the objective function is smooth or nonsmooth regular;4) the penalty parameters need to be selected and large enough. Finally, simulation results and an application in optimizing condition number verify the practical applicability of the presented algorithm. © 2024, The Authors. All rights reserved.

关键词： optimization algorithms

optimization Algorithm Design via Electric Circuits

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Boyd, Stephen P. Parshakova, Tetiana Ryu, Ernest K. Suh, Jaewook J. Stanford University United States UCLA United States Rice University United States

We present a novel methodology for convex optimization algorithm design using ideas from electric RLC circuits. Given an optimization problem, the first stage of the methodology is to design an appropriate electric circuit whose continuous-time dynamics converge to the solution of the optimization problem at hand. Then, the second stage is an automated, computer-assisted discretization of the continuous-time dynamics, yielding a provably convergent discrete-time algorithm. Our methodology recovers many classical (distributed) optimization algorithms and enables users to quickly design and explore a wide range of new algorithms with convergence *** Codes 47H05, 90C25, 37M15 Copyright © 2024, The Authors. All rights reserved.

关键词： optimization algorithms

Stochastic optimization over expectation-formulated generalized Stiefel manifold

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Jiang, Linshuo Xiao, Nachuan Liu, Xin State Key Laboratory of Scientific and Engineering Computing Academy of Mathematics and Systems Science Chinese Academy of Sciences University of Chinese Academy of Sciences China The Institute of Operations Research and Analytics National University of Singapore Singapore

In this paper, we consider a class of stochastic optimization problems over the expectation-formulated generalized Stiefel manifold (SOEGS), where the objective function f is continuously differentiable. We propose a novel constraint dissolving penalty function with a customized penalty term (CDFCP), which maintains the same order of differentiability as f. Our theoretical analysis establishes the global equivalence between CDFCP and SOEGS, in the sense that they share the same first-order and second-order stationary points under mild conditions. These results on equivalence enable the direct implementation of various stochastic optimization approaches to solve SOEGS. In particular, we develop a stochastic gradient algorithm and its accelerated variant by incorporating an adaptive step size strategy. Furthermore, we prove their O(Ε−4) sample complexity for finding an Ε-stationary point of CDFCP. Comprehensive numerical experiments show the efficiency and robustness of our proposed algorithms. Copyright © 2024, The Authors. All rights reserved.

关键词： optimization algorithms

COBO: Collaborative Learning via Bilevel optimization

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Hashemi, Diba He, Lie Jaggi, Martin EPFL Switzerland

Collaborative learning is an important tool to train multiple clients more effectively by enabling communication among clients. Identifying helpful clients, however, presents challenging and often introduces significant overhead. In this paper, we model client-selection and model-training as two interconnected optimization problems, proposing a novel bilevel optimization problem for collaborative learning. We introduce COBO, a scalable and elastic, SGD-type alternating optimization algorithm that efficiently addresses these problem with theoretical convergence guarantees. Empirically, COBO achieves superior performance, surpassing popular personalization algorithms by 9.3% in accuracy on a task with high heterogeneity, involving datasets distributed among 80 clients. © 2024, CC BY.

关键词： optimization algorithms

Distributed optimization via Energy Conservation Laws in Dilated Coordinates

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Baranwal, Mayank Chakrabarti, Kushal The Tata Consultancy Services Research Maharashtra Mumbai400607 India The Indian Institute of Technology Maharashtra Bombay400076 India

Optimizing problems in a distributed manner is critical for systems involving multiple agents with private data. Despite substantial interest, a unified method for analyzing the convergence rates of distributed optimization algorithms is lacking. This paper introduces an energy conservation approach for analyzing continuous-time dynamical systems in dilated coordinates. Instead of directly analyzing dynamics in the original coordinate system, we establish a conserved quantity, akin to physical energy, in the dilated coordinate system. Consequently, convergence rates can be explicitly expressed in terms of the inverse time-dilation factor. Leveraging this generalized approach, we formulate a novel second-order distributed accelerated gradient flow with a convergence rate of O(1/t2−Ε) in time t for Ε > 0. We then employ a semi second-order symplectic Euler discretization to derive a rate-matching algorithm with a convergence rate of O(1/k2−Ε) in k iterations. To the best of our knowledge, this represents the most favorable convergence rate for any distributed optimization algorithm designed for smooth convex optimization. Its accelerated convergence behavior is benchmarked against various state-of-the-art distributed optimization algorithms on practical, large-scale problems. © 2024, CC BY.

关键词： optimization algorithms

Regret Minimization in Scalar, Static, Non-linear optimization Problems

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Wang, Ying Pasquini, Mirko Colin, Kévin Hjalmarsson, Håkan The Division of Decision and Control Systems KTH Royal Institute of Technology Stockholm10044 Sweden The Center for Advanced Bio Production AdBIOPRO KTH Royal Institute of Technology Stockholm10044 Sweden

We study the problem of determining an effective exploration strategy in static and non-linear optimization problems, which depend on an unknown scalar parameter to be learned from online collected noisy data. An optimal tradeoff between exploration and exploitation is crucial for effective optimization under uncertainties, and to achieve this we consider a cumulative regret minimization approach over a finite horizon, with each time instant in the horizon characterized by a stochastic exploration signal, whose variance is to be designed. We aim to extend the well-established concepts of regret minimization from linear to non-linear systems, with a focus on the subsequent conceptual differences and challenges. Thus, under an idealized assumption on an appropriately defined information function associated with the excitation, we are able to show that an optimal exploration strategy is either to use no exploration at all (called lazy exploration) or adding an exploration excitation only at the first time instant of the horizon (called immediate exploration). A quadratic numerical example is presented to demonstrate the effectiveness of the proposed strategy. © 2024, CC0.

关键词： optimization algorithms

Analytical-Heuristic Modeling and optimization for Low-Light Image Enhancement

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Martinez, Axel Hernandez, Emilio Olague, Matthieu Olague, Gustavo Ensenada Center for Scientific Research and Higher Education Km 107 Carretera Tijuana-Ensenada Baja California Ensenada22860 Mexico IBM Technology Campus Guadalajara Guadalajara Jalisco El Salto45680 Mexico

Low-light image enhancement remains an open problem, and the new wave of artificial intelligence is at the center of this problem. This work describes the use of genetic algorithms for optimizing analytical models that can improve the visualization of images with poor light. Genetic algorithms are part of metaheuristic approaches, which proved helpful in solving challenging optimization tasks. We propose two analytical methods combined with optimization reasoning to approach a solution to the physical and computational aspects of transforming dark images into visible ones. The experiments demonstrate that the proposed approach ranks at the top among 26 state-of-the-art algorithms in the LOL benchmark. The results show evidence that a simple genetic algorithm combined with analytical reasoning can defeat the current mainstream in a challenging computer vision task through controlled experiments and objective comparisons. This work opens interesting new research avenues for the swarm and evolutionary computation community and others interested in analytical and heuristic reasoning. © 2024, CC BY-NC-ND.

关键词： optimization algorithms

Riemannian conditional gradient methods for composite optimization problems

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Chen, Kangming Fukuda, Ellen H. Graduate School of Informatics Kyoto University Japan

In this paper, we propose Riemannian conditional gradient methods for minimizing composite functions, i.e., those that can be expressed as the sum of a smooth function and a geodesically convex one. We analyze the convergence of the proposed algorithms, utilizing three types of step-size strategies: adaptive, diminishing, and those based on the Armijo condition. We establish the convergence rate of O(1/k) for the adaptive and diminishing step sizes, where k denotes the number of iterations. Additionally, we derive an iteration complexity of O(1/ϵ2) for the Armijo step-size strategy to achieve ϵ-optimality, where ϵ is the optimality tolerance. Finally, the effectiveness of our algorithms is validated through some numerical experiments performed on the sphere and Stiefel manifolds. Copyright © 2024, The Authors. All rights reserved.

关键词： optimization algorithms