A Practical Theory of Generalization in Selectivity Learning

• URL: http://arxiv.org/abs/2409.07014v1
• Date: Wed, 11 Sep 2024 05:10:32 GMT
• Title: A Practical Theory of Generalization in Selectivity Learning
• Authors: Peizhi Wu, Haoshu Xu, Ryan Marcus, Zachary G. Ives,
• Abstract summary: query-driven machine learning models have emerged as a promising estimation technique for query selectivities. We bridge the gaps between state-of-the-art (SOTA) theory based on the Probably Approximately Correct (PAC) learning framework. We show that selectivity predictors induced by signed measures are learnable, which relaxes the reliance on probability measures in SOTA theory.
• Score: 8.268822578361824
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Query-driven machine learning models have emerged as a promising estimation technique for query selectivities. Yet, surprisingly little is known about the efficacy of these techniques from a theoretical perspective, as there exist substantial gaps between practical solutions and state-of-the-art (SOTA) theory based on the Probably Approximately Correct (PAC) learning framework. In this paper, we aim to bridge the gaps between theory and practice. First, we demonstrate that selectivity predictors induced by signed measures are learnable, which relaxes the reliance on probability measures in SOTA theory. More importantly, beyond the PAC learning framework (which only allows us to characterize how the model behaves when both training and test workloads are drawn from the same distribution), we establish, under mild assumptions, that selectivity predictors from this class exhibit favorable out-of-distribution (OOD) generalization error bounds. These theoretical advances provide us with a better understanding of both the in-distribution and OOD generalization capabilities of query-driven selectivity learning, and facilitate the design of two general strategies to improve OOD generalization for existing query-driven selectivity models. We empirically verify that our techniques help query-driven selectivity models generalize significantly better to OOD queries both in terms of prediction accuracy and query latency performance, while maintaining their superior in-distribution generalization performance.

Related papers

• On the Generalization of Preference Learning with DPO [17.420727709895736]
  Large language models (LLMs) have demonstrated remarkable capabilities but often struggle to align with human preferences. Preference learning trains models to distinguish between preferred and non-preferred responses based on human feedback. This paper introduces a new theoretical framework to analyze the generalization guarantees of models trained with direct preference optimization (DPO)
  arXiv  Detail & Related papers  (2024-08-06T22:11:00Z)
• Distribution Learning and Its Application in Deep Learning [5.281849820329249]
  This paper introduces a novel theoretical learning framework, termed probability distribution learning (PD learning) PD learning focuses on learning the underlying probability distribution, which is modeled as a random variable within the probability simplex.
  arXiv  Detail & Related papers  (2024-06-09T06:49:22Z)
• Mitigating Simplicity Bias in Deep Learning for Improved OOD Generalization and Robustness [5.976013616522926]
  We propose a framework that encourages the model to use a more diverse set of features to make predictions. We first train a simple model, and then regularize the conditional mutual information with respect to it to obtain the final model. We demonstrate the effectiveness of this framework in various problem settings and real-world applications.
  arXiv  Detail & Related papers  (2023-10-09T21:19:39Z)
• Topology-aware Robust Optimization for Out-of-distribution Generalization [18.436575017126323]
  Out-of-distribution (OOD) generalization is a challenging machine learning problem yet highly desirable in many high-stake applications. We propose topology-aware robust optimization (TRO) that seamlessly integrates distributional topology in a principled optimization framework. We theoretically demonstrate the effectiveness of our approach and empirically show that it significantly outperforms the state of the arts in a wide range of tasks including classification, regression, and semantic segmentation.
  arXiv  Detail & Related papers  (2023-07-26T03:48:37Z)
• Provable Reward-Agnostic Preference-Based Reinforcement Learning [61.39541986848391]
  Preference-based Reinforcement Learning (PbRL) is a paradigm in which an RL agent learns to optimize a task using pair-wise preference-based feedback over trajectories. We propose a theoretical reward-agnostic PbRL framework where exploratory trajectories that enable accurate learning of hidden reward functions are acquired.
  arXiv  Detail & Related papers  (2023-05-29T15:00:09Z)
• Guide the Learner: Controlling Product of Experts Debiasing Method Based on Token Attribution Similarities [17.082695183953486]
  A popular workaround is to train a robust model by re-weighting training examples based on a secondary biased model. Here, the underlying assumption is that the biased model resorts to shortcut features. We introduce a fine-tuning strategy that incorporates the similarity between the main and biased model attribution scores in a Product of Experts loss function.
  arXiv  Detail & Related papers  (2023-02-06T15:21:41Z)
• Synergies between Disentanglement and Sparsity: Generalization and Identifiability in Multi-Task Learning [79.83792914684985]
  We prove a new identifiability result that provides conditions under which maximally sparse base-predictors yield disentangled representations. Motivated by this theoretical result, we propose a practical approach to learn disentangled representations based on a sparsity-promoting bi-level optimization problem.
  arXiv  Detail & Related papers  (2022-11-26T21:02:09Z)
• Scalable PAC-Bayesian Meta-Learning via the PAC-Optimal Hyper-Posterior: From Theory to Practice [54.03076395748459]
  A central question in the meta-learning literature is how to regularize to ensure generalization to unseen tasks. We present a generalization bound for meta-learning, which was first derived by Rothfuss et al. We provide a theoretical analysis and empirical case study under which conditions and to what extent these guarantees for meta-learning improve upon PAC-Bayesian per-task learning bounds.
  arXiv  Detail & Related papers  (2022-11-14T08:51:04Z)
• Making Linear MDPs Practical via Contrastive Representation Learning [101.75885788118131]
  It is common to address the curse of dimensionality in Markov decision processes (MDPs) by exploiting low-rank representations. We consider an alternative definition of linear MDPs that automatically ensures normalization while allowing efficient representation learning. We demonstrate superior performance over existing state-of-the-art model-based and model-free algorithms on several benchmarks.
  arXiv  Detail & Related papers  (2022-07-14T18:18:02Z)
• Learning Causal Semantic Representation for Out-of-Distribution Prediction [125.38836464226092]
  We propose a Causal Semantic Generative model (CSG) based on a causal reasoning so that the two factors are modeled separately. We show that CSG can identify the semantic factor by fitting training data, and this semantic-identification guarantees the boundedness of OOD generalization error.
  arXiv  Detail & Related papers  (2020-11-03T13:16:05Z)
• Learning the Truth From Only One Side of the Story [58.65439277460011]
  We focus on generalized linear models and show that without adjusting for this sampling bias, the model may converge suboptimally or even fail to converge to the optimal solution. We propose an adaptive approach that comes with theoretical guarantees and show that it outperforms several existing methods empirically.
  arXiv  Detail & Related papers  (2020-06-08T18:20:28Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.