CS Paper Radar

Robust Model Order Selection via Dithered Differential Step-Down Thresholding

Aleksandr Kharin

eess.SP math.ST ·submitted 2026-08-30 15:55 UTC · v3
theory

Abstract

We propose a dithered differential step-down thresholding (DSDT) algorithm for robust model order selection in stationary noise. Evaluating only exceedance counts over a decreasing threshold grid, the proposed algorithm stops when detecting noise extrema value clustering. We prove that deterministic threshold grids are inconsistent under lowered floor detection thresholds due to threshold grid misalignment error. We bound this error using randomized grid dithering. For arbitrary deterministic shifts, any joint noise distribution, and data-dependent thresholds, we obtain non-asymptotic bounds on the estimation risk and family-wise error rate, establishing DSDT as a universal false alarm suppressor for any single-threshold algorithm. When the scale sequence tends to zero or extremes cluster along the search grid, DSDT achieves asymptotic exact order recovery of separated deterministic components exceeding the noise maximum plus the grid step, even below the minimax threshold or without a detection threshold. Using multiple independent dithers reduces error bounds. We provide convergence and consistency analysis for an arbitrary number of dithers. This analysis establishes asymptotic bounds under extreme value laws and non-asymptotic bounds under nondecreasing hazard rates. The results extend to unseparated deterministic shifts, random shifts, unknown noise scales, and multi-dimensional search grids. We show that DSDT is robust to data quantization.

Comment
major rev3

Closest papers

Nearest neighbours by meaning across the whole index.

On the VC Dimension of Autoregressive Linear Threshold Functions

cs.LG ·2026-10-27 ·Ilan Doron-Arad, Idan Mehalel, Elchanan Mossel
theory similarity 0.52
Abstract

Linear threshold functions (LTFs) are a canonical class of Boolean predictors. In the autoregressive setting, the same LTF reads the most recent $d$ bits, generates the next bit, and returns the bit produced after $T$ steps. While the one-step class has VC dimension $d$, for general $T$ the counting upper bound is $O(d^2)$. We prove that the VC dimension is $Θ(d^2)$ for every $T\ge d^2$, resolving the quadratic gap for deterministic autoregressive LTFs. We then adapt the same technique to show an exponential separation between deterministic and stochastic autoregressive models: replacing the sign of LTFs by logistic sampling can increase the VC dimension of the final majority prediction class from quadratic to exponential in $d$.

0.50

Robust Satisficing Ensemble: Scalable Model Aggregation Under Distribution Shifts

cs.LG cs.AIstat.ML ·2026-11-07 ·Ahmet Faruk Cetinkaya, Enes Agirman, Cem Tekin
top venuetheory similarity 0.52
Abstract · Accepted at NeurIPS 2026 (Spotlight)

Standard ensemble methods can improve robustness by mitigating individual model stochasticity, but they frequently fail to generalize beyond the training distribution, leaving systems vulnerable to out-of-distribution (OOD) data. We introduce the Robust Satisficing Ensemble (RSE), a scalable probabilistic aggregation framework designed to secure model combinations by minimizing their fragility against distributional changes. By bridging a robust satisficing objective with a quadratic risk surrogate, RSE derives an analytical inner adversary. This fundamental reformulation enables highly efficient weight updates without the computational bottleneck of standard minimax optimization, crucially decoupling optimization complexity from sample size to scale effectively to large datasets. In particular, we prove a geometrically decaying truncation error for the fragility approximation via Lagrange-Burmann expansion and establish stationarity guarantees for RSE. We evaluate RSE across a comprehensive spectrum of distribution shifts, including adversarial label shift (SST-5, TREC), natural subpopulation and temporal shifts (CivilComments, HuffPost). Our results demonstrate that RSE consistently outperforms strong robust baselines, including GroupDRO, IRM, and SRM. These findings establish RSE as a practical, theoretically grounded safeguard for reliable model aggregation in dynamic environments.

0.43

Calibrating Ambiguity Set via Diagnostic Transport for Distributionally Robust Optimization

cs.LG stat.MLmath.OC ·2026-10-07 ·Wenbin Zhou, Elizabeth Cucuzzella, Shixiang Zhu
similarity 0.51
Abstract

Distributionally robust optimization (DRO) protects decisions against distributional uncertainty by optimizing over an ambiguity set, but poorly aligned set geometry can require large radii and yield overly conservative decisions. We introduce diagnostic-transport DRO (DT-DRO), which uses held-out calibration data to adapt the ambiguity-set geometry to observed predictive errors. DT-DRO uses the conditional probability integral transform cumulative distribution function to diagnose systematic probability misallocation and translates this information into an outcome-level transport that jointly adjusts the ambiguity-set center and ground cost. The resulting formulation admits a computationally tractable dual reformulation. Theoretically, we derive valid ambiguity radii and decision-risk guarantees that tighten as estimation and approximation errors vanish, and show that DT-DRO can eliminate the nonvanishing robustness floor caused by model misspecification. Synthetic experiments and a power-outage application demonstrate improved decision quality, particularly under structural and tail misspecification.

0.22

Response-Threshold Framework for First-Peak Preservation in Noisy Grover Search

cs.ET quant-ph ·2026-11-16 ·Ge Zhong, Charith Jayasekara, Nisal De Silva, Chetan Arora
hot direction similarity 0.50
Abstract · 35 pages, 9 figures, 7 tables

Grover search is executed only after integer iterations, so noise can alter the stopping decision even when a continuous first peak remains visible. We develop a response-threshold framework separating continuous peak motion, stroboscopic geometry, and the discrete sampled-success argmax. For a Drude-Lorentz environment, linearized HEOM supplies an a priori timing coefficient and sampled-probability differentials. The first-order layer is used as a conservative screen: well-separated points retain the nominal step, whereas near-threshold points escalate to finite-$λ$ evaluation. Across 260 unique HEOM points drawn from five overlapping validation sets, it detects all 15 observed stopping changes with zero regret on the changed subset; its residual errors are 45 one-step-early calls on otherwise stable points; the 245-point stable subset has mean regret $4.42\times10^{-3}$. An empirically validated two-stage workflow escalates every observed change while avoiding 160 of 260 unique full-HEOM propagations. Same-bath NZ2 reduces early calls. A heterogeneous three-qubit circuit exhibits three stopping-transition scales, each replicated across eight marked targets, and finite-shot recovery is 96.18% overall, with failures localized to a near-degenerate boundary at $s=1.5$. A depth-refined transfer test supports the predicted local quadratic timing-to-loss relation.

0.58

SparseMax-dSTL: Sound Robustness with Horizon-Independent Gradient Allocation for Temporal Logic Trajectory Optimization

eess.SY cs.LOcs.RO ·2026-10-16 ·Sai Sandeep Damera, Ryan Matheu, John S. Baras, Calin Belta
theory similarity 0.50
Abstract · 8 pages, 5 figures. This work has been submitted to the IEEE for possible publication

A gradient-based solver that enforces a Signal Temporal Logic (STL) specification uses a smooth approximation of its quantitative semantics, the robustness. In safety-critical trajectory optimization, this approximation must have two properties. First, it must be sound, that is, nonnegative only on trajectories that satisfy the specification. Second, at each temporal operator, the weight of its gradient on the violating samples must stay bounded away from zero, however long the horizon. The approximations in use, including the log-sum-exp, its sound variant, and the generalized-mean robustness, do not have both. We introduce lower approximations of the minimum and the maximum whose gradients are sparsemax projections, and we prove that the robustness built from them has both. It lies below the exact robustness and is therefore sound, and its error has a bound that is independent of the number of samples and known before optimization. The gradient of each approximation is exactly zero on every sample beyond a data-dependent threshold, so the weight on violating samples a gap beyond the others has a positive lower bound at every horizon. On a planar unicycle and on a seven-joint manipulator beside a person in simulation, the log-sum-exp approximation is positive on a violating trajectory. As the horizon of the manipulator's task grows from 10 to 80 s, the gradient weight of the sound variant on the violating samples falls from 0.22 to 0.04, while that of sparsemax stays at 1. In a constrained trajectory optimization of the unicycle, the constraint on the log-sum-exp robustness returns a violating trajectory, whereas the constraint on the sparsemax robustness returns a trajectory that satisfies the specification with the required margin.

0.20

Certify or Refuse: A Cross-Model Map for Selective Risk Control with Coverage Floors under Covariate Shift

cs.CL ·2026-08-11 ·Jiamiao Liu, Dewen Qiao, Yu Zhang, Xuetao Chen
theory similarity 0.50
Abstract

Certified selective predictors attain whatever coverage they attain; operators impose an automation floor: answer at least a $β$-fraction of shifted target traffic with at most an $α$-fraction of answers wrong. Under bounded-ratio covariate shift we prove the Floor Certification Map: once that floor must be certified alongside the selection-conditioned risk $α$, certification acquires a feasibility frontier and a two-resource complexity map, additive up to constants: risk in labeled source, the floor in unlabeled target samples. The rates are local, needing a regular frontier margin, slack below the local-regime threshold, and lattice conditions: pre-registered with a lattice margin for the upper bounds, compatible per-slack for the lower. The displayed split is the operational route; oracle weights also allow a labeled-source floor estimate. Three model-tagged results: a lower bound (Model-B), a matching oracle-weight upper bound (Model-A), and an implementable upper bound (Model-B') valid under a pre-registered exact stratified-shift model with nuisance cost priced explicitly. The match is across these models rather than a single-model minimax theorem, and necessarily so: over the full bounded-ratio class no unknown-weight procedure matches at any sample size (Model-B is inconsistent, witnessed at $α=β=1/2$). The nuisance's necessity is only partially settled. Complexity tracks a localized accepted-region functional, not global effective sample size (ESS), on both sides, though a fixed-ESS separation theorem is left open; both lower-bound axes vanish as $β\to0$, so the floor creates the map. Empirically, the registered bite family diverges with log-log slope $-2.002$ within its pre-registered band; a 1,024-cell audit records 0 violations where the formal certificates fire; and a single-corpus SQuAD-to-NewsQA feasibility audit returns honest refusal.

0.34

Distinguishability and Recovery for a Doubly Sparse Spiked Wigner Model

cs.LG stat.ML ·2026-10-16 ·Ioana Dumitriu, JD Flynn, Zhichao Wang
similarity 0.50
Abstract · 50 pages, 9 figures, 8 tables

We study distinguishability and recovery of a sparse rank-one signal in a spiked Wigner model with independently sparse noise through a variety of algorithms and parameter regimes. The signal and noise have separate sparsity parameters, while the signal-to-noise ratio (SNR) remains of constant order as the matrix size grows. For sub-Gaussian noise and spikes whose nonzero coordinates are bounded away from zero, a leave-one-out quadratic thresholding procedure (a generalization of Ding et al., 2024) identifies the support. Sign synchronization yields exact recovery for a Rademacher spike, and spectral refinement yields strong recovery. The quadratic thresholding search parameter gives an explicit tradeoff between signal sparsity, noise sparsity, and computational cost. We also study extensions to sub-Gaussian spike priors through diagonal and quadratic thresholding. For Rademacher spikes with continuous nonzero noise, we develop an identical search algorithm that exploits unblurred signal entries, the existence of which permits distinguishability; connectivity of the graph they reveal provides a sufficient condition for exact recovery. These guarantees do not require moment assumptions on the continuous noise distribution. Together with our previous PCA results (Dumitriu et al., 2026), our analysis covers almost the entire space of parameters and regimes for distinguishing and recovering in our doubly sparse spiked Wigner model.

0.35

Local Sensitivity in Exponential Selection: Failure Modes and Valid Calibrations

cs.DS cs.CR ·2026-10-08 ·Dung Nguyen, Anil Vullikanti
theoryhot direction similarity 0.50
Abstract

Selection is a task that chooses one element from a finite public candidate range to maximize a data-dependent score. In differential privacy (DP), the exponential mechanism (EM) samples a candidate at a temperature calibrated to the global sensitivity. In this paper, we study when dataset-dependent sensitivity can safely replace global sensitivity in private selection. We propose three valid approaches. First, a private, high-probability upper bound on local sensitivity yields approximate DP, and the method extends to finite higher-order sensitivity hierarchies. Second, our Propose-Test-Release (PTR) variant privately searches a finite public grid for a temperature scale rather than fixing it in advance. Third, smooth sensitivity supports several designs. A candidate-independent smooth geometric construction produces a sensitivity envelope that is admissible under the local dampening framework, which privacy is guaranteed for any admissible envelope. Additionally, a separate logarithmic transformation utilizes smooth sensitivity to produce a smoothed candidate score function with advantages: having controlled global sensitivity, and preserving the maximizers of the original utility score, i.e., candidates maximizing the utility. Both of the designs yield range-independent pure DP. Besides that, we also give two approximate DP private selectors using smooth sensitivity: a direct EM with smooth sensitivity calibrated to the candidate range and privacy parameters that matches a theoretical lower bound up to some constant factor, and one using a privatized smooth upper scale by analyzing the logarithmic transform of the smoothness. For every proposed mechanism, we derive a high-probability regret bound under its stated conditions.

0.31