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

Partition Constraints for Conjunctive Queries: Bounds and Worst-Case Optimal Joins

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Deeds, Kyle Merkl, Timo Camillo University of Washington SeattleWA United States TU Wien Vienna Austria

In the last decade, various works have used statistics on relations to improve both the theory and practice of conjunctive query execution. Starting with the AGM bound which took advantage of relation sizes, later works incorporated statistics like functional dependencies and degree constraints. Each new statistic prompted work along two lines;bounding the size of conjunctive query outputs and worst-case optimal join algorithms. In this work, we continue in this vein by introducing a new statistic called a partition constraint. This statistic captures latent structure within relations by partitioning them into sub-relations which each have much tighter degree constraints. We show that this approach can both refine existing cardinality bounds and improve existing worst-case optimal join algorithms. Copyright © 2025, The Authors. All rights reserved.

关键词： optimization algorithms

PROVABLY EFFICIENT MULTI-OBJECTIVE BANDIT algorithms UNDER PREFERENCE-CENTRIC CUSTOMIZATION

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Cao, Linfeng Shi, Ming Shroff, Ness B. Department of CSE The Ohio State University United States Department of Electrical Engineering University at Buffalo United States Department of ECE The Ohio State University United States

Multi-objective multi-armed bandit (MO-MAB) problems traditionally aim to achieve Pareto optimality. However, real-world scenarios often involve users with varying preferences across objectives, resulting in a Pareto-optimal arm that may score high for one user but perform quite poorly for another. This highlights the need for customized learning, a factor often overlooked in prior research. To address this, we study a preference-aware MO-MAB framework in the presence of explicit user preference. It shifts the focus from achieving Pareto optimality to further optimizing within the Pareto front under preference-centric customization. To our knowledge, this is the first theoretical study of customized MO-MAB optimization with explicit user preferences. Motivated by practical applications, we explore two scenarios: unknown preference and hidden preference, each presenting unique challenges for algorithm design and analysis. At the core of our algorithms are preference estimation and preference-aware optimization mechanisms to adapt to user preferences effectively. We further develop novel analytical techniques to establish near-optimal regret of the proposed algorithms. Strong empirical performance confirm the effectiveness of our approach. © 2025, CC BY.

关键词： optimization algorithms

DADA: Dual Averaging with Distance Adaptation

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Moshtaghifar, Mohammad Rodomanov, Anton Vankov, Daniil Stich, Sebastian U. Sharif University of Technology Iran CISPA Helmholtz Center for Information Security Germany Arizona State University United States

We present a novel universal gradient method for solving convex optimization problems. Our algorithm—Dual Averaging with Distance Adaptation (DADA)—is based on the classical scheme of dual averaging and dynamically adjusts its coefficients based on observed gradients and the distance between iterates and the starting point, eliminating the need for problem-specific parameters. DADA is a universal algorithm that simultaneously works for a broad spectrum of problem classes, provided the local growth of the objective function around its minimizer can be bounded. Particular examples of such problem classes are nonsmooth Lipschitz functions, Lipschitz-smooth functions, Hölder-smooth functions, functions with high-order Lipschitz derivative, quasi-self-concordant functions, and (L0, L1)-smooth functions. Crucially, DADA is applicable to both unconstrained and constrained problems, even when the domain is unbounded, without requiring prior knowledge of the number of iterations or desired accuracy. Copyright © 2025, The Authors. All rights reserved.

关键词： optimization algorithms

Bayesian Optimisation with Unknown Hyperparameters: Regret Bounds Logarithmically Closer to Optimal

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Ziomek, Juliusz Adachi, Masaki Osborne, Michael A. Machine Learning Research Group University of Oxford United Kingdom Toyota Motor Corporation Japan

Bayesian optimization (BO) is widely used for optimising black-box functions but requires us to specify the length scale hyperparameter, which defines the smoothness of the functions the optimizer will consider. Most current BO algorithms choose this hyperparameter by maximizing the marginal likelihood of the observed data, albeit risking misspecification if the objective function is less smooth in regions we have not yet explored. The only prior solution addressing this problem with theoretical guarantees was A-GP-UCB, proposed by Berkenkamp et al. (2019). This algorithm progressively decreases the length scale, expanding the class of functions considered by the optimizer. However, A-GP-UCB lacks a stopping mechanism, leading to over-exploration and slow convergence. To overcome this, we introduce Length scale Balancing (LB)—a novel approach, aggregating multiple base surrogate models with varying length scales. LB intermittently adds smaller length scale candidate values while retaining longer scales, balancing exploration and exploitation. We formally derive a cumulative regret bound of LB and compare it with the regret of an oracle BO algorithm using the optimal length scale. Denoting the factor by which the regret bound of A-GP-UCB was away from oracle as g(T), we show that LB is only log g(T) away from oracle regret. We also empirically evaluate our algorithm on synthetic and real-world benchmarks and show it outperforms A-GP-UCB, maximum likelihood estimation and MCMC. © 2024, CC BY.

关键词： optimization algorithms

Convergence towards a local minimum by direct search methods with a covering step

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Bouchet, Pierre-Yves Audet, Charles Bourdin, Loïc École Polytechnique de Montréal MontréalQCH3T 1J4 Canada GERAD MontréalQCH3T 1J4 Canada XLIM Research Institute University of Limoges France

This paper introduces a new step to the Direct Search Method (DSM) to strengthen its convergence analysis. By design, this so-called covering step may ensure that, for all refined points of the sequence of incumbent solutions generated by the resulting cDSM (covering DSM), the set of all evaluated trial points is dense in a neighborhood of that refined point. We prove that this additional property guarantees that all refined points are local solutions to the optimization problem. This new result holds true even for a discontinuous objective function, under a mild assumption that we discuss in details. We also provide a practical construction scheme for the covering step that works at low additional cost per iteration. Finally, we show that the covering step may be adapted to classes of algorithms differing from the DSM. © 2024, CC BY.

关键词： optimization algorithms

Population-Level Center-Based Sampling for Meta-Heuristic algorithms

学校读者我要写书评

暂无评论

SSRN

SSRN 2024年

作者： Khosrowshahli, Rasa Rahnamayan, Shahryar Ibrahim, Amin Bidgoli, Azam Asilian Makrehchi, Masoud Faculty of Engineering and Applied Sciences Ontario Tech University OshawaON Canada Department of Engineering Brock University St. CatharinesON Canada Faculty of Business and Information Technology Ontario Tech University OshawaON Canada Faculty of Science Wilfrid Laurier University WaterlooON Canada

In recent years, center-based sampling has demonstrated p results for enhancing the efficiency and effectiveness of meta-heuristic algorithms. The strategy of center-based sampling can be utilized at either the operation and/or population levels. Despite the overall efficiency of the center-based sampling in population-based algorithms, utilization at the operation requires customizing the strategy for a specific algorithm, degrading the generalization of the scheme. This study proposes a center-based sampling at the population level, which is operation-independent and correspondingly can be embedded in any population-based optimization algorithm. The proposed center-based sampling uses a collaborative multi-parent approach to generate multiple center-based solutions leading to augmented diversity as well as the exploitation of the solution space. Accordingly, two population-level center-based sampling, namely cluster-driven center-based sampling and ranking-driven center-based sampling are proposed to enhance population-based single- and multi-objective optimization algorithms, respectively. In order to assess the performance of proposed schemes, the proposed strategy is integrated in well-known single- and multi-objective optimization algorithms to solve the CEC-2017 benchmark functions. The experimental outcomes confirm that the algorithm with embedded population-level center-based samplings have a crucial positive impact on the convergence rate of various families of optimization algorithms compared to the parent algorithm. © 2024, The Authors. All rights reserved.

关键词： optimization algorithms

Overcoming Brittleness in Pareto-Optimal Learning-Augmented algorithms

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Angelopoulos, Spyros Dürr, Christoph Elenter, Alex Lefki, Yanni Sorbonne Université CNRS LIP6 Paris France Ecole Polytechnique Palaiseau France

The study of online algorithms with machine-learned predictions has gained considerable prominence in recent years. One of the common objectives in the design and analysis of such algorithms is to attain (Pareto) optimal tradeoffs between the consistency of the algorithm, i.e., its performance assuming perfect predictions, and its robustness, i.e., the performance of the algorithm under adversarial predictions. In this work, we demonstrate that this optimization criterion can be extremely brittle, in that the performance of Pareto-optimal algorithms may degrade dramatically even in the presence of imperceptive prediction error. To remedy this drawback, we propose a new framework in which the smoothness in the performance of the algorithm is enforced by means of a user-specified profile. This allows us to regulate the performance of the algorithm as a function of the prediction error, while simultaneously maintaining the analytical notion of consistency/robustness tradeoffs, adapted to the profile setting. We apply this new approach to a well-studied online problem, namely the one-way trading problem. For this problem, we further address another limitation of the state-of-the-art Pareto-optimal algorithms, namely the fact that they are tailored to worst-case, and extremely pessimistic inputs. We propose a new Pareto-optimal algorithm that leverages any deviation from the worst-case input to its benefit, and introduce a new metric that allows us to compare any two Pareto-optimal algorithms via a dominance relation. © 2024, CC BY-NC-SA.

关键词： optimization algorithms

A Framework for Decentralized Equilibrium Seeking in Networked Sampled-Data Games using Hybrid Control Tools*

学校读者我要写书评

暂无评论

IFAC-PapersOnLine 2023年第2期56卷 5095-5100页

作者： Vishal Shenoy Jorge I. Poveda Department of Electrical and Computer Engineering University of California San Diego CA 92093 USA

We study the steady-state Nash equilibrium-seeking problem for sampled-data games with LTI dynamics and quadratic costs. The key challenge is to guarantee the robust stability and convergence properties of the closed-loop system in the presence of local individual sampling mechanisms assigned to each of the players in the game. This problem is non-trivial due to the unstable behaviors that can arise when sequential control updates (rather than parallel) emerge in the closed-loop system because of the existence of local control triggering mechanisms in each node of the network. To address this issue, we introduce a controls framework based on tools from hybrid dynamical systems theory. Our results are illustrated via numerical examples.

关键词： Equilibrium-Seeking Network Systems Hybrid Control optimization algorithms Cyber-Physical Systems

Pandora with Inaccurate Priors

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Banihashem, Kiarash Chen, Xiang Hajiaghayi, MohammadTaghi Kim, Sungchul Mahadik, Kanak Rossi, Ryan Yu, Tong University of Maryland United States Adobe Research United States Adobe Systems United States

We investigate the role of inaccurate priors for the classical Pandora’s box problem. In the classical Pandora’s box problem we are given a set of boxes each with a known cost and an unknown value sampled from a known distribution. We investigate how inaccuracies in the beliefs can affect existing algorithms. Specifically, we assume that the knowledge of the underlying distribution has a small error in the Kolmogorov distance, and study how this affects the utility obtained by the optimal algorithm. Copyright © 2025, The Authors. All rights reserved.

关键词： optimization algorithms