Cover Image

Near-Optimal Algorithms for Omniprediction

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Okoroafor, Princewill, Kleinberg, Robert, Kim, Michael P.
Format:	Preprint
Published:	2025
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

Breaking the $T^{2/3}$ Barrier for Sequential Calibration
by: Dagan, Yuval, et al.
Published: (2024)

Omnipredictors for Regression and the Approximate Rank of Convex Functions
by: Gopalan, Parikshit, et al.
Published: (2024)

Simultaneous Blackwell Approachability and Applications to Multiclass Omniprediction
by: Hu, Lunjia, et al.
Published: (2026)

Omnipredicting Single-Index Models with Multi-Index Models
by: Hu, Lunjia, et al.
Published: (2024)

Mistake-Bounded Language Generation
by: Kleinberg, Jon, et al.
Published: (2026)

Water-Filling is Universally Minimax Optimal
by: Banerjee, Siddhartha, et al.
Published: (2026)

Near-Optimal Regret for Efficient Stochastic Combinatorial Semi-Bandits
by: Ye, Zichun, et al.
Published: (2025)

Optimal Algorithms for Augmented Testing of Discrete Distributions
by: Aliakbarpour, Maryam, et al.
Published: (2024)

Ads that Stick: Near-Optimal Ad Optimization through Psychological Behavior Models
by: Darmasubramanian, Kailash Gopal, et al.
Published: (2025)

A Simple Approximation Algorithm for Optimal Decision Tree
by: Zhuo, Zhengjia, et al.
Published: (2025)

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

Overcoming Brittleness in Pareto-Optimal Learning-Augmented Algorithms
by: Angelopoulos, Spyros, et al.
Published: (2024)

Nearly Tight Bounds for Exploration in Streaming Multi-armed Bandits with Known Optimality Gap
by: Karpov, Nikolai, et al.
Published: (2025)

Submodular Maximization subject to a Knapsack Constraint: Combinatorial Algorithms with Near-optimal Adaptive Complexity
by: Amanatidis, Georgios, et al.
Published: (2021)

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

Language Generation and Identification From Partial Enumeration: Tight Density Bounds and Topological Characterizations
by: Kleinberg, Jon, et al.
Published: (2025)

Language Generation in the Limit
by: Kleinberg, Jon, et al.
Published: (2024)

Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms
by: Li, Yi, et al.
Published: (2024)

Improved Algorithms for Kernel Matrix-Vector Multiplication Under Sparsity Assumptions
by: Indyk, Piotr, et al.
Published: (2025)

Near-optimal Active Regression of Single-Index Models
by: Li, Yi, et al.
Published: (2025)

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

LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions
by: Kannan, Ravindran, et al.
Published: (2024)

Nearly-Linear Time Private Hypothesis Selection with the Optimal Approximation Factor
by: Aliakbarpour, Maryam, et al.
Published: (2025)

Nearly Optimal Robust Covariance and Scatter Matrix Estimation Beyond Gaussians
by: Novikov, Gleb
Published: (2025)

Nearly-tight Approximation Guarantees for the Improving Multi-Armed Bandits Problem
by: Blum, Avrim, et al.
Published: (2024)

On Computing Optimal Tree Ensembles
by: Komusiewicz, Christian, et al.
Published: (2023)

Robust Learning with Optimal Error
by: Blanc, Guy
Published: (2026)

Sinkhorn Algorithm for Sequentially Composed Optimal Transports
by: Watanabe, Kazuki, et al.
Published: (2024)

A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noise
by: Diakonikolas, Ilias, et al.
Published: (2025)

Instance-Optimal Uniformity Testing and Tracking
by: Blanc, Guy, et al.
Published: (2025)

Pareto Optimal Algorithmic Recourse in Multi-cost Function
by: Chen, Wen-Ling, et al.
Published: (2025)

Oracle-efficient Hybrid Learning with Constrained Adversaries
by: Okoroafor, Princewill, et al.
Published: (2026)

Efficient and Provable Algorithms for Covariate Shift
by: Adil, Deeksha, et al.
Published: (2025)

Testing Noise Assumptions of Learning Algorithms
by: Goel, Surbhi, et al.
Published: (2025)

Algorithms with Calibrated Machine Learning Predictions
by: Shen, Judy Hanwen, et al.
Published: (2025)

A Faster $k$-means++ Algorithm
by: Liang, Jiehao, et al.
Published: (2022)

Approximation Algorithms for D-optimal Design
by: Singh, Mohit, et al.
Published: (2018)

Online Algorithms with Limited Data Retention
by: Immorlica, Nicole, et al.
Published: (2024)

Approximation Algorithms for Combinatorial Optimization with Predictions
by: Antoniadis, Antonios, et al.
Published: (2024)

Learning-Augmented Algorithms with Explicit Predictors
by: Elias, Marek, et al.
Published: (2024)