Theory

Theory is the study of idealized settings. A result here is proved, which means it is true forever and true only under the assumptions it was proved under. Both halves matter.

Convex optimization guarantees that any local minimum is a global one, and the guarantee evaporates the moment your loss surface stops being convex, which for a neural network it never was. The value of knowing the theorem is not that you get the guarantee. It is that you know exactly which assumption you broke and therefore what kind of failure to expect.

This branch is organized by academic field rather than by application area, because that is how the results are actually indexed. When somebody at a whiteboard says “that is just a regret bound” or “you are describing a martingale,” they are naming a field, and the field carries a century of results you can look up. A page here tries to leave you able to follow that sentence and find the theorem.

Every page states its assumptions before its results. Where a result is famous and the assumptions are routinely forgotten, the page says so plainly. Where a conjecture is open, it is labeled open rather than presented as settled.

Contents

OptimizationMinimizing under constraint, the rates convexity buys, and what survives without itOperations ResearchLinear programming, duality, network flows, queues, and scheduling scarce resourcesInformation TheoryEntropy, mutual information, channel capacity, and why compression is what models optimizeLearning TheoryWhy fitting a finite sample predicts the next, and how much dataDecision TheorySingle choices without dynamics, covering utility axioms, information value, and regretReinforcement LearningLearning a policy from interaction, with value, policy gradient, and reward specificationControl TheorySteering a system you cannot fully model, and proving it stableGame TheoryPayoffs depending on everyone else, the resulting equilibria, and where they failAsset PricingWhat an uncertain future claim is worth, and the no-arbitrage assumptions beneathLogicWhat follows from what, the incompleteness and undecidability results, and machine-checked proofComputability and ComplexityWhat a machine can compute, what it computes cheaply, and what cannotQuantum ComputingAlgorithms proved to win, the error correction required, and the remaining distance