Gradients Through Swap Rounding: Low-Variance Learning Over Exactly Budgeted Sets

Many learning problems end in a hard combinatorial choice: pick exactly $k$ patients to call this week, select one item from each of several groups, allocate a fixed number of treatments. The usual recipe first solves a relaxed problem, a linear programming (LP) relaxation that lets each decision be a fraction between 0 and 1. It then converts the fractions into a real set with a rounding procedure. Swap rounding is one such procedure. It repeatedly takes two fractional entries and shifts mass between them until one hits 0 or 1. It never violates a cardinality or matroid constraint, and it keeps each item's selection probability equal to its fraction. Today it is used only as a post-processing step. It is never differentiated, never sampled from during training, and never used as a source of lower-variance gradients.

This note proposes to treat swap rounding as a learnable sampler. The key observation is that one run of swap rounding is a short sequence of binary coin flips. Each flip's probability is a simple rational function of the current fractions. The probability of any rounding trajectory can therefore be written down and differentiated. That gives an unbiased score-function gradient, a gradient estimator built from the derivative of the log-probability of the sampled outcome, for the expected objective of the deployed set. Every training sample is exactly feasible. The flip sequence also forms a binary tree, so we can apply the antithetic couplings developed for categorical latent variables, which pair each sample with a deliberately "opposite" partner. We expect this combination to give gradients whose variance is well below that of independent sampling. Part of the reduction should come from the coupling, and part from the negative correlation that swap rounding induces among selected items.

Core Claim

Swap rounding over a cardinality or partition-matroid polytope defines an explicit, differentiable distribution over feasible sets. Its sampling tree supports unbiased, coupled, Rao-Blackwellized gradient estimators, and these should reduce gradient variance relative to independent-Bernoulli and uncoupled estimators at equal numbers of function evaluations. We claim a measurable win in variance and in final objective, not just a feasibility guarantee. Where the objective can only be evaluated on feasible sets, as in simulated budgeted interventions or exactly-$k$ latent codes, the method should also beat penalty-based relaxations outright.

The step structure is concrete. Suppose the current pair of fractions is $(x_a, x_b)$ with sum $s = x_a + x_b$. If $s \le 1$, the pair moves to $(s, 0)$ with probability $x_a/s$ and to $(0, s)$ otherwise. If $s > 1$, it moves to $(1, s-1)$ with probability $(1-x_b)/(2-s)$ and to $(s-1, 1)$ otherwise. With a fixed pairing order, a trajectory $\tau$ of at most $n$ steps has probability

$$ p_\theta(\tau) = \prod_{t=1}^{T} \pi_t(x^{(t-1)}_\theta), $$

where $x^{(0)}_\theta$ are the fractions output by a model with parameters $\theta$, and $\pi_t$ is the probability of the branch taken at step $t$ given the fractions just before it. The gradient of the deployed objective $J(\theta) = \mathbb{E}_{\tau \sim p_\theta}[f(S(\tau))]$, where $S(\tau)$ is the rounded set, is then available through $\nabla_\theta \log p_\theta(\tau)$.

Swap rounding preserves marginals, so any part of $f$ that is linear in the indicators has expectation exactly linear in $x$. Its gradient can be computed analytically and removed from the sampled term. This is the same move as Sticking the Landing, which drops a term whose expectation is known and keeps only the part that needs sampling.

Relation to Prior Work

Two papers establish the ingredients without combining them. Dependent Randomized Rounding for Budget Constrained Experimental Design proves that swap rounding meets a budget exactly and lowers the variance of an inverse-propensity estimator through negative correlation. It motivates our variance hypothesis and supplies a lever we reuse: ordering the pairs by covariate similarity. However, it rounds fixed, precomputed probabilities and never takes a gradient. Coupled Gradient Estimators for Discrete Latent Variables supplies the method. It decomposes a categorical choice into a stick-breaking sequence or binary tree and couples paired samples antithetically. It also reports that the variance depends on the arbitrarily imposed ordering. ARSM achieves similar reductions through swap-merge couplings. Both are confined to choosing one of $C$ categories. Our point is that a constraint polytope comes with its own binary tree, the swap-rounding trajectory. Choosing the one-of-$C$ case, i.e. $k=1$, recovers exactly their setting, and larger $k$ or partition matroids extend it.

Three papers optimize relaxations with gradients but leave the variance question open. Submodular Maximization via Gradient Ascent runs projected gradient ascent on a concave relaxation of deep submodular functions and then applies pipage rounding. It assumes exact supergradients. EQUATOR uses stochastic Frank-Wolfe with randomized smoothing and then swap rounding. It does not analyze the variance of its gradient estimator. Both optimize a proxy, the relaxed objective, rather than the expected value of the rounded set. Differentiable Integer Linear Programming turns constraints into expected-violation penalties with soft/hard reparameterization. It reaches only 50.8% feasibility on Set Covering, which constrains our design: penalty relaxations should not be relied on for hard constraints.

We are honest about scope. Swap rounding guarantees feasibility for cardinality and matroid constraints. Knapsacks need the modified variant of A Nearly-linear Time Algorithm for Submodular Maximization with a Knapsack Constraint. General covering LPs are out of scope, so we do not compete on Set Covering.

Research Program

We will build a PyTorch module that takes fractions $x_\theta$ and returns a feasible set, the log-probability of its trajectory, and the analytic gradient of the linear part.

We will then derive a coupled estimator by running two trajectories with shared uniforms $u_t$ and $1-u_t$. At each node where the branches disagree, we apply the DisARM-Tree weighting from Coupled Gradient Estimators, which keeps the estimator unbiased despite the correlation between the pair. The remaining work is to verify this carefully when the trajectories diverge, since the downstream step probabilities then differ. We will check unbiasedness by exact enumeration for $n \le 12$.

The pairing order will be treated as a design variable. We will compare a random order, the covariate-ordered tour of the experimental-design paper, and an order sorted by fraction, the last motivated by the ascending-order finding in Coupled Gradient Estimators.

On the analysis side, we will bound the estimator's variance for modular-plus-pairwise objectives. For those objectives, the negative-correlation argument of the experimental-design paper carries over directly to the score-function term.

Baselines

The naive reference is independent Bernoulli sampling with a REINFORCE leave-one-out baseline. During training, sets that violate the budget are either projected to feasibility or penalized. At deployment, the method swap-rounds the final fractions. This is "do nothing new": the standard estimator plus post-hoc rounding. We beat it if we reach equal or better deployed objective with fewer function evaluations, and if we show lower per-coordinate gradient variance at matched fractions.

The strongest competitor on optimization problems is the independent-sampling multilinear gradient, which estimates each partial derivative as the average of $f(R \cup i) - f(R \setminus i)$ over sampled sets $R$. It is unbiased and well understood, and it is the estimator inside continuous-greedy and Frank-Wolfe methods such as EQUATOR, followed by swap rounding. For deep submodular functions we also run exact-supergradient projected ascent with pipage rounding from Submodular Maximization via Gradient Ascent as a noise-free upper reference. The file gives no scalar objective value for it, so we will report our own reproduction. On the robust budget allocation task, the target is the result reported in the EQUATOR paper: utility within 4–8% of the global optimum. On restless bandits, it is ProbFair's reported 80–90% of the fairness-agnostic Whittle index benefit (Planning to Fairly Allocate). On categorical VAEs, it is ARSM's reported 82.0 and 86.7 negative ELBO on binarized MNIST against Gumbel-Softmax's 93.6 and 95.9 (ARSM).

Every method gets the same instances, the same number of $f$ evaluations per step, and the same learning-rate grid of equal size. Each is run with ten seeds.

Two ablations isolate the ingredients. Uncoupled REINFORCE through swap rounding, using the same trajectory log-probability without antithetic pairing, isolates what the coupling adds. Removing the analytic linear-term gradient isolates what the Rao-Blackwellization adds.

Why not just…?

Why not just use a Gumbel-style continuous relaxation with a penalty, as DiffILO does? Relaxations are biased and mismatch training and deployment. ARSM reports roughly an 11-nat gap to Gumbel-Softmax on binarized MNIST, and DiffILO's penalty approach leaves 49.2% of Set Covering instances infeasible. We include a relaxed-top-$k$ penalty baseline on the exactly-$k$ VAE and bandit tasks to measure the gap in our regime rather than assume it.

Why not just optimize the multilinear extension with independent samples and round once at the end? This is the real threat. If $f$ can be queried cheaply on infeasible sets, feasibility during training may not matter, and this estimator may match ours. We see two reasons it might not. First, it needs about two evaluations per coordinate for each gradient. Second, it optimizes the multilinear proxy rather than the expected value of the rounded set, which differs for nonlinear $f$. Experiments A and B settle it directly. If it matches our deployed objective at equal evaluations, we will narrow the claim to settings where $f$ exists only on feasible sets.

Why not just use REINFORCE with a good baseline? Score-function estimators keep variance even near the optimum (Sticking the Landing), and coupled estimators cut variance by one to four orders of magnitude on categorical problems (ARSM). Our uncoupled-swap ablation is exactly this alternative, so the experiments measure how much the coupling adds.

Why not just call an exact solver? For fixed, fully known instances, that is often the right answer. Our targets are expectations over noisy or simulated outcomes, and amortized policies that output fractions per state. In those settings exact solvers do not apply directly, and EQUATOR reports that solver-based baselines time out on 1,000-node graphs.

Proposed Experiments

Experiment A: synthetic deep submodular functions. We use partition matroids with rank $k$ from $10^2$ to $10^4$, following the DSF paper's setup. We add noise by evaluating the functions' modular weights on mini-batches. We measure gradient variance at fixed fractions, deployed objective versus the number of evaluations, and wall-clock time.

Experiment B: robust budget allocation. On the Yahoo! Webscope robust budget allocation task, we replace EQUATOR's gradient estimator with ours and report the gap to the global optimum against the reported 4–8%.

Experiment C: restless bandits. On the CPAP adherence simulator and on synthetic transition matrices, a policy network outputs per-step fractions. These are swap-rounded to the exact budget and trained end to end on simulated rollouts. We report expected reward as a fraction of the Whittle index benefit and the earth-mover's fairness distance. Coupling requires two rollouts from the same state, which a simulator permits. We flag this reset requirement, noted as open in the coupled-estimator literature, as a limit on deployment.

Experiment D: exactly-$k$ latent VAE. We train a VAE with exactly-$k$ latent codes on binarized MNIST, Omniglot, and FashionMNIST. At $k=1$ it serves as a sanity check against ARSM and DisARM-Tree. For $k>1$ we found no reported result on Lacuna.

The decisive check is a matched-evaluation variance and objective comparison between our coupled swap estimator and the independent multilinear estimator in Experiments A and B. It will be reported together with the pairing-order study. If the coupled estimator does not reduce variance by at least an order of magnitude and improve the deployed objective at equal budget, the contribution reduces to feasibility-constrained training, and Experiments C and D alone would have to carry it.