The Application of Optimization Techniques in Machine Learning

Abstract

The past decades have witnessed significantly progress in machine learning,

and solving these problems requires the advancing in optimization techniques.

High dimensional sparse learning has imposed a great computational challenge to large

scale data analysis. In this dissertation, parametric simplex method is applied to solve

a broad class of sparse learning approaches, which can be formulated as linear programs

parametrized by a regularization parameter. There are serious drawbacks to the existing

methods for solving these types of problems as tuning the parameter for the desired solution is very inefficient.

The customized parametric simplex method is introduced and it uses the unknown weighting factor

as the parameter and provides a powerful and efficient way to address these shortcomings. Although the simplex method has an

exponential complexity in the worse case, it has been shown that the parametric simplex method is an appropriate method for these cases when the expected solution is sparse. An R package named fastclime which

efficiently solves a variety machine learning problems by the customized parametric simplex method is developed. A convex optimization method named Inexact Peaceman-Rachford Splitting Method (IPRSM) is studied.

Similar to the Alternating Direction Method of Multiplier (ADMM), the strictly

contractive Peaceman-Rachford Splitting Method (PRSM) is also used to solve a convex minimization problem

with linear constraints and a separable objective function. In many applications, it

is quite expensive to obtain exact solutions to these subproblems. The inexact methods

intend to solve the iterative subproblems when the exact solutions do not exist or they are

hard to obtain. Finally, the new graph Perceptron algorithm, a graph estimation method which performs on online binary classification problems is proposed. The new graph Perceptron algorithm is a new kernel based Perceptron derived from online class-action and extend to online graph estimation with a new kernel trick.