brycewang-stanford 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-submissionfor 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
- 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.
- Sweep DBLP's COLT/ALT indices for the last five editions on your model keywords, then chase citations backward from the two nearest hits.
- 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.
- Check whether a COLT open-problem piece poses your question; solving one unknowingly wastes the single best positioning sentence available to you.
- 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