The algorithms with the best guarantees for selecting a subset of items when adding too many items hurts are almost never run on large problems. This setting is called non-monotone submodular maximization: "submodular" means each added item helps less than the one before, and "non-monotone" means past some point extra items make the total worse. The strongest methods work on a continuous relaxation, in which each item gets a fractional inclusion level between 0 and 1. They then push every one of the $n$ coordinates forward at every step, which becomes impractical when $n$ is in the millions. Sparse-regression solvers solved the analogous problem years ago with active sets: a small working set of variables that are allowed to move while every other variable is held at zero. We propose to build that machinery for non-monotone submodular maximization. The central idea is a screening rule that removes an item for good once it provably cannot help, and it relies on a property specific to submodular functions.
Somatic variant calling supplies a real problem at this scale. The task is to find tumor mutations present in only a few percent of the sequenced DNA. Multi-sample callers such as Moss first run a standard caller with lenient settings and take the union of candidate sites, which yields millions of candidates across biopsies. Only a small fraction of these are real mutations. Many false candidates come in clusters, because the same few misaligned reads support several neighbouring fake mutations at once. Choosing which candidates to report can therefore be framed as a non-monotone submodular problem with a very sparse solution, which is the regime active sets are designed for.
Core Claim
Continuous algorithms for non-monotone submodular maximization have a property that makes screening safe along their main trajectories. For DR-submodular relaxations, the gradient in coordinate $i$ can only fall as the fractional solution grows. Under continuous greedy and its dampened variant the solution only grows, so once coordinate $i$ has a non-positive gradient it will never rise again and can be dropped permanently. The research file's candidate-gap analysis raises the worry that "an element with negative marginal gain early can become positive later". That worry is wrong for these increasing phases. It only applies to phases that also remove mass, namely the local search of Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes and the double-greedy stage of Constrained Submodular Maximization: Beyond 1/e. For those phases the screening rule has to be derived afresh.
We claim three things. First, safe screening combined with a two-tier pool of candidates in the style of Thunder makes the 0.372-guarantee continuous method practical on ground sets of $10^6$–$10^7$ items. Second, a concave relaxation specific to the objective yields an upper bound on the best achievable value for each instance, so every algorithm's optimality gap can be measured rather than inferred from worst-case ratios. Third, whether the stronger-guarantee methods find better solutions than fast discrete methods on real instances has not been tested, and screening makes the test possible. In the variant-calling application, we test whether a set-level objective that penalizes shared evidence beats per-site calling at 1–10% variant allele frequency (VAF, the fraction of reads at a site that carry the mutation).
The Objective
Let $C$ be the candidate calls pooled across samples. Let $R_c$ be the alternate-allele reads supporting candidate $c$. Let $w_r \ge 0$ be a read's weight, built from its base quality and mapping quality. Let $\lambda_c \ge 0$ be a per-call cost derived from a background error model of the kind Moss fits from the normal sample and reference counts. We maximize
$$f(S) = \sum_{r} w_r \,\mathbb{1}\Big[r \in \textstyle\bigcup_{c \in S} R_c\Big] \;-\; \sum_{c \in S} \lambda_c ,$$
subject to either a cardinality budget or a knapsack budget. The knapsack case models a targeted deep-validation panel whose cost depends on how many amplicons the chosen sites require. The first term counts each read once, however many candidates it supports. As a result, a second call in a cluster of misaligned reads gains little while paying the full $\lambda_c$. The function is a coverage function minus a modular cost, so it is submodular and non-monotone.
The objective has two useful computational features. Its multilinear extension has a closed form, $\sum_r w_r(1-\prod_{c \ni r}(1-x_c)) - \sum_c \lambda_c x_c$, so gradients are exact and cost only the number of reads a candidate touches. Replacing the coverage term by $\sum_r w_r \min(1, \sum_{c\ni r} x_c)$ gives a concave program whose optimum upper-bounds the discrete optimum. This bound plays the role that the duality-gap certificate plays in Thunder: a Fast Coordinate Selection Solver for Sparse Learning.
Research Program
The first component is the screening theory, derived separately for each phase. For the increasing phases, a coordinate is frozen once its exact gradient is non-positive. A coordinate is also placed in a "cold" pool when a stale gradient bound falls below the current $k$-th largest active gradient. It stays there until the running threshold drops beneath that stale bound. This rule mirrors lazy evaluation, but applied to a continuous trajectory. The decreasing trajectory of continuous double greedy needs a different rule, because on that side gradients rise. There we use the ordering $\nabla_i F(y) \le \nabla_i F(x)$ for $y \ge x$ to fix a coordinate to 0 or 1 once the bounds from both trajectories agree in sign. We will prove that the screened algorithms keep the guarantees of their unscreened versions: 0.372 from Constrained Submodular Maximization: Beyond 1/e and the down-closed bounds from Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes. We will also bound per-iteration cost by the size of the active set times the average read degree.
The second component borrows two techniques from sparse regression. From Thunder: a Fast Coordinate Selection Solver for Sparse Learning we take the pool of "warm" and "cold" inactive coordinates and random-batch recruitment. From A Primal Dual Active Set Algorithm with Continuation for Compressed Sensing we take continuation: we start with inflated costs $\lambda_c$, which makes the solution tiny, then relax the costs and warm-start from the previous active set. The contrast with prior active-set work on submodular problems matters. Active-set Methods for Submodular Minimization Problems builds its ordered partitions on the convex Lovász extension, which exists only for minimization. Maximization has no such convex structure, and our screening relies on DR-monotonicity of gradients instead. The "active-set non-monotone" method of Minimization over the ℓ 1-ball using an active-set non-monotone projected gradient uses "non-monotone" to describe a line search, and it serves only as the source of its zero/non-zero partitioning idea.
The third component uses rounding. Contention-resolution rounding followed by pruning of negative-marginal elements, as in the relax-and-round scheme, then runs only over the final active set.
Baselines
The naive reference point is per-site calling. Concretely, it is Mutect2 run on the lenient candidate union with its standard filters. It is equivalent to our objective with the coverage term replaced by a per-site modular score, which is the same as thresholding each site on its own. As a model ablation we run this same modular objective with our learned $\lambda_c$. That run isolates whether counting each read once, the only set-level ingredient, adds anything.
The strongest variant-calling competitors are Moss and the rank combination of Hofmann et al. Moss enables high sensitivity single-nucleotide variant calling from multiple bulk DNA tumor samples jointly scores the same lenient candidate union across samples, site by site. It is the closest system to ours, since it differs only in lacking set-level interactions, and it reports rescuing 466 variants missed by Mutect2 on 23 liver biopsies, about 70% of which met clinical-grade review. Detailed simulation of cancer exome sequencing data reveals differences and common limitations of variant callers reports 78% sensitivity at 90% precision for rank-combining five callers on its simulated ccRCC exome, against 71% for the best single tool. For low VAF it also reports JointSNVMix2 at 61% sensitivity for 5–10% VAF. Beating Hofmann means exceeding 78% sensitivity at 90% precision on that simulation. On COLO829 the reference point is the reported F1 of about 0.926 for TransSSVs: a Transformer-based deep learning model for accurate detection of somatic small variants in paired tumor and normal sequencing data, against 0.885 for Mutect2. We would feed TransSSVs scores into $\lambda_c$ rather than compete with it. Success there means improving on TransSSVs' own calls by adding the set-level term. For fairness, every method receives the same aligned reads, the same candidate union and the same normal sample. Any threshold is tuned on a held-out chromosome at a fixed 90% precision.
On the optimization side, the discrete baselines are FastInterlaceGreedy from Interlaced Greedy Algorithm for Maximization of Submodular Functions in Nearly Linear Time for cardinality budgets and SampleGreedy from Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint for knapsack budgets. Both use lazy or threshold evaluations and are the fastest methods with guarantees. FIG is reported to run more than an order of magnitude faster than the previous deterministic algorithm, with "stealing" improving objective value by up to 45% on BA graphs. The file gives no absolute objective values for it; no reported result found on Lacuna for FIG objective values on ER/BA Max-Cut or ca-AstroPh. We also include plain lazy greedy and a concave-relaxation-plus-rounding baseline, in which the concave program is solved directly and then rounded.
Two ablations isolate the proposal's key ingredient. The first runs the continuous method without screening, at scales where that is feasible. The second replaces the safe rule with an unsafe gradient-magnitude freeze in the style of Thunder. Every optimizer gets the same wall-clock and oracle budgets on the same hardware. Beating the optimization baselines means one of two outcomes. Either the screened continuous method reaches a strictly smaller certified gap than FIG or SampleGreedy within the same time, or it matches their gap faster than the unscreened method.
Why not just…?
Why not just use lazy or threshold greedy, which already skips most evaluations? This is the most serious threat. On coverage-minus-cost instances, FIG with stealing may already come within a few percent of the concave upper bound. In that case the continuous algorithms' better worst-case ratio would buy nothing in practice. The certified-gap experiment settles this directly. If FIG's gap is already negligible, we will report that and reposition the contribution as the certificate plus screening for knapsack and matroid constraints. Discrete methods have weaker guarantees under those constraints (SampleGreedy's factor is 5.83), so the case for continuous methods is stronger there.
Why not just solve the concave relaxation and round? For monotone coverage this is a strong approach, and we include it as a baseline. With the subtracted cost, rounding can land on sets whose true value is far below the relaxed value. The contention-resolution-with-pruning step of Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes exists to handle exactly that failure. Measured gaps will show which approach performs better. Solving the relaxation at $10^7$ variables also benefits from the same screening.
Why not just call sites independently with a Bayesian model and add a filter for clustered calls? Moss already does per-site joint scoring well, and a hand-written cluster filter captures some of what read-level de-duplication does. The modular ablation, which is our objective without the coverage term, measures this directly. If it matches the full objective at 1–5% VAF, the set formulation adds nothing for calling, and we will say so. Our hypothesis is that hard cluster filters also discard real variants in dense mutational regions, whereas reads shared by a real variant and an artifact are split correctly by the coverage term. We check this with a stratified analysis of loci that have multiple candidates within read length.
Why not just train a deep model such as TransSSVs end to end? TransSSVs reports that performance degrades beyond seven flanking sites. It also needs curated labels, which are scarce for low-purity or multi-region data. Our objective can use its scores as $\lambda_c$, so the two are complementary rather than competing.
Proposed Experiments
The optimization study runs on the Erdős–Rényi (ER) and Barabási–Albert (BA) Max-Cut graphs and the ca-AstroPh network from the FIG paper, and on MovieLens and the YouTube graph from the SampleGreedy paper. It then moves to the genomic instances, which grow to $10^7$ candidates by pooling multi-region samples. We report the certified gap against wall-clock time, the fraction of coordinates screened, and a check that screened and unscreened runs produce the same solution on instances small enough to run both.
The calling study uses four datasets: the simulated ccRCC exome at depths from 12× to 212× and contamination from 10% to 60%; the Moss HCC and AML datasets, where the AML truth comes from 1500× validation; and the ICGC CLL and medulloblastoma gold set from A comprehensive assessment of somatic mutation detection in cancer using whole-genome sequencing. The ICGC samples have 95–98% purity, so we also dilute them in silico with matched normal reads to push true variants below 2% VAF. That is the regime the benchmark does not cover and the one where shared-evidence artifacts should dominate. The same paper reports that above roughly 100× depth, errors are driven by alignment rather than sampling depth.
The decisive checks are these. On the diluted ICGC data, the full objective must beat the modular ablation and Moss in sensitivity at 90% precision, specifically in the 1–5% VAF stratum. On the simulated ccRCC data, it must exceed the reported 78% at 90% precision. On the largest instances, the screened 0.372 method must finish within the time budget with a certified gap no worse than FIG's. The paper still has a result if some checks fail: a failure of the first two would mean the set structure does not help calling, and a failure of the third would mean screening does not rescue the continuous methods.
References
- Submodular function maximization via the multilinear relaxation and contention resolution schemes
- Constrained Submodular Maximization: Beyond 1/e
- Thunder: a Fast Coordinate Selection Solver for Sparse Learning
- A Primal Dual Active Set Algorithm with Continuation for Compressed Sensing
- Active-set Methods for Submodular Minimization Problems
- Minimization over the ℓ 1-ball using an active-set non-monotone projected gradient
- Moss enables high sensitivity single-nucleotide variant calling from multiple bulk DNA tumor samples
- Detailed simulation of cancer exome sequencing data reveals differences and common limitations of variant callers
- TransSSVs: a Transformer-based deep learning model for accurate detection of somatic small variants in paired tumor and normal sequencing data
- Interlaced Greedy Algorithm for Maximization of Submodular Functions in Nearly Linear Time
- Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint
- A comprehensive assessment of somatic mutation detection in cancer using whole-genome sequencing