Introduction
A training pool for a driving planner consists of logged frames annotated with scenario tags,
such as lane changes, ramps, cut-ins and stops at red lights. Scenarios that are rare in the logs
may nevertheless be important for the model. The pool is therefore resampled before training:
frames from under-represented scenarios are repeated, while those from over-represented scenarios
may be removed where permitted. Because each frame can carry several tags, repeat factors must
be chosen jointly. A frame tagged with both ramp and is_decel, for example, contributes to both
scenario counts, so changing one target affects the other. Assigning one weight to each tag
combination allows the scenario targets to be met while minimising changes to the original pool.
In survey statistics, this procedure is known as raking, or calibration of sampling weights to
known marginal totals [1], [2]. Related work addresses calibration of design weights [3] and
generalized raking for regression in two-phase samples [4].
This article develops the sampling formulation and optimisation methods for balancing such a pool. The task is first formulated as an equality-constrained problem: minimise a per-row distance from the original pool, subject to a linear equality for each scenario target and bounds on each weight. A penalised formulation is then introduced because overlapping tags can make a set of sixty prescribed targets jointly infeasible. The balancing procedure must still return weights and quantify the error for each target. The penalised problem is solved using FISTA [5], an accelerated projected-gradient method. A second solver is derived in the dual space, where the number of multipliers is much smaller than the number of weights. The two methods are evaluated on a private dataset of 172 million frames, with 16,269 tag combinations and 61 targets.
The procedure groups rows into a few thousand patterns, solves a convex optimisation problem over their weights, and rounds the weighted counts to integer copies. On the measured pool, FISTA meets every target to 0.1 % after 30,000 iterations, but its objective remains 15 % above the optimum. Eleven thousand rare tag combinations retain their initial weight, while common combinations receive additional copies. This reflects early stopping in a problem whose curvatures span twelve orders of magnitude. The dual method solves the same problem to machine precision in twelve steps, approximately a hundred times faster, and provides an optimality certificate. Both solutions satisfy the targets, but allocate copies to different rows within each scenario. Per-target errors alone do not reveal this difference.
Section 1 defines the sampling task. Sections 2–5 develop the pattern representation, the equality-constrained and penalised formulations, rounding, and target-error evaluation. Sections 6 and 7 examine combined tags and the resulting coupling between target totals. Section 8 considers scaling with the number of tags. Section 9 first derives the FISTA updates, then the dual semismooth Newton method, and provides pseudocode and a numerical comparison of the two solvers. References are provided in Section 10.
1. The problem
Each training row represents one frame and carries a set of tags, such as free_cruise,
right_turn, stop or ramp. For each targeted tag $c$, a multiplier $t_c$ specifies the
required sampled count relative to its original count. Thus, $t_c=4$ requests four times the
original number of rows carrying that tag. These totals overlap: a row with two targeted tags
contributes to both totals but receives only one sampling weight.
2. Step 1 — collapse rows into patterns
After excluding rows outside the study population, group the retained rows by the tags needed to evaluate the target conditions and by their permitted weight bounds. Rows with the same tag membership and bounds form a pattern $p$, containing $n_p$ rows. All rows in a pattern share one sampling weight. A row that contributes to no target condition retains weight 1.
This grouping reduces the size of the optimisation without changing the sampling problem: the pool used here has 16,269 patterns covering 123 M rows, plus 41.4 M unconstrained rows and 8.2 M excluded rows.
3. Step 2 — a convex quadratic optimisation problem over the pattern weights
Let $P$ denote the number of patterns, with counts $n_p$, and $C$ the number of constraints: one for each targeted tag or tag combination. For constraint $c$, let $\mathcal{P}_c$ be the patterns satisfying its tag condition. The original count is
$$ N_c \;=\; \sum_{p \in \mathcal{P}_c} n_p \qquad\text{(natural count of rows carrying } c\text{, across all sources)} $$Let $t_c>0$ be the prescribed target multiplier for condition $c$, relative to its original count $N_c$. It is a fixed input: for example, $t_c=4$ requests four times the original count. The required sampled count is therefore $t_cN_c$. Define the constraint matrix $A$ by dividing each contributing pattern’s original count by this required count:
$$ a_{cp} \;=\; \frac{n_p}{t_c \, N_c}\quad (p \in \mathcal{P}_c), \qquad a_{cp} = 0 \text{ otherwise.} $$Let $w_p$ be the continuous sampling weight shared by every row in pattern $p$, so that the pattern contributes $n_pw_p$ copies before integer rounding. For example, $w_p=2$ doubles the pattern’s original count. The weights $w=(w_1,\dots,w_P)$ are the optimisation variables.
With this normalisation, $\sum_p a_{cp} w_p = 1$ means that condition $c$ meets its target exactly, and $\sum_p a_{cp} w_p - 1$ is its relative target error.
Equality-constrained formulation. Among the weight vectors that meet every target and respect the bounds, choose the one that minimises the count-weighted squared deviation from retaining each row once:
$$ \begin{aligned} \min_{w\in\mathbb{R}^{P}}\quad & \tfrac{1}{2} \sum_{p=1}^{P} d_p \,(w_p - 1)^{2} \\ \text{s.t.}\quad & \sum_{p} a_{cp}\, w_p \;=\; 1 \qquad c = 1,\dots,C \\ & w_{\min} \;\le\; w_p \;\le\; w_{\max} \qquad p = 1,\dots,P , \end{aligned} $$The counts, targets, coefficients and bounds are fixed inputs. The optimisation chooses only the vector $w$. The notation is:
| notation | meaning |
|---|---|
| $P$, $p$ | Number of patterns and the index of one pattern, $p=1,\dots,P$. A pattern groups rows with the same constrained tags and weight bounds. |
| $C$, $c$ | Number of target constraints and the index of one constraint, $c=1,\dots,C$. A constraint can refer to one tag or a specified combination of tags. |
| $n_p$ | Number of original rows in pattern $p$, before resampling. |
| $\mathcal{P}_c$, $N_c$ | Patterns that satisfy tag condition $c$, and their total original row count: $N_c=\sum_{p\in\mathcal{P}_c}n_p$. For a combination, a row must carry every member tag. |
| $t_c$ | Requested multiplier for condition $c$; its required sampled count is $t_cN_c$. |
| $w=(w_1,\dots,w_P)\in\mathbb{R}^{P}$, $w_p$ | The vector of $P$ real-valued sampling weights, and the weight shared by every row in pattern $p$. That pattern contributes $n_pw_p$ copies before integer rounding. |
| $d_p>0$ | Fixed coefficient determining how much pattern $p$ contributes to the objective. Choosing $d_p\propto n_p$ gives every original row the same importance. It is not a sampling weight to be learned. |
| $a_{cp}$, $A$ | Normalised contribution of pattern $p$ to condition $c$: $a_{cp}=n_p/(t_cN_c)$ if $p\in\mathcal{P}_c$, and $0$ otherwise. $A$ is the $C\times P$ matrix of these coefficients. |
| $w_{\min}$, $w_{\max}$ | Lower bound for pattern $p$ and common upper bound for every weight. Here $w_{\min}=0$ where down-sampling is allowed and $1$ otherwise; $w_{\max}=96$. |
The pattern index on $w_{\min}$ is suppressed; the bound can differ by pattern. In vector expressions, $\mathbf{w}_{\min}$ collects these lower bounds.
The lower bound is set per data source: $w_{\min}=0$ for a synthetic source, so its rows may be
down-sampled, and $w_{\min}=1$ for a real-data source, so its rows are retained at least once.
For real-data patterns, this default can be relaxed to $w_{\min}=0$ when down-sampling is explicitly permitted.
Bounded weights are also used in generalized raking [6].
The upper bound $w_{\max}=96$ accommodates the target of approximately 76 for ramp_dec_aug;
a cap of 64 would make that target unattainable.
For example, $w_p=1$ retains every row of pattern $p$ once, $w_p=2$ doubles its copies, and $w_p=0.5$ keeps half its original count on average, if the bounds allow it. The optimisation uses continuous weights; the rounding step later converts $n_pw_p$ into an integer number of copies.
Interpretation of the objective. A weight of $1$ corresponds to no resampling. The term $(w_p-1)^2$ penalises deviations from this reference, with larger changes receiving a greater penalty. For the equality-constrained problem, a convenient normalisation is
$$ d_p=\frac{n_p}{\sum_{q=1}^{P}n_q}, \qquad \frac{1}{2}\sum_{p=1}^{P}d_p(w_p-1)^2 =\frac{\sum_{p=1}^{P}n_p(w_p-1)^2}{2\sum_{q=1}^{P}n_q}. $$Here $q$ indexes all patterns, so $\sum_q n_q$ is the total number of rows represented in the optimisation. The objective is half the average squared change in row weight. For a given change, a pattern with 1,000 rows contributes ten times as much as one with 100 rows. The factor $1/2$ simplifies differentiation without affecting the minimising weights; multiplying all $d_p$ by any positive constant also leaves the equality-constrained solution unchanged. The objective is zero when every $w_p=1$. When resampling is required, it selects the feasible weights with the smallest squared deviation, rather than the fewest changed rows. This is the chi-square distance of Deville and Särndal [2] between the resampled and original pools.
Interpretation of the constraints. The abbreviation “s.t.” means “subject to”. Each equality is the normalised form of
$$ \sum_{p\in\mathcal{P}_c}n_pw_p=t_cN_c: \qquad\text{sampled count for condition }c=\text{required count}. $$All $C$ equalities must hold simultaneously because a row with several tags contributes to each corresponding count. In matrix notation, $Aw=\mathbf{1}$, where $\mathbf{1}$ is the length-$C$ vector of ones. The inequalities $w_{\min}\le w_p\le w_{\max}$ restrict each weight to its permitted interval; together, these intervals form the box. The objective selects among weights satisfying both the equalities and the box constraints. Section 9 derives the dual, and §9.3 describes the exact equality-constrained solution.
Rationale for the penalised formulation. The equality-constrained problem has a solution only if all $C$ target equations can hold simultaneously within the box. The number of equations relative to the number of unknowns does not establish feasibility. Although $C = 61$ equations in $P = 16{,}269$ unknowns form an underdetermined system, the box introduces $2P$ inequalities. Feasibility depends on whether the affine subspace $\{Aw=\mathbf{1}\}$ intersects the box.
To ensure that balancing still returns weights when the targets are inconsistent, the equalities are replaced by a quadratic penalty:
$$ \min_{w}\;\; \tfrac{1}{2} \sum_{c=1}^{C} \rho_c \Big( \sum_{p} a_{cp}\, w_p \;-\; 1 \Big)^{2} \;+\; \tfrac{1}{2} \sum_{p=1}^{P} d_p \,(w_p - 1)^{2} $$$$ \text{s.t.}\qquad w_{\min} \;\le\; w_p \;\le\; w_{\max} $$Here $\rho_c>0$ is the fixed penalty coefficient for target $c$: it weights the squared relative error $(\sum_p a_{cp}w_p-1)^2$. A larger $\rho_c$ penalises errors in that target more strongly. The numerical comparison uses $\rho_c=1$ for every target.
Existence and uniqueness. The penalised problem has a unique solution when $d_p>0$ for every pattern and the box is nonempty. The continuous objective attains a minimum on the closed, bounded box, which guarantees existence.
To establish uniqueness, let $f(w)$ denote the penalised objective above and let $v\in\mathbb{R}^{P}$ be any nonzero direction in weight space. Its curvature in this direction, expressed through the Hessian $\nabla^2 f$ (the matrix of second derivatives), is
$$ v^{\!\top}\nabla^2 f\,v = \underbrace{\sum_{c=1}^{C}\rho_c\left(\sum_{p=1}^{P}a_{cp}v_p\right)^2}_{\ge 0} \;+\; \underbrace{\sum_{p=1}^{P}d_pv_p^2}_{>0\;\text{when every }d_p>0}. $$At least one component of $v$ is nonzero, so the second term is strictly positive when every $d_p>0$. The objective therefore has positive curvature in every nonzero direction and is strictly convex.
In the measured problem, $A$ has 61 rows and 16,269 columns, so there are nonzero directions $v$ with $Av=0$. Moving along such a direction leaves every target count unchanged, and the target penalty has zero curvature in that direction. Positive $d_p$ supplies the missing curvature. Requiring $d_p>0$ for every pattern is a sufficient condition for uniqueness; the box constraints can sometimes yield a unique solution under weaker conditions.
When the equalities are feasible, the penalised solution approximates the equality-constrained optimum, with a discrepancy determined by the penalty strength. At the setting used here, the maximum weight difference is 0.07 and the copy-count difference is 0.02 % (§9.3). When the equalities are infeasible, each residual measures a target’s relative error (§5), indicating which targets may need revision. The formulation introduces the parameter $\lambda$, defined below, which controls how closely the targets are enforced and has no counterpart in the equality-constrained problem. This choice is separate from both the solver and the allocation of copies within a tag. The dual method solves the penalised problem exactly in 12 steps (§9.3), whereas FISTA does not converge within the measured iteration budget (§9.7). The allocation depends on $d_p$: both formulations admit either the optimum independent of pattern size or the pattern-size floor alternative. The equality-constrained solver remains useful for checking a new target specification: a zero residual certifies joint attainability, while unbounded multipliers certify infeasibility.
How $d_p$ is set. A common regularisation parameter $\lambda>0$ is scaled by each pattern’s share of the pool:
$$ d_p \;=\; \lambda^{2}\,\frac{n_p}{\sum_q n_q}. $$The numerical comparison uses $\lambda=0.01$.
With 61 constraints and 16,269 weights, the system has a large null space of equally valid solutions. The regulariser $\tfrac{1}{2}\sum_p d_p (w_p-1)^2$ selects the solution closest to no resampling in the Deville–Särndal chi-square distance [2] and makes the QP strictly convex. Choosing $d_p\propto n_p$ assigns a penalty of $\lambda^2/N$ to each row and sums it over the pattern. The regulariser therefore measures the average squared change in row weight; without this scaling, patterns containing 3 rows and 3 M rows would be penalised equally. Along constrained directions, the constraint curvature is $\sim(\text{share}_p/t_c)^2$, whereas the regulariser contributes $\lambda^2\,\text{share}_p$. The resulting bias in a realised multiplier is approximately
$$ \text{bias}_c \;\approx\; \frac{d_p}{1/t_c^{2} + d_p}, $$At the scale of this pool (share $\sim 10^{-5}$), the bias is $<0.1\%$, consistent with the $\le 0.16\%$ errors in §5. Along null-space directions, $d_p$ is the only contribution and fixes those weights at exactly 1. Increasing $\lambda$ favours weights closer to 1 while permitting larger target errors. Decreasing it enforces the targets more closely but worsens conditioning and slows FISTA.
Extension to other linear requirements. The formulation also accommodates requirements beyond per-tag multipliers. Let $c_p = n_p w_p$ be the sampled copies of pattern $p$. The objective is a separable distance between the sampled and original pools, the box bounds each pattern’s multiplier, and each requirement is linear in the copies. Any such requirement can be added as a row of the general system $Aw = b$:
$$ \sum_p g_{cp}\, c_p = h_c \quad\Longleftrightarrow\quad a_{cp} = \frac{g_{cp}\, n_p}{T_c},\qquad b_c = \frac{h_c}{T_c}, $$Here $T_c$ is a scale for each row. Taking $T_c = h_c$ makes $\sum_p a_{cp}w_p - b_c$ a relative error, so the penalties $\rho_c$ are comparable across requirement types. The multiplier target in §1 uses $g_{cp}=\mathbf{1}[p\ni c]$ and $h_c = t_c N_c$, giving $b_c = 1$. The penalised objective becomes $\tfrac{1}{2}\sum_c\rho_c\big(\sum_p a_{cp}w_p-b_c\big)^2+\tfrac{1}{2}\sum_p d_p(w_p-1)^2$. Rounding and target-error evaluation remain unchanged. The dual method in §9.3 also applies, with the gradient replaced by $\nabla g(\mu)=Aw(\mu)-b-R^{-1}\mu$. Examples of compatible requirements are listed below.
| what is held fixed | requirement on the copies $c_p=n_p w_p$ | row $g_{c\cdot}$ and right-hand side $h_c$ |
|---|---|---|
| multiplier target $t_c$ for tag $c$ (the targets of §1) | $\sum_{p\ni c} c_p = t_c N_c$ | $g_{cp}=\mathbf{1}[p\ni c]$, $h_c = t_cN_c$ |
| absolute count $K_c$ of tag $c$ | $\sum_{p\ni c} c_p = K_c$ | $g_{cp}=\mathbf{1}[p\ni c]$, $h_c = K_c$ |
| number of training samples per epoch $T$ | $\sum_p c_p = T$ | $g_p = 1$, $h = T$ |
| share $s_c$ of the epoch for tag $c$ (a fixed ratio) | $\sum_{p\ni c} c_p = s_c\sum_p c_p$ | $g_{cp}=\mathbf{1}[p\ni c]-s_c$, $h_c = 0$ |
| ratio $r$ between tags $c_1$ and $c_2$ | $\sum_{p\ni c_1} c_p = r\sum_{p\ni c_2} c_p$ | $g_p=\mathbf{1}[p\ni c_1]-r\,\mathbf{1}[p\ni c_2]$, $h=0$ |
| joint tag ($c_1$ and $c_2$ together) | $\sum_{p\ni c_1,\,c_2} c_p = K$ | $g_p=\mathbf{1}[p\ni c_1\wedge p\ni c_2]$, $h=K$ |
| quota $Q_s$ for a data source $s$ | $\sum_{p\in s} c_p = Q_s$ | $g_p=\mathbf{1}[p\in s]$, $h = Q_s$ (include source membership in the pattern key for this requirement) |
Requirements with $h_c = 0$, such as shares and ratios, are homogeneous: scaling every weight by the same factor preserves them. They determine the composition of the epoch but leave its size unspecified. A total or absolute count must fix the scale; otherwise, the regulariser determines it. Different requirement types can be combined, for example by specifying multiplier targets and an epoch size, or fixed shares and a fixed total.
Structural requirements. Four properties support these extensions: weights are assigned per pattern, the objective is separable across patterns, requirements are linear in the copies, and bounds apply independently to each pattern. Pattern scanning, rounding and reporting rely on the first property. The closed-form expression $w_p(\mu)$ and the $C\times C$ dual in §9 use the second and third, while clipping uses the fourth. Additional linear requirements therefore leave the procedure intact. The dual has one multiplier per requirement, regardless of the number of patterns.
Results on the measured pool. The equality-constrained variant in §9.3 was used to solve
several requirement sets exactly. Combining the 61 multiplier targets with an epoch size of
550 M or 650 M samples gives 62 equations and requires 36 or 40 Newton steps, respectively,
in 0.1 s; all targets remain satisfied to $10^{-14}$. Changing the epoch size requires
redistributing copies between single-tag and multi-tag patterns: a copy with $k$ tags
contributes $k$ times to the marginals but once to the total. An epoch of 650 M therefore
places 95 multi-tag patterns at their lower bound, while 550 M places 4 singleton patterns
there. Expressing the 61 targets as shares, together with their implied total of 590.4 M,
reproduces the multiplier solution to $10^{-7}$. Keeping those shares with a 700 M epoch
scales the solution by $700/590.4$, with three patterns at $w_{\max}$.
The shares are attainable only for epochs between 590.4 M and 743.2 M samples. Below that
range, intersection_type_8, whose single 17,260-row pattern is already at $w_{\min} = 1$,
would require fewer copies than permitted. Above it, patterns reach $w_{\max}$.
The penalised formulation still returns a solution outside this range, with the residual
report identifying the requirements that were relaxed.
Limits of the formulation. Inequality requirements, such as “at least” or “at most”, remain linear in the copies but require a one-sided penalty or a slack variable in place of the quadratic penalty. Nonlinear requirements, such as an entropy bound for the epoch, do not fit this formulation. The distance can also be changed: replacing the chi-square term $\tfrac{1}{2}d_p(w_p-1)^2$ with another separable convex distance $G_p(w_p)$ preserves the $C$-dimensional dual. The exponential distance of classical raking, for example, gives the iterative-proportional-fitting update. In this case, $w_p(\mu)$ is obtained by inverting $G_p'$ rather than clipping a linear expression, still requiring only one scalar equation per pattern.
Pre-solve validation. Check each target against the interval allowed by the pattern bounds. A target below the minimum attainable count is unreachable. Revise the target or allow down-sampling on the relevant patterns before solving.
4. Step 3 — deterministic quota rounding
Per pattern $p$:
$$ \text{total}_p = \operatorname{round}(n_p\, w_p), \qquad \text{base}_p,\; \text{extra}_p = \operatorname{divmod}(\text{total}_p,\; n_p) $$Every row of the pattern receives $\text{base}_p$ copies; the $\text{extra}_p$ rows with the smallest values of a deterministic hash of their unique identifiers receive one more. This gives the same allocation regardless of the order in which rows are processed; unconstrained rows are retained once.
5. Step 4 — evaluate target errors
For each constraint:
$$ \text{expected}_c = \frac{\sum_{p\in\mathcal{P}_c} n_p w_p}{N_c},\qquad \text{rounded}_c = \frac{\sum_{p\in\mathcal{P}_c} \text{total}_p}{N_c},\qquad \text{rel}_c = \frac{\text{expected}_c - t_c}{t_c} $$These quantities distinguish the error from optimisation from the additional error due to rounding. Target errors should be evaluated alongside an optimality certificate: small marginal errors alone do not show that the objective has been minimised.
For the pool used here (61 constraints, 16,269 patterns, 172 M rows), the worst and some representative target errors of the FISTA solution are:
| tag | $N_c$ | target | realized | rel |
|---|---|---|---|---|
ramp | 323,230 | 47.44 | 47.39 | −0.10 % (worst) |
highspeed_curve_left | 314,125 | 57.50 | 57.45 | −0.10 % |
ramp_dec_aug | 2,120 | 76.27 | 76.27 | −0.00 % |
ego_lane_change_for_navigation | 2.74 M | 15.92 | 15.92 | −0.05 % |
navigation_aug | 6.75 M | 9.53 | 9.53 | −0.04 % |
free_cruise | 7.03 M | 4.76 | 4.76 | −0.00 % |
right_turn | 1.09 M | 4.71 | 4.71 | −0.00 % |
stop | 20.9 M | 1.01 | 1.01 | +0.00 % |
The complete 61-row table, for both solvers, is in §9.7.2.
6. Combined tags
A combined-tag condition is a conjunction: a row satisfies it only when it carries every
member tag. For example, ramp ∧ lane_split describes rows carrying both tags.
(a) Pattern resolution. The pattern representation must retain every tag needed to evaluate
the target conditions. Thus, if a condition involves lane_split, rows carrying
{ramp, lane_split} and rows carrying only {ramp} belong to different patterns.
Retaining an additional tag can split a pattern without adding a constraint. If the resulting
patterns have identical constraint membership and bounds, they can be merged again (§9.4).
(b) Constraint construction. Let $K$ be the set of tags in a conjunction and let $\mathcal{P}_K$ contain all patterns carrying every tag in $K$. Its original count is $N_K=\sum_{p\in\mathcal{P}_K}n_p$. A multiplier target $t_K$ adds the equality
$$ \sum_{p\in\mathcal{P}_K}n_pw_p=t_KN_K, $$or the corresponding residual term in the penalised formulation. This is another row of the same constraint matrix. A row satisfying the conjunction also contributes to each applicable single-tag constraint; one weight must account for all of these contributions. Without a separate conjunction target, the combination’s sampled count is determined by the existing constraints, the objective and the bounds.
7. Why weights must be chosen jointly
The requested multiplier $t_c$ describes the total count of a tag, rather than the weight of each row carrying it. Overlapping tags couple these totals: changing one pattern’s weight changes every constraint to which that pattern contributes. Consequently, its weight must be chosen from the complete system of targets.
The optimisation makes this dependence explicit through $Aw=\mathbf{1}$, or through the joint residual penalty when exact satisfaction is relaxed. The objective then selects among the possible allocations of copies. Section 9.1 shows how the solution can be expressed through one multiplier per constraint, even though the weights belong to patterns.
8. Scaling with the number of tags
Number of observed patterns. A pattern is a set of constrained tags, so $N$ tags allow up to $2^N$ subsets: $2.3\times10^{18}$ when $N = 61$. A pattern is represented, however, only if at least one row carries that tag set:
$$ P \;\le\; \min\!\big(2^{N},\ \#\text{rows}\big), $$Observed co-occurrence is sparse: a frame cannot be both right_turn and go_straight,
and many tags occur in only one source. The pool studied here contains 172 M rows but only
16,269 patterns, approximately $2^{14}$. Doubling $N$ roughly doubles or triples $P$
rather than squaring it. Approaching $\min(2^N, \text{rows})$ would require independent
labels that co-occur uniformly at random, unlike the scenario tags considered here.
Computational cost. Each FISTA iteration costs $O(\mathrm{nnz}(A))$, where $\mathrm{nnz}(A) = \sum_p |\text{tags}(p)| \le N P$; this pool has 65,108 nonzero entries. The $O(1/k^2)$ convergence rate is independent of $P$, but conditioning affects the speed of convergence. The coefficients $d_p$ ensure strict convexity.
The data scan. Constructing the pattern counts requires reading the rows’ tag memberships and bounds. This work is linear in the number of rows, can be parallelised over subsets of the pool, and does not depend on the target multiplier values.
Implications of a large target set.
- Feasibility. Overlapping constraints increase the likelihood of inconsistent targets, for example when tag A requires ×47 and tag B requires ×7.7, but most A rows also carry B. The penalised QP returns a solution whose residuals identify the conflict (§3); a solver cannot eliminate contradictory requirements.
- Upper-bound saturation. A high multiplier for a tag that usually co-occurs with a low-multiplier tag pushes patterns carrying only the first tag towards $w_{\max}$. Counting weights at this bound reveals the effect.
- Interpretability. Realised multipliers remain exact, but the allocation of copies across thousands of patterns becomes difficult to trace manually.
Conjunction targets (§6) add one constraint for each specified combination, without requiring enumeration of all $\binom{N}{2}$ tag pairs. The pattern table already represents every observed conjunction as a variable. Selected combinations can therefore be constrained while the QP determines the remaining allocations.
9. Efficient optimisation using constraint multipliers
The number of constraints, $C=61$, is much smaller than the number of patterns, $P=16{,}269$. The structure of the QP allows optimisation in $\mathbb{R}^{C}$ rather than $\mathbb{R}^{P}$.
9.1 Recovering optimal weights from constraint multipliers
Without the box constraints, stationarity of
$$ f(w)=\tfrac{1}{2}\sum_c \rho_c\big(a_c^{\!\top}w-1\big)^2+\tfrac{1}{2}\sum_p d_p\,(w_p-1)^2 $$gives per pattern $d_p\,(w_p - 1) = -\sum_c a_{cp}\,\rho_c\,r_c$ with $r_c = a_c^{\!\top}w-1$, i.e.
$$ \boxed{\;w_p \;=\; 1-\frac{1}{d_p}\sum_{c=1}^{C} a_{cp}\,\mu_c\;},\qquad \mu_c=\rho_c\,r_c . $$Each weight is $1$ plus a linear combination of the multipliers $\mu_c$ for the constraints to which its pattern contributes. Substitution gives
$$ \big(A D^{-1} A^{\!\top} + R^{-1}\big)\,\mu \;=\; A\mathbf{1} - \mathbf{1}, \qquad D=\operatorname{diag}(d_p),\; R=\operatorname{diag}(\rho_c), $$This is a dense $C\times C$ linear system, only 61×61 here, solvable in microseconds. Forming $A D^{-1} A^{\!\top}$ requires one pass over the pattern table, at a cost of $O(\mathrm{nnz}(A)\cdot C)$.
9.2 Solving the QP with FISTA
FISTA [5] is an accelerated projected-gradient method. It requires neither matrix assembly nor a linear solve and enforces the box constraints by clipping. The following description uses the notation of §3 to support comparison with the dual method. Numerical values are taken from the pattern table evaluated in §9.7.
Step 1 — the gradient. With $f(w)=\tfrac{1}{2}\sum_c\rho_c(a_c^{\!\top}w-1)^2+\tfrac{1}{2}\sum_p d_p(w_p-1)^2$,
$$ \nabla f(w) \;=\; A^{\!\top}\big(\rho\odot(Aw-\mathbf{1})\big) \;+\; d\odot(w-\mathbf{1}), $$Evaluating the gradient requires one pass through $A$ and one through $A^{\!\top}$, at a cost of $O(\mathrm{nnz}(A))$. On this pool, with 65,108 nonzero entries, a single-threaded evaluation takes 1.7 ms. The first term accounts for target residuals; the second penalises deviations from a weight of 1.
Step 2 — global step size. A safe gradient step requires a step size smaller than $1/L$, where $L$ is the largest curvature of $f$, or the largest eigenvalue of the Hessian $H = A^{\!\top}RA + D$. In the numerical comparison, $L$ is estimated using 30 power iterations on $Hv$, and the step size is set to
$$ \eta \;=\; \frac{1}{1.05\,L}. $$For this pool, $L = 1.000$, determined by intersection_type_8: a single-pattern constraint
with target 1.0 and coefficient $a_{cp}=n_p/(t_cN_c)=1$. Thus, $\eta = 0.952$. This same
step size is applied to every coordinate, including a 4-row pattern whose curvature is
$d_p\approx10^{-12}$.
Step 3 — initialise. $w^{0}=\Pi_{[\mathbf{w}_{\min},w_{\max}]}(\mathbf{1})=\mathbf{1}$, extrapolation point $y^{0}=w^{0}$, momentum counter $t_0=1$.
Step 4 — the accelerated iteration. For $k = 0,1,2,\ldots$
$$ w^{k+1} = \Pi_{[\mathbf{w}_{\min},\,w_{\max}]}\!\big(y^{k}-\eta\,\nabla f(y^{k})\big),\qquad t_{k+1} = \frac{1+\sqrt{1+4t_k^{2}}}{2},\qquad y^{k+1} = w^{k+1} + \frac{t_k-1}{t_{k+1}}\big(w^{k+1}-w^{k}\big). $$The first update is projected gradient descent, with element-wise clip providing the
exact projection $\Pi$ onto the box. The extrapolation uses Nesterov momentum: the next
gradient is evaluated beyond $w^{k+1}$ in the direction of the preceding update, with a
coefficient approaching $1-3/k$. This acceleration improves the $O(1/k)$ rate of standard
gradient descent to $O(1/k^{2})$.
Step 5 — adaptive restart. If $f(w^{k+1}) > f(w^{k})$, the momentum has caused an overshoot. The method resets $y = w^{k+1}$ and $t=1$, following the O’Donoghue–Candès restart [7]. This keeps the objective monotone and recovers a linear rate for strongly convex problems.
Step 6 — stopping rule. Iteration stops when the relative change in the objective falls below $\tau_f=10^{-10}$ or the budget of $K=30{,}000$ iterations is reached. The stopping status records which condition applied. The rule does not check the gradient, distance to the optimum, or duality gap.
Algorithm 1 — FISTA for the penalised QP. The algorithm combines FISTA [5] with adaptive restart [7] to solve the formulation in §3.
| Algorithm 1: FISTA for the penalised raking QP | |
|---|---|
| Input | $A\in\mathbb{R}^{C\times P}$, $\rho\in\mathbb{R}^{C}$, $d\in\mathbb{R}^{P}_{>0}$, bounds $\mathbf{w}_{\min}, w_{\max}$, iteration budget $K=30{,}000$, stopping tolerance $\tau_f=10^{-10}$ |
| Output | weights $w$, iteration count, stopping status |
| 1 | $\nabla f(w) := A^{\!\top}\big(\rho\odot(Aw-\mathbf{1})\big)+d\odot(w-\mathbf{1})$ |
| 2 | $L\leftarrow$ largest eigenvalue of $A^{\!\top}RA+D$ by 30 power iterations on $v\mapsto A^{\!\top}(\rho\odot Av)+d\odot v$; $\eta\leftarrow 1/(1.05\,L)$ |
| 3 | $w\leftarrow\Pi_{[\mathbf{w}_{\min},w_{\max}]}(\mathbf{1})$, $y\leftarrow w$, $t\leftarrow 1$, $f_{\text{prev}}\leftarrow+\infty$ |
| 4 | for $k = 0,1,\dots,K-1$: |
| 5 | $w_{\text{new}}\leftarrow\Pi_{[\mathbf{w}_{\min},w_{\max}]}\big(y-\eta\,\nabla f(y)\big)$ (projected gradient step; $\Pi$ = clip) |
| 6 | $t_{\text{new}}\leftarrow\tfrac{1}{2}\big(1+\sqrt{1+4t^{2}}\big)$, $\quad y\leftarrow w_{\text{new}}+\tfrac{t-1}{t_{\text{new}}}\,(w_{\text{new}}-w)$ (Nesterov momentum) |
| 7 | $f\leftarrow f(w_{\text{new}})$; if $f > f_{\text{prev}}$: $y\leftarrow w_{\text{new}}$, $t_{\text{new}}\leftarrow 1$ (adaptive restart) |
| 8 | if $\lvert f_{\text{prev}}-f\rvert\le\tau_f\cdot\max(1,\lvert f\rvert)$: return $w_{\text{new}}$, $k+1$, stopping criterion met |
| 9 | $w\leftarrow w_{\text{new}}$, $t\leftarrow t_{\text{new}}$, $f_{\text{prev}}\leftarrow f$ |
| 10 | return $w$, $K$, iteration budget reached |
Each iteration requires one product with $A$, one with $A^{\!\top}$, and element-wise operations, for a cost of $O(\mathrm{nnz}(A))$. No matrix is assembled or linear system solved. On the measured pool, the algorithm reaches its iteration limit at line 10.
Convergence bound and observed behaviour. FISTA [5] satisfies
$$ f(w^{k})-f^{\ast} \;\le\; \frac{2L\,\lVert w^{0}-w^{\ast}\rVert^{2}}{(k+1)^{2}}, $$This bound has no dependence on the small curvatures. On the measured pool, $\lVert w^{0}-w^{\ast}\rVert = 3{,}188$: many small patterns have optimal weights 10–90 away from their initial value of 1. The bound is $10\,f^{\ast}$ at 30,000 iterations, $0.1\,f^{\ast}$ at 300,000, and $0.01\,f^{\ast}$ at $10^{6}$. The observed gaps of $0.15\,f^{\ast}$ and $0.011\,f^{\ast}$ lie within these bounds. Restarts may instead give a linear rate with contraction $1-\sqrt{d_{\min}/L}$ per iteration. Reaching a fixed relative accuracy would then require $\sqrt{L/d_{\min}}=\sqrt{\kappa}\approx10^{6}$ iterations, thirty times the budget. The slow convergence is therefore consistent with first-order optimisation when curvatures span twelve orders of magnitude.
Comparison with the dual solver.
| FISTA | dual Newton (§9.3) | |
|---|---|---|
| unknowns iterated | $P = 16{,}269$ weights | $C = 61$ multipliers |
| per-iteration work | one $\nabla f$: $O(\mathrm{nnz}(A))$ | one $w(\mu)$ + $\nabla g$: $O(\mathrm{nnz}(A))$, plus a $61\times61$ solve |
| per-coordinate scaling | none: one $\eta=1/(1.05L)$ for all $p$ | exact: $w_p$ is rescaled by $1/d_p$ inside $w(\mu)$ |
| iterations on this pool | 30,000 (cap hit) | 12 |
| wall time on this pool | 9.1 s | 87 ms |
| box constraint | clip after each step | clip inside $w(\mu)$; free set changes handled by the line search |
| convergence certificate | none (relative change of $f$) | duality gap $f(w)-g(\mu)$, zero at the optimum |
| what it returns at the cap | targets met, tail frozen at $w=1$ (§9.7) | the unique optimum |
Both methods access the same matrix the same number of times per iteration. Their main difference is coordinate scaling. FISTA applies a common step size to all gradients, so a pattern with a gradient of $10^{-6}$ changes by approximately $10^{-6}$ per step. The dual method divides by $d_p$ when recovering the weights, immediately assigning each pattern the weight implied by the 61 multipliers.
9.3 Dual formulation and semismooth Newton method
The derivation in §9.1 omitted the box constraints. With $w_{\min} \le w_p \le w_{\max}$, unconstrained stationarity no longer applies directly, but the separable structure remains. The $C$ constraint residuals are the only terms coupling the $P$ weights. Dualising these residuals gives a $C$-dimensional problem, from which every $w_p$ can be recovered in closed form. The derivation below specifies the sign conventions governing the multiplier and weight updates. It also applies to the equality-constrained and pattern-size-floor variants described at the end of this section.
Step 0 — introduce the residual variables. Define $r_c = \sum_p a_{cp} w_p - 1$, the relative error for tag $c$. The QP in §3 becomes
$$ \min_{w,\,r}\;\; \underbrace{\tfrac{1}{2}\sum_{c} \rho_c\, r_c^{2}}_{\text{targets}} \;+\; \underbrace{\tfrac{1}{2}\sum_{p} d_p\,(w_p-1)^{2}}_{\text{stay near 1}} \qquad\text{s.t.}\quad r = A w - \mathbf{1},\quad w_{\min} \le w_p \le w_{\max}. $$Introducing $r$ separates the objective into $C$ scalar terms in $r$ and $P$ scalar terms in $w$. The variables are coupled only through $r = Aw - \mathbf{1}$.
Step 1 — form the Lagrangian. Assign a multiplier $\mu_c$ to each of the $C$ coupling equations. Retain the box as an explicit constraint, enforced by projection:
$$ \mathcal{L}(w, r;\mu) \;=\; \tfrac{1}{2}\sum_c \rho_c r_c^{2} + \tfrac{1}{2}\sum_p d_p (w_p-1)^{2} \;+\; \sum_c \mu_c\Big(\sum_p a_{cp} w_p - 1 - r_c\Big), \qquad w_{\min} \le w_p \le w_{\max}. $$The dual function is $g(\mu) = \min_{r,\;w\in\text{box}} \mathcal{L}(w,r;\mu)$. Because $\mathcal{L}$ is a sum of terms each involving a single $r_c$ or a single $w_p$, the minimisation splits into $C + P$ scalar problems.
Step 2 — minimise over each residual. $\partial\mathcal{L}/\partial r_c = \rho_c r_c - \mu_c = 0$ gives
$$ r_c(\mu) = \frac{\mu_c}{\rho_c}, \qquad \min_{r_c}\Big[\tfrac{1}{2} \rho_c r_c^{2} - \mu_c r_c\Big] = -\frac{\mu_c^{2}}{2\rho_c}. $$Thus, $\mu_c$ is the residual for tag $c$ scaled by $\rho_c$; a negative value indicates that the tag is below target. This recovers the identity $\mu_c = \rho_c r_c$ used in §9.1.
Step 3 — minimise over each bounded weight. Let $s_p = \sum_c a_{cp}\,\mu_c = (A^{\!\top}\mu)_p$ collect the multiplier contributions for pattern $p$. The terms in $\mathcal{L}$ involving $w_p$ form a convex quadratic:
$$ \varphi_p(w_p) = \tfrac{1}{2} d_p (w_p-1)^{2} + s_p\, w_p, \qquad \varphi_p'(w_p) = 0 \;\Rightarrow\; \hat w_p = 1 - \frac{s_p}{d_p}. $$The minimiser of a convex scalar function over an interval is the projection of its unconstrained minimiser onto that interval. If $\hat w_p$ lies inside, it is optimal; otherwise, monotonicity over the interval places the optimum at the nearest endpoint. Therefore,
$$ \boxed{\;w_p(\mu) \;=\; \Pi_{[w_{\min},\,w_{\max}]}\!\Big(1-\frac{1}{d_p}\sum_c a_{cp}\,\mu_c\Big)\;} $$This is the expression in §9.1 with clipping added. Substituting $a_{cp}=n_p/(t_cN_c)$ and $d_p=\lambda^2 n_p/\sum_q n_q$ cancels $n_p$, giving the projection argument $1+\sum_{c\in\text{tags}(p)}\beta_c$, where $\beta_c=-\frac{\sum_q n_q}{\lambda^2}\frac{\mu_c}{t_cN_c}$. This is the additive relationship evaluated in §9.7.3. A tag below target ($\mu_c<0$) contributes a positive increment.
Step 4 — construct the dual function. Substituting the results of Steps 2 and 3 into $\mathcal{L}$ gives
$$ g(\mu) \;=\; -\tfrac{1}{2}\,\mu^{\!\top} R^{-1}\mu \;-\; \mu^{\!\top}\mathbf{1} \;+\; \sum_{p}\Big[\tfrac{1}{2} d_p\big(w_p(\mu)-1\big)^{2} + s_p\, w_p(\mu)\Big], \qquad R=\operatorname{diag}(\rho_c). $$For an unclipped pattern, the bracketed term is $s_p - s_p^{2}/(2d_p)$. For a clipped pattern, it is $\tfrac{1}{2} d_p(b_p-1)^2 + s_p b_p$, where $b_p$ is the active bound. If no pattern is clipped, $g$ is the concave quadratic $-\tfrac{1}{2}\mu^{\!\top}\big(R^{-1}+AD^{-1}A^{\!\top}\big)\mu+\mu^{\!\top}(A\mathbf{1}-\mathbf{1})$, whose maximiser solves the $C\times C$ system in §9.1.
Weak duality. For any feasible $w$ set $r=Aw-\mathbf{1}$; then $\mathcal{L}(w,r;\mu)=f(w)$ for every $\mu$, and $g(\mu)$ is a minimum over a larger set, so $g(\mu)\le f(w)$. In particular $g(\mu)\le f^\ast$ for all $\mu$.
Concavity. For fixed $(w,r)$, $\mathcal{L}$ is affine in $\mu$; $g$ is a pointwise minimum of affine functions, hence concave. The maximisation over $\mu\in\mathbb{R}^{C}$ is unconstrained and has no spurious local maxima.
Gradient. By the envelope theorem (differentiate $\mathcal{L}$ at the minimiser; the minimiser’s own dependence on $\mu$ contributes nothing to first order, because on free coordinates $\partial\mathcal{L}/\partial w_p=0$ and clipped coordinates do not move),
$$ \boxed{\nabla g(\mu) = A\,w(\mu) - \mathbf{1} - R^{-1}\mu} $$The gradient is the difference between the realised residual and the residual implied by the multiplier. Because $w(\mu)$ is continuous and piecewise linear, $g$ is continuously differentiable and piecewise quadratic; changes in curvature occur when a pattern enters or leaves a bound. The expression was checked numerically against central differences on this pool’s table. The alternative sign convention $\mathbf{1} - Aw - R^{-1}\mu$ does not match this calculation: it corresponds to $\mu\to-\mu$, which would also change Step 3 to $1+s_p/d_p$.
Step 5 — strong duality and the certificate. The primal is a convex quadratic over a box, so strong duality holds ($\max_\mu g = \min_w f$) and the pair $(w^\ast,\mu^\ast)$ is characterised by $\nabla g(\mu^\ast)=0$, i.e.
$$ \mu^\ast_c = \rho_c\Big(\sum_p a_{cp}\,w_p(\mu^\ast) - 1\Big),\qquad w^\ast = w(\mu^\ast). $$The dual provides two forms of certification. First, any $\mu$ bounds the error of its recovered primal weights: $0\le f\big(w(\mu)\big)-f^\ast\le f\big(w(\mu)\big)-g(\mu)$. The duality gap is therefore a computable upper bound on suboptimality, independent of another solver. The Newton solution has a gap of $0$ to machine precision on this pool. Second, any primal iterate $w$ can be assessed by setting $\mu_w=R(Aw-\mathbf{1})$. For the FISTA iterate, $f(w_F)-g(\mu_{w_F}) = 5.4\times10^{-4}$, which bounds its actual suboptimality of $3.4\times10^{-4}$: a relative bound of 24 % compared with the actual 15 %. The FISTA stopping rule does not include this check (§9.7.1).
Step 6 — Newton on the dual. Where $g$ is twice differentiable,
$$ \nabla^{2} g(\mu) \;=\; -\Big(A_{\mathcal{F}}\,D_{\mathcal{F}}^{-1}A_{\mathcal{F}}^{\!\top} + R^{-1}\Big), \qquad \mathcal{F}(\mu)=\{p:\ w_{\min}<\hat w_p(\mu)< w_{\max}\}, $$For a free pattern, $\partial w_p/\partial\mu = -a_{\cdot p}/d_p$; for a clipped pattern, the derivative is $0$. The bracketed $C\times C$ matrix is symmetric positive definite. The free-pattern term supplies strict concavity along directions involving those patterns, and $R^{-1}$ supplies it in the remaining directions. At clipping boundaries, the expression serves as the generalised Hessian. The Newton ascent update is
$$ \mu \;\leftarrow\; \mu + \tau\,\Big(A_{\mathcal{F}}D_{\mathcal{F}}^{-1}A_{\mathcal{F}}^{\!\top}+R^{-1}\Big)^{-1}\nabla g(\mu), $$A backtracking line search on $g$ selects $\tau\in(0,1]$ to handle changes in the free set $\mathcal{F}$. This is a semismooth Newton method [8]. Once the correct free set is identified, a full step reaches the exact maximiser because $g$ is quadratic in that region. Each iteration evaluates $w(\mu)$ and $\nabla g$, assembles $A_{\mathcal{F}}D^{-1}_{\mathcal{F}}A_{\mathcal{F}}^{\!\top}=\sum_{p\in\mathcal{F}}\frac1{d_p}a_{\cdot p}a_{\cdot p}^{\!\top}$ through rank-$k_p$ updates, and solves a $61\times61$ system. Here each pattern has $k_p\le 8$ nonzero entries, and $\sum_p k_p^2 = 2.8\times10^{5}$ multiply-adds are required. Starting at $\mu=0$, which gives $w=\mathbf{1}$ as in FISTA, the method takes 10 damped steps to establish the free set and 2 steps in the quadratic regime.
Algorithm 2 — dual semismooth Newton method. The semismooth Newton framework [8] is applied to the dual derived above to obtain the results in §9.7.
| Algorithm 2: semismooth Newton on the dual of the penalised raking QP | |
|---|---|
| Input | $A$, $\rho$ (so $R=\operatorname{diag}\rho$), $d$ (so $D=\operatorname{diag}d$), bounds $\mathbf{w}_{\min}, w_{\max}$, tolerance $\tau$ ($10^{-13}$), step cap (100) |
| Output | multipliers $\mu^\ast$, weights $w^\ast=w(\mu^\ast)$, duality gap $f(w^\ast)-g(\mu^\ast)$ |
| 1 | $w(\mu) := \Pi_{[\mathbf{w}_{\min},\,w_{\max}]}\big(\mathbf{1}-D^{-1}A^{\!\top}\mu\big)$; $\mathcal{F}(\mu) := \{p:\ w_{\min}<1-(A^{\!\top}\mu)_p/d_p< w_{\max}\}$ (Step 3: KKT map and free set) |
| 2 | $g(\mu) := -\tfrac{1}{2}\mu^{\!\top}R^{-1}\mu-\mu^{\!\top}\mathbf{1}+\sum_p\big[\tfrac{1}{2}d_p(w_p(\mu)-1)^{2}+(A^{\!\top}\mu)_p\,w_p(\mu)\big]$ (Step 4: the dual) |
| 3 | $\mu\leftarrow 0$ (so $w(\mu)=\mathbf{1}$, the same start as Algorithm 1) |
| 4 | repeat |
| 5 | $w\leftarrow w(\mu)$, $\ \mathcal{F}\leftarrow\mathcal{F}(\mu)$, $\ r\leftarrow Aw-\mathbf{1}-R^{-1}\mu$ ($r=\nabla g(\mu)$, Step 4) |
| 6 | if $\lVert r\rVert_\infty\le\tau$: break (Step 5: $\nabla g=0$ is optimality) |
| 7 | $H\leftarrow A_{\mathcal{F}}D_{\mathcal{F}}^{-1}A_{\mathcal{F}}^{\!\top}+R^{-1}$ ($C\times C$, SPD; Step 6) |
| 8 | solve $H\,\delta = r$ (Newton ascent direction) |
| 9 | $t\leftarrow 1$; while $g(\mu+t\delta) < g(\mu)$: $t\leftarrow t/2$ (backtracking on the dual; guards changes of $\mathcal{F}$) |
| 10 | $\mu\leftarrow\mu+t\,\delta$ |
| 11 | until converged or the step cap is reached |
| 12 | $w^\ast\leftarrow w(\mu)$; report $f(w^\ast)-g(\mu)$ (the certificate: $0$ at the optimum) |
| 13 | return $\mu^\ast=\mu$, $w^\ast$ |
Each step requires one product with $A$ and one with $A^{\!\top}$ to evaluate $w(\mu)$ and $r$, the rank-$k_p$ updates used to assemble $H$, and a dense $61\times61$ solve. Assembly requires $\sum_{p\in\mathcal{F}}k_p^{2}$ multiply-adds, or $2.8\times10^{5}$ here. The measured run takes 12 steps: 10 damped steps while the free set changes, followed by 2 full steps. The diagonal term $R^{-1}$ keeps $H$ nonsingular, so the penalised solver requires no continuation. The equality-constrained variant has $R^{-1}=0$.
Local convergence guarantees. Let $\mu^\ast$ be the unique maximiser of the penalised dual, and let $e_k=\lVert\mu^k-\mu^\ast\rVert_2$ denote the multiplier error at iteration $k$. With exact Newton solves, a sufficiently close starting point and full steps, semismooth Newton theory [8] gives superlinear convergence, $e_{k+1}/e_k\to0$. The strongly semismooth gradient in this problem gives the stronger local quadratic bound
$$ \boxed{ \lVert\mu^{k+1}-\mu^\ast\rVert_2 \;\le\; K\,\lVert\mu^k-\mu^\ast\rVert_2^2, \qquad k\ge k_0 , } $$where $K>0$ is a problem-dependent constant and $k_0$ marks entry into the neighbourhood where full steps are accepted. Once the error is small, this approximately doubles the number of accurate digits per step, until rounding errors in the numerical computation dominate.
The assumptions can be checked from the formulation. Clipping an affine function is continuous and piecewise affine, so $w(\mu)$ and $\nabla g(\mu)$ are strongly semismooth: their generalised linear approximation has an error of at most second order in the step. Moreover, since $d_p>0$ and $\rho_c>0$, every Newton matrix satisfies
$$ H_k=A_{\mathcal F_k}D_{\mathcal F_k}^{-1}A_{\mathcal F_k}^{\!\top}+R^{-1} \;\succeq\;mI, \qquad m=\min_c\frac{1}{\rho_c}>0 . $$Here $I$ is the identity matrix and $H_k\succeq mI$ means that every eigenvalue of $H_k$ is at least $m$. Thus $\lVert H_k^{-1}\rVert_2\le1/m$: the inverse matrices remain bounded, including when the set of clipped patterns changes. These properties give the quadratic rate above [8].
To express the rate in objective values, define the dual objective gap $\Delta_k=g(\mu^\ast)-g(\mu^k)$ and $M=\lambda_{\max}(AD^{-1}A^{\!\top}+R^{-1})$, the largest eigenvalue of the displayed matrix. Strong concavity and the gradient bound give
$$ \frac{m}{2}e_k^2\le\Delta_k\le\frac{M}{2}e_k^2, \qquad \Delta_{k+1}\le\frac{2MK^2}{m^2}\,\Delta_k^2 \quad(k\ge k_0). $$The dual objective gap therefore also converges locally quadratically. The primal objective error of the recovered weights is bounded by the computable duality gap in Step 5. This local result complements the $O(1/k^2)$ objective-gap bound for standard FISTA [5]; it does not give a bound on how many damped Newton steps are needed to reach the local regime.
Comparing the rates directly. The exponent 2 has different meanings in the two statements. Standard FISTA [5] bounds the primal objective gap by $E_k=f(w^k)-f^\ast\le B/(k+1)^2$, where $B=2L\lVert w^0-w^\ast\rVert_2^2$ is a fixed problem-dependent constant. Newton’s local bound relates consecutive errors: writing $a=2MK^2/m^2$, it gives $\Delta_{k+1}\le a\Delta_k^2$. This is a bound on the next error in terms of the current error, rather than a formula in $k$.
To see why repeated squaring is faster once the error is small, define the scaled dual gap $q_k=a\Delta_k$. Then, within the local convergence region,
$$ q_{k+1}\le q_k^2, \qquad q_{k+j}\le q_k^{\,2^j}, $$where $j$ is the number of additional iterations. If $q_k=10^{-2}$, the next three gaps are bounded by
$$ 10^{-2}\;\longrightarrow\;10^{-4}\;\longrightarrow\;10^{-8} \;\longrightarrow\;10^{-16}. $$Each local step doubles the exponent in this bound. In contrast, reducing FISTA’s $B/(k+1)^2$ bound by a factor of $10^4$ requires increasing $k+1$ by a factor of 100. Newton needs only one additional local step to reduce a scaled gap of $10^{-4}$ to at most $10^{-8}$. These are illustrations of the rate bounds, not exact error trajectories. The condition $q_k<1$ matters: squaring then improves the bound, and the improvement becomes stronger as the error decreases.
For a comparison using the same objective, evaluate $E_k=f(w^k)-f^\ast$ for both methods, with $w^k=w(\mu^k)$ for dual Newton. Its computable duality gap from Step 5 is
$$ 0\le E_k\le\Gamma_k, \qquad \Gamma_k=f(w(\mu^k))-g(\mu^k) =\tfrac12\nabla g(\mu^k)^\top R\,\nabla g(\mu^k). $$The last identity follows by substituting the primal and dual objectives and completing the square in $Aw(\mu^k)-\mathbf{1}-R^{-1}\mu^k$. Since $m e_k\le\lVert\nabla g(\mu^k)\rVert_2\le M e_k$ and $R$ is positive definite, $\Gamma_k$ is bounded above and below by positive constants times $e_k^2$. It therefore also satisfies a local quadratic recurrence, with its own constant. Thus $\Gamma_k\le\varepsilon$ certifies the same primal accuracy $E_k\le\varepsilon$.
| method | guarantee for primal objective accuracy | sufficient iteration count as $\varepsilon\to0$ |
|---|---|---|
| standard FISTA [5] | $E_k\le B/(k+1)^2$ | $O(\varepsilon^{-1/2})$ |
| dual Newton under the local assumptions [8] | $E_k\le\Gamma_k$, with $\Gamma_k$ converging quadratically | $k_0+O(\log\log(1/\varepsilon))$ |
Here the problem parameters are fixed, $\varepsilon>0$ is the desired objective accuracy, and $k_0$ counts the iterations before the local regime begins. The Newton estimate assumes that this regime is reached; it does not bound $k_0$ or give a global iteration guarantee. The comparison also assumes exact arithmetic; finite precision eventually limits attainable accuracy. Numerical comparisons should plot the same primal gap against both iteration count and elapsed time, because Newton and FISTA iterations have different costs (§9.7.1).
For this piecewise-quadratic problem there is an even sharper conclusion once the final clipping region is identified. If the current iterate and the solution lie in the same region, the gradient is affine with constant derivative $-H_k$, so
$$ \nabla g(\mu^k)=-H_k(\mu^k-\mu^\ast) \quad\Longrightarrow\quad \mu^{k+1}=\mu^k+H_k^{-1}\nabla g(\mu^k)=\mu^\ast . $$One full step then solves that region exactly in exact arithmetic. On the measured pool, the ten damped steps followed by two full steps are consistent with reaching this final regime; the observed twelve-step total is an empirical result, not a universal iteration bound.
The backtracking rule in Algorithm 2 enforces $g(\mu^{k+1})\ge g(\mu^k)$. Monotonicity alone does not establish a global convergence rate from an arbitrary starting point; a global theorem would require a sufficient-increase condition and its assumptions. The bounds above apply to the penalised dual. For the equality-constrained variant below, the $R^{-1}$ term disappears, so local quadratic convergence additionally requires the limiting Newton matrices to remain nonsingular.
Conditioning in the dual space. The primal Hessian $A^{\!\top}RA + D$ has eigenvalues from $\min_p d_p\approx10^{-12}$ to approximately $1$, a range that slows first-order methods (§9.7.1). The dual Hessian $AD^{-1}A^{\!\top}+R^{-1}$ depends on constraint overlap rather than pattern sizes: the factors $1/d_p$ enter a $61\times61$ sum that Newton inverts exactly. The large, ill-conditioned primal problem is thus reduced to a small dense system.
Variants of the dual formulation.
Equality constraints. For the problem stated in §3, corresponding to the $\lambda\to0$ limit, replace $\tfrac{1}{2}\sum_c\rho_c r_c^2$ with $r=0$. Step 2 is omitted, and the $R^{-1}$ terms disappear from the dual, gradient and Hessian:
$$ g(\mu) = -\mu^{\!\top}\mathbf{1} + \sum_p\Big[\tfrac{1}{2} d_p\big(w_p(\mu)-1\big)^2 + s_p\,w_p(\mu)\Big], \qquad \nabla g(\mu) = A\,w(\mu) - \mathbf{1}, \qquad \nabla^2 g(\mu) = -A_{\mathcal{F}}D_{\mathcal{F}}^{-1}A_{\mathcal{F}}^{\!\top}. $$The Hessian is invertible only when the free columns of $A$ have full row rank. At the initial point $w=\mathbf{1}$, every pattern with $w_{\min}=1$ is clipped at its lower bound. The resulting small free set causes the Newton iteration to stall. Proximal continuation addresses this by solving $g-\tfrac{\varepsilon}{2}\lVert\mu\rVert^2$ as $\varepsilon\to0$. The first stage is the penalised dual above and takes 12 steps; each subsequent decade of $\varepsilon$ requires one or two steps. On this pool, the full procedure takes 22 steps and 0.13 s, reaching a residual of $10^{-13}$. The $\mu_c$ are then Lagrange multipliers, $d_p$ determines the form of the solution, and $\lambda$ no longer affects it. The solution also provides a feasibility certificate (§3).
Pattern-size floor. Only the diagonal $D$ changes,
$$ d_p = \lambda^2\,\frac{n_p+n_0}{\sum_q n_q}, \qquad w_p(\mu) = \Pi_{[w_{\min},\,w_{\max}]}\!\Big(1+\frac{n_p}{n_p+n_0}\sum_{c\in\text{tags}(p)}\beta_c\Big), $$Steps 1–6 still apply, with the factor $n_p/(n_p+n_0)$ shrinking the additive increment.
Merged patterns (§9.4). Patterns with identical constraint membership and bounds share the ratio $s_p/d_p$ and hence $w_p(\mu)$; they can be summed into one column before Step 3.
The problem can be solved in two equivalent ways:
- Newton on the dual. The method derived above converges locally quadratically and takes one exact full step once the final clipping region is identified. It requires 12 iterations on the measured pool (§9.7).
- Active set on the primal. Choose a set of clipped patterns, solve the reduced system for the remaining weights, move bound-violating weights to their bounds, and repeat. At the optimum, one pattern is at its lower bound and none is at $w_{\max}$ (§9.7). Despite this small final active set, Newton starting from $\mu=0$ takes about 10 damped steps before its two quadratic steps. The relationship between active-set and semismooth Newton methods is developed in [9].
The method follows the generalized-raking and calibration framework [2], [6], specialising the Lagrange-multiplier Newton iteration to the chi-square distance with box constraints. Its per-iteration cost has the same $O(\mathrm{nnz}(A))$ scaling as FISTA, but it requires about 10 iterations rather than 30,000. The measured speed-up is approximately two orders of magnitude: 9 s versus 87 ms on this pool (×105), and ×240 with 16 times as many patterns (§9.7). It also returns an optimality certificate, whereas FISTA reaches its iteration budget before convergence.
9.4 Merge constraint-equivalent patterns
$w_p$ depends on $p$ only through its column $a_{\cdot p}$ (up to the $n_p$ scaling) and its bounds. Patterns with identical constraint membership and bounds receive the same $\mu$-combination and can be merged before solving:
$$ P \;\to\; P^{\ast} \;\le\; \#\{\text{distinct rows of } A^{\!\top}\}. $$With only single-tag targets, this equals the number of distinct subsets of targeted tags. Splits caused by conjunction members that lack their own targets (§6a) disappear, leaving an equivalent QP. No reduction is possible on this pool ($P^{\ast}=P=16{,}269$, §9.7): every constrained tag has a target, so constraint membership coincides with the tag set.
9.5 Reusing pattern counts across target edits
Once the pattern memberships, counts and bounds are available, changing the target multipliers requires rebuilding the constraint coefficients and solving again. The rows need not be scanned again unless the target conditions or the pattern representation change. The small dual solve therefore supports rapid exploration of alternative target values.
9.6 Choosing a solver
The primal projected-gradient solver is deterministic and straightforward to implement, using coordinate-wise clipping for projection. With $P = 16$ k and $C = 61$, it runs for about 9 s on one thread (§9.7), but stops far from the optimum at the chosen λ. The dual or active-set method is preferable when $P$ grows to millions, whether through additional tags or independent labels, or when cached pattern counts are used for interactive target tuning. These conditions are plausible as the scenario vocabulary expands or target values are revised.
Effect on the sampled distribution. The FISTA run is unconverged (§9.7), so the two solutions match the 61 target marginals to 0.1 % but place about 15 % of the copies on different patterns. The optimum spreads a tag’s up-sampling over its co-tag combinations, while FISTA concentrates it on the largest ones. Comparing solvers therefore requires examining the pattern weights and sampled counts as well as the marginal errors.
Choice of formulation and solver. The penalised QP in §3 provides a suitable basis for the balancing procedure because overlapping tags can make the prescribed targets jointly infeasible. In that case, the equality-constrained problem has no solution, whereas the penalised problem returns weights and per-tag residuals that guide revision of the targets. When the equalities are feasible, the two solutions agree within a tenth of a weight. The dual method in §9.3 is the preferred solver: for the penalised problem, $R^{-1}$ keeps the Hessian nonsingular, so no continuation is required. It converges in a dozen steps and supplies a duality-gap certificate, while FISTA reaches its iteration cap with an objective 15 % above the optimum. The equality-constrained variant remains useful for checking whether a new target specification is jointly attainable.
9.7 Numerical comparison of FISTA and dual Newton
Set-up. The private dataset is reduced to the pattern counts, tag memberships and bounds
defined in §2. Both solvers receive identical $A,\rho,d,\mathbf{w}_{\min},w_{\max}$ from §3, with $\rho_c=1$,
$w_{\max}=96$ and $\lambda=0.01$. The bounds permit down-sampling of the stop and
uniform_speed patterns. FISTA uses Algorithm 1 with 30 000 iterations, tolerance
$10^{-10}$ and adaptive restart. Dual Newton uses Algorithm 2 with a dense $61\times61$
generalised Hessian on the currently free patterns, backtracking on the dual objective,
and stopping criterion $\|\nabla g\|_\infty\le10^{-13}$.
Timings use single-threaded NumPy/OpenBLAS on one server core.
| scan of the pool | value |
|---|---|
| rows before exclusions | 172,197,088 |
| rows excluded before optimisation | 8,154,326 |
| unconstrained rows (no targeted tag, kept at $w=1$, not in the QP) | 41,369,503 |
| rows inside the QP | 122,673,259 |
| patterns $P$ | 16,269 |
| constraints $C$ / nnz($A$) | 61 / 65,108 |
| $n_p$ percentiles 50 / 90 / 99 / max | 11, 582, 57,133, 18,391,036 |
Algorithm summary. The following table summarises the procedures in §9.2 and §9.3 before comparing their numerical solutions.
| Algorithm 1: FISTA | Algorithm 2: dual Newton | |
|---|---|---|
| problem solved | the penalised QP of §3 | the same QP, through its dual |
| unknowns iterated | the $P = 16{,}269$ weights | the $C = 61$ multipliers; weights from the closed form $w(\mu)$ |
| information used | gradient only, one global step $\eta=1/(1.05L)$ | gradient and $C\times C$ generalised Hessian; exact Newton step |
| per-iteration cost | $A$, $A^{\!\top}$ once each: $O(\mathrm{nnz}(A))$ | $A$, $A^{\!\top}$ once each $+$ $\sum_{p\in\mathcal{F}}k_p^{2}$ $+$ one $61\times61$ solve |
| box constraint | clip after every step | clip inside $w(\mu)$; free set $\mathcal{F}$ re-detected every step |
| targets | approached through the penalty gradient, never settled | residuals $r_c=\mu_c/\rho_c$ read off the multipliers; exact for the penalised problem |
| parameters | iteration budget $K$, tolerance $\tau_f$ | tolerance $\tau$ |
| convergence rate | $O(1/k^{2})$; $\sim\sqrt{\kappa}$ iterations needed, $\kappa\approx10^{12}$ | quadratic once the free set has settled |
| stopping rule | relative change of $f$ | $\lVert\nabla g\rVert_\infty\le\tau$ |
| certificate | none | duality gap $f(w)-g(\mu)$, zero at the optimum |
| cold start from $w=\mathbf{1}$ | works, just slow | works: $R^{-1}$ keeps the Hessian non-singular, no continuation needed |
| iterations / wall time on the pool | 30 000 (cap) / 9.1 s | 12 steps / 87 ms |
| result on the pool | targets to 0.1 %, objective +15 %, 11 000 weights frozen at 1 | the optimum; targets to 0.08 % (the penalty’s softness) |
9.7.1 Speed and optimality
| table | $P$ | $P^{\ast}$ (merged) | $C$ | nnz($A$) | FISTA wall | FISTA iters | dual Newton wall | Newton iters | speed-up |
|---|---|---|---|---|---|---|---|---|---|
| the pool (real scan) | 16,269 | 16,269 | 61 | 65,108 | 9.1 s | 30,000 (hit cap) | 87 ms | 12 | ×105 |
| generated 4x (P=65076) | 65,076 | 65,073 | 61 | 227,817 | 56.5 s | 30,000 (hit cap) | 348 ms | 16 | ×163 |
| generated 16x (P=260304) | 260,304 | 260,301 | 61 | 979,822 | 248.9 s | 30,000 (hit cap) | 1035 ms | 12 | ×241 |
The generated 4x/16x cases retain the 61 observed tags and their targets, but use random
patterns of 1–4 tags with lognormal counts $n_p$. They assess scaling with $P$:
both methods have $O(\mathrm{nnz}(A))$ cost per iteration and therefore scale linearly,
with their relative iteration requirements remaining approximately 30 000 to 12.
| solution quality on the real table | FISTA 30 000 it | FISTA 300 000 it | dual Newton |
|---|---|---|---|
| wall time | 9.1 s | 110 s | 87 ms |
| primal objective $f(w)$ | $2.563652\times10^{-3}$ | $2.253713\times10^{-3}$ | $2.228413\times10^{-3}$ $=f^\ast$ |
| relative gap $(f-f^\ast)/f^\ast$ | 15.0 % | 1.1 % | 0 |
| duality gap $f(w)-g(\mu)$ | – | – | 0 (machine precision) |
| projected-gradient residual $\lVert w-\Pi_{[\mathbf{w}_{\min},w_{\max}]}(w-\nabla f(w))\rVert_\infty$ | $3.3\times10^{-7}$ | $5.3\times10^{-9}$ | $6.7\times10^{-16}$ |
| same residual scaled by curvature, $\max_p\lvert\nabla f_p\rvert/d_p$ (diagonal-Newton step; bounds the distance) | 5,118 | 91 | $2\times10^{-8}$ |
| $\max_p\lvert w_p-w_p^\ast\rvert$ | 91 | 88 | 0 |
| $\operatorname{median}_p\lvert w_p-w_p^\ast\rvert$ | 15.0 | 12.4 | 0 |
| patterns more than 1 away from $w^\ast$ | 16,062 of 16,269 | 14,289 | 0 |
| max relative error over the 61 constraints (2 % threshold) | 0.104 % | 0.081 % | |
| patterns at $w_{\max}$ / at $w_{\min}$ / free | 0 / – / – | 0 / 1 / 16,268 |
The dual-Newton solution provides the reference $w^\ast$ throughout the table. Its optimality is established independently of solver speed: the duality gap is zero and the curvature-scaled residual is $10^{-8}$, certifying the unique optimum of the strictly convex QP. The 300 000-iteration FISTA run shows that a tenfold increase in iterations still leaves substantial differences in the weights.
Left: FISTA through 300 000 iterations, compared with the dual-Newton optimum $w^\ast$. The blue and orange curves (left axis) show the relative objective gaps for λ = 0.01 and 0.1. The red curves (right axis) show $\max_p\lvert w_p-w_p^\ast\rvert$ (solid) and $\operatorname{median}_p\lvert w_p-w_p^\ast\rvert$ (dashed) for λ = 0.01. The vertical dash-dotted line marks the 30 000-iteration budget. The objective gap decreases by four orders of magnitude while the maximum weight difference remains near 90 and the median near 15, reflecting low curvature for small patterns. Right: distributions of the $P$ pattern weights returned by both solvers at λ = 0.01.
Both solvers use the same initial primal weights. Algorithm 1 sets $w=\Pi_{[\mathbf{w}_{\min},w_{\max}]}(\mathbf{1})=\mathbf{1}$, while dual Newton starts at $\mu=0$, giving $w(\mu)=\Pi(\mathbf{1}-0)=\mathbf{1}$. For the dual method, the starting point does not affect the result: the strictly convex QP has a unique optimum, reached in 12 iterations from any starting point. Initialisation matters for FISTA because coordinates that change little within the iteration budget retain values close to their initial weights.
Objective and weight errors for both solvers on logarithmic iteration axes. The 12 dual evaluations appear at the left, while FISTA extends to 300 000 iterations. Left: relative primal objective gap. For dual Newton, the solid red curve shows the gap for $w(\mu_k)$; the dashed curve shows $(f(w(\mu_k))-g(\mu_k))/f^\ast$, the normalised duality gap from §9.3, Step 5. Both reach $10^{-16}$ at the 12th evaluation. Right: maximum and median distance to $w^\ast$. The primal errors need not decrease monotonically: the line search ensures only that $g(\mu)$ does not decrease. At evaluation 2, the primal candidate’s error is seven times its initial value. During evaluations 1–9, backtracking accepts steps of $10^{-6}$ of the Newton direction, so $\mu$ changes little. Near $\mu=0$, the factors $1/d_p\approx10^{12}$ for small patterns dominate the dual curvature, and full Newton steps cross the clipping boundaries. During these evaluations, the free set expands from 12 to 16,268 patterns. Once it is established, a full step at evaluation 10 reduces the gap to $4\times10^{-2}$, and the next reduces it to zero. The quadratic phase therefore lasts two iterations. FISTA has a gap of $10^{4}$ at 12 iterations and still $10^{-2}$ at 300 000.
Interpretation of the results.
Speed. On the observed pattern table, runtime decreases from approximately 9 s to 87 ms (×105), and the iteration count from 30 000 to 12. Starting from $\mu=0$, Newton takes 10 damped steps as the clipped set changes, followed by two quadratic steps. The final values of $\|\nabla g\|_\infty$ are $7.9$, $1.4\times10^{-2}$ and $4.2\times10^{-15}$. At 16 times the pattern count, the speed-up increases to ×241 as the fixed cost of the $C\times C$ solve becomes a smaller fraction of the total.
Convergence within the iteration budget. FISTA reaches the 30 000-iteration cap with an objective 15 % above the optimum and a maximum weight error of 91. After 300 000 iterations (110 s), the objective gap falls to 1.1 %, but the maximum weight error remains 88, and 14,289 of 16,269 weights differ from the optimum by more than 1. The limiting factor is conditioning: $d_p=\lambda^2 n_p/\sum n$ is approximately $10^{-12}$ for a 4-row pattern, while the largest curvature is approximately $1$. Thus, $\kappa\approx10^{12}$, and an accelerated first-order method requires $\sim\sqrt{\kappa}\approx10^{6}$ steps in the slow directions. The unscaled residual of $3\times10^{-7}$ can suggest convergence because the gradient for a small pattern is multiplied by its small $d_p$. For strongly convex $f$, the bound $\lVert w-w^\ast\rVert\le\lVert\nabla f\rVert/d_{\min}$ still permits a distance of $4\times10^{5}$ here. The curvature-scaled residual is 5,118 at 30 000 iterations, overstating the actual error of 91 because it still includes constraint misfit. At 300 000 iterations it is 91, close to the actual maximum error of 88, with only the regulariser contribution remaining. Algorithm 1’s objective-change criterion also misses this discrepancy because the objective is nearly flat along small-pattern coordinates.
Target accuracy and sampled composition. Both solvers satisfy the 2 % target-error threshold, and the 61 marginals agree to 0.1 %. Marginal errors therefore do not distinguish the solutions (§9.7.2). The difference lies in how each tag’s up-sampling is distributed across its patterns (§9.7.3 and §9.7.4): 89.8 M of approximately 600 M rounded copies (15 %) are assigned to different patterns. The median weight difference is 15, and total sample sizes differ by 4 %.
Pattern merging. No reduction is possible here (§9.4): $P^\ast=P$, because every constrained tag has a target. Constraint membership therefore coincides with the tag set, and no two patterns share a column of $A$. Merging is useful when conjunction members without their own targets split patterns (§6a).
Largest weight differences. The largest differences occur in rare multi-tag patterns
whose FISTA weights remain near the initial value of 1. At the optimum, these patterns
receive the full sum of their tag increments (§9.7.3). Each of the twenty patterns
below carries ramp, highspeed_curve_left or another tag with a large target,
and none contains more than a dozen rows:
| pattern (constrained tag set) | rows $n_p$ | $w_p$ FISTA | $w_p^\ast$ | $w_p-w_p^\ast$ | copies FISTA → optimum |
|---|---|---|---|---|---|
{is_decel, ramp, ramp_dec_aug, speeding_dec_aug, ego_lane_change_for_navigation, road_diverge} | 4 | 1.28 | 92.68 | -91.4 | 5 → 371 |
{is_decel, ramp, ramp_dec_aug, speeding_dec_aug, free_cruise, enter_branch_road} | 1 | 1.07 | 82.19 | -81.1 | 1 → 82 |
{highspeed_curve_left, in_lane_vru_avoidance} | 4 | 1.06 | 81.29 | -80.2 | 4 → 325 |
{is_decel, ramp, ramp_dec_aug, speeding_dec_aug, road_merge} | 3 | 1.21 | 80.57 | -79.4 | 4 → 242 |
{is_decel, ramp, ramp_dec_aug, speeding_dec_aug, lane_merge} | 3 | 1.21 | 80.45 | -79.2 | 4 → 241 |
{is_decel, ramp, ramp_dec_aug, speeding_dec_aug, lane_split} | 8 | 1.55 | 80.34 | -78.8 | 12 → 643 |
{ramp, ramp_dec_aug, speeding_dec_aug, road_merge} | 2 | 1.14 | 79.87 | -78.7 | 2 → 160 |
{is_decel, ramp, ramp_dec_aug, speeding_dec_aug, ego_lane_change_for_efficiency} | 11 | 1.76 | 80.14 | -78.4 | 19 → 882 |
{aug_current_frame_started_to_stopped, keepcenter, ramp, enter_or_leave_turn_waiting_zone} | 2 | 1.03 | 78.09 | -77.1 | 2 → 156 |
{is_cipv_decel, is_decel, ramp, ramp_dec_aug, speeding_dec_aug, free_cruise} | 1 | 1.07 | 78.12 | -77.1 | 1 → 78 |
{aug_current_frame_started_to_stopped, ramp, left_turn_with_left_signal, enter_or_leave_turn_waiting_zone} | 1 | 1.02 | 77.90 | -76.9 | 1 → 78 |
{is_decel, ramp, ramp_dec_aug, speeding_dec_aug, car_following_cruise} | 6 | 1.41 | 78.17 | -76.8 | 8 → 469 |
{aug_current_frame_started_to_stopped, is_cipv_decel, ramp, decel_or_stop_to_yield, obstacle_bypass, head_car_start_stop_at_obstacle} | 1 | 1.02 | 77.60 | -76.6 | 1 → 78 |
{is_decel, ramp, ramp_dec_aug, speeding_dec_aug, right_turn} | 4 | 1.27 | 77.52 | -76.2 | 5 → 310 |
{is_decel, ramp, ramp_dec_aug, speeding_dec_aug, road_diverge} | 45 | 4.10 | 80.13 | -76.0 | 185 → 3,606 |
{ramp, ramp_dec_aug, speeding_dec_aug, free_cruise} | 1 | 1.07 | 76.65 | -75.6 | 1 → 77 |
{keepcenter, ramp, ramp_pos_aug, in_lane_vru_avoidance} | 7 | 1.10 | 76.13 | -75.0 | 8 → 533 |
{is_cipv_decel, is_decel, ramp, ramp_dec_aug, speeding_dec_aug} | 10 | 1.68 | 76.63 | -74.9 | 17 → 766 |
{is_decel, keepcenter, ramp, ramp_pos_aug, safe_to_accelerate, ego_lane_change_for_navigation, road_diverge, enter_branch_road} | 1 | 1.01 | 75.29 | -74.3 | 1 → 75 |
{ramp, ramp_pos_aug, decel_or_stop_to_yield, in_lane_vru_avoidance} | 3 | 1.04 | 75.05 | -74.0 | 3 → 225 |
The largest differences in copy counts occur instead among common patterns, especially singletons. FISTA assigns these higher weights to compensate for the small patterns that remain near their initial values, reversing the direction of the discrepancy:
| pattern (constrained tag set) | rows $n_p$ | $w_p$ FISTA | $w_p^\ast$ | $w_p-w_p^\ast$ | copies FISTA → optimum |
|---|---|---|---|---|---|
{highspeed_curve_left} | 157,283 | 67.89 | 56.04 | +11.8 | 10,678,104 → 8,814,638 |
{highspeed_curve_right} | 235,854 | 36.83 | 30.62 | +6.2 | 8,686,752 → 7,221,158 |
{keepcenter} | 1,894,642 | 6.29 | 5.58 | +0.7 | 11,918,231 → 10,580,680 |
{is_decel} | 8,856,939 | 1.57 | 1.70 | -0.1 | 13,875,316 → 15,012,950 |
{is_decel, ramp} | 35,229 | 73.33 | 44.18 | +29.1 | 2,583,284 → 1,556,360 |
{ego_lane_change_for_navigation} | 806,875 | 14.75 | 13.55 | +1.2 | 11,899,265 → 10,935,054 |
{road_merge} | 369,975 | 8.19 | 5.71 | +2.5 | 3,030,443 → 2,113,298 |
{car_following_cruise} | 1,450,851 | 3.92 | 3.31 | +0.6 | 5,689,974 → 4,805,602 |
{lane_merge} | 425,609 | 7.61 | 5.59 | +2.0 | 3,237,685 → 2,381,140 |
{road_diverge} | 292,125 | 8.19 | 5.28 | +2.9 | 2,391,634 → 1,542,174 |
{speeding_dec_aug} | 1,608,908 | 4.67 | 4.19 | +0.5 | 7,515,292 → 6,737,001 |
{obstacle_bypass} | 1,578,920 | 6.14 | 5.66 | +0.5 | 9,695,309 → 8,943,302 |
{ramp} | 23,627 | 74.76 | 43.48 | +31.3 | 1,766,302 → 1,027,381 |
{front_car_cut_in} | 801,231 | 6.74 | 5.85 | +0.9 | 5,403,598 → 4,688,244 |
{is_decel, ramp, ramp_pos_aug} | 61,511 | 57.47 | 46.99 | +10.5 | 3,535,220 → 2,890,447 |
{high_speed} | 677,972 | 4.40 | 3.52 | +0.9 | 2,983,352 → 2,388,546 |
{is_decel, enter_branch_road} | 793,450 | 7.28 | 6.54 | +0.7 | 5,773,630 → 5,190,627 |
{enter_or_leave_turn_waiting_zone} | 135,614 | 18.49 | 14.21 | +4.3 | 2,507,438 → 1,926,639 |
{ego_lane_change_for_efficiency} | 1,208,781 | 5.76 | 5.28 | +0.5 | 6,959,811 → 6,386,658 |
{is_cipv_decel} | 7,160,291 | 1.86 | 1.78 | +0.1 | 13,295,623 → 12,722,486 |
Across all 16 269 patterns, FISTA assigns less weight than the optimum to 15 813 patterns,
a deficit of 32.8 M copies, and more weight to 249 common patterns, an excess of 57.1 M
copies. The 1 350 patterns with $\lvert w_p-w_p^\ast\rvert>50$ have a median size
of 4 rows and a maximum of 1 180. Individually, they have no visible effect on the
61 marginals, which explains why marginal errors do not reveal the differences.
The largest excess weights occur in singletons or pairs involving tags with large
targets: ramp alone, 74.8 versus 43.5; is_decel + ramp, 73.3 versus 44.2;
in_lane_vru_avoidance, 48.2 versus 26.3; and intersection_83 + free_cruise,
38.3 versus 10.2.
Sampled copies per tag combination, $n_p w_p$. Weights alone do not show the scale
of resampling. A weight of 92 for 4 rows produces 371 copies, while a change of 0.13
for is_decel changes the count by 1.1 M copies. Rounded copy counts determine
how often each pattern appears during training. FISTA produces 614.7 M copies,
compared with 590.3 M at the optimum, a reduction of 4 %. The two solutions assign
89.8 M copies to different patterns.
Pattern weights $w_p$ by combination index, ranked from largest to smallest original
row count. The corresponding counts appear in the next figure. Left: all 16,269
patterns on logarithmic axes. The solutions are similar for the approximately
400 combinations with at least 10 k rows (median weights 9.0 and 7.9), then diverge.
Between indices 400 and 3,400, the median FISTA weight is 1.9, compared with 12.4
at the optimum. Beyond index 3,400, where patterns contain fewer than 100 rows,
FISTA assigns weights of 1.0–1.1 to 80 % of combinations, while optimal weights
range from 10 to 51. Horizontal bands in the optimal weights reflect the additive
relationship $1+\sum\beta_c$: combinations with the same tag set receive the
same weight regardless of size (§9.7.3). Right: the 400 largest patterns, with
weight on a logarithmic axis. The largest differences involve ramp and
highspeed patterns that FISTA weights more heavily: ramp, 74.8 versus 43.5;
is_decel + ramp, 73.3 versus 44.2; intersection_83 + free_cruise, 38.3 versus
10.2; and in_lane_vru_avoidance, 48.2 versus 26.3.
Copies per tag combination, ordered by decreasing original count $n_p$. Index 1 is
the stop singleton with 18.4 M rows; index 400 has approximately 10 k rows;
index 16,269 has one row. Both solutions use the same ordering. The black $n_p$
curve is therefore monotone, while fluctuations in sampled copies reflect the
tags present, such as a ramp combination with $w\approx60$ next to an
is_decel combination with $w\approx1.7$. Left: all 16,269 combinations on
logarithmic axes. The black curve gives the original count, and the dashed curve
the cap $96\,n_p$. Beyond index 3,400, FISTA’s blue points coincide with the
original counts, while the optimal red points lie 10–90 times higher.
Right: the 400 largest combinations, with a linear index and logarithmic copy
counts. These account for 96 % of FISTA’s epoch and 91 % of the optimal epoch.
The curves remain within a factor of approximately 1.5. FISTA assigns more copies
to the labelled highspeed_curve_left/right, keepcenter and is_decel + ramp
patterns, and fewer to is_decel. Each difference is 1–2 M copies out of
approximately 600 M.
Largest increases in copy count at the optimum. The first three entries are large
is_decel or highspeed_center patterns, where weight changes of a few percent
affect millions of rows. The remaining entries are medium-sized
highspeed_curve_left combinations with 3–5 k rows, whose copy counts roughly
double at the optimum:
| pattern (constrained tag set) | rows $n_p$ | copies, FISTA | copies, optimum | optimum − FISTA | ratio |
|---|---|---|---|---|---|
{is_decel} | 8,856,939 | 13,875,316 | 15,012,950 | +1,137,634 | ×1.08 |
{is_cipv_decel, is_decel} | 4,895,680 | 11,829,834 | 12,101,440 | +271,606 | ×1.02 |
{highspeed_center} | 3,260,556 | 7,191,166 | 7,326,676 | +135,510 | ×1.02 |
{highspeed_curve_left, speeding_dec_aug, free_cruise} | 4,359 | 153,217 | 264,698 | +111,481 | ×1.73 |
{high_speed, highspeed_curve_left, safe_to_accelerate} | 3,807 | 120,606 | 230,705 | +110,099 | ×1.91 |
{highspeed_curve_left, keepcenter} | 3,424 | 98,854 | 207,589 | +108,735 | ×2.10 |
{high_speed, highspeed_curve_left, safe_to_accelerate, free_cruise} | 3,058 | 82,245 | 189,885 | +107,640 | ×2.31 |
{highspeed_curve_left, is_cipv_decel, is_decel} | 4,019 | 126,345 | 231,153 | +104,808 | ×1.83 |
{high_speed, highspeed_curve_left} | 4,638 | 168,152 | 271,630 | +103,478 | ×1.62 |
{highspeed_curve_left, car_following_cruise} | 3,109 | 80,705 | 181,427 | +100,722 | ×2.25 |
Largest decreases in copy count. These occur in common singleton patterns and
is_decel + ramp, which FISTA weights more heavily to supply their tags’ marginal
counts:
| pattern (constrained tag set) | rows $n_p$ | copies, FISTA | copies, optimum | optimum − FISTA | ratio |
|---|---|---|---|---|---|
{highspeed_curve_left} | 157,283 | 10,678,104 | 8,814,638 | -1,863,466 | ×0.83 |
{highspeed_curve_right} | 235,854 | 8,686,752 | 7,221,158 | -1,465,594 | ×0.83 |
{keepcenter} | 1,894,642 | 11,918,231 | 10,580,680 | -1,337,551 | ×0.89 |
{is_decel, ramp} | 35,229 | 2,583,284 | 1,556,360 | -1,026,924 | ×0.60 |
{ego_lane_change_for_navigation} | 806,875 | 11,899,265 | 10,935,054 | -964,211 | ×0.92 |
{road_merge} | 369,975 | 3,030,443 | 2,113,298 | -917,145 | ×0.70 |
{car_following_cruise} | 1,450,851 | 5,689,974 | 4,805,602 | -884,372 | ×0.84 |
{lane_merge} | 425,609 | 3,237,685 | 2,381,140 | -856,545 | ×0.74 |
{road_diverge} | 292,125 | 2,391,634 | 1,542,174 | -849,460 | ×0.64 |
{speeding_dec_aug} | 1,608,908 | 7,515,292 | 6,737,001 | -778,291 | ×0.90 |
Largest relative increases. The largest ratios occur in patterns containing fewer
than ten rows and combining ramp or highspeed_curve_left with other tags that
have large targets. At the optimum, 12,340 patterns containing 306,954 rows receive
more than ten times as many copies as under FISTA. Their total rises from 0.5 M
to 7.8 M copies, still only 1.3 % of the epoch:
| pattern (constrained tag set) | rows $n_p$ | copies, FISTA | copies, optimum | optimum − FISTA | ratio |
|---|---|---|---|---|---|
{is_decel, ramp, ramp_dec_aug, speeding_dec_aug, free_cruise, enter_branch_road} | 1 | 1 | 82 | +81 | ×82.00 |
{highspeed_curve_left, in_lane_vru_avoidance} | 4 | 4 | 325 | +321 | ×81.25 |
{ramp, ramp_dec_aug, speeding_dec_aug, road_merge} | 2 | 2 | 160 | +158 | ×80.00 |
{aug_current_frame_started_to_stopped, is_cipv_decel, ramp, decel_or_stop_to_yield, obstacle_bypass, head_car_start_stop_at_obstacle} | 1 | 1 | 78 | +77 | ×78.00 |
{aug_current_frame_started_to_stopped, ramp, left_turn_with_left_signal, enter_or_leave_turn_waiting_zone} | 1 | 1 | 78 | +77 | ×78.00 |
{aug_current_frame_started_to_stopped, keepcenter, ramp, enter_or_leave_turn_waiting_zone} | 2 | 2 | 156 | +154 | ×78.00 |
{is_cipv_decel, is_decel, ramp, ramp_dec_aug, speeding_dec_aug, free_cruise} | 1 | 1 | 78 | +77 | ×78.00 |
{ramp, ramp_dec_aug, speeding_dec_aug, free_cruise} | 1 | 1 | 77 | +76 | ×77.00 |
{is_decel, keepcenter, ramp, ramp_pos_aug, safe_to_accelerate, ego_lane_change_for_navigation, road_diverge, enter_branch_road} | 1 | 1 | 75 | +74 | ×75.00 |
{ramp, ramp_pos_aug, decel_or_stop_to_yield, in_lane_vru_avoidance} | 3 | 3 | 225 | +222 | ×75.00 |
{highspeed_curve_left, is_decel, keepcenter, enter_or_leave_turn_waiting_zone} | 1 | 1 | 75 | +74 | ×75.00 |
{is_decel, ramp, ramp_dec_aug, speeding_dec_aug, ego_lane_change_for_navigation, road_diverge} | 4 | 5 | 371 | +366 | ×74.20 |
Aggregation by number of constrained tags. The optimum redistributes approximately 38 M copies from patterns with one or two tags to combinations with three or more:
| constrained tags per pattern | patterns | rows | copies, FISTA | copies, optimum | optimum − FISTA | ratio |
|---|---|---|---|---|---|---|
| 1 | 57 | 78,131,746 | 294,629,195 | 274,133,293 | -20,495,902 | ×0.93 |
| 2 | 766 | 32,314,884 | 207,748,558 | 189,718,196 | -18,030,362 | ×0.91 |
| 3 | 4,183 | 10,338,333 | 95,355,592 | 98,669,258 | +3,313,666 | ×1.03 |
| 4 | 6,421 | 1,710,350 | 16,042,636 | 24,205,274 | +8,162,638 | ×1.51 |
| 5 | 3,848 | 168,192 | 864,608 | 3,347,926 | +2,483,318 | ×3.87 |
| 6 | 913 | 9,455 | 14,314 | 262,141 | +247,827 | ×18.31 |
| 7 | 80 | 298 | 311 | 11,794 | +11,483 | ×37.92 |
| 8 | 1 | 1 | 1 | 75 | +74 | ×75.00 |
Aggregation by pattern size. The optimum redistributes copies from patterns with at least 10 k rows to smaller patterns. The four smallest bins, together containing 3.6 M rows, increase from 22 M to 53 M copies:
| pattern size $n_p$ | patterns | rows | copies, FISTA | copies, optimum | optimum − FISTA | ratio |
|---|---|---|---|---|---|---|
| 1–10 | 7,822 | 26,962 | 28,673 | 632,242 | +603,569 | ×22.05 |
| 10–100 | 5,059 | 166,739 | 197,096 | 3,312,940 | +3,115,844 | ×16.81 |
| 100–1,000 | 2,118 | 721,830 | 1,717,102 | 12,370,734 | +10,653,632 | ×7.20 |
| 1,000–10,000 | 857 | 2,672,596 | 20,507,630 | 36,410,739 | +15,903,109 | ×1.78 |
| 10,000–100,000 | 285 | 8,556,992 | 112,231,880 | 89,816,144 | -22,415,736 | ×0.80 |
| 100,000–1,000,000 | 109 | 32,780,613 | 245,123,720 | 219,184,260 | -25,939,460 | ×0.89 |
| ≥ 1,000,000 | 19 | 77,747,527 | 234,849,114 | 228,620,898 | -6,228,216 | ×0.97 |
These differences imply different sampling policies. FISTA repeats common scenes associated with large-target tags 40–75 times, whereas the optimum assigns copies to every combination according to the sum of its tag increments. A 4-row scene can thus be repeated approximately 90 times per epoch. The 61 marginals remain the same. Whether this allocation is desirable depends on the choice of $d_p$: the pattern-size floor in §9.3 keeps rare combinations near their original frequency. This is a modelling choice rather than a solver choice.
Effect of λ on convergence and target accuracy. Increasing λ improves the conditioning of the primal problem. However, the same coefficients $d_p$ that accelerate FISTA also pull weights towards 1 and increase target errors:
| λ | $\kappa=L/\min_p d_p$ | FISTA gap at stop (cap 30 000 it) | first it. with gap < 1 % | Newton iters | max rel. error (Newton) | median $\lvert w^{\text{FISTA}}-w^{\ast}\rvert$ |
|---|---|---|---|---|---|---|
| 0.01 | $10^{12}$ | 15 % | — | 12 | 0.08 % | 15.05 |
| 0.03 | $10^{11}$ | 4.9 % | — | 26 | 0.72 % | 14.51 |
| 0.1 | $10^{10}$ | 1.1 % | — | 32 | 7.48 % | 12.37 |
| 0.3 | $10^{9}$ | 0.17 % | 9674 | 66 | 41.44 % | 5.00 |
| 1.0 | $10^{8}$ | 0.0049 % | 2325 | 25 | 86.50 % | 0.24 |
| 3.0 | $3\times10^{7}$ | 0.00063 % | 827 | 19 | 96.63 % | 0.04 |
Only λ ≤ 0.03 satisfies the 2 % target-error threshold. At these values, FISTA
does not converge within the iteration budget, while the dual solver requires
12–66 iterations across the tested values of λ. The regulariser permits the
targets to remain soft: at λ = 0.01, the 0.08 % error for highspeed_curve_left
is $r_c=\mu_c/\rho_c$ and decreases in proportion to $\lambda^2$.
9.7.2 Accuracy of the tag targets
The table compares each target with the realised ratio
$\sum_{p\ni c} n_p w_p / N_c$ from both solvers. Integer rounding changes these
ratios by at most 0.07 % relative, for the 45-row static_start_0p5 tag, and by
less than $10^{-5}$ for large tags. The ten largest absolute relative errors in
the Newton solution are shown below; the remaining 51 tags are within 0.009 %.
The expandable table gives all 61 constraints. Each table also reports the
per-tag increment $\beta_c$ defined in §9.7.3.
| tag | target $t_c$ | rows $N_c$ | patterns | bump $\beta_c$ | realised FISTA | realised Newton | rel. err FISTA | rel. err Newton |
|---|---|---|---|---|---|---|---|---|
highspeed_curve_left | 57.5 | 314,125 | 236 | +55.043 | 57.4470 | 57.4581 | -0.100 % | -0.0811 % |
ramp | 47.44 | 323,230 | 1550 | +42.483 | 47.3926 | 47.4167 | -0.104 % | -0.0531 % |
ego_lane_change_for_navigation | 15.92 | 2,736,666 | 2224 | +12.552 | 15.9169 | 15.9176 | -0.049 % | -0.0446 % |
navigation_aug | 9.529 | 6,747,286 | 231 | +8.497 | 9.5250 | 9.5250 | -0.045 % | -0.0445 % |
highspeed_curve_right | 31.91 | 449,678 | 217 | +29.617 | 31.8967 | 31.8989 | -0.042 % | -0.0346 % |
head_car_start_stop_at_light | 7.741 | 7,669,456 | 2151 | +4.715 | 7.7387 | 7.7388 | -0.024 % | -0.0228 % |
keepcenter | 7.656 | 6,227,265 | 3220 | +4.585 | 7.6540 | 7.6542 | -0.021 % | -0.0178 % |
enter_or_leave_turn_waiting_zone | 17.03 | 587,401 | 835 | +13.207 | 17.0233 | 17.0238 | -0.014 % | -0.0108 % |
enter_branch_road | 9.191 | 2,880,245 | 1740 | +4.847 | 9.1900 | 9.1902 | -0.012 % | -0.0105 % |
redaug_v1 | 19.41 | 584,653 | 14 | +10.309 | 19.4106 | 19.4106 | -0.010 % | -0.0095 % |
All 61 constraints, sorted by target
| tag | target $t_c$ | rows $N_c$ | patterns | bump $\beta_c$ | realised FISTA | realised Newton | rel. err FISTA | rel. err Newton |
|---|---|---|---|---|---|---|---|---|
ramp_dec_aug | 76.27 | 2,120 | 16 | +28.487 | 76.2694 | 76.2692 | -0.000 % | -0.0004 % |
highspeed_curve_left | 57.5 | 314,125 | 236 | +55.043 | 57.4470 | 57.4581 | -0.100 % | -0.0811 % |
intersection_type_8_high_purity | 50 | 2,527 | 1 | +49.000 | 49.9997 | 49.9997 | -0.001 % | -0.0005 % |
ramp_pos_aug | 48.03 | 184,879 | 562 | +2.812 | 48.0440 | 48.0326 | +0.022 % | -0.0020 % |
ramp | 47.44 | 323,230 | 1550 | +42.483 | 47.3926 | 47.4167 | -0.104 % | -0.0531 % |
head_car_red2green | 33.38 | 334 | 14 | +27.188 | 33.3782 | 33.3782 | -0.000 % | -0.0000 % |
static_start_0p5 | 32.04 | 45 | 20 | +25.972 | 32.0436 | 32.0438 | -0.001 % | -0.0000 % |
highspeed_curve_right | 31.91 | 449,678 | 217 | +29.617 | 31.8967 | 31.8989 | -0.042 % | -0.0346 % |
head_red_stop_aug_v2_bazier | 30.87 | 6,389 | 1 | +19.565 | 30.8736 | 30.8736 | -0.000 % | -0.0003 % |
in_lane_vru_avoidance | 28.41 | 60,879 | 343 | +25.250 | 28.4059 | 28.4066 | -0.006 % | -0.0036 % |
slow_rightturn_static_start_aug | 25.47 | 129,990 | 1 | +24.467 | 25.4667 | 25.4667 | -0.007 % | -0.0066 % |
remove_stopline_bazier | 24.41 | 189,504 | 1 | +1.872 | 24.4061 | 24.4061 | -0.001 % | -0.0007 % |
head_red_stop_aug_v1_bazier | 23.47 | 379,008 | 2 | +11.226 | 23.4702 | 23.4702 | -0.008 % | -0.0081 % |
aug_current_frame_started_to_stopped | 20.64 | 86,771 | 624 | +16.819 | 20.6364 | 20.6367 | -0.004 % | -0.0025 % |
ego_lane_arrow_conflict_positive | 20 | 208,467 | 1 | +18.999 | 19.9987 | 19.9987 | -0.006 % | -0.0065 % |
fork_correct_lane_choice_1 | 20 | 9,127 | 418 | +8.901 | 20.0000 | 20.0000 | +0.000 % | -0.0001 % |
redaug_v1 | 19.41 | 584,653 | 14 | +10.309 | 19.4106 | 19.4106 | -0.010 % | -0.0095 % |
enter_or_leave_turn_waiting_zone | 17.03 | 587,401 | 835 | +13.207 | 17.0233 | 17.0238 | -0.014 % | -0.0108 % |
ego_lane_change_for_navigation | 15.92 | 2,736,666 | 2224 | +12.552 | 15.9169 | 15.9176 | -0.049 % | -0.0446 % |
intersection_83 | 15.42 | 56,486 | 452 | +7.668 | 15.4166 | 15.4168 | -0.002 % | -0.0005 % |
head_car_start_stop_at_obstacle | 13.81 | 657,654 | 1836 | +8.346 | 13.8054 | 13.8058 | -0.009 % | -0.0062 % |
static_start_1p0 | 13.01 | 87,082 | 752 | +9.241 | 13.0105 | 13.0107 | -0.002 % | -0.0009 % |
u_turn | 11.43 | 477,751 | 786 | +7.589 | 11.4328 | 11.4330 | -0.005 % | -0.0034 % |
redaug_v2 | 11.39 | 123,222 | 5 | +10.378 | 11.3881 | 11.3881 | -0.001 % | -0.0012 % |
red_queue_advance | 10.97 | 22,833 | 160 | +9.487 | 10.9749 | 10.9749 | -0.000 % | -0.0002 % |
yellow_to_red_with_speed_v1 | 9.697 | 24,264 | 1 | +8.697 | 9.6971 | 9.6971 | -0.000 % | -0.0002 % |
yellow_to_red_no_speed_v1 | 9.623 | 30,083 | 1 | +8.623 | 9.6234 | 9.6234 | -0.000 % | -0.0002 % |
navigation_aug | 9.529 | 6,747,286 | 231 | +8.497 | 9.5250 | 9.5250 | -0.045 % | -0.0445 % |
enter_branch_road | 9.191 | 2,880,245 | 1740 | +4.847 | 9.1900 | 9.1902 | -0.012 % | -0.0105 % |
decel_or_stop_to_yield | 8.988 | 1,925,559 | 2574 | +3.509 | 8.9875 | 8.9876 | -0.007 % | -0.0050 % |
left_turn_with_left_signal | 8.636 | 1,532,300 | 721 | +4.396 | 8.6353 | 8.6354 | -0.005 % | -0.0047 % |
lane_merge | 8.473 | 1,238,155 | 1713 | +4.595 | 8.4723 | 8.4724 | -0.006 % | -0.0039 % |
road_diverge | 8.294 | 845,752 | 1798 | +4.279 | 8.2936 | 8.2937 | -0.004 % | -0.0024 % |
road_merge | 8.08 | 957,782 | 1615 | +4.712 | 8.0799 | 8.0801 | -0.004 % | -0.0030 % |
decel_caused_by_front_car | 8.051 | 648,255 | 1005 | +4.918 | 8.0503 | 8.0504 | -0.003 % | -0.0021 % |
fork_correct_lane_choice_2 | 8 | 32,898 | 562 | +5.078 | 8.0000 | 8.0000 | -0.000 % | -0.0001 % |
far_prepare_l0_gt400_trusted_frenet_v2 | 8 | 6,342 | 182 | +3.975 | 8.0000 | 8.0000 | -0.000 % | -0.0000 % |
lane_split | 7.749 | 3,164,490 | 1919 | +4.489 | 7.7487 | 7.7488 | -0.010 % | -0.0090 % |
head_car_start_stop_at_light | 7.741 | 7,669,456 | 2151 | +4.715 | 7.7387 | 7.7388 | -0.024 % | -0.0228 % |
keepcenter | 7.656 | 6,227,265 | 3220 | +4.585 | 7.6540 | 7.6542 | -0.021 % | -0.0178 % |
left_turn_without_left_signal | 7.531 | 1,529,111 | 835 | +3.685 | 7.5306 | 7.5307 | -0.004 % | -0.0035 % |
front_car_cut_in | 7.489 | 2,313,918 | 1801 | +4.851 | 7.4881 | 7.4882 | -0.008 % | -0.0069 % |
static_start_1p5 | 7.409 | 136,779 | 695 | +4.071 | 7.4092 | 7.4092 | -0.001 % | -0.0003 % |
speed_limit_cruise | 6.933 | 2,301 | 38 | +2.132 | 6.9335 | 6.9335 | -0.000 % | -0.0000 % |
obstacle_bypass | 6.809 | 3,098,863 | 1202 | +4.664 | 6.8079 | 6.8080 | -0.009 % | -0.0080 % |
high_speed | 6.771 | 3,135,647 | 1128 | +2.523 | 6.7704 | 6.7705 | -0.006 % | -0.0044 % |
ego_lane_change_for_efficiency | 6.547 | 2,726,085 | 1477 | +4.284 | 6.5462 | 6.5462 | -0.007 % | -0.0062 % |
speeding_dec_aug | 6.336 | 4,220,676 | 1412 | +3.187 | 6.3356 | 6.3357 | -0.008 % | -0.0069 % |
traffic_jam | 5.691 | 1,858,681 | 1221 | +2.518 | 5.6904 | 5.6904 | -0.003 % | -0.0022 % |
safe_to_accelerate | 5.313 | 8,344,585 | 1606 | +2.034 | 5.3124 | 5.3124 | -0.008 % | -0.0074 % |
is_decel | 5.253 | 31,150,338 | 6301 | +0.695 | 5.2529 | 5.2528 | -0.008 % | -0.0093 % |
car_following_cruise | 5.134 | 3,757,242 | 1559 | +2.312 | 5.1340 | 5.1341 | -0.005 % | -0.0036 % |
is_aug_cutin | 5.107 | 2,440,779 | 61 | +4.091 | 5.1072 | 5.1072 | -0.004 % | -0.0042 % |
free_cruise | 4.76 | 12,996,080 | 2492 | +1.494 | 4.7598 | 4.7598 | -0.008 % | -0.0075 % |
right_turn | 4.712 | 3,149,877 | 1462 | +1.669 | 4.7122 | 4.7122 | -0.002 % | -0.0020 % |
is_cipv_decel | 4.37 | 24,570,975 | 6064 | +0.777 | 4.3702 | 4.3702 | -0.007 % | -0.0068 % |
front_car_cut_out | 4.296 | 689,635 | 1084 | +1.660 | 4.2955 | 4.2956 | -0.001 % | -0.0004 % |
highspeed_center | 4.197 | 4,062,073 | 518 | +1.247 | 4.1974 | 4.1974 | -0.002 % | -0.0017 % |
uniform_speed | 2.663 | 8,781,588 | 2476 | -0.165 | 2.6634 | 2.6634 | +0.000 % | +0.0003 % |
stop | 1.013 | 20,924,251 | 1171 | -0.435 | 1.0130 | 1.0130 | +0.001 % | +0.0008 % |
intersection_type_8 | 1 | 17,260 | 1 | -0.000 | 1.0000 | 1.0000 | +0.000 % | +0.0000 % |
At the optimum, 52 of 61 targets have errors below 0.01 %, compared with 50 under
FISTA. Only intersection_type_8 is clipped, at $w_{\min}=1$ for a target of 1.0.
The only negative increments occur for tags that permit down-sampling:
stop has an increment of −0.435, giving $w=0.565$ on 18.4 M rows, and
uniform_speed has an increment of −0.165.
9.7.3 Observed tag combinations and additive weights
Of the $2^{61}$ possible tag combinations, only 16,269 occur as patterns, illustrating the sparse co-occurrence discussed in §8. Their distribution by number of constrained tags is:
| constrained tags per pattern | patterns | rows |
|---|---|---|
| 1 | 57 | 78,131,746 |
| 2 | 766 | 32,314,884 |
| 3 | 4,183 | 10,338,333 |
| 4 | 6,421 | 1,710,350 |
| 5 | 3,848 | 168,192 |
| 6 | 913 | 9,455 |
| 7 | 80 | 298 |
| 8 | 1 | 1 |
Most rows belong to the 57 singleton patterns, while most distinct patterns contain 3–5 tags. Thousands of combinations contain only a few rows each. The two solvers differ most on these rare combinations.
Additive structure of the optimum. From §9.1, $w_p = 1-\frac1{d_p}\sum_c a_{cp}\mu_c$, with $a_{cp}=n_p/(t_cN_c)$ and $d_p=\lambda^2 n_p/\sum n$. The factor $n_p$ cancels, so every unclipped pattern satisfies
$$ w_p \;=\; 1+\sum_{c\,\in\,\text{tags}(p)}\beta_c,\qquad \beta_c=-\frac{\sum_q n_q}{\lambda^2}\,\frac{\mu_c}{t_c N_c}. $$The dual solution is represented by the 61 increments $\beta_c$. The 16,268 free patterns in the observed table satisfy this relationship to $3\times10^{-14}$, or machine precision. The remaining pattern is clipped because its sum would fall below $w_{\min}$. These increments are determined jointly by the optimisation and differ from the requested count multipliers $t_c$ (§7). Examples from the observed table are shown below, with $n$ denoting pattern size.
| pattern | $n_p$ | $1+\sum\beta_c$ | $w_p$ Newton | $w_p$ FISTA |
|---|---|---|---|---|
{is_decel} | 8,856,939 | 1.695 | 1.695 | 1.567 |
{is_cipv_decel} | 7,160,291 | 1.777 | 1.777 | 1.857 |
{is_cipv_decel, is_decel} | 4,895,680 | 2.472 | 2.472 | 2.416 |
{ramp} | 23,627 | 43.483 | 43.483 | 74.758 |
{ramp, ramp_pos_aug} | 34,829 | 46.296 | 46.296 | 60.990 |
{is_decel, ramp, ramp_pos_aug} | 61,511 | 46.991 | 46.991 | 57.473 |
{is_decel, ramp, ramp_dec_aug, speeding_dec_aug} | 1,670 | 75.853 | 75.853 | 92.225 |
{is_cipv_decel, is_decel, front_car_cut_in} | 224,152 | 7.323 | 7.323 | 8.359 |
{stop} | 18,391,036 | 0.565 | 0.565 | 0.564 |
{stop, head_car_start_stop_at_light} | 717,895 | 5.280 | 5.280 | 5.549 |
{is_decel, ramp, ramp_dec_aug, speeding_dec_aug, ego_lane_change_for_navigation, road_diverge} | 4 | 92.685 | 92.685 | 1.282 |
The weight for is_cipv_decel + is_decel is exactly 1 + 0.777 + 0.695, with one
weight serving both constraints (§6). The combination
stop + head_car_start_stop_at_light combines negative and positive increments:
1 − 0.435 + 4.715. FISTA’s weights do not satisfy the additive relationship;
the best additive fit has a median residual of 0.36 and a maximum of 84.
FISTA assigns 1.28 to the 4-row, six-tag pattern, compared with the optimal
92.7, and 74.8 to the ramp singleton, compared with 43.5. The ramp marginal
is similar in both solutions, but the copies come from different rows.
9.7.4 Pattern contributions to each tag’s target
Each pattern contributes $n_p w_p/N_c$ to a tag’s realised ratio. The following
examples examine three distinct cases: ramp, with 1 550 tag combinations and
a large target; ramp_dec_aug, with 16 patterns and a target of 76.3 close to
$w_{\max}$; and stop, with down-sampling permitted and a target near 1.
ramp — target 47.44, $N_c$ = 323,230 rows over 1550 patterns; realised 47.3926 (FISTA) / 47.4167 (Newton).
| pattern containing the tag | rows $n_p$ | share $n_p/N_c$ | $w_p$ FISTA | contrib. FISTA | $w_p$ Newton | contrib. Newton |
|---|---|---|---|---|---|---|
{is_decel, ramp, ramp_pos_aug} | 61,511 | 19.03 % | 57.47 | 10.937 | 46.99 | 8.942 |
{is_decel, ramp} | 35,229 | 10.90 % | 73.33 | 7.992 | 44.18 | 4.815 |
{ramp, ramp_pos_aug} | 34,829 | 10.78 % | 60.99 | 6.572 | 46.30 | 4.988 |
{is_decel, ramp, ramp_pos_aug, free_cruise} | 26,868 | 8.31 % | 65.05 | 5.407 | 48.48 | 4.030 |
{ramp} | 23,627 | 7.31 % | 74.76 | 5.465 | 43.48 | 3.178 |
{ramp, ramp_pos_aug, free_cruise} | 13,550 | 4.19 % | 55.53 | 2.328 | 47.79 | 2.003 |
{is_decel, ramp, right_turn} | 8,002 | 2.48 % | 57.86 | 1.432 | 45.85 | 1.135 |
{is_decel, ramp, free_cruise} | 6,674 | 2.06 % | 51.50 | 1.063 | 45.67 | 0.943 |
| … 1,542 smaller patterns | 112,940 | 34.94 % | 6.196 | 17.381 | ||
| sum | 323,230 | 100 % | 47.393 | 47.417 |
ramp_dec_aug — target 76.27, $N_c$ = 2,120 rows over 16 patterns; realised 76.2694 (FISTA) / 76.2692 (Newton).
| pattern containing the tag | rows $n_p$ | share $n_p/N_c$ | $w_p$ FISTA | contrib. FISTA | $w_p$ Newton | contrib. Newton |
|---|---|---|---|---|---|---|
{is_decel, ramp, ramp_dec_aug, speeding_dec_aug} | 1,670 | 78.77 % | 92.23 | 72.649 | 75.85 | 59.752 |
{is_decel, ramp, ramp_dec_aug, speeding_dec_aug, free_cruise} | 324 | 15.28 % | 22.64 | 3.459 | 77.35 | 11.821 |
{is_decel, ramp, ramp_dec_aug, speeding_dec_aug, road_diverge} | 45 | 2.12 % | 4.10 | 0.087 | 80.13 | 1.701 |
{ramp, ramp_dec_aug, speeding_dec_aug} | 27 | 1.27 % | 2.84 | 0.036 | 75.16 | 0.957 |
{is_decel, ramp, ramp_dec_aug, speeding_dec_aug, ego_lane_change_for_efficiency} | 11 | 0.52 % | 1.76 | 0.009 | 80.14 | 0.416 |
| … 11 smaller patterns | 43 | 2.03 % | 0.029 | 1.622 | ||
| sum | 2,120 | 100 % | 76.269 | 76.269 |
stop — target 1.013, $N_c$ = 20,924,251 rows over 1171 patterns; realised 1.0130 (FISTA) / 1.0130 (Newton).
| pattern containing the tag | rows $n_p$ | share $n_p/N_c$ | $w_p$ FISTA | contrib. FISTA | $w_p$ Newton | contrib. Newton |
|---|---|---|---|---|---|---|
{stop} | 18,391,036 | 87.89 % | 0.56 | 0.496 | 0.56 | 0.496 |
{is_cipv_decel, stop} | 735,625 | 3.52 % | 1.48 | 0.052 | 1.34 | 0.047 |
{stop, head_car_start_stop_at_light} | 717,895 | 3.43 % | 5.55 | 0.190 | 5.28 | 0.181 |
{stop, traffic_jam} | 204,988 | 0.98 % | 3.54 | 0.035 | 3.08 | 0.030 |
| … 1,167 smaller patterns | 874,707 | 4.18 % | 0.240 | 0.258 | ||
| sum | 20,924,251 | 100 % | 1.013 | 1.013 |
These examples show differences in both the allocation of copies and proximity to the weight cap.
Allocation within a tag. For ramp, the 1,542 smaller combinations contain 35 %
of the rows. At the optimum, they contribute 17.4 of the realised ratio of 47.4,
approximately their share of the rows, because every ramp pattern receives
the same +42.5 increment plus those of its other tags. FISTA assigns them only
6.2 and compensates by tripling the contributions of the ramp and
is_decel + ramp patterns. Although the marginals are similar, the unconverged
solution over-represents common ramp scenes and under-represents rare
combinations, contrary to the intended purpose of balancing.
Proximity to the cap. The target of approximately 76 for ramp_dec_aug may
suggest limited scope for further up-sampling under $w_{\max}=96$. In the
FISTA solution, the main pattern has a weight of 92.2, while the other
15 patterns have weights of 3–23. At the optimum, all have weights of 75–80,
well within the cap. The apparent saturation therefore results from
incomplete convergence.
10. References
[1] W. E. Deming and F. F. Stephan, “On a Least Squares Adjustment of a Sampled Frequency Table When the Expected Marginal Totals are Known,” The Annals of Mathematical Statistics, vol. 11, no. 4, pp. 427–444, 1940. doi:10.1214/aoms/1177731829.
[2] J.-C. Deville and C.-E. Särndal, “Calibration Estimators in Survey Sampling,” Journal of the American Statistical Association, vol. 87, no. 418, pp. 376–382, 1992. doi:10.1080/01621459.1992.10475217.
[3] S. Singh and R. Arnab, “On calibration of design weights,” arXiv preprint, arXiv:0902.3343, 2009. arXiv:0902.3343.
[4] T. Chen, J. Slone, G. Amorim, P. A. Shaw, B. E. Shepherd, and T. Lumley, “Generalized raking and stabilized weights for regression modeling in two-phase samples,” arXiv preprint, arXiv:2605.15802, 2026. arXiv:2605.15802.
[5] A. Beck and M. Teboulle, “A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems,” SIAM Journal on Imaging Sciences, vol. 2, no. 1, pp. 183–202, 2009. doi:10.1137/080716542.
[6] J.-C. Deville, C.-E. Särndal, and O. Sautory, “Generalized Raking Procedures in Survey Sampling,” Journal of the American Statistical Association, vol. 88, no. 423, pp. 1013–1020, 1993. doi:10.1080/01621459.1993.10476369.
[7] B. O’Donoghue and E. Candès, “Adaptive Restart for Accelerated Gradient Schemes,” Foundations of Computational Mathematics, vol. 15, no. 3, pp. 715–732, 2015. doi:10.1007/s10208-013-9150-3.
[8] L. Qi and J. Sun, “A nonsmooth version of Newton’s method,” Mathematical Programming, vol. 58, pp. 353–367, 1993. doi:10.1007/BF01581275.
[9] M. Hintermüller, K. Ito, and K. Kunisch, “The Primal-Dual Active Set Strategy as a Semismooth Newton Method,” SIAM Journal on Optimization, vol. 13, no. 3, pp. 865–888, 2002. doi:10.1137/S1052623401383558.