WHEN BATCH SCHEDULES CANNOT BE CERTIFIED: CAPACITY OF GLOBALLY VALID MONOMIAL CERTIFICATES ON INTEGER LOG-HULLS
Abstract
A discrete training schedule can be nearly optimal and still be impossible to certify with one reusable global witness. For and budget , the integer optimum is , whereas every globally valid single monomial certifies at most . We call the best reusable proof endpoint single-monomial certificate capacity; throughout, this term refers only to a monomial lower bound valid on the entire positive orthant, not to arbitrary certificates or true model risk. The capacity gap is the log-ratio to the best integer schedule. For positive reciprocal risk interfaces we show that the strongest reusable monomial is obtained by minimizing over the convex hull of logarithmic integer schedules. This gives an exact plan-level obstruction, a finite-support bound in terms of covering radius, and a contractive-SGD realization on a strongly convex quadratic loss of the predicted gap, which is to first order for the log-ratio. Support expansion is therefore a measurable proof resource: it admits a covering-radius upper bound on the remaining finite-domain certificate gap. A product frontier and a controlled noncommuting moment-family audit reproduce the predicted support obstruction without relying on a particular optimizer or data set.
est. 32% chance this paper gets accepted at ICLR 2027.
What do you think this paper will get?
All positions stay anonymous.