Cover Image

Analyzing the effect of prediction accuracy on the distributionally-robust competitive ratio

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Yoshinaga, Toru, Kawase, Yasushi
Format:	Preprint
Published:	2026
Subjects:	Machine Learning Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Online Algorithms for Repeated Optimal Stopping: Balancing Baseline Guarantees and Regret
by: Harada, Tsubasa, et al.
Published: (2025)

Online Matching with Delays and Size-based Costs
by: Kawase, Yasushi, et al.
Published: (2024)

On efficient robust regression with subquadratic samples
by: Adil, Deeksha, et al.
Published: (2026)

Fast, robust approximate message passing
by: Ivkov, Misha, et al.
Published: (2024)

Scheduling on Identical Machines with Setup Time and Unknown Execution Time
by: Kawase, Yasushi, et al.
Published: (2025)

Outlier-robust Mean Estimation near the Breakdown Point via Sum-of-Squares
by: Chen, Hongjie, et al.
Published: (2024)

Algorithms for Caching and MTS with reduced number of predictions
by: Sadek, Karim Abdel, et al.
Published: (2024)

Competitive strategies to use "warm start" algorithms with predictions
by: Srinivas, Vaidehi, et al.
Published: (2024)

Graph neural networks extrapolate out-of-distribution for shortest paths
by: Nerem, Robert R., et al.
Published: (2025)

On the query complexity of sampling from non-log-concave distributions
by: He, Yuchen, et al.
Published: (2025)

Efficient distributional regression trees learning algorithms for calibrated non-parametric probabilistic forecasts
by: Duchemin, Quentin, et al.
Published: (2025)

Fair Allocation with Binary Valuations for Mixed Divisible and Indivisible Goods
by: Kawase, Yasushi, et al.
Published: (2023)

Easy, robust approximate message passing for planted spike models
by: Ivkov, Misha, et al.
Published: (2026)

High-accuracy log-concave sampling with stochastic queries
by: Chen, Fan, et al.
Published: (2026)

Efficiently learning and sampling multimodal distributions with data-based initialization
by: Koehler, Frederic, et al.
Published: (2024)

Rate-optimal community detection near the KS threshold via node-robust algorithms
by: Ding, Jingqiu, et al.
Published: (2025)

Improved sampling algorithms and functional inequalities for non-log-concave distributions
by: He, Yuchen, et al.
Published: (2025)

The sample complexity of multi-distribution learning
by: Peng, Binghui
Published: (2023)

Data organization limits the predictability of binary classification
by: Jing, Fei, et al.
Published: (2024)

Predicting quantum channels over general product distributions
by: Chen, Sitan, et al.
Published: (2024)

Optimal Prediction-Augmented Algorithms for Testing Independence of Distributions
by: Aliakbarpour, Maryam, et al.
Published: (2026)

Efficient Adaptive Data Analysis over Dense Distributions
by: Huh, Joon Suk
Published: (2026)

Near-optimal Swap Regret Minimization for Convex Losses
by: Hu, Lunjia, et al.
Published: (2026)

Approximating splits for decision trees quickly in sparse data streams
by: Tatti, Nikolaj
Published: (2026)

The Art of Being Difficult: Combining Human and AI Strengths to Find Adversarial Instances for Heuristics
by: Nikoleit, Henri, et al.
Published: (2026)

Online Learning with Limited Information in the Sliding Window Model
by: Braverman, Vladimir, et al.
Published: (2026)

The tractability landscape of diffusion alignment: regularization, rewards, and computational primitives
by: Moitra, Ankur, et al.
Published: (2026)

Asymptotically Robust Learning-Augmented Algorithms for Preemptive FIFO Buffer Management
by: Hsieh, Wen-Han, et al.
Published: (2026)

New Bounds for Kernel Sums via Fast Spherical Embeddings
by: Wagner, Tal
Published: (2026)

Equivalence of Coarse and Fine-Grained Models for Learning with Distribution Shift
by: Klivans, Adam R., et al.
Published: (2026)

Adaptive Power Iteration Method for Differentially Private PCA
by: Nguyen, Ta Duy, et al.
Published: (2026)

Incremental Strongly Connected Components with Predictions
by: Deng, Ronald, et al.
Published: (2026)

Finite Sample Bounds for Learning with Score Matching
by: Smedira, Devin, et al.
Published: (2026)

Deterministic Coreset for Lp Subspace
by: Chhaya, Rachit, et al.
Published: (2026)

Compact Conformal Subgraphs
by: Gollapudi, Sreenivas, et al.
Published: (2026)

Towards Optimal Robustness in Learning-Augmented Paging
by: Chen, Peng, et al.
Published: (2026)

Optimal Dimension-Free Sampling for Regularized Classification
by: Alishahi, Meysam, et al.
Published: (2026)

Learning with Monotone Adversarial Corruptions
by: Larsen, Kasper Green, et al.
Published: (2026)

Sample-and-Search: An Effective Algorithm for Learning-Augmented k-Median Clustering in High dimensions
by: Cheng, Kangke, et al.
Published: (2026)

Lumberjack: Better Differentially Private Random Forests through Heavy Hitter Detection in Trees
by: Lebeda, Christian Janos, et al.
Published: (2026)