Gradient-Free Warm-Start Library Recovery: an Amortized-Regret Separation

• URL: http://arxiv.org/abs/2606.21253v1
• Date: Fri, 19 Jun 2026 09:30:55 GMT
• Title: Gradient-Free Warm-Start Library Recovery: an Amortized-Regret Separation
• Abstract summary: Continual learning that is gradient-free, local, online, and append-only is attractive for edge and streaming deployment.<n>We give a provable account on recurring-regime streams.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Continual learning that is gradient-free, local, online, and append-only is attractive for edge and streaming deployment, but its value is usually argued informally. We give a provable account on recurring-regime streams. Given segmentation, a warm-start library learner attains amortized recovery cost $O\!\big(KD/\varepsilon^2+(R-K)\logK/Δ^2\big)$ versus a memoryless re-estimator's $Θ(RD/\varepsilon^2)$, an advantage $(R-K)\,Θ(D/\varepsilon^2)$ growing with dimension $D$ and recurrence density. The mechanism is a decoupling: recognizing which of $K$ seen regimes is active costs $O(\log K/Δ^2)$, independent of $D$, whereas estimating a regime costs $Θ(D/\varepsilon^2)$. We prove this is tight: matching lower bounds give recognition $Θ(\log K/Δ^2)$ and a memoryless-class bound $Ω(RD/\varepsilon^2)$, so each term is individually minimax-tight (the joint statement is conditional). The separation is born-immune (a memoryless learner's advantage is identically zero) and paradigm-level: it matches, and does not beat, a fair spawn-capable Bayesian baseline; the contribution is attaining this cost structure without end-to-end backprop and with zero forgetting by construction. A count-calibrated variant ties the baseline's leading constant up to a bounded, never-negative per-recurrence overshoot, hyperparameter-free and with no per-step transcendentals. We bound the scope: recognizable regimes are capped by simplex packing (walls $e^{Θ(D)}$); autonomous segmentation is impossible at the packing wall (no detector escapes the false-alarm/delay frontier as regimes overlap); the advantage vanishes under overlap. The dimension-dependent separation is corroborated on synthetic streams and real $k$-mer genome distributions (memoryless cost $\propto D^{1.04}$, recognition $D$-independent); the one real sequential stream sits in the $D{=}1$ near-null corner.

Related papers

• Sharp Minimax Regret for Infinite-Memory Logistic Prediction [55.29259818039367]
  Lag $j$ can affect prediction by scale $r_j$ and enters only $n_T,j=T-j+1$ prediction rounds.<n>For every summable envelope, a localized mixture proves $cR_T(r)leq C_T(r)$.<n>For exponential and envelopes, under the stated finite-sample condition, a Toeplitz-design converse proves $cR_T(r)geq c_T(r)$.
  arXiv  Detail & Related papers  (2026-08-27T01:31:46Z)
• The Sharp Tail of Uniform Stability [1.14219428942199]
  Uniform stability controls how much one training example can change the loss at any test point.<n>A new logarithmic-free upper bound shows that a $$-uniformly stable algorithm with loss in $[0,L]$ has generalization gap at most $O left(log(1/) +Lsqrtfraclog (1/)nright)$ with probability $1-$.
  arXiv  Detail & Related papers  (2026-08-25T05:53:31Z)
• The Sample Complexity of Fidelity Estimation to a Known Rank-$r$ Reference State Is $\widetildeΘ(r^2/\varepsilon^2)$ [0.0]
  We prove a near-quadratic lower bound $widetilde(r2)$ for quantum spectrum estimation at constant accuracy.<n>We also prove a near-quadratic lower bound $widetilde(r2)$ for quantum spectrum estimation at constant accuracy.
  arXiv  Detail & Related papers  (2026-08-03T06:43:01Z)
• Optimal Dimension-Free Sampling for Regularized Classification [56.72526267755301]
  We prove optimal sampling bounds achieving $(1pmvarepsilon)$-relative error for a broad class of Lipschitz continuous classification loss functions.<n>This includes important functions such as logistic and sigmoid loss, hinge loss, and ReLU loss, as prominent and popular representative examples.
  arXiv  Detail & Related papers  (2026-05-22T15:05:33Z)
• Trade-off Functions for DP-SGD with Subsampling based on Random Shuffling: Tight Upper and Lower Bounds [7.787109481104569]
  We derive a tight analysis of the trade-off function for Differentially Private Gradient Descent (DP-SGD) with subsampling based on random shuffling.<n>Our concrete bounds, derived via the Berry-Esseen theorem, are tight up to constant factors within the proof framework.
  arXiv  Detail & Related papers  (2026-05-07T13:35:43Z)
• Online Realizable Regression and Applications for ReLU Networks [14.292982828097465]
  We study realizable online regression in the adversarial model under losses that satisfy an approximate triangle inequality (approximate pseudo-metrics)<n>Our main contribution is a generic potential method that upper bounds $mathbbD_mathrmonl$ by a concrete Dudley-type entropy integral.
  arXiv  Detail & Related papers  (2026-02-22T13:02:25Z)
• Robust learning of halfspaces under log-concave marginals [6.852292115526837]
  We give an algorithm that learns linear threshold functions and returns a classifier with boundary volume $O(r+varepsilon)$ at radius perturbation $r$.<n>The time and sample complexity of $dtildeO (1/varepsilon2)$ matches the complexity of Boolean regression.
  arXiv  Detail & Related papers  (2025-05-19T20:12:16Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  Under nonlinear measurements, most prior results are non-uniform, i.e., they hold with high probability for a fixed $mathbfx*$ rather than for all $mathbfx*$ simultaneously. Our framework accommodates GCS with 1-bit/uniformly quantized observations and single index models as canonical examples. We also develop a concentration inequality that produces tighter bounds for product processes whose index sets have low metric entropy.
  arXiv  Detail & Related papers  (2023-09-25T17:54:19Z)
• Optimal Sketching Bounds for Sparse Linear Regression [116.30196615349226]
  We study oblivious sketching for $k$-sparse linear regression under various loss functions such as an $ell_p$ norm, or from a broad class of hinge-like loss functions. We show that for sparse $ell$vareps regression, there is an oblivious distribution over sketches with $Theta(klog(d/k)/varepsilon2)$ rows, which is tight up to a constant factor. We also show that sketching $O(mu2 klog(mu n d/varepsilon)/var
  arXiv  Detail & Related papers  (2023-04-05T07:24:19Z)
• Sparse Signal Detection in Heteroscedastic Gaussian Sequence Models: Sharp Minimax Rates [1.0309387309011746]
  We study the signal detection problem against sparse alternatives, for known sparsity $s$. We find minimax upper and lower bounds over the minimax separation radius $epsilon*$ and prove that they are always matching. Our results reveal new phase transitions regarding the behavior of $epsilon*$ with respect to the level of sparsity, to the $Lt$ metric, and to the heteroscedasticity profile of $Sigma$.
  arXiv  Detail & Related papers  (2022-11-15T23:53:39Z)
• Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes [62.90204655228324]
  We study regret minimization for reinforcement learning (RL) in Latent Markov Decision Processes (LMDPs) with context in hindsight. We design a novel model-based algorithmic framework which can be instantiated with both a model-optimistic and a value-optimistic solver.
  arXiv  Detail & Related papers  (2022-10-20T21:32:01Z)
• Sampling from Log-Concave Distributions with Infinity-Distance Guarantees and Applications to Differentially Private Optimization [33.38289436686841]
  We present an algorithm that outputs a point from a distributionO(varepsilon)$close to $$ in infinity-distance. We also present a "soft-pi" version of the Dikin walk which may be independent interest.
  arXiv  Detail & Related papers  (2021-11-07T13:44:50Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  Up to logarithmic factors the optimal excess population loss of any $(varepsilon,delta)$-differently private is $sqrtlog(d)/n + sqrtd/varepsilon n.$ We show that when the loss functions satisfy additional smoothness assumptions, the excess loss is upper bounded (up to logarithmic factors) by $sqrtlog(d)/n + (log(d)/varepsilon n)2/3.
  arXiv  Detail & Related papers  (2021-03-02T06:53:44Z)
• Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
  We consider the problem of learning the best-fitting single neuron as measured by the expected square loss. For the ReLU activation, our population risk guarantee is $O(mathsfOPT1/2)+epsilon$. For the ReLU activation, our population risk guarantee is $O(mathsfOPT1/2)+epsilon$.
  arXiv  Detail & Related papers  (2020-05-29T07:20:35Z)

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.