Regulatory T cells (Tregs) play a crucial role in mediating immune response. Yet an algorithmic understanding of the role of Tregs in adaptive immunity remains lacking. Here, we present a biophysically realistic model of Treg mediated self-tolerance in which Tregs bind to self-antigens and locally inhibit the proliferation of nearby activated T cells. By exploiting a duality between ecological dynamics and constrained optimization, we show that Tregs tile the potential antigen space while simultaneously minimizing the overlap between Treg activation profiles. We find that for sufficiently high Treg diversity, Treg mediated self-tolerance is robust to fluctuations in self-antigen concentrations but lowering the Treg diversity results in a sharp transition -- related to the Gardner transition in perceptrons -- to a regime where changes in self-antigen concentrations can result in an auto-immune response. We propose a novel experimental test of this transition in immune-deficient mice and discuss potential implications for autoimmune diseases.