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

Efficient algorithms for Empirical Group Distributionally Robust optimization and Beyond

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Yu, Dingzhi Cai, Yunuo Jiang, Wei Zhang, Lijun National Key Laboratory for Novel Software Technology Nanjing University Nanjing China School of Data Science Fudan University Shanghai China Guangzhou China

In this paper, we investigate the empirical counterpart of Group Distributionally Robust optimization (GDRO), which aims to minimize the maximal empirical risk across m distinct groups. We formulate empirical GDRO as a two-level finite-sum convex-concave minimax optimization problem and develop an algorithm called ALEG to benefit from its special structure. ALEG is a double-looped stochastic primal-dual algorithm that incorporates variance reduction techniques into a modified mirror prox routine. To exploit the two-level finite-sum structure, we propose a simple group sampling strategy to construct the stochastic gradient with a smaller Lipschitz constant and then perform variance reduction for all groups. Theoretical analysis shows that ALEG achieves Ε-accuracy within a computation complexity of O ( m√n¯Εln m ) , where n¯ is the average number of samples among m groups. Notably, our approach outperforms the state-of-the-art method by a factor of √m. Based on ALEG, we further develop a two-stage optimization algorithm called ALEM to deal with the empirical Minimax Excess Risk optimization (MERO) problem. The computation complexity of ALEM nearly matches that of ALEG, surpassing the rates of existing methods. Copyright © 2024, The Authors. All rights reserved.

关键词： optimization algorithms

optimization with First Order algorithms

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Dossal, Charles Hurault, Samuel Papadakis, Nicolas IMT Univ. Toulouse INSA Toulouse Toulouse France ENS Paris - CNRS France Univ. Bordeaux CNRS INRIA Bordeaux INP IMB UMR 5251 TalenceF-33400 France

These notes focus on the minimization of convex functionals using first-order optimization methods, which are fundamental in many areas of applied mathematics and engineering. The primary goal of this document is to introduce and analyze the most classical first-order optimization algorithms. We aim to provide readers with both a practical and theoretical understanding in how and why these algorithms converge to minimizers of convex functions. The main algorithms covered in these notes include gradient descent, Forward-Backward splitting, Douglas-Rachford splitting, the Alternating Direction Method of Multipliers (ADMM), and Primal-Dual algorithms. All these algorithms fall into the class of first order methods, as they only involve gradients and subdifferentials, that are first order derivatives of the functions to optimize. For each method, we provide convergence theorems, with precise assumptions and conditions under which the convergence holds, accompanied by complete proofs. Beyond convex optimization, the final part of this manuscript extends the analysis to nonconvex problems, where we discuss the convergence behavior of these same first-order methods under broader assumptions. To contextualize the theory, we also include a selection of practical examples illustrating how these algorithms are applied in different image processing problems. © 2024, CC BY.

关键词： optimization algorithms

Multicriteria optimization and Decision Making Principles, algorithms and Case Studies

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Emmerich, Michael Deutz, André MSc Course 2012-2023 LIACS Leiden University Netherlands

Real-world decision and optimization problems, often involve constraints and conflicting criteria. For example, choosing a travel method must balance speed, cost, environmental footprint, and convenience. Similarly, designing an industrial process must consider safety, environmental impact, and cost efficiency. Ideal solutions where all objectives are optimally met are rare;instead, we seek good compromises and aim to avoid lose-lose scenarios. Multicriteria optimization offers computational techniques to compute Pareto optimal solutions, aiding decision analysis and decision making. This reader offers an introduction to this topic and is based on the revised edition of the MSc computer science course lecture"Multicriteria optimization and Decision Analysis" at the Leiden Institute of Advanced Computer Science, Leiden University, The Netherlands, conducted from 2007 to 2023. The introduction is organized in a unique didactic manner developed by the authors, starting from more simple concepts such as linear programming and single-point methods, and advancing from these to more difficult concepts such as optimality conditions for nonlinear optimization and set-oriented solution algorithms. In addition, we focus on the mathematical modeling and foundations rather than on specific algorithms, though we do not exclude the discussion of some representative examples of solution algorithms. Our aim was to make the material accessible to MSc students who do not study mathematics as their core discipline by introducing basic numerical analysis concepts when necessary and providing numerical examples for interesting *** Codes 90C29 Copyright © 2024, The Authors. All rights reserved.

关键词： optimization algorithms

Approximation algorithms for Combinatorial optimization with Predictions

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Antoniadis, Antonios Eliáš, Marek Polak, Adam Venzin, Moritz University of Twente Netherlands Bocconi University Italy

We initiate a systematic study of utilizing predictions to improve over approximation guarantees of classic algorithms, without increasing the running time. We propose a systematic method for a wide class of optimization problems that ask to select a feasible subset of input items of minimal (or maximal) total weight. This gives simple (near-)linear time algorithms for, e.g., Vertex Cover, Steiner Tree, Min-Weight Perfect Matching, Knapsack, and Clique. Our algorithms produce optimal solutions when provided with perfect predictions and their approximation ratios smoothly degrade with increasing prediction error. With small enough prediction error we achieve approximation guarantees that are beyond reach without predictions in the given time bounds, as exemplified by the NP-hardness and APX-hardness of many of the above problems. Although we show our approach to be optimal for this class of problems as a whole, there is a potential for exploiting specific structural properties of individual problems to obtain improved bounds;we demonstrate this on the Steiner Tree problem. We conclude with an empirical evaluation of our approach. Copyright © 2024, The Authors. All rights reserved.

关键词： optimization algorithms

Differentially Private algorithms for Linear Queries via Stochastic Convex optimization

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Micali, Giorgio Lezane, Clement Betken, Annika Drienerlolaan 5 Enschede7522 NB Netherlands

This article establishes a method to answer a finite set of linear queries on a given dataset while ensuring differential privacy. To achieve this, we formulate the corresponding task as a saddle-point problem, i.e. an optimization problem whose solution corresponds to a distribution minimizing the difference between answers to the linear queries based on the true distribution and answers from a differentially private distribution. Against this background, we establish two new algorithms for corresponding differentially private data release: the first is based on the differentially private Frank-Wolfe method, the second combines randomized smoothing with stochastic convex optimization techniques for a solution to the saddle-point problem. While previous works assess the accuracy of differentially private algorithms with reference to the empirical data distribution, a key contribution of our work is a more natural evaluation of the proposed algorithms' accuracy with reference to the true data-generating distribution. Copyright © 2024, The Authors. All rights reserved.

关键词： optimization algorithms

Formalization of Complexity Analysis of the Firstorder algorithms for Convex optimization

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Li, Chenyi Wang, Ziyu He, Wanyi Wu, Yuxuan Xu, Shengyang Wen, Zaiwen School of Mathematical Sciences Peking University China Yuanpei College Peking University China Beijing International Center for Mathematical Research Peking University China

The convergence rate of various first-order optimization algorithms is a pivotal concern within the numerical optimization community, as it directly reflects the efficiency of these algorithms across different optimization problems. Our goal is to make a significant step forward in the formal mathematical representation of optimization techniques using the Lean4 theorem prover. We first formalize the gradient for smooth functions and the subgradient for convex functions on a Hilbert space, laying the groundwork for the accurate formalization of algorithmic structures. Then, we extend our contribution by proving several properties of differentiable convex functions that have not yet been formalized in Mathlib. Finally, a comprehensive formalization of these algorithms is presented. These developments are not only noteworthy on their own but also serve as essential precursors to the formalization of a broader spectrum of numerical algorithms and their applications in machine learning as well as many other areas. © 2024, CC BY.

关键词： optimization algorithms

First-order algorithms for robust optimization problems via convex-concave saddle-point Lagrangian reformulation

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Postek, Krzysztof Shtern, Shimrit Faculty of Electrical Enginnering Mathematics and Computer Science Delft University of Technology Delft Netherlands Faculty of Industrial Engineering and Management Technion - Israel Institute of Technology Haifa Israel

Robust optimization (RO) is one of the key paradigms for solving optimization problems affected by uncertainty. Two principal approaches for RO, the robust counterpart method and the adversarial approach, potentially lead to excessively large optimization problems. For that reason, first order approaches, based on online-convex-optimization, have been proposed Ben-Tal et al. (2015b), Ho-Nguyen and Kılınç-Karzan (2018) as alternatives for the case of large-scale problems. However, these methods are either stochastic in nature or involve a binary search for the optimal value. We show that this problem can also be solved with deterministic first-order algorithms based on a saddle-point Lagrangian reformulation that avoid both of these issues. Our approach recovers the other approaches’ O(1/ϵ2) convergence rate in the general case, and offers an improved O(1/ϵ) rate for problems with constraints which are affine both in the decision and in the uncertainty. Experiment involving robust quadratic optimization demonstrates the numerical benefits of our approach. Copyright © 2021, The Authors. All rights reserved.

关键词： optimization algorithms

Two-sided Assortment optimization: Adaptivity Gaps and Approximation algorithms

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Housni, Omar El Torrico, Alfredo Hennebelle, Ulysse Cornell Tech Cornell University United States CDSES Cornell University United States Ecole Polytechnique

Two-sided matching platforms have recently proliferated thanks to their application in labor markets, dating, accommodation and ride-sharing. Due to correlated preferences, these platforms face the challenge of reducing choice congestion among popular options who receive more requests than they can handle, which may lead to suboptimal market outcomes. To address this challenge we introduce a two-sided assortment optimization framework under general choice preferences. The goal in this problem is to maximize the expected number of matches by deciding which assortments are displayed to the agents and the order in which they are shown. In this context, we identify several classes of policies that platforms can use in their design. Our goals are: (1) to measure the value that one class of policies has over another one, and (2) to approximately solve the optimization problem itself for a given class. For (1), we define the adaptivity gap as the worst-case ratio between the optimal values of two different policy classes. First, we show that the gap between the class of policies that statically show assortments to one-side first and the class of policies that adaptively show assortments to one-side first is exactly 1 − 1/e. Second, we show that the gap between the latter class of policies and the fully adaptive class of policies that show assortments to agents one by one is exactly 1/2. We also note that the worst policies are those who simultaneously show assortments to all the agents, in fact, we show that their adaptivity gap even with respect to one-sided static policies can be arbitrarily small. For (2), we first show that there exists a polynomial time policy that achieves a 1/4 approximation factor within the class of policies that adaptively show assortments to agents one by one. Finally, when agents’ preferences are governed by multinomial-logit models, we show that a 0.082 approximation factor can be obtained within the class of policies that show assortments to

关键词： optimization algorithms

A Tutorial on the Design, Experimentation and Application of Metaheuristic algorithms to Real-World optimization Problems

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Osaba, Eneko Villar-Rodriguez, Esther Del Ser, Javier Nebro, Antonio J. Molina, Daniel LaTorre, Antonio Suganthan, Ponnuthurai N. Coello Coello, Carlos A. Herrera, Francisco Derio48160 Spain Bilbao48013 Spain DaSCI Andalusian Institute of Data Science and Computational Intelligence University of Granada Granada18071 Spain Dept. de Lenguajes y Ciencias de la Computación ITIS Software Universidad de Málaga Spain CINVESTAV-IPN DF Mexico07360 Mexico Nanyang Technological University 639798 Singapore Center for Computational Simulation Universidad Politécnica de Madrid Madrid Spain

In the last few years, the formulation of real-world optimization problems and their efficient solution via metaheuristic algorithms has been a catalyst for a myriad of research studies. In spite of decades of historical advancements on the design and use of metaheuristics, large difficulties still remain in regards to the understandability, algorithmic design uprightness, and performance verifiability of new technical achievements. A clear example stems from the scarce replicability of works dealing with metaheuristics used for optimization, which is often infeasible due to ambiguity and lack of detail in the presentation of the methods to be reproduced. Additionally, in many cases, there is a questionable statistical significance of their reported results. This work aims at providing the audience with a proposal of good practices which should be embraced when conducting studies about metaheuristics methods used for optimization in order to provide scientific rigor, value and transparency. To this end, we introduce a step by step methodology covering every research phase that should be followed when addressing this scientific field. Specifically, frequently overlooked yet crucial aspects and useful recommendations will be discussed in regards to the formulation of the problem, solution encoding, implementation of search operators, evaluation metrics, design of experiments, and considerations for real-world performance, among others. Finally, we will outline important considerations, challenges, and research directions for the success of newly developed optimization metaheuristics in their deployment and operation over real-world application environments. © 2024, CC BY-NC-ND.

关键词： optimization algorithms