Cover Image

Improved and Oracle-Efficient Online $\ell_1$-Multicalibration

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Ghuge, Rohan, Muthukumar, Vidya, Singla, Sahil
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

Single-Sample and Robust Online Resource Allocation
by: Ghuge, Rohan, et al.
Published: (2025)

Semi-Bandit Learning for Monotone Stochastic Optimization
by: Agarwal, Arpit, et al.
Published: (2023)

Tradeoffs between Mistakes and ERM Oracle Calls in Online and Transductive Online Learning
by: Attias, Idan, et al.
Published: (2025)

Query-Efficient Correlation Clustering with Noisy Oracle
by: Kuroki, Yuko, et al.
Published: (2024)

Bandit Sequential Posted Pricing via Half-Concavity
by: Singla, Sahil, et al.
Published: (2023)

Online Combinatorial Allocations and Auctions with Few Samples
by: Dütting, Paul, et al.
Published: (2024)

Connectivity Oracles for Predictable Vertex Failures
by: Hu, Bingbing, et al.
Published: (2023)

Optimal bounds for $\ell_p$ sensitivity sampling via $\ell_2$ augmentation
by: Munteanu, Alexander, et al.
Published: (2024)

Integral Online Algorithms for Set Cover and Load Balancing with Convex Objectives
by: Kesselheim, Thomas, et al.
Published: (2025)

Accelerating Matroid Optimization through Fast Imprecise Oracles
by: Eberle, Franziska, et al.
Published: (2024)

Matroid Algorithms Under Size-Sensitive Independence Oracles
by: Banihashem, Kiarash, et al.
Published: (2026)

Metric $k$-clustering using only Weak Comparison Oracles
by: Raychaudhury, Rahul, et al.
Published: (2026)

Coresets for Multiple $\ell_p$ Regression
by: Woodruff, David P., et al.
Published: (2024)

Improving Online Algorithms via ML Predictions
by: Kumar, Ravi, et al.
Published: (2024)

Improved Bounds for Online Facility Location with Predictions
by: Fotakis, Dimitris, et al.
Published: (2021)

Fast White-Box Adversarial Streaming Without a Random Oracle
by: Feng, Ying, et al.
Published: (2024)

Top-k on a Budget: Adaptive Ranking with Weak and Strong Oracles
by: Oettershagen, Lutz
Published: (2026)

Sharper Bounds for $\ell_p$ Sensitivity Sampling
by: Woodruff, David P., et al.
Published: (2023)

Turnstile $\ell_p$ leverage score sampling with applications
by: Munteanu, Alexander, et al.
Published: (2024)

Online Correlation Clustering: Simultaneously Optimizing All $\ell_p$-norms
by: Davies, Sami, et al.
Published: (2025)

Sample-efficient Multiclass Calibration under $\ell_{p}$ Error
by: Bairaktari, Konstantina, et al.
Published: (2025)

Ridge Leverage Score Sampling for $\ell_p$ Subspace Approximation
by: Woodruff, David P., et al.
Published: (2024)

Efficient, Low-Regret, Online Reinforcement Learning for Linear MDPs
by: John, Philips George, et al.
Published: (2024)

Learning the Inverse Temperature of Ising Models under Hard Constraints using One Sample
by: Chauhan, Rohan, et al.
Published: (2025)

Supermodular Approximation of Norms and Applications
by: Kesselheim, Thomas, et al.
Published: (2024)

A Fixed-Parameter Tractable Algorithm for Counting Markov Equivalence Classes with the same Skeleton
by: Sharma, Vidya Sagar
Published: (2023)

The Cost of Compression: Tight Quadratic Black-Box Attacks on Sketches for $\ell_2$ Norm Estimation
by: Ahmadian, Sara, et al.
Published: (2025)

A Sublinear-Time Spectral Clustering Oracle with Improved Preprocessing Time
by: Shen, Ranran, et al.
Published: (2023)

Fitting trees to $\ell_1$-hyperbolic distances
by: Yim, Joon-Hyeok, et al.
Published: (2024)

Efficient Approximation Schemes for Stochastic Probing and Selection-Stopping Problems
by: Segev, Danny, et al.
Published: (2020)

Online Graph Balancing and the Power of Two Choices
by: Bansal, Nikhil, et al.
Published: (2026)

Online Classification with Predictions
by: Raman, Vinod, et al.
Published: (2024)

Complexity of Classical Acceleration for $\ell_1$-Regularized PageRank
by: Fountoulakis, Kimon, et al.
Published: (2026)

Oracle-based Uniform Sampling from Convex Bodies
by: Dang, Thanh, et al.
Published: (2025)

Online Prediction with Limited Selectivity
by: Liu, Licheng, et al.
Published: (2025)

Online Combinatorial Optimization with Graphical Dependencies
by: Gao, Zhimeng, et al.
Published: (2025)

Online Learning in the Random Order Model
by: Bernasconi, Martino, et al.
Published: (2025)

Online Two-Stage Submodular Maximization
by: Nikolaou, Iasonas, et al.
Published: (2025)

Transductive and Learning-Augmented Online Regression
by: Raman, Vinod, et al.
Published: (2025)

Online Weighted Paging with Unknown Weights
by: Levy, Orin, et al.
Published: (2024)