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

Alternating optimization Approach for Computing α-Mutual Information and α-Capacity

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Kamatsuka, Akira Kazama, Koki Yoshida, Takahiro Shonan Institute of Technology Japan Nihon University Japan

This study presents alternating optimization (AO) algorithms for computing α-mutual information (α-MI) and αcapacity based on variational characterizations of α-MI using a reverse channel. Specifically, we derive several variational characterizations of Sibson, Arimoto, Augustin–Csiszár, and Lapidoth–Pfister MI and introduce novel AO algorithms for computing αMI and α-capacity;their performances for computing α-capacity are also compared. The comparison results show that the AO algorithm based on the Sibson MI’s characterization has the fastest convergence speed. Copyright © 2024, The Authors. All rights reserved.

关键词： optimization algorithms

On the Hardness of Meaningful Local Guarantees in Nonsmooth Nonconvex optimization

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Kornowski, Guy Padmanabhan, Swati Shamir, Ohad Weizmann Institute of Science Massachusetts Institute of Technology United States

We study the oracle complexity of nonsmooth nonconvex optimization, with the algorithm assumed to have access only to local function information. It has been shown by Davis, Drusvyatskiy, and Jiang (2023) that for nonsmooth Lipschitz functions satisfying certain regularity and strictness conditions, perturbed gradient descent converges to local minimizers asymptotically. Motivated by this result and by other recent algorithmic advances in nonconvex nonsmooth optimization concerning Goldstein stationarity, we consider the question of obtaining a non-asymptotic rate of convergence to local minima for this problem class. We provide the following negative answer to this question: Local algorithms acting on regular Lipschitz functions cannot, in the worst case, provide meaningful local guarantees in terms of function value in sub-exponential time, even when all near-stationary points are global minima. This sharply contrasts with the smooth setting, for which it is well-known that standard gradient methods can do so in a dimension-independent rate. Our result complements the rich body of work in the theoretical computer science literature that provide hardness results conditional on conjectures such as P ≠ NP or cryptographic assumptions, in that ours holds unconditional of any such assumptions. © 2024, CC BY.

关键词： optimization algorithms

Multiple Global Peaks Big Bang-Big Crunch Algorithm for Multimodal optimization

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Stroppa, Fabio Astar, Ahmet Computer Engineering Department Kadir Has University Cibali Kadir Has Cd. Fatih Istanbul34083 Turkey

The main challenge of multimodal optimization problems is identifying multiple peaks with high accuracy in multidimensional search spaces with irregular landscapes. This work proposes the Multiple Global Peaks Big Bang-Big Crunch (MGP-BBBC) algorithm, which addresses the challenge of multimodal optimization problems by introducing a specialized mechanism for each operator. The algorithm expands the Big Bang-Big Crunch algorithm, a state-of-the-art metaheuristic inspired by the universe's evolution. Specifically, MGP-BBBC groups the best individuals of the population into cluster-based centers of mass and then expands them with a progressively lower disturbance to guarantee convergence. During this process, it (i) applies a distance-based filtering to remove unnecessary elites such that the ones on smaller peaks are not lost, (ii) promotes isolated individuals based on their niche count after clustering, and (iii) balances exploration and exploitation during offspring generation to target specific accuracy levels. Experimental results on twenty multimodal benchmark test functions show that MGP-BBBC generally performs better or competitively with respect to other state-of-the-art multimodal optimizers. © 2024, CC BY.

关键词： optimization algorithms

Refining asymptotic complexity bounds for nonconvex optimization methods, including why steepest descent is o(ϵ−2) rather than O(ϵ−2)

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Gratton, Serge Sim, Chee-Khian Toint, Philippe L. Université de Toulouse INP IRIT Toulouse France University of Portsmouth Hampshire United Kingdom NAXYS University of Namur Namur Belgium

MSC Codes 49M37, 65K05, 68Q17, 68W40, 90C30We revisit the standard "telescoping sum" argument ubiquitous in the final steps of analyzing evaluation complexity of algorithms for smooth nonconvex optimization, and obtain a refined formulation of the resulting bound as a function of the requested accuracy ϵ. While bounds obtained using the standard argument typically are of the form O(ϵ−α) for some positive α, the refined results are of the form o(ϵ−α). We then explore to which known algorithms our refined bounds are applicable and finally describe an example showing how close the standard and refined bounds can be. Copyright © 2024, The Authors. All rights reserved.

关键词： optimization algorithms

AN optimization PROBLEM AND POINT-EVALUATION IN PALEY-WIENER SPACES

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Instanes, Sarah May TrondheimNO-7491 Norway

We study the constant Cp defined as the smallest constant C such that |f(0)|p ≤ Ckfkpp holds for every function f in the Paley-Wiener space PWp. Brevig, Chirre, Ortega-Cerdà, and Seip have recently shown that Cp... 详细信息

关键词： optimization algorithms

Dynamic Incremental optimization for Best Subset Selection

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Ren, Shaogang Qian, Xiaoning Department of Computer Science and Engineering University of Tennessee at Chattanooga United States Department of Electrical and Computer Engineering Texas A&M University United States

Best subset selection is considered the ‘gold standard’ for many sparse learning problems. A variety of optimization techniques have been proposed to attack this non-smooth non-convex problem. In this paper, we investigate the dual forms of a family of 0-regularized problems. An efficient primal-dual algorithm is developed based on the primal and dual problem structures. By leveraging the dual range estimation along with the incremental strategy, our algorithm potentially reduces redundant computation and improves the solutions of best subset selection. Theoretical analysis and experiments on synthetic and real-world datasets validate the efficiency and statistical properties of the proposed solutions. © 2024, CC BY-NC-ND.

关键词： optimization algorithms

Fast FISTA Algorithm With New Backtracking Technique For Multiobjective optimization

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Chengzhi, Huang Jian, Chen Liping, Tang National Center for Applied Mathematics in Chongqing Chongqing Normal University Chongqing401331 China

This paper proposes a new backtracking strategy based on the FISTA accelerated algorithm for multiobjective optimization problems. The strategy addresses the limitation of existing algorithms that struggle to handle situations where the Lipschitz constant L(f) of the objective function’s gradient is still being determined. It mitigates the petite iteration step sizes caused by a significant value of L(f). Furthermore, the proposed strategy effectively avoids the limitation in convergence proofs arising from the non-negativity of the auxiliary sequence Wk(z):= mini=1,···,m[Fi(xk) - Fi(z)], thus providing a theoretical guarantee for its performance. We demonstrate that, under relatively mild assumptions, the algorithm achieves the convergence rate of O(1/k2). Copyright © 2024, The Authors. All rights reserved.

关键词： optimization algorithms

DESIGN GUIDELINES FOR NOISE-TOLERANT optimization WITH APPLICATIONS IN ROBUST DESIGN

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Lou, Yuchen Sun, Shigeng Nocedal, Jorge Department of Industrial Engineering and Management Sciences Northwestern University United States Department of Engineering Sciences and Applied Mathematics Northwestern University United States

The development of nonlinear optimization algorithms capable of performing reliably in the presence of noise has garnered considerable attention lately. This paper advocates for strategies to create noise-tolerant nonlinear optimization algorithms by adapting classical deterministic methods. These adaptations follow certain design guidelines described here, which make use of estimates of the noise level in the problem. The application of our methodology is illustrated by the development of a line search gradient projection method, which is tested on an engineering design problem. It is shown that a new self-calibrated line search and noise-aware finite-difference techniques are effective even in the high noise regime. Numerical experiments investigate the resiliency of key algorithmic components. A convergence analysis of the line search gradient projection method establishes convergence to a neighborhood of *** Codes 90C30, 90C15, 93B51, 65K05 © 2024, CC BY.

关键词： optimization algorithms

SPARKLE: A Unified Single-Loop Primal-Dual Framework for Decentralized Bilevel optimization

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Zhu, Shuchen Kong, Boao Lu, Songtao Huang, Xinmeng Yuan, Kun Peking University China IBM Research United States University of Pennsylvania United States National Engineering Labratory for Big Data Analytics and Applications AI for Science Institute Beijing China

This paper studies decentralized bilevel optimization, in which multiple agents collaborate to solve problems involving nested optimization structures with neighborhood communications. Most existing literature primarily utilizes gradient tracking to mitigate the influence of data heterogeneity, without exploring other well-known heterogeneity-correction techniques such as EXTRA or Exact Diffusion. Additionally, these studies often employ identical decentralized strategies for both upper- and lower-level problems, neglecting to leverage distinct mechanisms across different levels. To address these limitations, this paper proposes SPARKLE, a unified Single-loop Primal-dual AlgoRithm frameworK for decentraLized bilEvel optimization. SPARKLE offers the flexibility to incorporate various heterogeneity-correction strategies into the algorithm. Moreover, SPARKLE allows for different strategies to solve upper- and lower-level problems. We present a unified convergence analysis for SPARKLE, applicable to all its variants, with state-of-the-art convergence rates compared to existing decentralized bilevel algorithms. Our results further reveal that EXTRA and Exact Diffusion are more suitable for decentralized bilevel optimization, and using mixed strategies in bilevel algorithms brings more benefits than relying solely on gradient tracking. © 2024, CC BY.

关键词： optimization algorithms