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

Stochastic optimization and sparse statistical recovery: Optimal algorithms for high dimensions 12

学校读者我要写书评

暂无评论

Stochastic optimization and sparse statistical recovery: Opt...

Annual Conference on Neural Information Processing Systems

作者： Alekh Agarwal Sahand N. Negahban Martin J. Wainwright Microsoft Research New York NY Dept. of EECS MIT Dept. of EECS and Statistics UC Berkeley

ISBN: (纸本)9781627480031

We develop and analyze stochastic optimization algorithms for problems in which the expected loss is strongly convex, and the optimum is (approximately) sparse. Previous approaches are able to exploit only one of these two structures, yielding a O(d/T) convergence rate for strongly convex objectives in d dimensions and O(s(log d)/T)~(1/2) convergence rate when the optimum is s-sparse. Our algorithm is based on successively solving a series of ?_1 -regularized optimization problems using Nesterov's dual averaging algorithm. We establish that the error of our solution after T iterations is at most O(s(log d)/T), with natural extensions to approximate sparsity. Our results apply to locally Lipschitz losses including the logistic, exponential, hinge and least-squares losses. By recourse to statistical minimax results, we show that our convergence rates are optimal up to constants. The effectiveness of our approach is also confirmed in numerical simulations where we compare to several baselines on a least-squares regression problem.

关键词： optimization algorithms Optimum BASELINE dimensions Stochastic Converge Convexity algorithms

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

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

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

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