The Cost of Adaptivity: Matching Lower Bounds Across Learning Problems

• URL: http://arxiv.org/abs/2608.08826v1
• Date: Sun, 09 Aug 2026 17:19:11 GMT
• Title: The Cost of Adaptivity: Matching Lower Bounds Across Learning Problems
• Abstract summary: We formalize nuisance adaptation via a slice-normalized minimax ratio.<n>We also define the cost of expanding from one preannounced Gaussian query to arbitrary post-hoc inspection.
• Score: 1.0742675209112622
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Adaptive procedures must work without nuisance information an oracle may use, such as a gradient scale or smoothness index, and robust procedures may have to answer queries whose coordinate and inspection time are chosen only after the data are seen. Such comparisons are meaningful only when the oracle advantage and validity contract are stated explicitly. We formalize nuisance adaptation via a slice-normalized minimax ratio retaining the worst-case instance within each nuisance slice, and separately define the robustness cost of expanding from one preannounced Gaussian query to arbitrary post-hoc inspection. Our main result is a finite-horizon composition law for Gaussian certification: from M independent coordinates, a familywise certifier protecting every coordinate and time up to T pays optimal normalized squared half-width of order log(eM) + log log(e^eT), within the sample-mean-centered rectangular class. Epoch stitching gives the upper bound; independent Gaussian block increments across coordinates and geometric time scales give a matching lower bound, already holding on a geometric checkpoint grid, forcing quantiles of the realized maximum width so selection and stopping taxes add. Two benchmark regimes complete the picture: unknown gradient scale in online convex optimization has constant cost, while pointwise adaptation over nested Holder classes costs order (log n / log log n)^(s1/(2s1+1)). Cast as model monitoring, the law lets an analyst inspect any of M slice metrics at any data-dependent time: the naive fixed-query band's selected coverage degrades sharply, to 0.30 at M=1 and to zero for M>=10, while the epoch-stitched certifier holds familywise coverage at an additive iterated-logarithm width cost. Experiments put both sharp predictions at risk of refutation; both survive.

Related papers

• Observation Design for Certified Control Authority: Projection--Estimability Separation and Active-Face Equivalence [2.7954473524479275]
  A gate executes only actions it can certify, and certifies only what its observations support.<n>This paper asks how observations should be designed to maximize the set of actions that can be safely admitted.
  arXiv  Detail & Related papers  (2026-09-05T07:57:04Z)
• DualCert: A Solver for the Traveling Salesman Problem with Constraint-Coupled Learning [4.941039246565574]
  Large traveling salesman problem (TSP) instances require a solver to allocate limited computation while preserving the validity of its outputs.<n> DualCert introduces emphconstraint-coupled learning, in which current degree equations and dynamically separated subtour-elimination constraints define each learned transition.<n>On 1,000 held-out TSP1000 instances, DualCert attains a mean tour-cost gap of (0.0573%) from Lin--Kernighan--Helsgaun version 3 (LKH-3) reference tours in (9.55) batch-amortized seconds per instance
  arXiv  Detail & Related papers  (2026-08-10T02:48:16Z)
• Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions [51.50375419691955]
  Distributionally robust Markov decision processes provide a principled framework for sequential decision making under model uncertainty.<n>We study how many samples are necessary and sufficient to learn an $varepsilon$-optimal robust policy under the average-reward criterion.
  arXiv  Detail & Related papers  (2026-08-06T19:49:48Z)
• Filtered Conformal Ellipsoids for Graph-Native Time Series [0.8460698440162889]
  We use a filter to choose the ellipsoid shape; conformal calibration chooses the scalar radius.<n>We analyse contraction in an observable predictive-law quotient.<n>We instantiate the framework with a GCN-GRU filter with diagonal-plus-low-rank covariance.
  arXiv  Detail & Related papers  (2026-06-15T17:46:19Z)
• Filtered ANN as a Phase Transition: When Selectivity-Estimation Error Causes Plan Regret [0.0]
  We show that selectivity-estimation error produces plan regret -- recall lost versus the oracle strategy -- only in the critical regions around those boundaries.<n>A real approximate index does not mis-locate the boundary, but a biased cost model opens a persistent miscalibration band that estimation-error robustness cannot fix.
  arXiv  Detail & Related papers  (2026-06-15T07:44:58Z)
• Measuring the Symmetry--Data Exchange Rate [0.2538209532048867]
  We show that a wrong-group control with identical orbit size and matched compute is worse than no constraint.<n>Relative exchange rate beta_diff = 1.28 is consistent in sign and order of magnitude with the theoretical bootstrap 1.0.<n>The methodological contributions -- the relative-rate estimator that cancels the shared-difficulty confound, the wrong-group control, and a pre-specified failure taxonomy -- transfer to any inductive bias whose strength can be parameterised.
  arXiv  Detail & Related papers  (2026-05-31T08:17:40Z)
• Correction and Corruption: A Two-Rate View of Error Flow in LLM Protocols [51.56484100374058]
  We propose a paired-outcome measurement interface for auditing a single protocol step on exact-match tasks.<n>For each instance, the interface records a baseline correctness bit and a post-step correctness bit.<n>These rates predict accuracy changes and define a reusable empirical interface testable across seeds, mixtures, and pipelines.
  arXiv  Detail & Related papers  (2026-04-20T13:25:40Z)
• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  A fundamental and long-standing challenge is their efficient approximation.<n>We develop a linear-space algorithm that requires $P(|hatboldsymbol-boldsymbol|_2geq)leq $ for all commonly used semi-values.<n>Our algorithm allows explicit minimization of the mean square error for each specific utility function.
  arXiv  Detail & Related papers  (2026-04-09T16:38:14Z)
• Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency [90.40062452292091]
  We present the first computationally efficient algorithm for linear bandits with heteroscedastic noise. Our algorithm is adaptive to the unknown variance of noise and achieves an $tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regret. We also propose a variance-adaptive algorithm for linear mixture Markov decision processes (MDPs) in reinforcement learning.
  arXiv  Detail & Related papers  (2023-02-21T00:17:24Z)
• Normalized/Clipped SGD with Perturbation for Differentially Private Non-Convex Optimization [94.06564567766475]
  DP-SGD and DP-NSGD mitigate the risk of large models memorizing sensitive training data. We show that these two algorithms achieve similar best accuracy while DP-NSGD is comparatively easier to tune than DP-SGD.
  arXiv  Detail & Related papers  (2022-06-27T03:45:02Z)
• Screening for a Reweighted Penalized Conditional Gradient Method [20.62129327196916]
  The conditional gradient method (CGM) is widely used in large-scale sparse convex optimization. We show how to adjust the sparsity acquiring properties of a general penalized generalizers. In our experiments, we verify the aggressiveness of the screening rule by tuning the concavity of the regularizer.
  arXiv  Detail & Related papers  (2021-07-02T14:37:37Z)
• Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds [72.63031036770425]
  We propose differentially private (DP) algorithms for bound non-dimensional optimization. We demonstrate two popular deep learning methods on the empirical advantages over standard gradient methods.
  arXiv  Detail & Related papers  (2020-06-24T06:01:24Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.