Machine Learning. The Science of Selection under Uncertainty

• URL: http://arxiv.org/abs/2509.21547v1
• Date: Thu, 25 Sep 2025 20:33:13 GMT
• Title: Machine Learning. The Science of Selection under Uncertainty
• Authors: Yevgeny Seldin,
• Abstract summary: The book provides statistical tools to obtain theoretical guarantees on the outcome of selection under uncertainty.<n>The book covers a broad range of inequalities, including Markov's, Chebyshev's, Hoeffding's, Bernstein's, Empirical Bernstein's, kl, and split-kl.<n>We present the space of online learning problems characterized by environmental feedback, environmental resistance, and structural complexity.
• Score: 9.594432031144718
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Learning, whether natural or artificial, is a process of selection. It starts with a set of candidate options and selects the more successful ones. In the case of machine learning the selection is done based on empirical estimates of prediction accuracy of candidate prediction rules on some data. Due to randomness of data sampling the empirical estimates are inherently noisy, leading to selection under uncertainty. The book provides statistical tools to obtain theoretical guarantees on the outcome of selection under uncertainty. We start with concentration of measure inequalities, which are the main statistical instrument for controlling how much an empirical estimate of expectation of a function deviates from the true expectation. The book covers a broad range of inequalities, including Markov's, Chebyshev's, Hoeffding's, Bernstein's, Empirical Bernstein's, Unexpected Bernstein's, kl, and split-kl. We then study the classical (offline) supervised learning and provide a range of tools for deriving generalization bounds, including Occam's razor, Vapnik-Chervonenkis analysis, and PAC-Bayesian analysis. The latter is further applied to derive generalization guarantees for weighted majority votes. After covering the offline setting, we turn our attention to online learning. We present the space of online learning problems characterized by environmental feedback, environmental resistance, and structural complexity. A common performance measure in online learning is regret, which compares performance of an algorithm to performance of the best prediction rule in hindsight, out of a restricted set of prediction rules. We present tools for deriving regret bounds in stochastic and adversarial environments, and under full information and bandit feedback.

Related papers

• A Principled Approach to Randomized Selection under Uncertainty: Applications to Peer Review and Grant Funding [68.43987626137512]
  We propose a principled framework for randomized decision-making based on interval estimates of the quality of each item.<n>We introduce MERIT, an optimization-based method that maximizes the worst-case expected number of top candidates selected.<n>We prove that MERIT satisfies desirable axiomatic properties not guaranteed by existing approaches.
  arXiv  Detail & Related papers  (2025-06-23T19:59:30Z)
• Probably Approximately Precision and Recall Learning [62.912015491907994]
  Precision and Recall are foundational metrics in machine learning. One-sided feedback--where only positive examples are observed during training--is inherent in many practical problems. We introduce a PAC learning framework where each hypothesis is represented by a graph, with edges indicating positive interactions.
  arXiv  Detail & Related papers  (2024-11-20T04:21:07Z)
• Debiasing Machine Learning Models by Using Weakly Supervised Learning [3.3298048942057523]
  We tackle the problem of bias mitigation of algorithmic decisions in a setting where both the output of the algorithm and the sensitive variable are continuous. Typical examples are unfair decisions made with respect to the age or the financial status. Our bias mitigation strategy is a weakly supervised learning method which requires that a small portion of the data can be measured in a fair manner.
  arXiv  Detail & Related papers  (2024-02-23T18:11:32Z)
• Partial-Label Learning with a Reject Option [3.1201323892302444]
  We propose a risk-consistent nearest-neighbor-based partial-label learning algorithm with a reject option.<n>Our method provides the best trade-off between the number and accuracy of non-rejected predictions.<n>When evaluated without the reject option, our nearest-neighbor-based approach also achieves competitive prediction performance.
  arXiv  Detail & Related papers  (2024-02-01T13:41:44Z)
• ASPEST: Bridging the Gap Between Active Learning and Selective Prediction [56.001808843574395]
  Selective prediction aims to learn a reliable model that abstains from making predictions when uncertain. Active learning aims to lower the overall labeling effort, and hence human dependence, by querying the most informative examples. In this work, we introduce a new learning paradigm, active selective prediction, which aims to query more informative samples from the shifted target domain.
  arXiv  Detail & Related papers  (2023-04-07T23:51:07Z)
• Prediction-Powered Inference [68.97619568620709]
  Prediction-powered inference is a framework for performing valid statistical inference when an experimental dataset is supplemented with predictions from a machine-learning system. The framework yields simple algorithms for computing provably valid confidence intervals for quantities such as means, quantiles, and linear and logistic regression coefficients. Prediction-powered inference could enable researchers to draw valid and more data-efficient conclusions using machine learning.
  arXiv  Detail & Related papers  (2023-01-23T18:59:28Z)
• What Should I Know? Using Meta-gradient Descent for Predictive Feature Discovery in a Single Stream of Experience [63.75363908696257]
  computational reinforcement learning seeks to construct an agent's perception of the world through predictions of future sensations. An open challenge in this line of work is determining from the infinitely many predictions that the agent could possibly make which predictions might best support decision-making. We introduce a meta-gradient descent process by which an agent learns what predictions to make, 2) the estimates for its chosen predictions, and 3) how to use those estimates to generate policies that maximize future reward.
  arXiv  Detail & Related papers  (2022-06-13T21:31:06Z)
• Selective Prediction via Training Dynamics [31.708701583736644]
  We show that state-of-the-art selective prediction performance can be attained solely from studying the training dynamics of a model.<n>In particular, we reject data points exhibiting too much disagreement with the final prediction at late stages in training.<n>The proposed rejection mechanism is domain-agnostic (i.e., it works for both discrete and real-valued prediction) and can be flexibly combined with existing selective prediction approaches.
  arXiv  Detail & Related papers  (2022-05-26T17:51:29Z)
• Balanced Q-learning: Combining the Influence of Optimistic and Pessimistic Targets [74.04426767769785]
  We show that specific types of biases may be preferable, depending on the scenario. We design a novel reinforcement learning algorithm, Balanced Q-learning, in which the target is modified to be a convex combination of a pessimistic and an optimistic term.
  arXiv  Detail & Related papers  (2021-11-03T07:30:19Z)
• Towards optimally abstaining from prediction [22.937799541125607]
  A common challenge across all areas of machine learning is that training data is not distributed like test data. We consider a model where one may abstain from predicting, at a fixed cost. Our work builds on a recent abstention algorithm of Goldwasser, Kalais, and Montasser ( 2020) for transductive binary classification.
  arXiv  Detail & Related papers  (2021-05-28T21:44:48Z)
• Distribution-Free, Risk-Controlling Prediction Sets [112.9186453405701]
  We show how to generate set-valued predictions from a black-box predictor that control the expected loss on future test points at a user-specified level. Our approach provides explicit finite-sample guarantees for any dataset by using a holdout set to calibrate the size of the prediction sets.
  arXiv  Detail & Related papers  (2021-01-07T18:59:33Z)
• A framework for predicting, interpreting, and improving Learning Outcomes [0.0]
  We develop an Embibe Score Quotient model (ESQ) to predict test scores based on observed academic, behavioral and test-taking features of a student. ESQ can be used to predict the future scoring potential of a student as well as offer personalized learning nudges.
  arXiv  Detail & Related papers  (2020-10-06T11:22:27Z)

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.