Writing study: From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model
← NeurIPS 2026 oral writing corpus
Shinsaku Sakaue, Yuichi Yoshida · Official NeurIPS 2026 oral record
Figure, table and section ledger
Editorial contribution type: Theory & formal analysis (primary).
Layout extraction, not a required paper template. Counts are distinct caption labels; a multi-panel figure counts once. Section spans are estimated from heading positions, including floats and whitespace. Method and limitations.
- Canonical PDF
- 51 physical pages
- Before references / appendix
- ≈ 10.69 page-equivalents
- Main figures / tables
- 0 / 0
- Attached appendix figures / tables
- 0 / 0
- Attached appendix span
- ≈ 36.91 page-equivalents
Source-bound correction: Top-level heading and reference/appendix boundaries checked against source PDF text. Bibliography titles/author initials, numbered contribution/property bullets, diagram steps, equations and TOC entries are not substantive headings. Section spans are page-coordinate estimates, not ink area or prose-only length. This is an author manuscript mirror, not a verified accepted-version template. Source layout uses physical single-column y/page-height, including equation-heavy pages.
Section-by-section lengths and source pages
The title/abstract/front matter precede the first numbered heading. A span ends at the next detected top-level heading, not at the last sentence; end-page whitespace is included. References and statements are listed separately. These are not measurements of text-only or artwork area.
| Top-level heading | Starts on PDF page | Estimated span | Share of entire PDF |
|---|---|---|---|
| 1 Introduction | 1 | ≈ 2.05 pp. | 4.02% |
| 2 Preliminaries | 3 | ≈ 1.2 pp. | 2.35% |
| 3 Batch-to-online transformation with time-varying approximation accuracy | 4 | ≈ 0.88 pp. | 1.73% |
| 4 Small-loss regret bound via time-varying approximation accuracy | 5 | ≈ 2.7 pp. | 5.29% |
| 5 Application to online submodular function minimization | 8 | ≈ 1.36 pp. | 2.67% |
| 6 Application to online ℓ1 regression | 9 | ≈ 0.74 pp. | 1.45% |
| 7 Further applications and a general idea for achieving small-loss bounds | 10 | ≈ 0.64 pp. | 1.25% |
| 8 Conclusion and limitations | 11 | ≈ 0.49 pp. | 0.96% |
| Acknowledgements | 11 | ≈ 0.11 pp. | 0.22% |
| References | 11 | ≈ 3.4 pp. | 6.67% |
| A Proof of Lemma 2.1 | 15 | ≈ 0.3 pp. | 0.59% |
| B Proof of Proposition 3.1 | 15 | ≈ 2.21 pp. | 4.33% |
| C Proof of Lemma 4.2 | 17 | ≈ 0.63 pp. | 1.24% |
| D Proof of Lemma 4.5 | 18 | ≈ 0.36 pp. | 0.71% |
| E Proof of Corollary 4.7 | 18 | ≈ 0.86 pp. | 1.69% |
| F Small-loss inconsistency bound | 19 | ≈ 3.27 pp. | 6.41% |
| G On a naive doubling reduction | 22 | ≈ 1.52 pp. | 2.98% |
| H Basic tools for average sensitivity analysis | 24 | ≈ 1.85 pp. | 3.63% |
| I Poissonized wrapper | 26 | ≈ 1.42 pp. | 2.78% |
| J Regularity condition for establishing Assumption 4.4 | 27 | ≈ 2.23 pp. | 4.37% |
| K Offline algorithm for submodular function minimization | 29 | ≈ 6.73 pp. | 13.2% |
| L Offline algorithm for ℓ1 regression | 36 | ≈ 5.82 pp. | 11.41% |
| M Details of other applications | 42 | ≈ 7.92 pp. | 15.53% |
| N Ω( nOPTT ) lower bound for online submodular function minimization | 50 | ≈ 1.79 pp. | 3.51% |
All detected figure and table locations
Main text
No recognized caption labels.
Attached appendix
No recognized caption labels.
Argument and organization
- Problem and contribution
Distinguishes uniformly random order from adversarial order and aims for loss-dependent bounds without relying on smoothness or linearity.
- Argument sequence
Introduces an offline-algorithm family, a time-varying transformation, a regret decomposition and two bounded terms before the final theorem and applications.
- Evidence and verification
Assumption 4.4 appears before the lemma that uses it; Theorem 4.6 explicitly references its conditions and a corollary gives a readable common case.
Problem, claim and contribution
Distinguishes uniformly random order from adversarial order and aims for loss-dependent bounds without relying on smoothness or linearity.
Sections 1–2 · Main paper
Argument and section order
Introduces an offline-algorithm family, a time-varying transformation, a regret decomposition and two bounded terms before the final theorem and applications.
Sections 3–7 · Main paper
Figures, captions and visual explanation
The main explanatory artifact is pseudocode plus an underbraced regret decomposition; repeated labels connect its two terms to subsequent proofs.
Algorithm 1 and Proposition 3.1, p. 5 · Main paper
Tables, comparisons and evidence
Assumption 4.4 appears before the lemma that uses it; Theorem 4.6 explicitly references its conditions and a corollary gives a readable common case.
Section 4.2–4.3, p. 7 · Main paper
Appendix and reproducibility
Detailed reductions, sensitivity tools and applications are separated; the naive-doubling discussion explains why an apparently simpler route is insufficient.
Appendices G–L · Main paper
Clarity and writing conventions
Short intuition paragraphs name the accuracy–stability trade-off and parameter-change cost before the formal manipulations.
Sections 3–4 · Main paper
What to reuse—and what not to infer
Transferable lesson: A theory paper can make its argument inspectable with named terms, pseudocode and a dependency map without adding decorative benchmark figures.
Boundary: These are random-order and stability-conditioned guarantees. The writing scan did not re-prove results or certify optimality.
Apply this lesson using the argument and evidence worksheet.
Inspection record and sources
- Checked
- 2026-10-02
- Reading status
- Writing-focused manuscript scan + selected visuals inspected
- Main text
- Writing-oriented distributed manuscript scan of Sections 1–8, pp. 1–11: abstract/framing, section sequence, substantive text windows, captions, evidence organization and conclusion; not exhaustive technical verification.
- Appendix / supplement
- Writing-oriented scan of Proof and application appendices through p. 51; includes the failed naive doubling route and explicit offline constructions; code and experiments were not executed.
- Visually inspected PDF pages
- 5, 7
This is a writing-focused scan of the manuscript and the stated supplementary scope: framing, organization, visual explanation, evidence presentation and wording. It is not a line-by-line proof audit, reproduction of results or exhaustive scientific review.