Survey of Data-driven Newsvendor: Unified Analysis and Spectrum of Achievable Regrets

• URL: http://arxiv.org/abs/2409.03505v3
• Date: Tue, 06 May 2025 01:24:39 GMT
• Title: Survey of Data-driven Newsvendor: Unified Analysis and Spectrum of Achievable Regrets
• Authors: Zhuoxin Chen, Will Ma,
• Abstract summary: In the Newsvendor problem, the goal is to guess the number that will be drawn from some distribution.<n>In the data-driven version, the distribution is unknown, and one must work with samples from the distribution.<n>This paper studies all combinations of these variants, filling in many gaps in the literature and simplifying many proofs.
• Score: 6.356813626290215
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In the Newsvendor problem, the goal is to guess the number that will be drawn from some distribution, with asymmetric consequences for guessing too high vs. too low. In the data-driven version, the distribution is unknown, and one must work with samples from the distribution. Data-driven Newsvendor has been studied under many variants: additive vs. multiplicative regret, high probability vs. expectation bounds, and different distribution classes. This paper studies all combinations of these variants, filling in many gaps in the literature and simplifying many proofs. In particular, we provide a unified analysis based on the notion of clustered distributions, which in conjunction with our new lower bounds, shows that the entire spectrum of regrets between $1/\sqrt{n}$ and $1/n$ can be possible. Simulations on commonly-used distributions demonstrate that our notion is the "correct" predictor of empirical regret across varying data sizes.

Related papers

• Gumbel-max List Sampling for Distribution Coupling with Multiple Samples [19.059328123272028]
  We develop a new mechanism for speculative sampling that is simple to implement and achieves performance competitive with baselines such as SpecTr and SpecInfer.<n>We consider distributed lossy compression with side information in a setting where a source sample is compressed and available to multiple decoders.
  arXiv  Detail & Related papers  (2025-06-05T23:32:08Z)
• Gradual Domain Adaptation via Manifold-Constrained Distributionally Robust Optimization [0.4732176352681218]
  This paper addresses the challenge of gradual domain adaptation within a class of manifold-constrained data distributions. We propose a methodology rooted in Distributionally Robust Optimization (DRO) with an adaptive Wasserstein radius. Our bounds rely on a newly introduced it compatibility measure, which fully characterizes the error propagation dynamics along the sequence.
  arXiv  Detail & Related papers  (2024-10-17T22:07:25Z)
• Theory on Score-Mismatched Diffusion Models and Zero-Shot Conditional Samplers [49.97755400231656]
  We present the first performance guarantee with explicit dimensional general score-mismatched diffusion samplers. We show that score mismatches result in an distributional bias between the target and sampling distributions, proportional to the accumulated mismatch between the target and training distributions. This result can be directly applied to zero-shot conditional samplers for any conditional model, irrespective of measurement noise.
  arXiv  Detail & Related papers  (2024-10-17T16:42:12Z)
• $O(d/T)$ Convergence Theory for Diffusion Probabilistic Models under Minimal Assumptions [6.76974373198208]
  We establish a fast convergence theory for a popular SDE-based sampler under minimal assumptions. Our analysis shows that, provided $ell_2$-accurate estimates of the score functions, the total variation distance between the target and generated distributions is upper bounded by $O(d/T)$. This is achieved through a novel set of analytical tools that provides a fine-grained characterization of how the error propagates at each step of the reverse process.
  arXiv  Detail & Related papers  (2024-09-27T17:59:10Z)
• Rejection via Learning Density Ratios [50.91522897152437]
  Classification with rejection emerges as a learning paradigm which allows models to abstain from making predictions.<n>We propose a different distributional perspective, where we seek to find an idealized data distribution which maximizes a pretrained model's performance.<n>Our framework is tested empirically over clean and noisy datasets.
  arXiv  Detail & Related papers  (2024-05-29T01:32:17Z)
• Universal Batch Learning Under The Misspecification Setting [4.772817128620037]
  We consider the problem of universal em batch learning in a misspecification setting with log-loss. We derive the optimal universal learner, a mixture over the set of the data generating distributions, and get a closed form expression for the min-max regret.
  arXiv  Detail & Related papers  (2024-05-12T11:16:05Z)
• Probabilistic Contrastive Learning for Long-Tailed Visual Recognition [78.70453964041718]
  Longtailed distributions frequently emerge in real-world data, where a large number of minority categories contain a limited number of samples. Recent investigations have revealed that supervised contrastive learning exhibits promising potential in alleviating the data imbalance. We propose a novel probabilistic contrastive (ProCo) learning algorithm that estimates the data distribution of the samples from each class in the feature space.
  arXiv  Detail & Related papers  (2024-03-11T13:44:49Z)
• An Improved Algorithm for Learning Drifting Discrete Distributions [2.2191203337341525]
  We present a new adaptive algorithm for learning discrete distributions under distribution drift. We observe a sequence of independent samples from a discrete distribution that is changing over time, and the goal is to estimate the current distribution. To use more samples, we must resort to samples further in the past, and we incur a drift error due to the bias introduced by the change in distribution. We present a novel adaptive algorithm that can solve this trade-off without any prior knowledge of the drift.
  arXiv  Detail & Related papers  (2024-03-08T16:54:27Z)
• Out-Of-Domain Unlabeled Data Improves Generalization [0.7589678255312519]
  We propose a novel framework for incorporating unlabeled data into semi-supervised classification problems. We show that unlabeled samples can be harnessed to narrow the generalization gap. We validate our claims through experiments conducted on a variety of synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2023-09-29T02:00:03Z)
• Tackling Combinatorial Distribution Shift: A Matrix Completion Perspective [42.85196869759168]
  We study a setting we call distribution shift, where (a) under the test- and training-random data, the labels $z$ are determined by pairs of features $(x,y)$, (b) the training distribution has coverage of certain marginal distributions over $x$ and $y$ separately, but (c) the test distribution involves examples from a product distribution over $(x,y)$ that is not covered by the training distribution.
  arXiv  Detail & Related papers  (2023-07-12T21:17:47Z)
• On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
  Social and real-world considerations have given rise to multi-distribution learning paradigms. We establish the optimal sample complexity of these learning paradigms and give algorithms that meet this sample complexity. Our algorithm design and analysis are enabled by our extensions of online learning techniques for solving zero-sum games.
  arXiv  Detail & Related papers  (2022-10-22T19:07:26Z)
• On Best-Arm Identification with a Fixed Budget in Non-Parametric Multi-Armed Bandits [0.0]
  We consider general, possibly non-parametric, models D for distributions over the arms. We propose upper bounds on the average log-probability of misidentifying the optimal arm based on information-theoretic quantities.
  arXiv  Detail & Related papers  (2022-09-30T10:55:40Z)
• Discovering Invariant Rationales for Graph Neural Networks [104.61908788639052]
  Intrinsic interpretability of graph neural networks (GNNs) is to find a small subset of the input graph's features. We propose a new strategy of discovering invariant rationale (DIR) to construct intrinsically interpretable GNNs.
  arXiv  Detail & Related papers  (2022-01-30T16:43:40Z)
• Robust Learning of Optimal Auctions [84.13356290199603]
  We study the problem of learning revenue-optimal multi-bidder auctions from samples when the samples of bidders' valuations can be adversarially corrupted or drawn from distributions that are adversarially perturbed. We propose new algorithms that can learn a mechanism whose revenue is nearly optimal simultaneously for all true distributions'' that are $alpha$-close to the original distribution in Kolmogorov-Smirnov distance.
  arXiv  Detail & Related papers  (2021-07-13T17:37:21Z)
• Predicting with Confidence on Unseen Distributions [90.68414180153897]
  We connect domain adaptation and predictive uncertainty literature to predict model accuracy on challenging unseen distributions. We find that the difference of confidences (DoC) of a classifier's predictions successfully estimates the classifier's performance change over a variety of shifts. We specifically investigate the distinction between synthetic and natural distribution shifts and observe that despite its simplicity DoC consistently outperforms other quantifications of distributional difference.
  arXiv  Detail & Related papers  (2021-07-07T15:50:18Z)
• Distributional Reinforcement Learning via Moment Matching [54.16108052278444]
  We formulate a method that learns a finite set of statistics from each return distribution via neural networks. Our method can be interpreted as implicitly matching all orders of moments between a return distribution and its Bellman target. Experiments on the suite of Atari games show that our method outperforms the standard distributional RL baselines.
  arXiv  Detail & Related papers  (2020-07-24T05:18:17Z)
• Multi-label Contrastive Predictive Coding [125.03510235962095]
  Variational mutual information (MI) estimators are widely used in unsupervised representation learning methods such as contrastive predictive coding (CPC) We introduce a novel estimator based on a multi-label classification problem, where the critic needs to jointly identify multiple positive samples at the same time. We show that using the same amount of negative samples, multi-label CPC is able to exceed the $log m$ bound, while still being a valid lower bound of mutual information.
  arXiv  Detail & Related papers  (2020-07-20T02:46:21Z)
• Differentially Private Assouad, Fano, and Le Cam [32.509176784239216]
  Le Cam's method, Fano's inequality, and Assouad's lemma are three techniques to prove lower bounds for statistical estimation tasks. We propose their analogues under central differential privacy. Our results are simple, easy to apply and we use them to establish sample complexity bounds in several estimation tasks.
  arXiv  Detail & Related papers  (2020-04-14T23:10:38Z)

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.