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

An adaptive forward-backward-forward splitting algorithm for solving pseudo-monotone inclusions

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Chorobura, Flavia Necoara, Ion Pesquet, Jean-Christophe Automatic Control and Systems Engineering Department National University of Science and Technology Politehnica Bucharest Bucharest060042 Romania Federal Institute of Education Science and Technology of Paraná campus Foz do Iguaçu Brazil Gheorghe Mihoc-Caius Iacob Institute of Mathematical Statistics and Applied Mathematics The Romanian Academy Bucharest050711 Romania University Paris-Saclay CentraleSupélec CVN Inria Gif-sur-Yvette France

In this paper, we propose an adaptive forward-backward-forward splitting algorithm for finding a zero of a pseudo-monotone operator which is split as a sum of three operators: the first is continuous single-valued, the second is Lipschitzian, and the third is maximally monotone. This setting covers, in particular, constrained minimization scenarios, such as problems having smooth and convex functional constraints (e.g., quadratically constrained quadratic programs) or problems with a pseudo-convex objective function minimized over a simple closed convex set (e.g., quadratic over linear fractional programs). For the general problem, we design a forward-backward-forward splitting type method based on novel adaptive stepsize strategies. Under an additional generalized Lipschitz property of the first operator, sublinear convergence rate is derived for the sequence generated by our adaptive algorithm. Moreover, if the sum is uniformly pseudo-monotone, linear/sublinear rates are derived depending on the parameter of uniform pseudo-monotonicity. Preliminary numerical experiments demonstrate the good performance of our method when compared to some existing optimization methods and software. © 2025, CC BY.

关键词： consensus algorithm

Greedy algorithm for Structured Bandits: A Sharp Characterization of Asymptotic Success / Failure

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Slivkins, Aleksandrs Xu, Yunzong Zuo, Shiliang Microsoft Research New York City United States University of Illinois Urbana-Champaign United States

We study the greedy (exploitation-only) algorithm in bandit problems with a known reward structure. We allow arbitrary finite reward structures, while prior work focused on a few specific ones. We fully characterize when the greedy algorithm asymptotically succeeds or fails, in the sense of sublinear vs. linear regret as a function of time. Our characterization identifies a partial identifiability property of the problem instance as the necessary and sufficient condition for the asymptotic success. Notably, once this property holds, the problem becomes easy—any algorithm will succeed (in the same sense as above), provided it satisfies a mild non-degeneracy condition. We further extend our characterization to contextual bandits and interactive decision-making with arbitrary feedback, and demonstrate its broad applicability across various examples. Copyright © 2025, The Authors. All rights reserved.

关键词： consensus algorithm

THE BEST TWO-TERM UNDERAPPROXIMATION USING NUMBERS FROM FIBONACCI-TYPE SEQUENCES

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Mark, Shiliaev Department of Mathematics Texas A&M University College StationTX77843 United States

This paper studies the greedy two-term underapproximation of θ ∈ (0, 1] using reciprocals of numbers from a Fibonacci-type sequence (Equation presented). We find the set of θ whose greedy two-term underapproximation is the best among all two-term underapproximations using 1/cn's. We then derive a neat description of the set when (Equation presented) is the Fibonacci sequence or the Lucas *** Codes 11A67, 11B99 © 2025, CC BY.

关键词： consensus algorithm

A declarative approach to specifying distributed algorithms using three-valued modal logic

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Gabbay, Murdoch J. Zanolini, Luca Heriot-Watt University Edinburgh United Kingdom Ethereum Foundation London United Kingdom

We present Coalition Logic, a three-valued modal fixed-point logic designed for declaratively specifying and reasoning about distributed algorithms, such as the Paxos consensus algorithm. Our methodology represents a distributed algorithm as a logical theory, enabling correctness properties to be derived directly within the framework—or revealing logical errors in the algorithm’s design when they exist. Coalition Logic adopts a declarative approach, specifying the overall logic of computation without prescribing control flow. Notably, message-passing is not explicitly modeled, distinguishing our framework from approaches like TLA+. This abstraction emphasises the logical essence of distributed algorithms, offering a novel perspective on their specification and reasoning. We define the syntax and semantics of Coalition Logic, explore its theoretical properties, and demonstrate its applicability through a detailed treatment of the Paxos consensus algorithm. By presenting Paxos as a logical theory and deriving its standard correctness properties, we showcase the framework’s capacity to handle non-trivial distributed systems. We envision Coalition Logic as a versatile tool for specifying and reasoning about distributed algorithms. The Paxos example highlights the framework’s ability to capture intricate details, offering a new lens through which distributed algorithms can be specified, studied, and *** Codes 03B45, 03B50, 68Q60 © 2025, CC BY.

关键词： consensus algorithm

Convergence analysis for a variant of manifold proximal point algorithm based on Kurdyka-Lojasiewicz property

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Yu, Peiran Zeng, Liaoyuan Pong, Ting Kei Department of Computer Science The University of Maryland United States School of Mathematical Sciences Zhejiang University of Technology China Department of Applied Mathematics The Hong Kong Polytechnic University Hong Kong

We incorporate an iteratively reweighted strategy in the manifold proximal point algorithm (ManPPA) in [12] to solve an enhanced sparsity inducing model for identifying sparse yet nonzero vectors in a given subspace. We establish the global convergence of the whole sequence generated by our algorithm by assuming the Kurdyka-Ĺojasiewicz (KL) properties of suitable potential functions. We also study how the KL exponents of the different potential functions are related. More importantly, when our enhanced model and algorithm reduce, respectively, to the model and ManPPA with constant stepsize considered in [12], we show that the sequence generated converges linearly as long as the optimal value of the model is positive, and converges finitely when the limit of the sequence lies in a set of weak sharp minima. Our results improve [13, Theorem 2.4], which asserts local quadratic convergence in the presence of weak sharp minima when the constant stepsize is small. Copyright © 2025, The Authors. All rights reserved.

关键词： consensus algorithm

A parallel algorithm for the odd two-face shortest k-disjoint path problem

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Chakraborty, Srijan Datta, Samir Chennai Mathematical Institute India

The shortest Disjoint Path problem (SDPP) requires us to find pairwise vertex disjoint paths between k designated pairs of terminal vertices such that the sum of the path lengths is minimum. The focus here is on SDPP restricted to planar graphs where all terminals are arbitrarily partitioned over two distinct faces with the additional restriction that each face is required to contain an odd number of terminals. We call this problem the Odd two-face planar SDPP. It is shown that this problem is solvable in randomized polynomial time and even in RNC. This is the first parallel (or even polynomial time) solution for the problem. Our algorithm combines ideas from the randomized solution for 2-SDPP by Björklund and Huslfeldt with its parallelization by Datta and Jaiswal along with the deterministic algorithm for One-face planar SDPP by Datta, Iyer, Kulkarni and Mukherjee. The proof uses a combination of two involutions to reduce a system of linear equations modulo a power of 2 to a system of triangular form that is, therefore, invertible. This, in turn, is proved by showing that the matrix of the equations, can be interpreted as (the adjacency matrix of) a directed acyclic graph (DAG). While our algorithm is primarily algebraic the proof remains combinatorial. We also give a parallel algorithm for the (A + B)-SDPP introduced by Hirai and Namba. © 2025, CC BY.

关键词： consensus algorithm

Revisited Convergence of Dolev et al’s BFS Spanning Tree algorithm

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Altisen, Karine Bozga, Marius Univ. Grenoble Alpes CNRS Grenoble INP VERIMAG Grenoble38000 France

We provide a constructive proof for the convergence of Dolev et al’s BFS spanning tree algorithm running under the general assumption of an unfair daemon. Already known proofs of this algorithm are either using non-constructive principles (e.g., proofs by contradiction) or are restricted to less general execution daemons (e.g., weakly fair). In this work, we address these limitations by defining the well-founded orders and potential functions ensuring convergence in the general case. The proof has been fully formalized in PADEC, a Coq-based framework for certification of self-stabilization algorithm. © 2025, CC BY.

关键词： consensus algorithm

Quantifying the Speed-Up from Non-Reversibility in MCMC Tempering algorithms

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Roberts, Gareth O. Rosenthal, Jeffrey S. University of Warwick United Kingdom University of Toronto Canada

We investigate the increase in efficiency of simulated and parallel temperingMCMC algorithms when using non-reversible updates to give them "momentum". Bymaking a connection to a certain simple discrete Markov chain, we show that,under appropriate assumptions, the non-reversible algorithms still exhibitdiffusive behaviour, just on a different time scale. We use this to argue thatthe optimally scaled versions of the non-reversible algorithms are indeed moreefficient than the optimally scaled versions of their traditional reversiblecounterparts, but only by a modest speed-up factor of about 42%. © 2025, CC BY.

关键词： consensus algorithm

A Refined Analysis of UCBVI

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Drago, Simone Mussi, Marco Metelli, Alberto Maria Politecnico di Milano Piazza Leonardo da Vinci 32 Milan20133 Italy

In this work, we provide a refined analysis of the UCBVI algorithm (Azar et al., 2017), improving both the bonus terms and the regret analysis. Additionally, we compare our version of UCBVI with both its original version and the state-of-the-art MVP algorithm. Our empirical validation demonstrates that improving the multiplicative constants in the bounds has significant positive effects on the empirical performance of the algorithms. © 2025, CC BY.

关键词： consensus algorithm