|Ph.D Thesis||Department of Electrical Engineering|
|Supervisor:||Prof. Meir Ron|
|Full Thesis text|
The goal of our work was to derive highly competitive classification algorithms based on data and algorithm dependent generalization error bounds. Our focus was both on statistically sound and accurate bounds and on computationally tractable algorithms. Thus our approach connects between statistical learning theory and state-of-the-art optimization techniques. Our main emphasis has been on sparsity related problems in Pattern Recognition, namely feature selection and sparse Support Vector Machines. We have also suggested using a novel non-convex function which provides a close approximation to the cardinality function, in order to encourage sparsity. This function was used for the aforementioned sparsity applications in Pattern Recognition, for a non-sparse application of outlier robust classification and for non-machine learning applications such as sparse regression and total variation.