acceptodds
Withdrawn from ICLR 2027

WHEN BATCH SCHEDULES CANNOT BE CERTIFIED: CAPACITY OF GLOBALLY VALID MONOMIAL CERTIFICATES ON INTEGER LOG-HULLS

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

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.

Primary area:
optimization
Keywords:
batch size scheduling, stochastic optimization, SGD, learning theory, certificates, resource allocation

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_gttAOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

This paper analyses monomial lower bounds for integer allocation problems; the authors supplement their theoretical results with experimental validation.

Critical strengths

None

Critical weaknesses

Readibility: This paper is extremely difficult to read and at first glance appears as thought the authors submitted the direct output of a conversation with ChatGPT or Claude. The abstract alone is written in an incomprehensible manner as in the second sentence, it introduces a function, with no relevant background, and compares it to a "monomial certificate". The rest of the paper fares little better on this front with numerous terms such as equality geometry, reusable monomials, and irreducible capacity tax. This strange use of notation and nomenclature becomes especially evident in the introduction, where a reading of the main results gives no insight into what the authors prove.

Novelty and Scope: The authors aim to present their work as providing a theoretical understanding when certain batch sizes should be used. Instead, the prove results concerning lower bounds for monomials, all the while giving no justification for why this class in particular is relevant to batching. Moreover, the text itself (lines 76-80) admits that the convex optimization ingredients are standard. This begs the question of where the technical novelty is. It appears to me their best result is a reformulation of the convex hull for their monomials of choice.

Questions for authors

Why is this setting relevant to the community at ICLR; the section why this matters does not even mention the headline setting of batching? See the weakness section.

Reviewer_9QWsOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

This paper studies batch size schedules, and answers a specific question of proving that a schedule is near-best. The authors derive an exact formula for the best certificate. A certificate in this context is a lower bound LL on the best achievable loss JJ of a schedule mm. The guarantee is of the form J(m)≤(1+ϵ)LJ(m) \leq (1 + \epsilon) L, which implies mm is within ϵ\epsilon of the optimal schedule. The best certificate is the minimum of the log loss over the convex hull of integer schedules, which is a continuous version of the problem, and thus there is a gap between the best lower bound and the true best integer schedule. The authors show how to reduce the gap using multiple certificates rather than just a single one. Finally, the gap is demonstrated on a small example using stochastic gradient descent (SGD).

Critical strengths

None

Critical weaknesses

The main weakness of the paper is in the novelty and motivation. The paper uses a lot of notation to define a straightforward, known quantity from convex optimization: the integrality gap of a convex relaxation. The gap scales like N/b3N/b^3, where NN is the number of steps and bb is the batch size, so only holds for very small batch sizes and many steps. It also vanishes entirely when the budget divides evenly. In most practical scenarios, JJ is either unavailable or is computed with estimates. If we let η\eta be estimation error than the certificate gap is at most 2η2\eta (Corollary A.5). This effectively means that the gap is dominated by the estimation error rather than the integrality gap. So either JJ is known and the domain is small, meaning we can just enumerate every schedule and choose the best one, or JJ is estimated, and the certificate is noisy due to estimation error.

Second, the experiments are insufficient at testing the desired mechanism. They are exclusively on a toy setting with small batch sizes and a small number of steps. The exact integer optimum is computed by enumerating every possible schedule, which means none of the experiments require the proposed certificate approach at all. No motivating example is provided where these certificates would be useful in practice.

Finally, the presentation is very poor. The writing is incredibly terse and full of jargon and non-standard terms that make it difficult to understand. No comparison is made with existing approaches, and the related work is incredibly sparse, suggesting a lack of proper literature review. Overall, the quality is well below what I would consider acceptable at one of the top AI/ML conferences in the world.

Questions for authors
  • What concrete task or application would require a valid lower bound on fractional schedules rather than on feasible integer schedules?
  • In what settings can J(m)J(m) be computed exactly?
  • How do the results degrade when JJ is estimated from data?
Reviewer_rHYJOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates why the optimal budget allocation across mini-batches during SGD training cannot always be rigorously verified by a single, universal mathematical certificate, and it derives an exact formula that bounds the strength of such a certificate. The authors demonstrate that employing multiple reference points can narrow the gap between the optimal schedule and its certified estimate, supporting this theory with both mathematical proofs and synthetic experiments.

Critical strengths
  1. The idea behind the paper seems quite fresh and interesting. I haven’t encountered this type of approach before; it holds promise for future development. This is an important detail.

  2. The authors construct a clear mathematical framework for solving a specific discrete optimization problem (although all the techniques are classic and not new).

  3. There is a connection to a quadratic problem, which is a positive step toward bridging the gap between theory and practical application.

Critical weaknesses
  1. The structure of the paper seems a bit strange to me. For instance, let’s look at (2.2). Why should we be solving this particular problem? One would need to be familiar with optimization theory to understand why such a formula for JmJ_m is used. I would suggest, for example, adding references and formulas from optimization theory. The main point here is that the article should be smooth reading for someone from the AI ​​community with a mathematical background—without them having to ask, "Where does this come from?" or "Why is this here?"

  2. For the more practically-oriented members of the community, I would suggest that the authors include a dedicated section—a "bridge"—that demonstrates how the developed theory can be applied. For instance, consider a scenario involving the training of a specific class of neural networks, where one might need to tune a vast number of hyperparameters (including batches): how could this problem be reformulated in the form of equation (2.2) to determine an optimal schedule? What i need to estimate in learning landscape? If such a reformulation is not feasible, the authors should explicitly state what the current model fails to account for, and what is missing to effectively bridge the gap between theory and practice.

  3. If it is not possible to build such a bridge, one could attempt to construct a different one—for instance, with the theory of the convergence of optimization methods. Currently, there are many diverse scenarios regarding convergence under various assumptions: cases involving heavy-tailed noise, conditions of smoothness (or specific types of smoothness L0,L1L_0, L_1), and other emerging themes. The more of these theoretical frameworks that can be incorporated into the formulation presented in 2.1 + 2.2, the more compelling that connection will become.

  4. There are far too many extraneous terms (for my taste); they complicate the narrative without adding any real substance, and often appear only once or twice after being introduced.

  5. The authors might consider including an extensive section on future directions for the theory’s development. It seems to me that this work could be extended in various ways; reflecting this would help underscore the fundamental nature of their contribution. Specifically, they could discuss the limitations of their framework—for instance, in relation to other existing results in the field of machine learning—and suggest how these might be addressed in future research.

  6. The results in the paragraph at line 342 are somewhat disappointing in terms of the theoretical findings obtained.

Summary:

The paper develops a clear mathematical framework; since the components of this framework are classical, it cannot be considered a distinct contribution in itself. It is important to determine what concrete conclusions can already be drawn—or might be drawn (given further refinement of the framework)—within the context of practical machine learning or theoretical-practical machine learning (such as the convergence theory of optimization algorithms used in training tasks). Without this connection being stated more explicitly, I am not yet prepared to accept the paper.

Questions for authors

Can the theory derived here be applied to the case where I want to use batch sizes that are powers of 2? It seems like this should be straightforward to do.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.