An efficient black-box reduction from PQ to TDS learning for any Boolean concept class in the distribution-free setting implies hardness for TDS learning of halfspaces, while membership queries enable efficient PQ learning of halfspaces via iterative Forster transforms.
Mixed citations
Title resolution pending
Mixed citation behavior. Most common role is background (60%).
19
Pith papers citing it
Background
60% of classified citations
citation-role summary
background 5
citation-polarity summary
verdicts
UNVERDICTED 19roles
background 5representative citing papers
Non-asymptotic decomposition of conditional miscoverage in conformal prediction into score-estimation error, finite-sample calibration error, and intrinsic conditional-mismatch error, with guidance for model selection and extensions to covariate shift and structured data.
Temporal correlations from lazy random walks enable efficient SGD learning of k-juntas via temporal-difference loss on ReLU networks, achieving linear sample complexity in d.
Stochastic integer optimization has sample complexity that matches, undercuts, or exceeds the continuous case based on objective structure, with new tight bounds for nonconvex continuous problems.
A dynamic pruning reduction from agnostic to realizable online learning via weak-consistency oracles achieves O(T^{d_VC+1}) query complexity with near-optimal regret and supplies matching upper and lower bounds on the regret-oracle tradeoff.
Derives loss-to-TV bounds providing probabilistic guarantees for GFlowNets and introduces Stable GFlowNets algorithm for improved training stability and distributional fidelity.
An efficient algorithm recovers phylogenetic trees from Θ(n) noisy quartets under random classification noise, matching the information-theoretic lower bound and achieving near-optimal quartet distance.
SGD is reformulated via a master equation from discrete updates, producing a discrete Fokker-Planck equation that predicts non-stationary variance growth proportional to learning rate in flat Hessian directions.
A fair conformal classification method guarantees conditional coverage on adaptively identified subgroups defined via learned representations.
Novel non-asymptotic uniform error bounds are derived for kernel regression under broad classes of non-Gaussian noise distributions that include correlated cases.
Triplet constraints realizable in D-dimensional Euclidean space cannot be preserved above 50% accuracy by any embedding of dimension at most cD for constant c<1, with UGC-hardness preventing better polynomial-time solutions in any dimension.
Clipped least-squares importance fitting enables weighted conformal prediction to achieve dataset-conditional coverage guarantees under unbounded covariate shifts by bounding undercoverage and estimating a corrective inflation factor from data.
StCP leverages transfer learning to stabilize the size of conformal prediction sets without additional target labels.
PAC-Bayes bounds for Gibbs posteriors are obtained via singular learning theory, producing explicit and tighter posterior-averaged risk bounds that adapt to data structure in overparameterized models.
SPIN lets weak LLMs become strong by self-generating training data from previous model versions and training to prefer human-annotated responses over its own outputs, outperforming DPO even with extra GPT-4 data on benchmarks.
Return-conditional diffusion models for policies outperform offline RL on benchmarks by circumventing dynamic programming and enable constraint or skill composition.
Bayesian inverse problem with diffusion model priors for CML-based rain field reconstruction outperforms baselines by preserving rainfall statistics better than Gaussian processes.
A GNN learns edge probabilities to prioritize paths in Ford-Fulkerson, reducing augmentations while keeping max-flow/min-cut optimality.
The paper motivates stochastic optimization problems from statistical perspectives and describes offline and online approaches to solve expectation minimization problems.
citing papers explorer
-
Equivalence of Coarse and Fine-Grained Models for Learning with Distribution Shift
An efficient black-box reduction from PQ to TDS learning for any Boolean concept class in the distribution-free setting implies hardness for TDS learning of halfspaces, while membership queries enable efficient PQ learning of halfspaces via iterative Forster transforms.
-
A Unified Theory of Conditional Coverage in Conformal Prediction with Applications
Non-asymptotic decomposition of conditional miscoverage in conformal prediction into score-estimation error, finite-sample calibration error, and intrinsic conditional-mismatch error, with guidance for model selection and extensions to covariate shift and structured data.
-
The Benefits of Temporal Correlations: SGD Learns k-Juntas from Random Walks Efficiently
Temporal correlations from lazy random walks enable efficient SGD learning of k-juntas via temporal-difference loss on ReLU networks, achieving linear sample complexity in d.
-
Sample Complexity of Stochastic Optimization with Integer Variables
Stochastic integer optimization has sample complexity that matches, undercuts, or exceeds the continuous case based on objective structure, with new tight bounds for nonconvex continuous problems.
-
Regret-Oracle Complexity Tradeoffs in Agnostic Online Learning
A dynamic pruning reduction from agnostic to realizable online learning via weak-consistency oracles achieves O(T^{d_VC+1}) query complexity with near-optimal regret and supplies matching upper and lower bounds on the regret-oracle tradeoff.
-
Stable GFlowNets with Probabilistic Guarantees
Derives loss-to-TV bounds providing probabilistic guarantees for GFlowNets and introduces Stable GFlowNets algorithm for improved training stability and distributional fidelity.
-
Optimal Phylogenetic Reconstruction from Sampled Quartets
An efficient algorithm recovers phylogenetic trees from Θ(n) noisy quartets under random classification noise, matching the information-theoretic lower bound and achieving near-optimal quartet distance.
-
Why SGD is not Brownian Motion: A New Perspective on Stochastic Dynamics
SGD is reformulated via a master equation from discrete updates, producing a discrete Fokker-Planck equation that predicts non-stationary variance growth proportional to learning rate in flat Hessian directions.
-
Fair Conformal Classification via Learning Representation-Based Groups
A fair conformal classification method guarantees conditional coverage on adaptively identified subgroups defined via learned representations.
-
On Uniform Error Bounds for Kernel Regression under Non-Gaussian Noise
Novel non-asymptotic uniform error bounds are derived for kernel regression under broad classes of non-Gaussian noise distributions that include correlated cases.
-
Provable Accuracy Collapse in Embedding-Based Representations under Dimensionality Mismatch
Triplet constraints realizable in D-dimensional Euclidean space cannot be preserved above 50% accuracy by any embedding of dimension at most cD for constant c<1, with UGC-hardness preventing better polynomial-time solutions in any dimension.
-
Weight Clipping for Robust Conformal Inference under Unbounded Covariate Shifts
Clipped least-squares importance fitting enables weighted conformal prediction to achieve dataset-conditional coverage guarantees under unbounded covariate shifts by bounding undercoverage and estimating a corrective inflation factor from data.
-
Stable Localized Conformal Prediction via Transduction
StCP leverages transfer learning to stabilize the size of conformal prediction sets without additional target labels.
-
PAC-Bayes Bounds for Gibbs Posteriors via Singular Learning Theory
PAC-Bayes bounds for Gibbs posteriors are obtained via singular learning theory, producing explicit and tighter posterior-averaged risk bounds that adapt to data structure in overparameterized models.
-
Self-Play Fine-Tuning Converts Weak Language Models to Strong Language Models
SPIN lets weak LLMs become strong by self-generating training data from previous model versions and training to prefer human-annotated responses over its own outputs, outperforming DPO even with extra GPT-4 data on benchmarks.
-
Is Conditional Generative Modeling all you need for Decision-Making?
Return-conditional diffusion models for policies outperform offline RL on benchmarks by circumventing dynamic programming and enable constraint or skill composition.
-
Bayesian Rain Field Reconstruction using Commercial Microwave Links and Diffusion Model Priors
Bayesian inverse problem with diffusion model priors for CML-based rain field reconstruction outperforms baselines by preserving rainfall statistics better than Gaussian processes.
-
Graph Neural Network-Informed Predictive Flows for Faster Ford-Fulkerson and PAC-Learnability
A GNN learns edge probabilities to prioritize paths in Ford-Fulkerson, reducing augmentations while keeping max-flow/min-cut optimality.
-
Stochastic Optimization and Data Science
The paper motivates stochastic optimization problems from statistical perspectives and describes offline and online approaches to solve expectation minimization problems.