Answer: Polynomial bit-time solvable. For \(K=\log(1/\mu_{\min})\), the computed weights satisfy \(\widehat R_H\leq\min\{H,K/\eta+\eta H/8+H\delta/2\}\). Tuning before play gives \(\sqrt{HK/2}+H\delta/2\), with arbitrarily small additional slack for a binary-rational learning rate. For \(\tau=1\), regret is zero.
Theorem 4 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateLet C be any valid convex cost function yielding φ-stable prices, and let αC be the penalty func- tion associated with C. Let A be the expert learn- ing algorithm with weights as in Equation 5 with ǫ = q 2 sup⃗p,⃗p ′∈∆N (αC(⃗p) −αC(⃗p ′))/(φT ). Then for any se- quence of expert losses ℓi,t ∈[0, 1] over T time steps, LA,T − min i∈{1,··· ,N} Li,T ≤ r 2T φ sup ⃗p,⃗p ′∈∆N (αC(⃗p) −αC(⃗p ′)) . This bound is very similar to the bound for FTRL given in Equation 4, with φ playing the role of λ.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite support of forecaster types with rational masses \(\mu_a>0\), horizon \(H\), and losses \(\ell_{a,t}\in[0,1]\) revealed each round, compute online weights using the weighted-LMSR update \(w_{a,t}\propto\mu_a\exp(-\eta\sum_{s<t}\ell_{a,s})\). What running time and regret guarantee against the best supported type can be achieved as functions of support size, input bit length, and requested precision?
A society is given by its support: a list \(A\) of \(\tau\geq1\) forecaster types with positive binary-rational masses \(\mu_a\), normalized by \(\sum_{a\in A}\mu_a=1\). Here \(\tau\) is the support size, not the number of possible types; there is no independent \(m\) parameter.
The horizon \(H\geq1\) is known in advance. Before round \(t\)'s losses are revealed, the prescribed weights are \(w_{a,t}=\mu_a\exp(-\eta\sum_{s<t}\ell_{a,s})/\sum_{b\in A}\mu_b\exp(-\eta\sum_{s<t}\ell_{b,s})\), for a fixed positive binary-rational learning rate \(\eta\).
After choosing weights, the learner observes every loss \(\ell_{a,t}\in[0,1]\), supplied as a binary rational; losses may be adversarial. Given binary-rational precision \(0<\delta<1\), output a rational probability vector \(\widehat w_t\) satisfying \(\|\widehat w_t-w_t\|_1\leq\delta\).
Let \(L\) be the total bit length of the support, masses, horizon, learning rate, precision, and revealed losses. Regret means \(\widehat R_H=\sum_{t=1}^{H}\sum_{a\in A}\widehat w_{a,t}\ell_{a,t}-\min_{a\in A}\sum_{t=1}^{H}\ell_{a,t}\).
Is this online evaluation problem solvable in polynomial bit time in \(\tau,H,L,\log(1/\delta)\), or is it NP-hard?
What worst-case regret guarantee holds for the computed weights, including its dependence on the masses, learning rate, and precision, and its value when the learning rate is tuned before play?
For finite experts, stable convex-cost learning updates have a square-root-horizon regret bound; uniform LMSR achieves \(2\sqrt{H\log\tau}\) regret with its prescribed tuning. [Source](https://arxiv.org/pdf/1003.0034v1).
Exponential weights with an arbitrary prior, including the displayed finite-support update, and a prior-dependent regret analysis are already established; the verified result does not specify the binary-rational implementation above. [Source](https://proceedings.mlr.press/v75/hoeven18a/hoeven18a.pdf).
The online evaluation problem is solvable in polynomial bit time in \(\tau,H,L,\log(1/\delta)\), under the usual binary encoding of rational numerators and denominators.
Write \(C_{a,t}=\sum_{s=1}^{t}\ell_{a,s}\), and let \(\mu_{\min}=\min_{a\in A}\mu_a\). For every positive learning rate \(\eta\), the computed weights satisfy, simultaneously for every expert \(a\),
\(\displaystyle \sum_{t=1}^{H}\sum_{b\in A}\widehat w_{b,t}\ell_{b,t}-C_{a,H}\leq \frac{\log(1/\mu_a)}{\eta}+\frac{\eta H}{8}+\frac{H\delta}{2}.\)
Consequently, putting \(K=\log(1/\mu_{\min})\),
\(\displaystyle \widehat R_H\leq \min\left\{H,\frac{K}{\eta}+\frac{\eta H}{8}+\frac{H\delta}{2}\right\}.\)
For \(\tau\geq2\), the real-valued tuning \(\eta_*=\sqrt{8K/H}\) gives
\(\displaystyle \widehat R_H\leq \min\left\{H,\sqrt{\frac{HK}{2}}+\frac{H\delta}{2}\right\}.\)
Because the prescribed learning rate must be binary rational, this tuning generally requires approximation. Below, we prove that a binary-rational learning rate chosen before play achieves the displayed bound with any desired positive additive slack, in polynomial bit time.
For \(\tau=1\), output the sole probability vector exactly; regret is zero.
The arbitrary-prior exponential-weights update is already established in the cited literature. The issue here is implementing it with a certified rational output. [Van der Hoeven, van Erven, and Kotłowski, equations (1)–(2)](https://proceedings.mlr.press/v75/hoeven18a/hoeven18a.pdf).
At round \(t\), compute the cumulative losses exactly, and define
\(\displaystyle c_t=\min_{a\in A}C_{a,t-1},\qquad x_a=\eta(C_{a,t-1}-c_t),\qquad v_a=\mu_a e^{-x_a}.\)
The common exponential factor cancels, so \(w_{a,t}=v_a/S\), where \(S=\sum_a v_a\).
Every \(x_a\) is nonnegative. At least one is zero, and therefore
\(\displaystyle S\geq\mu_{\min}>0.\)
This denominator bound permits absolute approximation of the exponentials, even when some \(x_a\) have enormous numerical value.
Set
\(\displaystyle \varepsilon=\frac{\delta\mu_{\min}}{2},\qquad B=\left\lceil\log_2(1/\varepsilon)\right\rceil,\qquad n=8B.\)
The integer \(B\) can be found by exact rational comparisons with powers of two.
For rational \(x\geq0\), define
\(\displaystyle q(x)= \begin{cases} 0,&x\geq B,\\ \left(\sum_{k=0}^{n-1}\frac{x^k}{k!}\right)^{-1},&0\leq x<B. \end{cases}\)
We prove that \(\lvert q(x)-e^{-x}\rvert\leq\varepsilon\).
If \(x\geq B\), then \(e^{-x}\leq2^{-B}\leq\varepsilon\).
Otherwise, put \(P=\sum_{k=0}^{n-1}x^k/k!\). Taylor’s theorem gives
\(\displaystyle 0\leq e^x-P\leq e^B\frac{B^n}{n!}.\)
The estimate \(n!\geq(n/e)^n\) follows from
\(\displaystyle \log(n!)=\sum_{k=1}^{n}\log k\geq\int_1^n\log u\,du=n\log n-n+1.\)
Using \(n=8B\), \(e<4\), and \(e/8<1/2\), we obtain
\(\displaystyle e^B\frac{B^n}{n!}\leq2^{2B}\left(\frac{eB}{n}\right)^n\leq2^{2B-n}=2^{-6B}\leq\varepsilon.\)
Since \(1\leq P\leq e^x\),
\(\displaystyle 0\leq\frac1P-e^{-x}=\frac{e^x-P}{Pe^x}\leq e^x-P\leq\varepsilon.\)
Thus the approximation claim holds in both cases. Also, \(q(x)\geq0\), and \(q(0)=1\) exactly.
Compute, using exact rational arithmetic,
\(\displaystyle \widetilde v_a=\mu_a q(x_a),\qquad \widetilde S=\sum_a\widetilde v_a,\qquad \widehat w_{a,t}=\frac{\widetilde v_a}{\widetilde S}.\)
An expert with \(x_a=0\) contributes its positive mass exactly, so \(\widetilde S>0\). Hence the output is a rational probability vector.
Let \(E=\sum_a\lvert\widetilde v_a-v_a\rvert\). Because the masses sum to one,
\(\displaystyle E\leq\sum_a\mu_a\varepsilon=\varepsilon,\qquad \lvert\widetilde S-S\rvert\leq E.\)
The triangle inequality gives
\(\displaystyle \sum_a\left|\frac{\widetilde v_a}{\widetilde S}-\frac{v_a}{S}\right| \leq \sum_a\left|\frac{\widetilde v_a}{\widetilde S}-\frac{\widetilde v_a}{S}\right| +\frac{E}{S} =\frac{|\widetilde S-S|+E}{S} \leq\frac{2\varepsilon}{\mu_{\min}} =\delta. \)
Thus every round meets the requested precision.
Under ordinary binary rational encoding, \(\log_2(1/\mu_{\min})=O(L)\). Therefore
\(\displaystyle B,n=O\bigl(L+\log(1/\delta)\bigr).\)
Exact cumulative sums have polynomial bit length: a common denominator can be taken as the product of the revealed denominators, whose total bit length is at most \(L\); numerator lengths grow by at most an additional \(O(\log H)\). Multiplication by the rational \(\eta\) preserves polynomial bit length.
Crucially, the algorithm compares \(x_a\) with \(B\) before constructing its Taylor approximation. Thus its running time does not depend polynomially on the numerical value of \(\eta H\).
For a retained rational \(x=p/d<B\), the Taylor sum has common denominator \(d^{n-1}(n-1)!\). Its numerator and denominator have polynomial bit length, since \(n\) and the bit lengths of \(p,d\) are polynomially bounded. Taking reciprocals, multiplying by masses, summing over \(\tau\) experts, and normalizing also preserve polynomial bit length.
There are polynomially many rational arithmetic operations over all \(H\) rounds. Standard integer arithmetic therefore gives the claimed polynomial bit-time algorithm. It uses only losses already revealed.
Fix a probability vector \(p\) and numbers \(z_a\in[0,1]\). Define
\(\displaystyle g(u)=\log\sum_a p_a e^{-uz_a}.\)
Differentiating the finite sum shows that \(g'(0)=-\sum_a p_a z_a\), while \(g''(u)\) is the variance of the \(z_a\) under the exponentially tilted distribution.
Every distribution supported on \([0,1]\) has variance at most \(1/4\): its variance is at most its expected squared distance from \(1/2\), and that squared distance is at most \(1/4\). Therefore
\(\displaystyle g(\eta)=g(0)+\eta g'(0)+\int_0^\eta(\eta-u)g''(u)\,du \leq-\eta\sum_a p_a z_a+\frac{\eta^2}{8}.\)
This proves the needed bounded-loss inequality for every \(\eta>0\).
Define
\(\displaystyle Z_t=\sum_a\mu_a e^{-\eta C_{a,t-1}},\qquad h_t=\sum_a w_{a,t}\ell_{a,t}.\)
Since \(Z_1=1\) and
\(\displaystyle \frac{Z_{t+1}}{Z_t}=\sum_a w_{a,t}e^{-\eta\ell_{a,t}},\)
the one-round inequality, applied with \(p=w_t\) and \(z_a=\ell_{a,t}\), yields
\(\displaystyle \log Z_{H+1}\leq-\eta\sum_{t=1}^{H}h_t+\frac{H\eta^2}{8}.\)
For every expert \(a\),
\(\displaystyle Z_{H+1}\geq\mu_a e^{-\eta C_{a,H}}.\)
Combining these inequalities and dividing by \(\eta>0\) gives
\(\displaystyle \sum_{t=1}^{H}h_t-C_{a,H}\leq\frac{\log(1/\mu_a)}{\eta}+\frac{\eta H}{8}.\)
The argument holds for every realized loss sequence, including losses chosen adaptively after the learner outputs its weights.
Let \(d_a=\widehat w_{a,t}-w_{a,t}\). Both vectors are probability vectors, so \(\sum_a d_a=0\). Consequently,
\(\displaystyle \sum_{d_a>0}d_a=\sum_{d_a<0}(-d_a)=\frac12\sum_a|d_a|.\)
Using \(0\leq\ell_{a,t}\leq1\),
\(\displaystyle \left|\sum_a d_a\ell_{a,t}\right|\leq\frac12\|\,\widehat w_t-w_t\,\|_1\leq\frac{\delta}{2}.\)
Summing over rounds proves the expert-dependent bound stated in Section 1.
There is also a stronger bound when several experts tie for best cumulative loss. Define
\(\displaystyle C_*=\min_a C_{a,H},\qquad A_*=\{a:C_{a,H}=C_*\},\qquad M_*=\sum_{a\in A_*}\mu_a.\)
Since \(Z_{H+1}\geq M_*e^{-\eta C_*}\), the same argument proves
\(\displaystyle \widehat R_H\leq\frac{\log(1/M_*)}{\eta}+\frac{\eta H}{8}+\frac{H\delta}{2}.\)
Because \(M_*\geq\mu_{\min}\), this implies the uniform worst-case bound using \(K\). Independently, regret is at most \(H\), which justifies the minimum with \(H\).
Assume \(\tau\geq2\). Then \(\mu_{\min}\leq1/2\), so \(K\geq\log2>0\). For the uniform worst-case upper bound, minimize
\(\displaystyle F(\eta)=\frac{K}{\eta}+\frac{H\eta}{8}.\)
Its derivative vanishes at \(\eta_*=\sqrt{8K/H}\), and its second derivative is positive. Thus
\(\displaystyle F(\eta_*)=\sqrt{\frac{HK}{2}}.\)
This minimizes the proved upper bound; it is not a claim about the exact minimax regret.
To handle the rational-input requirement, fix any binary-rational \(0<\rho<1\). We can compute a binary-rational rate satisfying
\(\displaystyle \eta_*\leq\eta\leq(1+\rho)\eta_*\)
in polynomial bit time.
Here are explicit ingredients. Write \(1/\mu_{\min}=2^j y\), where the integer \(j\) is found by rational comparisons and \(1\leq y<2\). For such \(y\),
\(\displaystyle \log y=2\sum_{k=0}^{\infty}\frac{z^{2k+1}}{2k+1},\qquad z=\frac{y-1}{y+1}\in[0,1/3].\)
After \(N\) terms, the positive remainder is at most \(3^{-2N}\). The same formula computes \(\log2\). Hence rational intervals enclosing \(K=j\log2+\log y\), with width at most \(\rho/8\), require only polynomially many terms and polynomial bit length.
Choose an upper endpoint \(K^+\) satisfying \(K\leq K^+\leq K+\rho/8\). Since \(K\geq1/2\),
\(\displaystyle s=\sqrt{8K^+/H}\leq(1+\rho/8)\eta_*.\)
Exact comparisons of rational squares and dyadic bisection produce a dyadic \(\eta\in[s,s+\rho/H]\). Since \(\eta_*\geq2/\sqrt H\),
\(\displaystyle \frac{\eta}{\eta_*}\leq1+\frac{\rho}{8}+\frac{\rho}{H\eta_*} \leq1+\frac{5\rho}{8}\leq1+\rho.\)
All these computations occur before play.
Writing \(r=\eta/\eta_*\), direct substitution gives
\(\displaystyle F(\eta)=\sqrt{\frac{HK}{2}}\frac{r+r^{-1}}{2} =\sqrt{\frac{HK}{2}}\left(1+\frac{(r-1)^2}{2r}\right).\)
Thus this rational tuning guarantees
\(\displaystyle \widehat R_H\leq \min\left\{H,\left(1+\frac{\rho^2}{2}\right)\sqrt{\frac{HK}{2}}+\frac{H\delta}{2}\right\}.\)
In particular, any prescribed positive binary-rational additive slack \(\kappa\) can be achieved by choosing \(\rho\) sufficiently small. Because \(K=O(L)\), this requires only polynomial bit time in the original parameters and \(\log(1/\kappa)\).
For uniform masses, \(K=\log\tau\). The sharper bounded-loss analysis above gives the ideal tuned upper bound
\(\displaystyle \sqrt{\frac{H\log\tau}{2}}+\frac{H\delta}{2},\)
with arbitrarily small additional slack for binary-rational tuning.
The cited paper uses the coarser bound \(H\eta+\log\tau/\eta\); its prescribed real-valued tuning yields \(2\sqrt{H\log\tau}\). [Chen and Vaughan, Section 3](https://arxiv.org/pdf/1003.0034v1). Consequently, that guarantee also transfers to computed weights with an additional \(H\delta/2\), subject to the same rational-tuning qualification.
For arbitrary masses, the corresponding prior dependence is \(K=\log(1/\mu_{\min})\), with the stronger expert-dependent and tied-best-expert bounds proved above. A fixed positive precision contributes a potentially linear term; choosing \(\delta=O(\sqrt{K/H})\) keeps this contribution within square-root order.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output resolves the finite-support evaluation problem and establishes the stated regret bounds, including the qualification needed for a binary-rational learning rate. I found no major or minor mathematical issues requiring repair.
The algorithm operates on the explicitly listed support of size \(\tau\), without introducing an independent parameter for possible types. Its complexity is measured in the parameters requested by USER_TASK.
The regret inequality is established simultaneously for every expert and for every realized loss sequence. The analysis permits adaptive losses: none of its inequalities requires independence between the losses and the learner’s previously output weights.
Subtracting the minimum cumulative loss introduces a common factor that cancels under normalization. Consequently, the shifted representation defines exactly the prescribed weights.
Every shifted exponent is nonnegative, and at least one is zero. The corresponding mass contributes unchanged to the denominator, so the asserted lower bound \(S\geq\mu_{\min}>0\) is valid. This remains true when several experts attain the minimum.
The chosen parameters satisfy \(0<\varepsilon<1/2\), so \(B\) and \(n\) are positive integers.
For the discarded branch, \(x\geq B\) implies \(e^{-x}\leq2^{-B}\leq\varepsilon\). The use of a binary threshold for a natural exponential is valid.
For the retained branch, Taylor’s theorem applies to the exponential on the interval from zero to \(x<B\). Its derivative bound gives the stated remainder. The factorial estimate follows from the displayed integral comparison, including its direction.
Substituting \(n=8B\) into the remainder estimate gives the stated upper bound \(2^{-6B}\). This is at most \(\varepsilon\), because \(2^{-B}\leq\varepsilon\). The reciprocal error calculation is also correct: \(P\geq1\) ensures that taking the reciprocal does not enlarge the established absolute error beyond the stated bound.
Nonnegativity and the exact identity \(q(0)=1\) hold in all applicable cases.
The approximation errors are multiplied by the masses, whose sum is one. Thus the aggregate unnormalized error is at most \(\varepsilon\), without an additional factor of \(\tau\).
The approximate denominator is positive because a zero shifted exponent contributes a positive mass exactly. Exact normalization therefore produces a rational probability vector.
The displayed normalization identity and triangle inequality are correct. In particular, the bound uses the exact denominator \(S\), so it does not require an unstated lower bound on an approximate denominator. The final error is at most \(\delta\).
A positive rational mass represented by binary integers has \(\log_2(1/\mu_{\min})=O(L)\). Therefore the approximation degree is polynomially bounded.
The cumulative-loss denominator bound is valid: the product of revealed denominators has bit length bounded by their aggregate encoding length. Numerators require only polynomially many additional bits. Exact comparison and multiplication by \(\eta\) preserve polynomial bit length.
The retained Taylor polynomial has the stated common denominator. Its numerator and denominator have polynomial bit length, as do the subsequent reciprocals and normalizations. Summing over the support can enlarge denominator lengths by a factor polynomial in \(\tau\), which remains within the requested complexity.
Comparing against the truncation threshold before evaluating the polynomial correctly avoids dependence on the numerical magnitude of \(\eta H\). Each round uses only previously revealed losses. Both the online requirement and the polynomial bit-time claim are established.
The logarithm is well-defined for every probability vector because its exponential sum is strictly positive. Differentiating the finite sum gives the stated mean and tilted variance.
The variance bound of \(1/4\) holds for every distribution on \([0,1]\). The integral Taylor identity consequently gives the coefficient \(\eta^2/8\). No restriction such as \(\eta\leq1\) is needed.
The potential ratio uses exactly the prescribed weights, and summing the logarithmic one-round inequalities telescopes correctly. The lower bound obtained from any individual expert has the correct prior factor and sign.
Combining these bounds gives the stated expert-dependent regret inequality for every positive \(\eta\).
The approximation penalty is correctly \(H\delta/2\). Both weight vectors have total mass one, so their difference has equal positive and negative mass. Losses in \([0,1]\) then give the stated factor of one-half.
The tied-best-expert bound follows from summing precisely the potential contributions of those experts. The worst-case replacement by \(\mu_{\min}\) is valid. The independent cap by \(H\) follows from the loss range.
For \(\tau\geq2\), \(K>0\), and the minimizer and minimum value of the displayed upper bound are computed correctly.
The logarithm series has the stated domain, positive remainder, and valid remainder bound. Applying it to the binary decomposition of the reciprocal mass permits certified rational intervals with polynomial effort.
The bounds relating \(K^+\), \(s\), and the dyadic learning rate are correct, including the case \(H=1\). Rational-square comparisons and dyadic bisection provide the claimed precision with polynomial bit complexity.
The identity involving \(r=\eta/\eta_*\) verifies the multiplicative tuning penalty. The assertion about arbitrary positive additive slack is a routine consequence of that explicit penalty and its precision dependence; it requires no additional mathematical lemma.
For \(\tau=1\), normalization forces the sole mass and weight to equal one, and regret is exactly zero.
The arbitrary-prior exponential update is consistent with equations (1)–(2) of [Van der Hoeven, van Erven, and Kotłowski](https://proceedings.mlr.press/v75/hoeven18a/hoeven18a.pdf).
The coarser uniform-prior bound and its tuning agree with Section 3 of [Chen and Vaughan](https://arxiv.org/pdf/1003.0034v1), with the LMSR correspondence discussed in Section 4.2. The sharper constant in the prover’s result is justified by its own bounded-loss analysis.
The output correctly distinguishes ideal real-valued tuning from admissible rational tuning, and minimizes its proved upper bound without claiming exact minimax optimality.
Required feedback: None. No missing hypothesis, false step, or substantive implementation gap was identified.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.