Research map / Learning theory and algorithms / Sample complexity
Efficient Optimal Approximation of Discrete Random Variables for Estimation of Probabilities of Missing Deadlines
Liat Cohen, Gera Weiss
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use linApprox instead of OptTrim | repeated support-size reduction · Task trees (Logistics, DRC-Drive, Sequential) | estimated error: 0.0046 -> 0.0024 | Improved |
| use linApprox instead of Trim | repeated support-size reduction · Task trees (Logistics, DRC-Drive, Sequential) | estimated error: 0.0068 -> 0.0024 | Improved |
| use linApprox instead of sampling with s=10^4 | repeated reduction · Logistics, DRC-Drive, Sequential, M=4 | estimated error: 0.0063 -> 0.0093 | Mixed |
| use linApprox instead of sampling with s=10^6 | repeated reduction · Task trees | estimated error: 0.0016 -> 0.008 | Hurt |
| use linApprox instead of OptTrim and Trim | single-step reduction · random variables n=100, varying m | Kolmogorov error | Improved |
| increase support size m | linApprox, OptTrim, Trim · random variables n=100 | Kolmogorov error | Improved |
| use linApprox instead of LP optimal algorithm | optimal Kolmogorov approximation · n=10, m=5 | run-time: 850 seconds -> less than a second | Improved |
| use linApprox instead of LP optimal algorithm | optimal Kolmogorov approximation · n=100, m=5 | run-time: more than a day -> 0.14 seconds | Improved |
| trim after each convolution with linApprox instead of exact computation | summation of random variables · 6 to 19 variables, m=10 | run-time | Improved |
| use linApprox (O(n log n)) instead of binsApprox (O(n^2 log n)) | optimal m-approximation · summation, 6 to 19 variables | run-time | Improved |
| use linApprox instead of faster Trim | summation of random variables · 6 to 19 variables | run-time | Hurt |
Closest papers by meaning
- Optimal Approximation of Random Variables for Estimating the Probability of Meeting a Plan Deadline (AAAI 2018 · similarity 0.89)
- Scheduling LLM Inference with Uncertainty-Aware Output Length Predictions (ICML 2026 · similarity 0.80)
- Discrete Markov Probabilistic Models: An Improved Discrete Score-Based Framework with sharp convergence bounds under minimal assumptions (ICML 2025 · similarity 0.79)
- Non-clairvoyant Scheduling with Partial Predictions (ICML 2024 · similarity 0.79)
- Randomized Kriging Believer For Parallel Bayesian Optimization With Regret Bounds (NeurIPS 2026 · similarity 0.79)
- Scalable Approximation Algorithms for $p$-Wasserstein Distance and Its Variants (ICML 2025 · similarity 0.78)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
