In the beginning of this thesis, we define the simplest learning model called the Empirical Risk Minimisation (ERM) model. After that we define a formal learning model, the PAC model, which relies on the RA assumption, and its agnostic variant in which this assumption is omitted. By defining the generalised loss function we improved the PAC model so we can use it, not only in the context of binary classification, but also on a wider range of learning problems. The main theorems are given in the central part of the thesis. The No Free Lunch theorem states that, if we don’t have any additional assumptions on the hypothesis class, no learner can succeed on all learning tasks. This means that every learning task requires individual analysis and when choosing the hypothesis class, we have to pay attention on the balance between the approximation and estimation errors, which is known as the biascomplexity tradeo. Using the Sauer-Shelah-Perles lemma and Massart lemma, we proved the key theorem of this thesis, the Fundamental Theorem of Statistical Learning, which reveals the connection between the notions of uniform convergence, (agnostic) PAC learning, ERM rule and VC dimension for binary classification problems. The theorem states that a hypothesis class is (agnostic) PAC learnable if and only if its VC dimension is finite. The quantitative version of the same theorem gives us the upper and lower bounds on the sample complexity of learning, which, among other things, depend on the VC dimension of the corresponding hypothesis class. In the last part of the thesis, we focus on two algorithms for binary classification problems. First of them uses the hypothesis class of halfspaces which belongs to the family of linear predictors, one of the most often used family of hypothesis classes. Using the Radon theorem we showed that the VC dimension of halfspaces is finite and after that we focused on the Perceptron algorithm, an iterative version of the ERM model. The second algorithm is one of many Boosting algorithms called the AdaBoost algorithm. This algorithm outputs a hypothesis that depends on a linear combination of certain simple hypothesis.