Result · DS-SCALAR-EFFICIENT-DP

Dynamic programming solves the scalar upper problem exactly

Proved herepublication: internalprior art found

Meaning

Interval dynamic programming optimizes the scalar efficient-score upper problem within the finite capacity limit.

Scientific context

For a single parameter of interest, the upper problem of maximizing between-cell efficient-score information has ordered interval cells and is solved exactly by a weighted interval dynamic program.

This is a known result, with prior art going back to Fisher's 1958 grouping algorithm for one-dimensional optimal grouping.

Statement

For d_ψ=1, deterministic D-optimal quantization of a scalar efficient score has ordered interval cells, and the finite-sample optimum can be solved exactly by dynamic programming.

cheap global upper certificate and initializer

Closest prior work

Fisher (1958)On Grouping for Maximum Homogeneity

Nearest prior work

Relationships

Rests on

D-optimal efficient-score quantization upper-bounds global DsDS-EFFICIENT-SCORE-GLOBAL-UPPER

The full chain beneath it

Enables

Open next door

In the library

Carried by ScalarDPConfig. Reference (opens in a new tab).

Every object and refusal

Local graph

Prerequisites to the left, what it enables or raises to the right, boundary cases below. Open in the map.

Proof

DS8. Scalar efficient-score upper problem is exactly solvable by DP

For $d_\psi=1$ , deterministic D-optimal quantization of a scalar atomless efficient score has ordered interval cells. On a finite sample the optimal interval partition can be solved exactly by dynamic programming.

Consequences:

cheap globally optimal upper bound for in-bin $D_s$ ;
strong initializer;
explicit optimality-gap certificate for a found $D_s$ solution.

Measured certificate gaps were 0.003–0.118 nat on reported $d=3,d_\psi=1,K=4,N=60$ tests and 0.011–0.19 nat on reported $d=4,d_\psi=2,K=5,N=80$ tests using the corresponding projected D upper problems.

From Profiled Ds-optimality · chapter contents