Campbell, Ibaibarriaga and Reyzin (arXiv:2605.20434) proved that the order-m contradiction graph Gₘ(H) of a concept class H determines whether VC(H) ≥ m: the graph contains a cube-trace clique of size 2ᵐ if and only if H shatters an m-point set. The vertice…
For a policy on two Bernoulli arms whose decisions are comparisons of rational numbers, the expected regret at horizon T on the instance with means (p,q) is a piecewise polynomial R_T(p,q) with rational coefficients, so its worst case over the instance squa…
For a finite concept class C, the best-case teaching dimension TSₘᵢₙ(C) is the least number of domain points on which some concept of C differs from every other concept of C; whether TSₘᵢₙ(C)=O(VCD(C)) is open, and everything known about the two parameters…
Fix the algorithm: Thompson sampling with independent Beta(1,1) priors on two Bernoulli arms, in the form of Agrawal and Goyal's Algorithm 1. Its expected regret at horizon T on the instance with means (p,q), q ≤ p, is a polynomial R_T(p,q) with rational co…
A learner pulls one of two Bernoulli arms for T rounds, sees only the reward of the arm it pulled, may randomise, and pays the pseudoregret (the gap times the expected number of pulls of the worse arm). We determine the minimax pseudoregret over randomised…
Let Y be a finite output set and let L be a metric on it. The margin-rescaling structured-SVM surrogate is S_(M)(v,y)=max_(y' ∈ Y){L(y,y')+v_(y')-v_y}, and the question is whether the canonical decoder v ↦ operatorname*arg max_y v_y is Fisher consistent for…
Yun, Sra and Jadbabaie compare the expected iterate of stochastic gradient descent on a quadratic finite sum under single shuffling, random reshuffling and plain gradient descent, and conjecture that for every number of components n, every epoch count K and…
For an integer step count T ≥ 1 put b₀(x)=T, bⱼ(x)=jx+(T-j) for 1 ≤ j ≤ T, and H_T(x) = T²xΣᵢ₌₁^(T)frac(1)i bᵢ(x) bᵢ₋₁(x)²,qquad x>0. This is the finite-step variance deficit of a Schrödinger-bridge sampler on the uniform grid, in the form derived by Fallah…
In the ranking-from-counterexamples game of Alon, Moran and Moran, a learner repeatedly proposes a linear order on n items and an adversarial oracle either declares the proposal correct or names an unordered pair whose relative order the proposal gets wrong…
A finite nonempty set Q ⊆ Y^(D) of patterns is a pseudo-cube on the finite index set D when every point of Q has, at every coordinate, a second point of Q agreeing with it off that coordinate and differing there; the largest |D| for which a function class h…
Barua and Khodadadian have recently shown that exact natural policy gradient (NPG) with a constant step size η>0 and uniform initialization, run on a tabular finite-horizon Markov decision process with horizon H and rewards in [0,1], satisfies V^(star,h)(s)…
For a finite concept class C over a finite domain, Kirkpatrick, Simon and Zilles and Fallat, Kirkpatrick, Simon, Soltani and Zilles ask whether NCTD(C)>VCD(C) is possible; the only search they report is over "those classes for which PBTD>VCD is known from t…
Fix an exponent r and an architecture d=(d₀,…,d_L). A polynomial neural network with power activation z ↦ zʳ parametrises a subvariety V_(d,r) — the neurovariety — of a space of tuples of forms of degree r^(L-1); the architecture is filling when V_(d,r) is…
For a multi-label problem with s labels the instance-wise Jaccard loss is the 2ˢ × 2ˢ matrix L^(Jac) = U - S whose score entries are S_(A,B) = Jac(A,B) = |A ∩ B|/|A ∪ B|, with Jac(emptyset,emptyset) = 1. Zhang, and independently Dewasurendra, have recently…
Let δ₁,…,δₘ lie in a real inner-product space E, let b ∈ ℝᵐ, and let a context h be drawn from a finitely supported distribution on E. Write q(h) = softmax(ip(δ_c, h) + b_c)_(c) for the induced conditional law on m classes, bar(q) = E q(h) for its marginal,…
For a multi-label problem with s labels, the instance-wise F₁ loss is the 2ˢ × 2ˢ matrix L^(F₁) = J - F with F(A,B) = 2|A ∩ B|/(|A|+|B|) and F(emptyset,emptyset) = 1. Zhang has recently determined rank L^(F₁) = s²-s+2 exactly, hence CCdim(L^(F₁)) ≤ s²-s+1,…
In the classical game of prediction with expert advice — k experts, T rounds, binary gains, full information, an adaptive adversary — the minimax expected regret V_T(k) is a rational number, but to our knowledge only the case k = 2 (Cover, 1965) is in print…
Hanneke, Moran, Shlimovich and Yehudayoff determined the worst-case risk ratio F_(w)(d,n) of the minimum-norm ERM under a weighted selection of n points of a dataset in ℝᵈ × ℝ outside the window d<n<2d, and asked for its value inside that window (Question 2…
We compute exactly the finite-horizon minimax expected regret of the two-armed adversarial bandit with {0,1} losses, an oblivious adversary, bandit feedback and regret measured against the best fixed arm: V^(B)(2,T)=1/2,1/2,3/4,(33)/(40) for T=1,2,3,4, and…
Let W range over the nonnegative n × K matrices of total mass one, let Y^(ℓ) be the signed one-hot label matrix of a label map ℓ: [n] → [K], and let v range over {± 1}^K. The quantity maxᵥ |(W odot Y^(ℓ))v|₁ is the binary weight mass that a factorized multi…
