COS Method

Download original file

This is the original TeX manuscript source. Use the paper’s PDF for typeset equations.

Read the typeset paper

Read this chapter with formatted equations

1 \chapter{Accuracy-driven certification}\label{ch:accuracy}
2 \chapterlead{A requested tolerance is an input to the problem, not an informal expectation
3 about its answer. The controller accepts a result only when an outward
4 probability interval proves the multiplicative accuracy requirement. Failure
5 to prove that inequality remains a failure of certification, even when a
6 point estimate appears accurate.}
7 \label{sec:final-5}
8 
9 The external numerical contract specifies the desired accuracy, not the
10 internal transform resolution.
11 
12 For an exact positive spectrum and threshold \(q\), the solver accepts a
13 requested relative multiplicative accuracy
14 \[
15 \varepsilon_{\rm req}>0
16 \]
17 and returns a certified interval
18 \[
19 [p_-,p_+]
20 \]
21 only when
22 \[
23 \boxed{
24 \frac{p_+}{p_-}-1
25 \le
26 \varepsilon_{\rm req}.
27 }
28 \]
29 
30 In logarithmic coordinates, if
31 \[
32 \log_{10}p\in[d_-,d_+],
33 \]
34 the acceptance rule is
35 \[
36 \boxed{
37 10^{d_+-d_-}-1
38 \le
39 \varepsilon_{\rm req}.
40 }
41 \]
42 
43 No value of \(N\), support width, or arithmetic precision appears in the
44 external contract.
45 
46 \begin{theorem}[Accuracy contract for the positive exact-spectrum backend]\label{claim:final-5-1}
47 Assume an exact supplied positive decimal spectrum of rank greater than two,
48 a threshold \(q\ge0\) with valid interval-design parameters, and requested multiplicative tolerance
49 \(\varepsilon_{\rm req}>0\).  Suppose the directed-rounding interval backend
50 returns an enclosure
51 \[
52 \log_{10}p\in[d_-,d_+]
53 \]
54 that includes the proved support/alias and omitted-mode remainders.  If the
55 accuracy-driven controller returns \texttt{certified=True}, then
56 \[
57 \boxed{
58 P(Q\ge q)\in[10^{d_-},10^{d_+}]
59 }
60 \]
61 and
62 \[
63 \boxed{
64 \frac{10^{d_+}}{10^{d_-}}-1
65 \le
66 \varepsilon_{\rm req}.
67 }
68 \]
69 If the resource caps are reached before this inequality is proved, the
70 controller returns \texttt{certified=False} rather than promoting the interval
71 midpoint to a certified answer.
72 \end{theorem}
73 
74 \begin{proof}
75 The directed-rounding backend encloses the finite transform and exponential
76 prefactor and then enlarges that enclosure by the proved support/alias and
77 infinite-mode error bounds.  Therefore the true tail probability lies inside
78 the returned interval.  The controller encloses
79 \(\operatorname{expm1}(\log(10)(d_+-d_-))\) by directed rounding and
80 sets \texttt{certified=True} only when the upper endpoint of that ratio
81 enclosure is no larger than the lower endpoint of the exact requested
82 tolerance enclosure.  High precision alone is not an enclosure proof.  The fail-closed branch follows directly from
83 the controller definition.
84 \end{proof}
85 
86 \section{Adaptive refinement}
87 
88 The controller adjusts three internal resources:
89 
90 \begin{enumerate}
91 \item the COS mode count \(N\).
92 \item the tilted support scale \(L\), which changes \(b\) and its associated
93 Chernoff parameter.
94 \item the interval arithmetic precision.
95 \end{enumerate}
96 
97 At each stage the full directed-rounding interval is recomputed.  If the
98 rounding component is material relative to the requested budget, arithmetic
99 precision is increased.  Otherwise the dominant analytic contribution
100 determines the next refinement: mode error increases \(N\), while
101 support/alias error increases \(L\).
102 
103 A certified return occurs only after the multiplicative inequality above
104 has been proved. Reaching a resource limit instead terminates the calculation
105 with the failure status described next.
106 
107 \section{Fail-closed behavior}
108 
109 If the configured resource caps are exhausted before the requested accuracy
110 is established, the solver does not silently return its midpoint as though it
111 were certified.
112 
113 Instead it returns
114 \[
115 \boxed{\texttt{certified = false}}
116 \]
117 together with the unresolved interval and a failure reason.
118 
119 This behavior is part of the numerical definition of the solver.
120 
121 \section{Accuracy ladder through \texorpdfstring{\(10^{-5000}\)}{1e-5000}}
122 
123 The exact control
124 \[
125 Q=0.02\chi^2_{80}
126 \]
127 was evaluated at tail depths
128 \[
129 10^{-100},
130 \qquad
131 10^{-1000},
132 \qquad
133 10^{-5000}.
134 \]
135 
136 For each depth the controller was asked to prove relative multiplicative
137 accuracies
138 \[
139 10^{-8},
140 \quad
141 10^{-10},
142 \quad
143 10^{-12},
144 \quad
145 10^{-14}.
146 \]
147 All twelve contracts were satisfied.
148 
149 At the \(10^{-5000}\) point, the controller produced:
150 
151 \begin{center}
152 \begin{tabular}{@{}rrrr@{}}
153 \toprule
154 requested accuracy & achieved ratio minus one & \(N\) & \(L\)\\
155 \midrule
156 \(10^{-8}\)  & \(3.19\times10^{-10}\) & 64  & 10\\
157 \(10^{-10}\) & \(7.70\times10^{-11}\) & 128 & 10\\
158 \(10^{-12}\) & \(3.48\times10^{-15}\) & 128 & 12\\
159 \(10^{-14}\) & \(3.48\times10^{-15}\) & 128 & 12\\
160 \bottomrule
161 \end{tabular}
162 \end{center}
163 
164 The gap between requested and achieved accuracy is expected: refinement is
165 discrete, so one additional support or mode refinement can improve the
166 certificate by several orders of magnitude.
167 
168 A further stress test requested
169 \[
170 10^{-16}
171 \quad\text{and}\quad
172 10^{-18}
173 \]
174 relative accuracy at the same \(10^{-5000}\) tail.  The solver obtained
175 approximately
176 \[
177 3.05\times10^{-18}
178 \]
179 and
180 \[
181 9.20\times10^{-20}
182 \]
183 respectively.
184 
185 \begin{figure}[htbp]
186 \centering
187 \includegraphics[width=\linewidth]{figures_production/figure_26_accuracy_driven_refinement.pdf}
188 \caption{Requested and achieved multiplicative widths, expressed as decimal accuracy orders. Larger values mean tighter widths, so points above the equality line meet the requested tolerance. The two deepest stress results use the rounded numerical summaries in the text. Acceptance itself uses the full directed endpoints.}
189 \label{fig:accuracy-driven}
190 \end{figure}
191 
192 \section{Acceptance arithmetic and serialization are directed}
193 
194 The acceptance condition must be evaluated as carefully as the probability
195 interval.
196 
197 Converting a tiny log-width \(w\) using
198 \[
199 10^w-1
200 \]
201 under an insufficient point-precision context can lose the width. At approximately \(10^{-15}\)
202 relative scales, the ratio can round to zero.
203 
204 Even when the probability interval remains valid, that conversion cannot
205 support a certification decision. The implementation encloses
206 \[
207 \boxed{
208 \operatorname{expm1}(\log(10)\,w)
209 }
210 \]
211 with directed interval arithmetic before deciding whether the requested
212 accuracy has been met.  Acceptance compares the upper endpoint of that ratio
213 with the lower endpoint of the requested exact tolerance, so a rounded point
214 estimate cannot promote an unresolved boundary case to success.
215 
216 Authoritative output strings must preserve the same outer enclosure.  The
217 implementation converts each exact binary interval endpoint to a decimal
218 string with \texttt{Decimal} and explicit \texttt{ROUND\_FLOOR} for lower
219 endpoints or \texttt{ROUND\_CEILING} for upper endpoints.  Ordinary interval
220 display formatting is not used as an authoritative serialization method:
221 nearest-rounded decimal text can move an endpoint inward even when the
222 internal interval arithmetic was directed.  Matrix-to-tail propagation keeps
223 these endpoint strings and applies the same directed ratio test.
224 
225 The correctness requirement applies not only to the tail integral but also
226 to the logic that labels its result certified.
227 
228 \section{Input semantics at \texorpdfstring{\(p\approx10^{-16}\)}{p about 1e-16}}
229 
230 At this accuracy scale, the representation of the threshold \(q\) itself is
231 measurable.  In the \(0.02\chi^2_{80}\) control targeted at \(10^{-16}\),
232 rounding the high-precision threshold to binary float64 shifts the exact tail
233 by approximately
234 \[
235 3.83\times10^{-15}
236 \]
237 decades.  The binary64 solver evaluated at that same rounded input
238 then differs from the exact tail of the rounded input by approximately
239 \[
240 5.17\times10^{-15}
241 \]
242 decades.
243 
244 Accordingly, claims below the float64 input-quantization scale use exact-decimal
245 or interval inputs.  The rigorous accuracy contract therefore certifies the
246 mathematical inputs supplied to it, rather than silently identifying a rounded
247 binary threshold with an ideal decimal threshold.
248 
249 
250 

Back to source controls

Back to COS Method