acceptodds
Under review as a conference paper at ICLR 2027

Fair Subset Selection across Categories and Views via Adaptive NEPv

Abstract

Modern machine learning increasingly relies on large datasets, but limited computational budgets can make training on all available examples impractical. In many cases, selecting a small training subset requires balancing category representation against feature diversity. This is especially difficult when categories overlap and one item contributes to several categories under a shared budget. We construct positive-definite category kernels by softening membership weights on a common feature geometry, then maximize a soft minimum of normalized log-determinants. Endpoint identities separate membership-count effects from diversity and distinguish zero-ridge and ridge-dominant regimes. A Stiefel relaxation yields an adaptive nonlinear eigenvalue formulation and a self-consistent-field solver. Its symmetric lifting has rank at most twice the subset size, an explicit spectrum, a uniform eigengap, and exact small-matrix compression; local convergence remains conditional on operator sensitivity. At a budget of 500 examples, trademark experiments report 81.91% mAP on OpenLogo retrieval and 53.67% category recall on USPTO description generation, compared with 76.15% and 51.36% under uniform sampling. The method does not lead on every metric. We distinguish these empirical comparisons from hard category quotas, global optimization guarantees, and downstream coreset guarantees.

Primary area:
optimization
Keywords:
subset selection, determinantal point processes, multi-view learning, robust optimization, manifold optimization, nonlinear eigenvalue problems

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_ae9EOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies subset selection under a shared budget when categories may overlap. It assigns each category a kernel on the same items and maximizes a soft minimum of normalized log-determinant scores, emphasizing the weakest category while encouraging feature diversity. The authors relax discrete selection to a Stiefel manifold problem, derive an adaptive nonlinear eigenvalue problem (NEPv), and round the resulting subspace to a subset. Experiments on OpenLogo and USPTO evaluate category-based selection.

Critical strengths

Relevant problem setting. Overlapping categories make independent per-category selection difficult under one shared budget. The common-index kernel formulation lets one selected item contribute to multiple categories.

Interpretable objective. The soft minimum adapts emphasis toward weaker category scores. The zero-ridge identity clarifies the tradeoff between category representation and feature diversity, while the paper correctly distinguishes that identity from the positive-ridge setting used in practice.

Useful spectral structure. The determinant-specific NEPv construction has rank at most 2k2k, an explicit spectrum, and an exact small-matrix compression that avoids a full n×nn \times n eigendecomposition.

Critical weaknesses

1.Narrow empirical scope. Both tasks use trademark data and primarily report k=500k=500. On USPTO, category recall exceeds the fixed-weight baseline by only 0.32 percentage points, while uniform sampling has slightly higher text-embedding cosine similarity.

2. Incomplete reproducibility details. The manuscript omits complete feature versions, selection parameters such as ridge and temperature, USPTO pool and test sizes, full training settings, and per-seed results.

Questions for authors

Main concerns:

1. Direct optimization baseline. How does FAIRNEPV compare with a discrete greedy algorithm that directly maximizes the proposed soft-min objective, preferably followed by the same one-swap refinement? This comparison would help establish the benefit of the NEPv solver beyond the objective itself.

2. Reproducibility. Could the authors provide the OpenLogo split identifiers and selected sample IDs, the USPTO test-pool size, and the complete selection and training configurations needed to reproduce the results?

3. Runtime and scalability. What are the wall-clock time and peak memory usage of FAIRNEPV, reported separately for the continuous solver and rounding? Please compare them with the proposed greedy baseline under the same selection budget and report how runtime scales with the candidate-pool size.

Minor concern:

-not using the official ICLR 2027 template

3 comments

Thank you for your careful and constructive review, and for the concrete experiments you suggested. We ran the direct greedy baseline you proposed, and it is now our method.

Q1: direct greedy. This was an excellent suggestion. Greedy maximization of the soft-min objective (Algorithm 1) beats the NEPv solver on the same objective and budget at every kk on COCO, and swaps after rounding do not close the gap (Appendix C). The relaxation wins only with near-duplicate items shared by several categories, the regime Proposition 4 identifies, on synthetic instances (Table 5) and drone video (Table 8).

Q3: runtime and scalability. We measured all three quantities you asked about (wall-clock time, peak memory, and the split between the continuous solver and rounding), on the same CPU (AMD Ryzen 9 9950X, 12 threads) and the full COCO pool of 107,266 images (Appendix C.2, Table 3). Each cell gives time and peak memory added on top of the loaded features:

kkGreedyRelaxed: SCF solveRelaxed: rounding
1004.3 s, 0.9 GB369 s, 1.4 GB0.2 s, 0.2 GB
2008.8 s, 0.9 GB611 s, 2.3 GB1.5 s, 0.3 GB
40017.7 s, 1.0 GB1,236 s, 4.2 GB7.1 s, 0.7 GB

On pools of 13k, 27k, 54k and 107k images at k=200k=200, greedy takes 1.1, 2.1, 4.4 and 8.6 seconds, linear in nn as its O(nk(p+k+M))O(nk(p+k+M)) cost predicts, and it is 60–90 times faster than the SCF solve throughout. Peak memory also grows linearly: 0.11–0.90 GB for greedy against 0.5–2.3 GB for the SCF solve. Greedy never forms an n×nn\times n matrix; most of its memory is a working copy of the feature matrix, and the algorithm itself needs only an n×kn\times k Cholesky factor.

W1: scope. We agree that the original evaluation was too narrow. It now spans long-tailed CIFAR-10/100 at three imbalance ratios, GTSRB, multi-label COCO, LVIS with 1,203 categories, near-duplicate pools and drone video, at several budgets, with linear probes and full fine-tuning (Section 6, Appendix D). Our method beats uniform sampling in every long-tailed setting and is more accurate than class-balanced sampling on the rarest classes in most settings (Tables 1–2).

W2/Q2: reproducibility. Appendix D now gives data sources with checksums, split seeds, pool and test sizes, the feature extractor, every selector's settings, training settings and the decision rule. Tables report means, standard deviations and per-comparison seed counts. We will release the code, split identifiers, selected indices and per-seed outputs.

Template. Thank you for noting this. The revised PDF uses the official ICLR 2027 style files.

We hope the new experiments and the direct comparison with greedy answer your questions, and we would be glad to provide further details where useful.

This revised version has indeed improved readability and informativeness. However, I did not see any superiority over other baselines (see Table 1), and the code has not been released or included as supplementary material, so I will maintain my score.

Thank you so much for reading the revised paper carefully, and for your kind words about the improvements over its readability and informativeness.

Code. We sincerely apologize for not including the code with the revision; this was an oversight on our part. We have just now prepared an anonymized version and uploaded it as supplementary material. It contains the code for every downstream experiment (selectors, objective, data preparation from public sources, training and evaluation), the launch scripts, our experiment ledger, and the per-run outputs, including the selected indices of every run. Its README maps each table in the paper to the corresponding code and outputs. As a check, running it from a clean copy reproduces the stored results exactly, with the same selected images and the same accuracies.

Comparison with baselines (Table 1). Thank you for raising this; we would like to clarify further on what Table 1 shows. Our method is more accurate than every category-blind baseline (uniform, kk-center, shared-kernel DPP and fixed weight) in all six settings, and more accurate than the averaged-kernel selector on CIFAR-10-LT and CIFAR-100-LT. It is close to class-balanced sampling overall and, as Tables 2 and 10 show, more accurate on the rarest classes in most settings, for example 95.5% against 93.9% on CIFAR-10-LT at k=200k=200. We agree that it does not beat class-balanced sampling on overall accuracy, and the paper says so. Appendix D.9 adds that, when each class receives only a few items, the zero-padding end of the same objective (an additional, exploratory run) beats class-balanced sampling on GTSRB by about 3 points overall and 10–13 points on tail classes.

Thank you again for your valuable feedback, which has substantially improved the paper. Understandably the feedback window is closing, but we would be happy to answer any further questions.

Reviewer_D3dMOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

This paper proposes FairNEPv, a framework for fair and diverse subset selection under a shared budget. It formulates the selection objective as a soft minimum of normalized category-wise log-determinant scores, allowing items to belong to multiple categories. To optimize this objective, the authors introduce a Stiefel manifold relaxation and derive an adaptive nonlinear eigenvalue problem (NEPv), which is solved using a self-consistent-field (SCF) iteration. The continuous solution is then converted into a discrete subset through leverage-based screening and greedy refinement. Experiments are conducted on two trademark-related tasks: OpenLogo retrieval and USPTO trademark description generation.

Critical strengths
  1. Meaningful problem formulation. The paper addresses the practical challenge of balancing category representation and diversity under a shared selection budget, including settings with overlapping category memberships.

  2. Nontrivial theoretical analysis. The authors derive determinant-specific spectral properties of the resulting NEPv, including an explicit spectrum, eigengap, and low-rank compression.

Critical weaknesses

Major Weaknesses

1. Insufficient comparison with existing methods.

The experimental evaluation mainly compares FairNEPv against uniform sampling, averaged-kernel selection, fixed-weight selection, and a stratified baseline on OpenLogo. However, the paper does not provide a direct comparison with any existing subset selection methods, particularly those developed for fair/diverse selection, as well as for robust or multiobjective submodular optimization. Without stronger baselines, it is difficult to assess whether the proposed framework offers a meaningful advantage over existing methods.

2. Lack of component-wise ablation studies.

The proposed algorithm combines several components, including Stiefel manifold relaxation, NEPv-based optimization, leverage-score screening, greedy selection, and one-swap refinement. However, the paper does not provide systematic ablations to isolate their respective contributions. In particular, it is unclear whether the NEPv-based optimization is necessary for the observed improvements, or whether simpler approaches, such as direct greedy selection with local refinement, could achieve comparable results. The reported feature ablation on OpenLogo does not address these algorithmic questions. Consequently, the experiments provide insufficient evidence to justify the complexity of the proposed optimization pipeline.

3. Unclear contribution.

Several key ingredients of the proposed framework, including log-determinant diversity objectives, soft-min aggregation, Stiefel manifold relaxation, NEPv/SCF optimization, and leverage-based rounding, have been studied previously. The most distinctive technical contribution appears to be the determinant-specific spectral structure of the resulting NEPv, including its explicit spectrum, eigengap, and low-rank compression. While these results are mathematically interesting, their practical implications are not sufficiently established. In particular, it remains unclear whether the derived spectral properties lead to substantial improvements in computational efficiency, optimization quality, or the quality of the selected subsets compared with existing approaches.

Minor Weaknesses

1. Limited empirical analysis of the optimization process.

Despite the emphasis on the NEPv-based solver and its theoretical properties, the real-world experiments provide little direct analysis of the optimization process. Providing e.g. convergence curves, final stationarity residuals, and objective values before and after discrete rounding would help assess the solver's practical behavior and the quality of its solutions. Such analysis would also help connect the theoretical results to the empirical performance.

2. Residual editorial and revision-related text.

The manuscript contains several passages that appear to be residual editorial or revision notes rather than finalized academic writing. For example:

  • Appendix C.2 refers to "the supplied text" and states that "no values are inferred here."
  • Appendix C.3 includes the sentence "This revision retains the numerical evidence and profile observations..."
  • Appendix H describes the full formulation as "retained as a deferred extension" and refers to "this revision."
  • Appendix I includes the phrase "the original text printed 0.565."

These passages give parts of the appendix the appearance of an internal revision record. I strongly recommend that the authors carry out a careful editorial review and cleanup to improve the clarity and professionalism of the manuscript.

Questions for authors
  1. Comparison with prior methods. How does FairNEPv compare with established fair/diverse subset selection methods? Is there any theoretical or empirical evidence that the proposed framework offers advantages over these alternatives?

  2. Necessity of the NEPv-based solver. To what extent do the reported improvements depend on the proposed NEPv-based optimization? Could simpler approaches, such as direct greedy selection followed by one-swap refinement, achieve comparable results under the same objective and selection budget?

2 comments

Thank you for your detailed and constructive review. We are especially grateful for your question about whether the NEPv solver is necessary; it changed the paper for the better.

Q2/W2: is the NEPv solver necessary? Following your suggestion, we tested this directly, and we found that it is not. We now optimize the objective with greedy (Algorithm 1) and compare it with swaps, random restarts and the NEPv relaxation under six rounding rules (Appendix C). On COCO with 80 categories, greedy reaches a higher objective than the relaxation at every budget and runs 60–90 times faster (Appendix C.2, Table 3). The relaxation keeps one well-defined role: near-duplicate items shared by several categories, where greedy provably can be trapped (Proposition 4) and the relaxation wins on drone video at k=20k=20 on all 15 pools (Table 8). The component that matters most is the soft minimum. A single greedy run on it beats exact-minimum optimizers on their own objective on all 50 pools (Table 4), because the exact minimum creates ties that stall local search (Theorem 1). The floor and temperature are ablated in Table 11.

Q1/W1: comparison with existing methods. Thank you for pointing us to fair-DPP and robust submodular methods. In addition to the uniform, class-balanced, k-center, shared-kernel DPP, averaged-kernel and fixed-weight selectors, we added both: a fair DPP with partition (quota) constraints, and SATURATE (Appendix D.9, Table 22). The comparison taught us something useful about our own objective. With 20–40 items per class, our method is more accurate on tail classes than the quota DPP in all six settings and more accurate overall than SATURATE in five. With only 2–10 items per class, diversity within each class matters most, and the zero-padding end of our objective provides exactly that (Proposition 11). In an additional run, it matches SATURATE on GTSRB and beats class-balanced sampling by 10–13 points on tail classes. The floor therefore selects between two regimes of one objective. Unlike quota methods, which need disjoint groups and counts fixed in advance, our objective applies directly when one item belongs to several categories.

W3: contribution. We appreciate the chance to state the contribution more clearly. (1) Category kernels over the whole dataset, which let one item serve several categories and provably prefer such items (Proposition 2), together with a soft minimum that removes the ties of the exact minimum (Theorem 1). (2) Greedy as a fast, analyzable optimizer: coverage-optimal on single-label data under a margin condition (Proposition 3), with a characterized failure mode (Proposition 4). (3) A systematic evaluation on six public benchmarks. The spectral results (Appendix B) make each SCF step well defined and avoid any n×nn\times n eigendecomposition; Proposition 10 shows why the relaxation remains a specialist tool rather than the default, since one SCF sweep costs at least as much as a whole greedy run.

Minor 1. Thank you for this suggestion. In a separate convergence study (k=100k=100, up to 1,000 iterations), Appendix C.2 reports stationarity residuals for each shift (2×10−32\times10^{-3} at σ=20/k\sigma=20/k); the reported selections use σ=6/k\sigma=6/k with at most 300 iterations. C.2 also reports the relaxed value against the best subset, and objective values before and after each rounding rule.

Minor 2. Thank you for listing these passages. All of them have been removed, and the full text has been rewritten.

If any part of the revision remains unclear, we would be happy to elaborate.

Thank you for the extensive revisions and detailed response. While I acknowledge the authors' efforts, I have serious concerns about the extent of the revision. The central method has been replaced, the experiments have been almost entirely rewritten, and substantial parts of the theoretical analysis have changed. The revised manuscript effectively constitutes a new paper, which cannot be adequately evaluated within the rebuttal period. Hence, I do not believe the revision provides sufficient grounds to reconsider my original assessment, and I will maintain my rating.

Reviewer_EEZTOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This work addresses subset selection (e.g. for choosing training data) when samples belong to multiple, possibly overlapping categories. Experiments include trademark datasets at a budget of 500.

Critical strengths

None

Critical weaknesses
  • The experimental configurations do not seem reproducible. C.2 states, “This section documents their stated setup and limitations; it is not a reconstruction of execution logs.” “The supplied text does not specify the complete feature-extractor versions, category-kernel ridge values, temperatures, selector implementations and stopping records for the trademark tables, or all downstream optimizer settings.”
  • The text reads as unfinished. Much of the main body seems to be unrevised draft text, possibly LLM-generated, which makes the paper substantially harder to read. Some phrasing is also unclear. For example, the word “supplied” appears frequently: in Section 6.1, it is not clear what “the supplied OpenLogo-derived corpus” refers to.
Questions for authors

None

2 comments

Thank you for the review. We have addressed both of the problems you raised.

Experimental settings. You noted that the paper did not specify the feature extractor, ridge values, temperatures, selector implementations, stopping records or downstream optimizer settings. All experiments now use public data, and Appendix D states each of these:

  • Features: OpenCLIP 4.2.1, ViT-B-32-quickgelu with the OpenAI weights; 512-dimensional outputs normalized to unit length.
  • Selector settings: membership floor LO=10−30\mathrm{LO}=10^{-30}, temperature τ=0.1\tau=0.1, ridge ρ=10−64\rho=10^{-64} (COCO: LO=10−3\mathrm{LO}=10^{-3}, ρ=10−10\rho=10^{-10}), fixed on one development setting and then frozen.
  • Selectors: the implementation of all nine selectors (Appendix D.3 and D.9).
  • Stopping: greedy runs exactly kk steps. On COCO the relaxed solver uses shift 6/k6/k, damping 0.7 and at most 300 iterations (drone video: Appendix C.4), and Table 3 records that it reached the cap in every run.
  • Downstream training: linear probe with full-batch AdamW (learning rate 10−210^{-2}, weight decay 10−410^{-4}, 300 epochs); fine-tuning with AdamW (10−510^{-5} encoder, 10−310^{-3} head, weight decay 0.05, batch 32, 30 epochs, cosine schedule).
  • Protocol: five seeds, and a decision rule fixed in advance.

We will also release the code, split identifiers, selected indices and per-seed outputs.

Writing. We have rewritten the paper around a single story (see the general response). Section 3 builds the category kernels, Section 4 the soft-minimum objective, Section 5 the greedy optimizer and its limits, and Section 6 the downstream results. With the additional page, we have also included four diagrams that make the key ideas easier to follow: how one image affects several categories (Figure 1), the determinant as a volume (Figure 2), and how the category kernels are built (Figures 3 and 4). Wording such as "supplied" no longer appears.

We hope the rewritten paper addresses both of your concerns, and we would welcome any remaining passages you still find unclear.

Thank you for the detailed response. The revision addresses my reproducibility and clarity concerns in spirit, but it changes the main method, the experiments and much of the theory. I think this version deserves a full fresh review rather than an evaluation during the rebuttal period, so I will keep my original assessment of the submission.

A note: because the changes are not highlighted in the revised PDF, I am also unable to tell which parts of the paper are new or check them against the submitted version. Marking revisions (e.g., in colored text) would help authors and reviewers going forward.

Comments on the paper

1 comment

We sincerely thank the three reviewers for their time and their thoughtful comments. Their questions have led to a substantially stronger paper, and we are grateful for them. The submitted version tried to combine two bodies of work, the category-kernel objective and a full NEPv theory with a convergence analysis, and we understand why it read as "patchy". The revision tells one story: category kernels, a soft-minimum objective, and how to optimize it, mainly with greedy selection. With the additional page, we have also included four diagrams that illustrate the key ideas: how one image affects several categories (Figure 1), the determinant as a volume (Figure 2), and how the category kernels are built (Figures 3 and 4). We would like to highlight four results of the revision:

  1. Greedy is now the method, and it is both better and far faster. On COCO with 80 categories, greedy reaches a higher objective than the NEPv relaxation at every budget. Selecting 100–400 images from the full pool of 107,266 takes greedy 4–18 seconds, against 6–21 minutes for the relaxation on the same CPU, and greedy's cost grows linearly with the pool (Appendix C.2, Table 3). We also identify the regime where the relaxation helps, near-duplicate items shared by several categories, and prove why greedy struggles there (Proposition 4).
  2. The soft minimum is what makes greedy work. A single greedy run on our soft minimum scores higher on the exact minimum than greedy, random restarts and relaxed samples that optimize the exact minimum directly, on all 50 COCO pools (Table 4). The exact minimum creates ties that stall local search (Theorem 1).
  3. Clear gains on public benchmarks. On long-tailed CIFAR-10/100 and GTSRB, our method beats uniform sampling in every setting (by 15.6–19.7 points on CIFAR-LT) and is more accurate than class-balanced sampling on the rarest classes in most settings (Tables 1–2). Multi-label COCO, LVIS and drone video provide further tests.
  4. One objective covers two regimes. The membership floor decides whether diversity is enforced across the whole subset or within each class (Proposition 11). Our main setting (the count regime) is about 5 points below class-balanced sampling on GTSRB (Table 2), where each class receives only 5–9 items. In an additional, exploratory run, the zero-padding end of the same objective instead beats class-balanced sampling there by about 3 points overall and 10–13 points on tail classes, and matches SATURATE (Appendix D.9). The floor should therefore follow the per-class budget: the count regime when classes receive many items, zero padding when they receive few.

Public benchmarks. We replaced the trademark experiments with public benchmarks, for three compelling reasons. First, they are easily accessible. Second, they test the two situations the method is designed for. Long-tailed classification asks whether rare categories get represented. Multi-label COCO and LVIS ask what happens when one image belongs to several categories. Third, they let us probe the method's limits, through pools with injected near-duplicates and drone video, where consecutive frames repeat. The new benchmarks span a wide variety of dataset types, from natural images and traffic signs to multi-label scenes and video:

  • long-tailed CIFAR-10 and CIFAR-100, each at three imbalance ratios;
  • GTSRB with its natural imbalance;
  • multi-label COCO;
  • LVIS, with 1,203 categories;
  • pools with injected near-duplicates;
  • VisDrone video.

Every experimental setting (data and checksums, splits, seeds, features, floor, ridge, temperature, selectors, training and the decision rule) is now stated in Appendix D, and we will release the code, split identifiers and selected indices.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.