A Characterization of List Regression

• URL: http://arxiv.org/abs/2409.19218v1
• Date: Sat, 28 Sep 2024 03:19:37 GMT
• Title: A Characterization of List Regression
• Authors: Chirag Pabbaraju, Sahasrajit Sarmasarkar,
• Abstract summary: We provide a complete characterization of list regression. We propose two dimensions, namely the $k$-OIG dimension and the $k$-fat-shattering dimension, and show that they optimally characterize realizable and $k$-list regression respectively.
• Score: 5.371337604556312
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: There has been a recent interest in understanding and characterizing the sample complexity of list learning tasks, where the learning algorithm is allowed to make a short list of $k$ predictions, and we simply require one of the predictions to be correct. This includes recent works characterizing the PAC sample complexity of standard list classification and online list classification. Adding to this theme, in this work, we provide a complete characterization of list PAC regression. We propose two combinatorial dimensions, namely the $k$-OIG dimension and the $k$-fat-shattering dimension, and show that they optimally characterize realizable and agnostic $k$-list regression respectively. These quantities generalize known dimensions for standard regression. Our work thus extends existing list learning characterizations from classification to regression.

Related papers

• Self-Calibrated Listwise Reranking with Large Language Models [137.6557607279876]
  Large language models (LLMs) have been employed in reranking tasks through a sequence-to-sequence approach. This reranking paradigm requires a sliding window strategy to iteratively handle larger candidate sets. We propose a novel self-calibrated listwise reranking method, which aims to leverage LLMs to produce global relevance scores for ranking.
  arXiv  Detail & Related papers  (2024-11-07T10:31:31Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  Single-Index Models are high-dimensional regression problems with planted structure. We show that computationally efficient algorithms, both within the Statistical Query (SQ) and the Low-Degree Polynomial (LDP) framework, necessarily require $Omega(dkstar/2)$ samples.
  arXiv  Detail & Related papers  (2024-03-08T18:50:19Z)
• List-aware Reranking-Truncation Joint Model for Search and Retrieval-augmented Generation [80.12531449946655]
  We propose a Reranking-Truncation joint model (GenRT) that can perform the two tasks concurrently. GenRT integrates reranking and truncation via generative paradigm based on encoder-decoder architecture. Our method achieves SOTA performance on both reranking and truncation tasks for web search and retrieval-augmented LLMs.
  arXiv  Detail & Related papers  (2024-02-05T06:52:53Z)
• Deep Imbalanced Regression via Hierarchical Classification Adjustment [50.19438850112964]
  Regression tasks in computer vision are often formulated into classification by quantizing the target space into classes. The majority of training samples lie in a head range of target values, while a minority of samples span a usually larger tail range. We propose to construct hierarchical classifiers for solving imbalanced regression tasks. Our novel hierarchical classification adjustment (HCA) for imbalanced regression shows superior results on three diverse tasks.
  arXiv  Detail & Related papers  (2023-10-26T04:54:39Z)
• List Online Classification [13.358536176734999]
  We study multiclass online prediction where the learner can predict using a list of multiple labels. We characterize learnability in this model using the $b$-ary Littlestone dimension. As part of our work, we adapt classical algorithms such as Littlestone's SOA and Rosenblatt's Perceptron to predict using lists of labels.
  arXiv  Detail & Related papers  (2023-03-27T16:56:57Z)
• Rank-LIME: Local Model-Agnostic Feature Attribution for Learning to Rank [16.780058676633914]
  Rank-LIME is a model-agnostic, local, post-hoc linear feature attribution method for the task of learning to rank. We employ novel correlation-based perturbations, differentiable ranking loss functions and introduce new metrics to evaluate ranking based additive feature attribution models.
  arXiv  Detail & Related papers  (2022-12-24T12:14:32Z)
• What learning algorithm is in-context learning? Investigations with linear models [87.91612418166464]
  We investigate the hypothesis that transformer-based in-context learners implement standard learning algorithms implicitly. We show that trained in-context learners closely match the predictors computed by gradient descent, ridge regression, and exact least-squares regression. Preliminary evidence that in-context learners share algorithmic features with these predictors.
  arXiv  Detail & Related papers  (2022-11-28T18:59:51Z)
• A Characterization of List Learnability [15.368858716555888]
  We consider list PAC learning where the goal is to output a list of $k$ predictions. Generalizing the recent characterization of multiclass learnability, we show that a hypothesis class is $k$-list learnable if and only if the $k$-DS dimension is finite.
  arXiv  Detail & Related papers  (2022-11-07T21:28:05Z)
• OrdinalCLIP: Learning Rank Prompts for Language-Guided Ordinal Regression [94.28253749970534]
  We propose to learn the rank concepts from the rich semantic CLIP latent space. OrdinalCLIP consists of learnable context tokens and learnable rank embeddings. Experimental results show that our paradigm achieves competitive performance in general ordinal regression tasks.
  arXiv  Detail & Related papers  (2022-06-06T03:54:53Z)
• UCSL : A Machine Learning Expectation-Maximization framework for Unsupervised Clustering driven by Supervised Learning [2.133032470368051]
  Subtype Discovery consists in finding interpretable and consistent sub-parts of a dataset, which are also relevant to a certain supervised task. We propose a general Expectation-Maximization ensemble framework entitled UCSL (Unsupervised Clustering driven by Supervised Learning) Our method is generic, it can integrate any clustering method and can be driven by both binary classification and regression.
  arXiv  Detail & Related papers  (2021-07-05T12:55:13Z)

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.