Research map / Learning theory and algorithms / Prediction and decision losses
Online Estimation via Offline Estimation: An Information-Theoretic Framework
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces Oracle-Efficient Online Estimation (OEOE), an information-theoretic framework where the learner converts black-box offline estimators into online estimators, and characterizes its minimax statistical rates and computational limits.
Problem
Whether offline estimation algorithms can be converted in a black-box way into online estimation algorithms (robust to adaptively chosen covariates), and what the statistical and computational complexity of doing so is.
Approach
Model the learner as accessing data only through a sequence of offline estimators from a black-box oracle; build a Version Space Averaging algorithm that uses the version space consistent with offline estimators and predicts by uniform sampling, achieving near-optimal O((offline param+1) log|F|) online error for finite classes, and a delayed-online-learning reduction for general classes.
Key results
- Version Space Averaging achieves online estimation error O((offline param+1) min{log|F|,|X|log T}) for finite classes, matched by a lower bound of Omega(min{(offline param+1)log|F|, ..., T}) up to log factors.
- Memoryless oracle-efficient algorithms incur Omega(min{N(offline param+1), T}) error, an exponential gap versus general algorithms.
- Under one-way function assumptions, no polynomial-time oracle-efficient algorithm achieves sublinear error for general classes, while for conditional density estimation with squared Hellinger distance computational efficiency matches unrestricted algorithms.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the full history of offline estimators and covariates rather than restricting predictions to the most recent offline estimator | Oracle-efficient online estimation · OEOE finite classes, binary classification | expected online estimation error: O((\offgan+1)\min\{\log|\cF|,|\cX|\log T\}) versus \Omega(\min\{N(\offgan+1),T\}) | Helped |
| Restrict the online estimator to depend only on the most recent offline estimator (memoryless algorithm) (ablation) | Oracle-efficient online estimation · OEOE finite classes, binary classification | expected online estimation error: \Omega ( \min \{N(\offgan+1) ,T\}) | Hurt |
| Use the offline oracle estimator directly as the online prediction | Memoryless OEOE · General metric-like estimation problem | online estimation error: O((\offgan+1)|\cX|\log T) | Mixed |
| Convert offline estimation to online estimation with Version Space Averaging | Finite-class OEOE · OEOE finite classes | online estimation error: O(C_\mathsf{D}(\offgan+1)\min\{\log|\cF|,|\cX|\log T\}) | Helped |
| Use a delayed-online-learning reduction with delay parameter N | Finite-class OEOE · OEOE finite classes | expected online estimation error: O(C_\mathsf{D}(N+\offgan T/N)+N\log|\cF|) | Mixed |
| Use polynomial-time computation rather than an unrestricted algorithm | Oracle-efficient online estimation · Polynomially computable classes | expected online estimation error: \En[\EstOnD(T)]\geq{}T/4; inefficient algorithm: \En[\EstOnD(T)]\leq{}O(\sqrt{n}) | Hurt |
| Reduce an unrestricted conditional-density online estimator to an oracle-efficient estimator | Conditional density estimation · Conditional density estimation (squared Hellinger) | expected online estimation error: \wt{O}(C_{\cF}\log V\cdot\offgan T/N+N(\RCDE(T)+C_{\cF}\log V)) | Helped |
Surprising findings
- Memoryless oracle-efficient algorithms cannot achieve low online error, even when allowed to remember past estimators, exhibiting an exponential gap from general algorithms.
- Computational hardness: under one-way functions, no polynomial-time oracle-efficient online estimator exists even though offline estimation is efficient.
Limitations
- Main finite-class upper bound is computationally inefficient (version space enumeration).
- Infinite-class results lose rates relative to offline, and the conditional density reduction requires high-probability base guarantees and bounded likelihood ratio V.
Experimental setup
Metrics: cumulative online estimation error
Baselines: exponential weights halving algorithm
Builds on: halving algorithm exponential weights delayed online learning Estimation-to-Decisions
Closest papers by meaning
- Off-policy estimation with adaptively collected data: the power of online learning (NeurIPS 2024 · similarity 0.87)
- Leveraging Offline Data in Linear Latent Contextual Bandits (ICML 2025 · similarity 0.86)
- Information-Directed Offline-to-Online Reinforcement Learning (NeurIPS 2026 · similarity 0.86)
- On The Statistical Complexity of Offline Decision-Making (ICML 2024 · similarity 0.85)
- Direction-Aware Offline-to-Online Learning in Linear Contextual Bandits (NeurIPS 2026 · similarity 0.85)
- Contextual Online Pricing with (Biased) Offline Data (NeurIPS 2025 · similarity 0.85)
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.