colt-related-work

COLT Related Work

At COLT, related work is quantitative: the reviewer wants to know exactly which bound,

in exactly which model, your result improves, matches, generalizes, or separates.

Prose adjacency ("much work has studied bandits") is filler; a rates table is

evidence. Use this skill to build the comparison and to keep it eligible under the

current CFP's overlap rules.

The known-vs-new ledger

For each of your main results, fill one row per nearest prior result:

| Prior result | Model / assumptions | Their bound | Your bound | Delta type |

|---|---|---|---|---|

| [Cite] Thm 4 | oblivious adversary, K arms | $O(\sqrt{TK\log K})$ | $O(\sqrt{TK})$ | log-factor removal |

| [Cite] Thm 1 | i.i.d., realizable | $O(d/\epsilon)$ | same rate, weaker assumption | assumption weakening |

| [Cite] | same model | lower bound $\Omega(\sqrt{TK})$ | upper matches | closes their gap |

Delta types COLT reviewers recognize as contributions: closing an upper/lower gap,

removing a log factor with a new technique, weakening assumptions at the same rate, a

new model with a separation from an old one, a simpler proof of a known result (yes —

if genuinely simpler, say so plainly), and resolving a posed open problem.

Literature lanes to cover

| Lane | Where it lives | What the reviewer checks |

|---|---|---|

| COLT/ALT lineage | PMLR volumes (e.g., v247 = COLT 2024, v291 = COLT 2025), ALT proceedings | Whether you know the direct predecessors and cite the newest ones |

| CS theory | STOC, FOCS, SODA, ITCS | Whether complexity/lower-bound machinery is attributed correctly |

| ML theory tracks | NeurIPS, ICML, AISTATS theory papers | Whether a recent conference paper already claims your rate |

| Statistics and probability | Annals of Statistics, JMLR, Bernoulli, probability literature | Whether your "new" phenomenon is classical under another name |

| Open problems | COLT open-problem pieces (e.g., PMLR v65:4-7) | Whether you cite the problem you are solving — and claim credit for it |

A bibliography missing the statistics lane invites the deadliest COLT review sentence:

"this is a known result in the empirical-process literature." Search old names for

your objects (regret has cousins in sequential analysis; PAC bounds have cousins in

empirical processes) before claiming firsts.

Open problems as positioning assets

COLT maintains a tradition of published open problems (short, citable pieces in the

proceedings — see the exemplars library for a verified instance). If your paper

resolves or dents one:

• cite the open-problem piece itself, state which part you resolve, and quote the

posed question's parameters honestly — partial resolutions must say so;

• expect the problem's posers as likely reviewers, and write accordingly.

Concurrency and arXiv norms

The theory community posts to arXiv aggressively, so collisions are routine:

• Concurrent arXiv work discovered before the deadline: cite it, mark it as

concurrent and independent, and state the technical difference without priority

litigation — reviewers verify tone here.

• Work appearing after submission: raise it in the rebuttal proactively if reviewers

will find it anyway; silence looks worse.

• Your own prior arXiv version of this paper is not prior work; do not cite it in a

way that de-anonymizes (see colt-submission for the anonymity sweep).

• The 2026 CFP barred parallel submission to journals and to proceedings venues of

substantially similar work (verified 2026-07-08); the related-work section is where

such overlap becomes visible, so audit your own citations for it.

Citation mechanics

Cite PMLR-published COLT papers by volume; the canonical form:

@inproceedings{rakhlin11beyond,
  title     = {Online Learning: Beyond Regret},
  author    = {Rakhlin, Alexander and Sridharan, Karthik and Tewari, Ambuj},
  booktitle = {Proceedings of the 24th Annual Conference on Learning Theory},
  series    = {Proceedings of Machine Learning Research},
  volume    = {19},
  pages     = {559--594},
  year      = {2011},
  publisher = {PMLR}
}

(Entry verified against proceedings.mlr.press/v19/rakhlin11a.html on 2026-07-08.)

Cite theorem numbers, not just papers, when you invoke a specific bound — "[23,

Thm 3.2]" is house style and lets referees check your usage in seconds.

A search protocol that catches the deadly citation

1. Enumerate your objects under alternate names: regret ↔ sequential prediction error

in sequential analysis; sample complexity ↔ rates of convergence in nonparametric

statistics; margin bounds ↔ empirical-process localization.

1. Sweep DBLP's COLT/ALT indices for the last five editions on your model keywords,

then chase citations backward from the two nearest hits.

1. Search arXiv for the last twelve months on the model name and the bound form —

this is the concurrency sweep, repeated once more in rebuttal week.

1. Check whether a COLT open-problem piece poses your question; solving one unknowingly

wastes the single best positioning sentence available to you.

1. For every external theorem you invoke, cite the original source, not the survey

you learned it from — theorists notice laundering through textbooks.

Anti-patterns

• A paragraph-per-paper related-work section with no comparison table.
• Citing surveys where the reviewer expects the original theorem's source.
• "To the best of our knowledge, this is the first..." without a search story; scope

the claim to a named model class instead.

• Comparing against a prior bound while quietly changing its model (their adaptive

adversary, your oblivious one) — reviewers catch model-shifted comparisons and read

them as either carelessness or spin.

Cycle-volatility warnings

• Overlap and dual-submission wording is re-issued each cycle; the rules summarized

here are the 2026 text (待核实 in later cycles).

• Whether an Open Problems track runs in the current cycle must be checked in the

live CFP.

Output format

[Ledger status] complete / rows missing for <results>
[Nearest prior work] <paper, theorem, exact bound>
[Delta type] gap-closing / log-removal / assumption-weakening / separation / simpler proof / open-problem resolution
[Lane coverage] COLT-ALT / CS-theory / ML-tracks / statistics / open-problems
[Overlap risk] none / concurrent arXiv / eligibility issue to declare