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

Adam with model exponential moving average is effective for nonconvex optimization

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Ahn, Kwangjun Cutkosky, Ashok Microsoft Research CambridgeMA United States Boston University BostonMA United States

In this work, we offer a theoretical analysis of two modern optimization techniques for training large and complex models: (i) adaptive optimization algorithms, such as Adam, and (ii) the model exponential moving average (EMA). Specifically, we demonstrate that a clipped version of Adam with model EMA achieves the optimal convergence rates in various nonconvex optimization settings, both smooth and nonsmooth. Moreover, when the scale varies significantly across different coordinates, we demonstrate that the coordinate-wise adaptivity of Adam is provably advantageous. Notably, unlike previous analyses of Adam, our analysis crucially relies on its core elements-momentum and discounting factors-as well as model EMA, motivating their wide applications in practice. © 2024, CC BY.

关键词： optimization algorithms

Out-of-distribution Robust optimization

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Cai, Zhongze Jiang, Hansheng Li, Xiaocheng Imperial College Business School Imperial College London United Kingdom Rotman School of Management University of Toronto Canada

In this paper, we consider the contextual robust optimization problem under an out-of-distribution setting. The contextual robust optimization problem considers a risk-sensitive objective function for an optimization problem with the presence of a context vector (also known as covariates or side information) capturing related information. While the existing works mainly consider the in-distribution setting, and the resultant robustness achieved is in an out-of-sample sense, our paper studies an out-of-distribution setting where there can be a difference between the test environment and the training environment where the data are collected. We propose methods that handle this out-of-distribution setting, and the key relies on a density ratio estimation for the distribution shift. We show that additional structures such as covariate shift and label shift are not only helpful in defending distribution shift but also necessary in avoiding non-trivial solutions compared to other principled methods such as distributionally robust optimization. We also illustrate how the covariates can be useful in this procedure. Numerical experiments generate more intuitions and demonstrate that the proposed methods can help avoid over-conservative solutions. © 2024, CC BY.

关键词： optimization algorithms

Online Convex optimization with a Separation Oracle

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Mhammedi, Zakaria

In this paper, we introduce a new projection-free algorithm for Online Convex optimization (OCO) with a state-of-the-art regret guarantee among separation-based algorithms. Existing projection-free methods based on the classical Frank-Wolfe algorithm achieve a suboptimal regret bound of O(T3/4), while more recent separation-based approaches guarantee a regret bound of O(κ√T), where κ denotes the asphericity of the feasible set, defined as the ratio of the radii of the containing and contained balls. However, for ill-conditioned sets, κ can be arbitrarily large, potentially leading to poor performance. Our algorithm achieves a regret bound of Õ(√dT + κd), while requiring only Õ(1) calls to a separation oracle per round. Crucially, the main term in the bound, Õ(√dT), is independent of κ, addressing the limitations of previous methods. Additionally, as a by-product of our analysis, we recover the O(κ√T) regret bound of existing OCO algorithms with a more straightforward analysis and improve the regret bound for projection-free online exp-concave optimization. Finally, for constrained stochastic convex optimization, we achieve a state-of-the-art convergence rate of Õ(σ/√T + κd/T), where σ represents the noise in the stochastic gradients, while requiring only Õ(1) calls to a separation oracle per iteration. © 2024, CC BY-NC-SA.

关键词： optimization algorithms

Stability of Primal-Dual Gradient Flow Dynamics for Multi-Block Convex optimization Problems

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Ozaslan, Ibrahim K. Patrinos, Panagiotis Jovanović, Mihailo R. Ming Hsieh Department of Electrical Engineering University of Southern California Los AngelesCA90089 United States KU Leuven Leuven3001 Belgium

We examine stability properties of primal-dual gradient flow dynamics for composite convex optimization problems with multiple, possibly nonsmooth, terms in the objective function under the generalized consensus constraint. The proposed dynamics are based on the proximal augmented Lagrangian and they provide a viable alternative to ADMM which faces significant challenges from both analysis and implementation viewpoints in large-scale multi-block scenarios. In contrast to customized algorithms with individualized convergence guarantees, we provide a systematic approach for solving a broad class of challenging composite optimization problems. We leverage various structural properties to establish global (exponential) convergence guarantees for the proposed dynamics. Our assumptions are much weaker than those required to prove (exponential) stability of various primal-dual dynamics as well as (linear) convergence of discrete-time methods, e.g., standard two-block and multi-block ADMM and EXTRA algorithms. Finally, we show necessity of some of our structural assumptions for exponential stability and provide computational experiments to demonstrate the convenience of the proposed dynamics for parallel and distributed computing applications. © 2024, CC BY.

关键词： optimization algorithms

A relative-error inexact ADMM splitting algorithm for convex optimization with inertial effects

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Alves, M. Marques Geremia, Marina Departamento de Matemática Universidade Federal de Santa Catarina Florianópolis88040-900 Brazil

We propose a new relative-error inexact version of the alternating direction method of multipliers (ADMM) for convex optimization. We prove the asymptotic convergence of our main algorithm as well as pointwise and ergodic iteration-complexities for residuals. We also justify the effectiveness of the proposed algorithm through some preliminary numerical experiments on regression problems. Copyright © 2024, The Authors. All rights reserved.

关键词： optimization algorithms

Some easy optimization problems have the overlap-gap property

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Li, Shuangping Schramm, Tselil Stanford University United States

We show that the shortest s-t path problem has the overlap-gap property in (i) sparse G(n, p) graphs and (ii) complete graphs with i.i.d. Exponential edge weights. Furthermore, we demonstrate that in sparse G(n, p) graphs, shortest path is solved by O(log n)-degree polynomial estimators, and a uniform approximate shortest path can be sampled in polynomial time. This constitutes the first example in which the overlap-gap property is not predictive of algorithmic intractability for a (non-algebraic) average-case optimization problem. Copyright © 2024, The Authors. All rights reserved.

关键词： optimization algorithms

A hybrid equilibrium optimizer with differential evolution algorithm

学校读者我要写书评

暂无评论

A hybrid equilibrium optimizer with differential evolution a...

2023 International Conference on Computer, Internet of Things and Smart City, CIOTSC 2023

作者： Duan, Meijun Zhang, Chao Li, Bo Xihua University School of Computer and Software Engineering Chengdu China Sichuan Police College Intelligent Policing Key Laboratory of Sichuan Province Luzhou China

ISBN: (纸本)9798350306569

For the population diversity decreasing rapidly in differential evolution (DE), a novel hybrid algorithm based on Equilibrium Optimizer (EO) and DE (HEODE) is presented. Firstly, a sharing learning mutation strategy is introduced in DE based on the sharing individual. By learning from the sharing individual, information exchange among the whole population can be achieved. Secondly, an effective hybridization mechanism is proposed to combine the advantages of two algorithms. A serial of experiments are used for effectiveness verification among 12 DEs and 5 none-DE based algorithms. The test results validate that HEODE outperforms all competitors. © 2023 IEEE.

关键词： optimization algorithms

Explicit and Implicit Graduated optimization in Deep Neural Networks

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Sato, Naoki Iiduka, Hideaki Meiji University Japan

Graduated optimization is a global optimization technique that is used to minimize a multimodal nonconvex function by smoothing the objective function with noise and gradually refining the solution. This paper experimentally evaluates the performance of the explicit graduated optimization algorithm with an optimal noise scheduling derived from a previous study and discusses its limitations. It uses traditional benchmark functions and empirical loss functions for modern neural network architectures for evaluating. In addition, this paper extends the implicit graduated optimization algorithm, which is based on the fact that stochastic noise in the optimization process of SGD implicitly smooths the objective function, to SGD with momentum, analyzes its convergence, and demonstrates its effectiveness through experiments on image classification tasks with ResNet architectures. © 2024, CC BY.

关键词： optimization algorithms

Differentially Private optimization with Sparse Gradients

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Ghazi, Badih Guzmán, Cristóbal Kamath, Pritish Kumar, Ravi Manurangsi, Pasin Google Research United States Institute for Mathematical and Computational Engineering Faculty of Mathematics School of Engineering Pontificia Universidad Católica de Chile Chile

Motivated by applications of large embedding models, we study differentially private (DP) optimization problems under sparsity of individual gradients. We start with new near-optimal bounds for the classic mean estimation problem but with sparse data, improving upon existing algorithms particularly for the high-dimensional regime. The corresponding lower bounds are based on a novel block-diagonal construction used in combination with existing DP mean estimation lower bounds. Next, we obtain pure- and approximate-DP algorithms with almost optimal rates for stochastic convex optimization with sparse gradients;the former represents the first nearly dimension-independent rates for this problem. Furthermore, by introducing novel analyses of bias-reduction in mean estimation and randomly-stopped biased SGD we obtain nearly dimension independent rates for near stationary points for the empirical risk in nonconvex settings under approximate-DP. © 2024, CC BY.

关键词： optimization algorithms