Rough sets have been studied for over 30 years, and the basic concepts of lower and upper approximations have been analysed in detail, yet nowhere has the idea of an `optimal' rough approximation been proposed or investigated. In this thesis, several concepts are used in proposing a generalized definition: measures, rough sets, similarity, and approximation are each surveyed. Measure Theory allows us to generalize the definition of the `size' for a set. Rough set theory is the foundation that we use to define the term `optimal' and what constitutes an `optimal rough set'. Similarity indexes are used to compare two sets, and determine how alike or different they are. These sets can be rough or exact. We use similarity indexes to compare sets to intermediate approximations, and isolate the optimal rough sets. The historical roots of these concepts are explored, and the foundations are formally defined. A definition of an optimal rough set is proposed, as well as a simple algorithm to find it. Properties of optimal approximations such as minimum, maximum, and symmetry, are explored, and examples are provided to demonstrate algebraic properties and illustrate the mechanics of the algorithm. / Thesis / Doctor of Philosophy (PhD) / Until now, in the context of rough sets, only an upper and lower approximation had been proposed. Here, an concept of an optimal/best approximation is proposed, and a method to obtain it is presented.

The foundations of deep learning are supported by the seemingly opposing perspectives of approximation or learning theory. The former advocates for large/expressive models that need not generalize, while the latter considers classes that generalize but may be too small/constrained to be universal approximators. Motivated by real−world deep learning implementations that are both expressive and statistically reliable, we ask: "Is there a class of neural networks that is both large enough to be universal but structured enough to generalize?" This paper constructively provides a positive answer to this question by identifying a highly structured class of ReLU multilayer perceptions (MLPs), which are optimal function approximators and are statistically well−behaved. We show that any L−Lipschitz function from [0,1]ᵈ to [−n,n] can be approximated to a uniform Ld/(2n) error on [0,1]ᵈ with a sparsely connected L−Lipschitz ReLU MLP of width 𝒪(dnᵈ), depth 𝒪(łog(d)), with 𝒪(dnᵈ) nonzero parameters, and whose weights and biases take values in {0,± 1/2} except in the first and last layers which instead have magnitude at−most $n$. Unlike previously known "large" classes of universal ReLU MLPs, the empirical Rademacher complexity of our class remains bounded even when its depth and width become arbitrarily large. Further, our class of MLPs achieves a near−optimal sample complexity of 𝒪(łog(N)/√{N}) when given N i.i.d. normalized sub−Gaussian training samples. We achieve this by avoiding the standard approach to constructing optimal ReLU approximators, which sacrifices regularity by relying on small spikes. Instead, we introduce a new construction that perfectly fits together linear pieces using Kuhn triangulations and avoids these small spikes. / Thesis / Master of Science (MSc)