THEORIA / RESEARCH CATALOG

Open problems
in foundations of AI/ML.

Find your next research direction. Explore conjectures and open questions through their models, mathematical targets and connections.

Theory & computationMathematical models & guarantees
119open problems

Explore with /next-steps ↗ or /attack slash commands

A source-linked collection of theoretical open problems. Explore challenges in AI safety, learning theory, transformers, world models, optimization, memory and inference. Each entry gives a precise research target, assumptions and known progress. Open status is provisional; broader programs explicitly need a framework. Sources & methodology ↗

Seed catalog · Browse the bundled collection. Search matches words; Supabase mode uses ranked full-text search.

START EXPLORING
SubjectAll subjects
TypeAll types
ReviewAll entries

Choose multiple options. Results match any selected value within each filter.

12 problems matching “bound_gap”

Multi-agent communication & games · Statistical learning theoryOpen question

The Price of Strategic Collaboration

Agents may contribute too little or duplicate work because of incentives and incomplete knowledge. This model makes the cost of coordinating them through information a precise worst-case quantity.

Editorially scoped

2 sources · Specified modelRead
Neural architecture & complexity · Learning dynamics & scalingOpen question

Can Sparse Experts Learn Without Starving?

A large pool of experts is efficient only if the router discovers their roles and sends enough learning signal to each useful expert. Efficiency payoff: Train a high-capacity model with low active computation without losing rare features through capacity overflow or early routing collapse.

Editorially scoped

3 sources · Framework needs definitionRead
Statistical learning theory · Optimization & optimizersOpen question

Fast Logistic Learning with Optimal Regret

Even a convex linear prediction model can have a gap between statistically optimal learning and an implementation whose cost scales gently with the data stream. Efficiency payoff: Obtain optimal online log-loss guarantees without expensive posterior integration or a large comparator-norm penalty.

Editorially scoped

3 sources · Specified modelRead
Statistical learning theoryOpen question

How Fast Can Forecasts Become Calibrated?

Reliable probability forecasts should become calibrated even when outcomes are chosen adversarially. The unresolved exponent measures the unavoidable speed of that process.

Editorially scoped

2 sources · Specified modelRead
Statistical learning theoryOpen question

The Exact Sample Cost of Multiclass Learning

The quantity of data needed for learning should be measured by the correct model complexity, without avoidable logarithmic losses from the proof or algorithm.

Editorially scoped

3 sources · Specified modelRead
Statistical inference · Statistical learning theoryOpen question

The True Sample Cost of Distribution Testing

Two distributions with equally large support can require very different amounts of data to distinguish from a reference. A sharp instance-dependent bound would capture that difference.

Editorially scoped

2 sources · Specified modelRead
Optimization & optimizers · Learning dynamics & scaling · Multi-agent communication & gamesOpen question

Fast Self-Play at Every Step Size

Aggressive or persistent updates can keep cycling yet learn efficiently in self-play. This problem asks whether shrinking the learning rate is unnecessary throughout a concrete higher-dimensional game family. Efficiency payoff: Keep a productive fixed update scale in coupled learning when diminishing steps are unnecessary.

Editorially scoped

2 sources · Specified modelRead
Neural architecture & complexity · Statistical learning theory · Memory & capacityOpen question

How Large Must a Shallow Network Be?

Depth can be traded for enormous width and precision. Once two layers suffice in principle, the meaningful question is how much model description is needed to realize that expressivity.

Editorially scoped

2 sources · Specified modelRead
Statistical inference · Statistical learning theoryOpen question

Learning Interactions from Fluctuations

Observed correlations reflect both interactions and the dynamics used to observe them. Inference near slow or critical regimes must account for both.

Editorially scoped

6 sources · Framework needs definitionRead
Privacy & encrypted learning · Neural architecture & complexityOpen question

Reasoning Without Decrypting the Prompt

Encrypted linear algebra is established, but nonlinear layers and autoregressive feedback can make a long private reasoning trace much more costly than one forward pass. Efficiency payoff: Co-design approximation, packing and decoding to reduce ciphertext work while preserving the complete generated answer.

Editorially scoped

5 sources · Framework needs definitionRead
Learning dynamics & scaling · Statistical learning theoryOpen question

Reconciling Kaplan and Chinchilla Exponents

Kaplan's commonly quoted adjusted parameter/data allocation is approximately C^0.73/C^0.27, whereas Chinchilla favors roughly C^0.50/C^0.50. Existing reconciliations explain much of this gap; reliable future scaling decisions require knowing which corrected differences can actually be resolved with finite evidence. Efficiency payoff: Avoid choosing an oversized model or an undersized training corpus because of biased scaling fits, incomplete FLOP accounting or uncharged optimizer tuning.

Editorially scoped

7 sources · Framework needs definitionRead
Statistical learning theory · Data-efficient learningOpen question

Teaching with Linearly Many Examples

A small set of carefully chosen examples can identify a rule much faster than random sampling. The question asks whether VC complexity also controls this teaching cost linearly.

Editorially scoped

3 sources · Specified modelRead