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

On counterexamples to the Mertens conjecture

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Kim, Seungki Nguyen, Phong Q. Department of Mathematical Sciences University of Cincinnati 4199 French Hall West 2815 Commons Way CincinnatiOH45221-0025 United States Department of Computer Science Ecole Normale Supérieure 45 rue d’Ulm Paris75005 France

We use state-of-art lattice algorithms to improve the upper bound on the lowest counterexample to the Mertens conjecture to ≈ exp(1.96 × 1019), which is significantly below the conjectured value of ≈ exp(5.15 &... 详细信息

关键词： consensus algorithm

Impatient Bandits: Optimizing for the Long-Term Without Delay

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Zhang, Kelly W. Baldwin-McDonald, Thomas Ciosek, Kamil Maystre, Lucas Russo, Daniel Imperial College London United Kingdom University of Manchester United Kingdom Spotify United States UiPath United States Columbia University United States

Increasingly, recommender systems are tasked with improving users’ long-term satisfaction. In this context, we study a content exploration task, which we formalize as a bandit problem with delayed rewards. There is an apparent trade-off in choosing the learning signal: waiting for the full reward to become available might take several weeks, slowing the rate of learning, whereas using short-term proxy rewards reflects the actual long-term goal only imperfectly. First, we develop a predictive model of delayed rewards that incorporates all information obtained to date. Rewards as well as shorter-term surrogate outcomes are combined through a Bayesian filter to obtain a probabilistic belief. Second, we devise a bandit algorithm that quickly learns to identify content aligned with long-term success using this new predictive model. We prove a regret bound for our algorithm that depends on the Value of Progressive Feedback, an information theoretic metric that captures the quality of short-term leading indicators that are observed prior to the long-term reward. We apply our approach to a podcast recommendation problem, where we seek to recommend shows that users engage with repeatedly over two months. We empirically validate that our approach significantly outperforms methods that optimize for short-term proxies or rely solely on delayed rewards, as demonstrated by an A/B test in a recommendation system that serves hundreds of millions of users. Copyright © 2025, The Authors. All rights reserved.

关键词： consensus algorithm

A Stochastic Conjugate Subgradient algorithm for Two-stage Stochastic Programming

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Zhang, Di Sen, Suvrajeet Department of Industrial and System Engineering University of Southern California Los AngelesCA United States

Stochastic Optimization is a cornerstone of operations research, providing a framework to solve optimization problems under uncertainty. Despite the development of numerous algorithms to tackle these problems, several persistent challenges remain, including: (i) selecting an appropriate sample size, (ii) determining an effective search direction, and (iii) choosing a proper step size. This paper introduces a comprehensive framework, the Stochastic Conjugate Subgradient (SCS) framework, designed to systematically address these challenges. Specifically, The SCS framework offers structured approaches to determining the sample size, the search direction, and the step size. By integrating various stochastic algorithms within the SCS framework, we have developed a novel stochastic algorithm for two-stage stochastic programming. The convergence and convergence rates of the algorithm have been rigorously established, with preliminary computational results support the theoretical analysis. Copyright © 2025, The Authors. All rights reserved.

关键词： consensus algorithm

Online Bidding algorithms with Strict Return on Spend (ROS) Constraint

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Vaze, Rahul Sinha, Abhishek School of Technology and Computer Science Tata Institute of Fundamental Research Mumbai400005 India

Auto-bidding problem under a strict return-on-spend constraint (ROSC) is considered, where an algorithm has to make decisions about how much to bid for an ad slot depending on the revealed value, and the hidden allocation and payment function that describes the probability of winning the ad-slot depending on its bid. The objective of an algorithm is to maximize the expected utility (product of ad value and probability of winning the ad slot) summed across all time slots subject to the total expected payment being less than the total expected utility, called the ROSC. A (surprising) impossibility result is derived that shows that no online algorithm can achieve a sub-linear regret even when the value, allocation and payment function are drawn i.i.d. from an unknown distribution. The problem is non-trivial even when the revealed value remains constant across time slots, and an algorithm with regret guarantee that is optimal up to logarithmic factor is derived. © 2025, CC BY-NC-ND.

关键词： consensus algorithm

Genetic algorithm with Border Trades (GAB)

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Lyu, Qingchuan Department of Computer Science Georgia Institute of Technology AtlantaGA United States Visa Inc. Foster CityCA United States

This paper introduces a novel approach to improving Genetic algorithms (GA) in large or complex problem spaces by incorporating new chromosome patterns in the breeding process through border trade activities. These strategies increase chromosome diversity, preventing premature convergence and enhancing the GA’s ability to explore the solution space more effectively. Empirical evidence demonstrates significant improvements in convergence behavior. This approach offers a promising pathway to addressing challenges in optimizing large or complex problem domains. Copyright © 2025, The Authors. All rights reserved.

关键词： consensus algorithm

Convergence Analysis of a Greedy algorithm for Conditioning Gaussian Random Variables

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Winkle, Daniel Steinwart, Ingo Haasdonk, Bernard University of Stuttgart Faculty 8: Mathematics and Physics Stuttgart Germany

In the context of Gaussian conditioning, greedy algorithms iteratively select the most informative measurements, given an observed Gaussian random variable. However, the convergence analysis for conditioning Gaussian random variables remains an open problem. We adress this by introducing an operator M that allows us to transfer convergence rates of the observed Gaussian random variable approximation onto the conditional Gaussian random variable. Furthermore we apply greedy methods from approximation theory to obtain convergence rates. These greedy methods have already demonstrated optimal convergence rates within the setting of kernel based function approximation. In this paper, we establish an upper bound on the convergence rates concerning the norm of the approximation error of the conditional covariance operator. © 2025, CC0.

关键词： consensus algorithm

Revisiting Ranking for Online Bipartite Matching with Random Arrivals: the Primal-Dual Analysis

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Peng, Bo Tang, Zhihao Gavin ITCS Shanghai University of Finance and Economics China

We revisit the celebrated Ranking algorithm by Karp, Vazirani, and Vazirani (STOC 1990) for online bipartite matching under the random arrival model, that is shown to be 0.696-competitive for unweighted graphs by Mahdian and Yan (STOC 2011) and 0.662-competitive for vertex-weighted graphs by Jin and Williamson (WINE 2021). In this work, we explore the limitation of the primal-dual analysis of Ranking and aim to bridge the gap between unweighted and vertex-weighted graphs. We show that the competitive ratio of Ranking is between 0.686 and 0.703, under our current knowledge of Ranking and the framework of primal-dual analysis. This confirms a conjecture by Huang, Tang, Wu, and Zhang (TALG 2019), stating that the primal-dual analysis could lead to a competitive ratio that is very close to 0.696. Our analysis involves proper discretizations of a variational problem and uses LP solver to pin down the numerical number. As a bonus of our discretization approach, our competitive analysis of Ranking applies to a more relaxed random arrival model. E.g., we show that even when each online vertex arrives independently at an early or late stage, the Ranking algorithm is at least 0.665-competitive, beating the 1 − 1/e ≈ 0.632 competitive ratio under the adversarial arrival model. Copyright © 2025, The Authors. All rights reserved.

关键词： consensus algorithm

Multi-objective Pseudo Boolean Functions in Runtime Analysis: A Review

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Liang, Zimin Li, Miqing School of Computer Science University of Birmingham Edgbaston BirminghamB15 2TT United Kingdom

Recently, there has been growing interest within the theoretical community in analytically studying multi-objective evolutionary algorithms. This runtime analysis-focused research can help formally understand algorithm behaviour, explain empirical observations, and provide theoretical insights to support algorithm development and exploration. However, the test problems commonly used in the theoretical analysis are predominantly limited to problems with heavy "artificial" characteristics (e.g., symmetric objectives and linear Pareto fronts), which may not be able to well represent realistic scenarios. In this paper, we survey commonly used multi-objective functions in the theory domain and systematically review their features, limitations and implications to practical use. Moreover, we present several new functions with more realistic features, such as local optimality and nonlinearity of the Pareto front, through simply mixing and matching classical single-objective functions in the area (e.g., LeadingOnes, Jump and RoyalRoad). We hope these functions can enrich the existing test problem suites, and strengthen the connection between theoretic and practical research. © 2025, CC BY.

关键词： consensus algorithm

Semi-Streaming algorithms for Hypergraph Matching

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Reinstädtler, Henrik Ferdous, S.M. Pothen, Alex Uçar, Bora Schulz, Christian Heidelberg University Germany Pacific Northwest National Laboratory RichlandWA United States Purdue University West LafayetteIN United States CNRS and LIP UMR5668 CNRS ENS de Lyon Inria UCBL1 France Georgia Institute of Technology AtlantaGA United States

We propose two one-pass streaming algorithms for the NP-hard hypergraph matching problem. The first algorithm stores a small subset of potential matching edges in a stack using dual variables to select edges. It has an approximation guarantee of d(1+1Ε) and requires O((n/Ε) log2 n) bits of memory. The second algorithm computes, stores, and updates a single matching as the edges stream, with an approximation ratio dependent on a parameter α. Its best approximation ratio is (2d−1)+21√d(d−1) , and it requires only O(n) memory. We have implemented both algorithms and have engineered variants for optimizing matching weights, memory consumption, and running times. These include relaxations of the rule for admitting edges into the stack and using a second pass to improve the weight. The evaluation is done on large-sized hypergraphs from circuit design and sparse matrix computations. Our results show that the streaming algorithms achieve much better approximation factors in practice than the worst-case bounds, reducing memory required by up to 50 times and outperforming the offline Greedy algorithm. Copyright © 2025, The Authors. All rights reserved.

关键词： consensus algorithm