REVIEW 3 major objections 4 minor 17 references
Distributionally Robust Coreset Selection under Covariate Shift
T0 review · 3 major / 4 minor · reviewed 2026-08-10 · deepseek-v4-flash
Pith's one-line read Coreset selection can be made robust to unknown covariate shift by minimizing an analytically computable bound on worst-case validation error, rather than the error itself.
desk verdict Useful idea, false as written: the DRCS bound's proof assumes a sum-to-n' constraint on validation weights that is not in the stated ambiguity set. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the duality gap $DG(v,w)$, the difference between the weighted training objective at the full-data solution and the weighted dual objective at the full-data dual solution. Under $\mu$-strong convexity of the regularizer, this gap controls the distance from the full-data solution to the parameters after retraining on the coreset: $\beta^*(v,w)\in B_{v,w}=\{\beta:\|\beta-\beta^*_{1_n,1_n}\|_2\le \sqrt{2/\lambda}\,DG(v,w)\}$. The proof pushes this parameter sphere through the validation set, labeling each validation point surely correct, surely incorrect, or unknown according to whether its signed margin is strictly positive, negative, or straddling zero over the whole sphere; the worst case counts every unknown point as an error. Maximizing the resulting error over the training-weight ball $W=\{w:\|w-1_n\|_2\le S\}$ and the validation-weight ball $W'=\{w':\|w'-1_{n'}\|_2\le Q\}$ yields the closed-form upper bound, and for L2 regularization the inner maximization $\max_{w\in W}DG(v,w)$ reduces to a tractable convex quadratic optimization problem.
What would settle it
On a small binary dataset, fix a coreset $v$, compute $\mathrm{WrVaEr}^{\mathrm{UB}}(v)$ from Eq. (18), then sample or enumerate weight vectors $w\in W$, retrain the logistic model for each, and evaluate weighted validation error under weights $w'\in W'$; if any retrained model exceeds the computed bound, Theorem 3.3 is false. A lighter empirical check is to build a test set whose density ratio has L2 distance from uniform larger than $S$ and see whether the measured error exceeds the certificate.
Extended reading notes
Core claim
The central claim is Theorem 3.3: for a coreset vector $v$, the worst-case weighted validation error $\mathrm{WrVaEr}(v)=\max_{w\in W}\mathrm{VaEr}(v,w)$ is bounded above by $\mathrm{WrVaEr}^{\mathrm{UB}}(v)$ given in Eq. (18). The bound is built from a set $\zeta(v)$ of validation points judged “surely correct” by comparing each point's margin against the radius $\sqrt{2/\lambda}\,\max_{w\in W}DG(v,w)$, where $DG(v,w)=P_{v,w}(\beta^*_{1_n,1_n})-D_{v,w}(\alpha^*_{1_n,1_n})$ is the duality gap between the weighted primal objective evaluated at the full-data solution and the weighted dual objective at the full-data dual solution. Strong convexity of the regularizer ensures that retrained parameters $\beta^*(v,w)$ lie inside a sphere centered at $\beta^*_{1_n,1_n}$ with that radius, so a validation point is surely correct only if its signed margin exceeds the maximal possible disturbance. The paper then turns the bound into a selection rule: remove, one at a time, the training instance that most reduces the bound, using three greedy variants that trade recomputation cost against fidelity.
Load-bearing premise
The certificate holds only if the true deployment distribution corresponds to importance weights inside an L2 ball around the uniform training and validation weights, and the proof of the bound also requires the validation weights to sum to $n'$; shifts outside those balls, or validation-weight choices violating the sum constraint, are not covered by the guarantee.
Editorial extensions
If this is right
- Any fixed coreset can be audited before retraining: evaluating Eq. (18) gives a guaranteed worst-case weighted validation accuracy over the chosen shift balls.
- Removing the instance that most reduces the bound gives a concrete construction of a robust subset, and the three proposed greedy algorithms trade recomputation cost against fidelity to that rule.
- The bound and selection procedure apply to binary classification with any strongly convex regularized objective, including kernel logistic regression and SVM.
- For deep networks, approximating the model with a neural tangent kernel or a fixed feature extractor brings the selection into the same convex regime.
- The achievable deletion ratio and the tightness of the guarantee are governed by the regularization strength $\lambda$, with stronger regularization yielding tighter parameter bounds but weaker underlying models.
Reading between the lines
- Switching the uncertainty set from an L2 ball of importance weights to a Wasserstein or KL ball would require a new worst-case computation for $\max_{w\in W}DG(v,w)$, since tractability here relies on the quadratic structure that L2 regularization creates.
- The three greedy rules are heuristics; an experiment comparing them with exhaustive search on small $n$ would show how much of the bound-minimizing objective is lost by greediness.
- The guarantee is for the validation set inside the assumed shift set, so its practical force depends on that set actually containing the deployment distribution; a shift outside the L2 balls is invisible to the certificate.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes Distributionally Robust Coreset Selection (DRCS) for choosing a training-data subset that performs well under an unknown covariate shift. The shift is modeled by L2 balls around uniform importance weights for both the training set (W, Eq. 5) and the validation set (W', Eq. 10). The central theoretical contribution is Theorem 3.3, which claims an upper bound WrVaErUB(v) on the worst-case weighted validation error, obtained by combining a model-parameter bound from a duality gap with a maximization over validation weights. The proposed algorithm greedily removes training instances that minimize this bound. Experiments on tabular data, CIFAR-10 features, and an NTK variant compare DRCS with standard coreset baselines and report both accuracy and a theoretical "Guarantee" curve.
Significance. If the bound in Theorem 3.3 were valid as stated, the paper would provide a useful pre-retraining certification tool for coresets under importance-weight uncertainty, and the greedy selection procedure would be a practical way to use that certificate. The paper is commendably concrete: it gives a complete proof outline, explicit algorithms, and extensive experimental comparisons, and the bound is derived from a duality gap rather than fitted to validation labels. However, the main theorem is currently stated for an ambiguity set that does not match the set used in the proof, and the experiments use validation weights that violate the proof's extra constraint. Because these issues affect the truth of the central guarantee and the validity of the plotted guarantee curves, the paper needs substantial revision before the claims can be accepted.
major comments (3)
- [Theorem 3.3 and Appendix C.1 (Lemma C.6)] The claimed upper bound is not established for the ambiguity set W' defined in Eq. (10). The theorem states Eq. (18) for W'={w' : ||w'-1_{n'}||_2 <= Q}, but Lemma C.6 introduces an additional constraint 1^T w'=n' (Eq. 36), and the closed form in Eq. (37) is derived from that constrained problem in Appendix C.2. The extra constraint is not cosmetic because VaEr is scale-invariant: the L2 ball without the sum constraint contains different rays from the ball intersected with the hyperplane. Concretely, take n'=2, Q=0.5, and zeta=(1,0). Equation (18) gives WrVaErUB = 1 - (1 - 0.5*sqrt(1-1/2))/2 ≈ 0.6768. The vector w'=(0.6,1.3) lies in the stated W' (distance 0.5 from (1,1)) and yields VaEr = 1 - 0.6/1.9 ≈ 0.6842 > 0.6768. Thus Theorem 3.3 is false as stated. The problem definition in Eq. (10) and the theorem statement must either include the sum-to-n' constraint, or be replaced by a guarantee that is actually valid for the unconstrained L2 ball.
- [Section 5.1 and Figures 4, 5] The experimental "Guarantee" curves are not lower bounds for the validation-weight perturbations actually used in the experiments. Section 5.1 sets validation weights to a for positive instances and 1 for negative instances, so 1^T w' = n' + n'_+(a-1), which is not equal to n' when a != 1. Since Eq. (18) and Lemma C.6 rely on the sum-to-n' constraint, the plotted guarantee does not cover the perturbations used in the accuracy comparisons. The authors should either normalize the validation weights so that their sum is n', recompute the guarantee curves under a correctly constrained W', or explicitly restrict the claim to a different perturbation model.
- [Theorem 3.3 and Eq. (19)] There is a mismatch between the stated assumption and the formulas when the regularization is not L2. The theorem assumes that rho in P_{1_n,1_n} is mu-strongly convex, but Eq. (19) and Lemma C.2 use lambda, which is only defined for the L2-regularization case rho(beta) = (lambda/2)||beta||^2. For a general strongly convex rho, Lemma A.4 would give a radius of sqrt(2/mu)(P-P*), not sqrt(2/lambda) DG. The theorem should either be stated specifically for L2 regularization or the strong-convexity parameter should be used consistently throughout.
minor comments (4)
- [General] The manuscript contains many typos and formatting errors, including "calucuration", "mehods", "valdation", "varidation", and "Fisrt". A careful proofread is needed before resubmission.
- [Figure 4 caption and Eq. (43)] The caption says the vertical axis is the weighted validation accuracy minimized with respect to w' by using Eq. (43), but Eq. (43) is about the bound and depends on the sum-to-n' constraint. The relationship between the plotted quantity and Eq. (43) should be clarified.
- [Eq. (10) and Eq. (9)] The set W' as defined is an L2 ball in R^{n'} and does not restrict w' to positive entries or exclude zero-sum vectors, although VaEr in Eq. (9) divides by the sum of w'. The paper should state positivity and rule out zero-sum weights, or explicitly restrict Q so that such cases cannot occur.
- [Section 5.2 / Algorithm 1] The text says Algorithm 1 removes the instance with the smallest DGi value, but the selection criterion is the overall upper bound WrVaErUB in Eq. (18), which also depends on the validation set through zeta. The pseudocode and the surrounding explanation should state whether DGi is being used as a surrogate and how zeta is updated after each removal.
Circularity Check
No significant circularity: Theorem 3.3's worst-case bound is derived analytically from a strong-convexity gap bound and explicit weight-set optimization, not from fitting the bound to the data it claims to predict; same-author citations are independent published lemmas.
full rationale
Walking the derivation chain, WrVaErUB(v) in Eq. (18) is obtained by (i) bounding the retrained parameter vector in the ball B_{v,w} via the duality gap (Lemma C.2, citing Hanada et al. 2023), (ii) converting that ball into per-validation-instance 'surely correct' indicators ζ(v) in Eq. (19), and (iii) maximizing the resulting weighted-error expression over validation weights in Lemma C.6. None of these steps fits a parameter to the validation labels and then reports that fit as a prediction: β*_{1n,1n} and α*_{1n,1n} are full-training solutions, max_w DG(v,w) is computed from the coreset and the assumed ambiguity ball, and the bound is an analytic function of those quantities. The same-author citations (Hanada et al. 2023, 2024) are load-bearing, but they are independently published technical lemmas with proofs rather than unverified assertions imported to force the conclusion, so they do not create circularity under the rules. The genuine caveat is a correctness gap, not circularity: Lemma C.6 solves the validation-weight maximization under the extra sum constraint 1^T w' = n' (Eq. 36), which is not part of W' as defined in Eq. (10), and the experimental perturbation (positive instances weighted a, negative instances weighted 1) does not satisfy that constraint; this means the stated theorem's guarantee may not apply to the stated ambiguity set. Because that is a mismatch between the theorem statement and its proof rather than an equivalence of the derived claim with its inputs, I find no significant circularity.
Assumptions & free parameters
free parameters (4)
- lambda (L2 regularization strength) =
per dataset via cross-validation (lambda_best, n*10^-3, n*10^-1.5, n)
- a (shift magnitude) =
1.0 to 1.05 in experiments
- S (training weight ball radius) =
sqrt(n_+)*|a-1|, S <= 1
- Q (validation weight ball radius) =
same as S
assumptions (6)
- domain assumption Strong convexity of rho and convexity of the loss in its second argument
- standard math Duality gap parameter bound from Hanada et al. (2023)
- domain assumption True test density ratios lie in the L2 ball W = {w: ||w-1_n||_2 <= S}
- domain assumption Validation set D' follows the same distribution as the training set
- standard math Fenchel duality and strong duality for the regularized ERM problem
- domain assumption Full-data dual solution alpha*_{1n,1n} is feasible for every reduced dual D_{v,w}
Cite this review
Pith. "Pith review of Distributionally Robust Coreset Selection under Covariate Shift." pith.science (2026). https://pith.science/paper/YQGX2UTF
@misc{pith2026250114253,
author = {Pith},
title = {Pith review of: Distributionally Robust Coreset Selection under Covariate Shift},
year = {2026},
howpublished = {\url{https://pith.science/paper/YQGX2UTF}},
note = {Machine review of arXiv:2501.14253}
}
read the original abstract
Coreset selection, which involves selecting a small subset from an existing training dataset, is an approach to reducing training data, and various approaches have been proposed for this method. In practical situations where these methods are employed, it is often the case that the data distributions differ between the development phase and the deployment phase, with the latter being unknown. Thus, it is challenging to select an effective subset of training data that performs well across all deployment scenarios. We therefore propose Distributionally Robust Coreset Selection (DRCS). DRCS theoretically derives an estimate of the upper bound for the worst-case test error, assuming that the future covariate distribution may deviate within a defined range from the training distribution. Furthermore, by selecting instances in a way that suppresses the estimate of the upper bound for the worst-case test error, DRCS achieves distributionally robust training instance selection. This study is primarily applicable to convex training computation, but we demonstrate that it can also be applied to deep learning under appropriate approximations. In this paper, we focus on covariate shift, a type of data distribution shift, and demonstrate the effectiveness of DRCS through experiments.
Figures
Figures from the paper (9 more)
Reference graph
Works this paper leans on
-
[1]
splice”). • In the table, the column “d
and detailed setups are as follows: • All of the datasets are downloaded from LIBSVM dataset (Chang & Lin, 2011). We used training datasets only if test datasets are provided separately (“splice”). • In the table, the column “d” denotes the number of features including the intercept feature. The choice of the regularization hyperparameterλ, based on the c...
work page 2011
-
[3]
As a method to solve the constrained maximization ofDGi inW, we apply method of Lagrange multiplier
Algorithm 3Distributionally Robust Coreset Selection for Large Datasets Input: DatasetD :={(xi,yi)}i∈[n], matrixA, vectorb, constantc 1: Initializev←{ 1}n 2: Compute worst-case weight that maximize the duality gap : wworst = arg max w∈W { (v⊗w)⊤A(v⊗w) +b⊤(v⊗w) +c } 3: Set desired number of deletions,ndel 4: for eachi∈ [n] do 5: Setv′←v and v′ i← 0 ▷ Remov...
work page 2024
-
[4]
Chengcheng Guo, Bo Zhao, and Yanbing Bai
doi: 10.1287/opre.1090.0795. Chengcheng Guo, Bo Zhao, and Yanbing Bai. Deepcore: A comprehensive library for coreset selection in deep learning. In International Conference on Database and Expert Systems Applications, pp. 181–195. Springer,
-
[10]
Active learning by acquiring contrastive examples.arXiv preprint arXiv:2109.03764,
Katerina Margatina, Giorgos Vernikos, Loïc Barrault, and Nikolaos Aletras. Active learning by acquiring contrastive examples.arXiv preprint arXiv:2109.03764,
-
[11]
URL https://github.com/google/neural-tangents. Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. NIPS 2017 Workshop Autodiff,
work page 2017
-
[13]
doi: 10.1038/s41592-019-0686-2. Liyuan Wang, Xingxing Zhang, Kuo Yang, Longhui Yu, Chongxuan Li, Lanqing HONG, Shifeng Zhang, Zhenguo Li, Yi Zhong, and Jun Zhu. Memory replay with data compression for continual learning. In International Conference on Learning Representations,
-
[31]
In general, whenBv,w is represented as a hypersphere, these bounds can be explicitly obtained. Lemma C.4. IfBv,w is given as a hypersphere of radiusR∈ R≥0 centered at the original model parameter β∗ 1n,1n, ( Bv,w := { β∈ Rk|∥β−β∗ 1n,1n∥2≤R }) , an upper and lower bounds of the linear scorey′ iβ⊤x′ i can be analytically calculated as min β∈Bv,w y′ iβ⊤ϕ(x′ ...
work page 2005
-
[2001]
Active learning for convolutional neural networks: A core-set approach
Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: A core-set approach. arXiv preprint arXiv:1708.00489,
Show all 17 references
-
[2009]
Jaehoon Lee, Yasaman Bahri, Roman Novak, Samuel S Schoenholz, Jeffrey Pennington, and Jascha Sohl- Dickstein
URLhttps://www.cs.toronto.edu/~kriz/cifar.html. Jaehoon Lee, Yasaman Bahri, Roman Novak, Samuel S Schoenholz, Jeffrey Pennington, and Jascha Sohl- Dickstein. Deep neural networks as gaussian processes.arXiv preprint arXiv:1711.00165,
-
[2010]
Steven Diamond and Stephen Boyd
doi: 10.1287/opre.1090.0741. Steven Diamond and Stephen Boyd. CVXPY: A Python-embedded modeling language for convex optimiza- tion. Journal of Machine Learning Research,
-
[2015]
Lemma A.5
for a detailed proof. Lemma A.5. For any vectorsa,c∈ Rn and a positive scalarS >0, the following holds: min p∈Rn:∥p−c∥2≤S a⊤p =a⊤c−S∥a∥2, max p∈Rn:∥p−c∥2≤S a⊤p =a⊤c +S∥a∥2. Proof. Using the Cauchy-Schwarz inequality, we derive: −∥a∥2∥p−c∥2≤a⊤(p−c)≤∥a∥2∥p−c∥2. The first inequal...
1970
-
[2016]
To appear
URL https://stanford.edu/~boyd/papers/pdf/ cvxpy_paper.pdf. To appear. Melanie Ducoffe and Frederic Precioso. Adversarial active learning for deep networks: a margin based approach. arXiv preprint arXiv:1802.09841,
- [2017]
-
[2020]
URL https: //doi.org/10.1038/s41586-020-2649-2
doi: 10.1038/s41586-020-2649-2. URL https: //doi.org/10.1038/s41586-020-2649-2. Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June
-
[2021]
Cody Coleman, Christopher Yeh, Stephen Mussmann, Baharan Mirzasoleiman, Peter Bailis, Percy Liang, Jure Leskovec, and Matei Zaharia
URL https://arxiv.org/abs/2108.08993. Cody Coleman, Christopher Yeh, Stephen Mussmann, Baharan Mirzasoleiman, Peter Bailis, Percy Liang, Jure Leskovec, and Matei Zaharia. Selection via proxy: Efficient data selection for deep learning.arXiv preprint arXiv:1906.11829,
1906 arXiv
-
[2022]
Generalized low-rank update: Model parameter bounds for low-rank training data modifications
Hiroyuki Hanada, Noriaki Hashimoto, Kouichi Taji, and Ichiro Takeuchi. Generalized low-rank update: Model parameter bounds for low-rank training data modifications. Neural Computation, 35(12):1970– 2005,
1970
-
[2024]
Charles R
URLhttps://arxiv.org/abs/2406.05964. Charles R. Harris, K. Jarrod Millman, Stéfan J. van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J. Smith, Robert Kern, Matti Pi- cus, Stephan Hoyer, Marten H. van Kerkwijk,...
Reviewed August 10, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.