Linear Algebra and Optimization with Applications to Machine Learning

The following sections are included:

• Preface
• Contents

This second volume covers some elements of optimization theory and applications, especially to machine learning. This volume is divided in five parts:

• Preliminaries of Optimization Theory.
• Linear Optimization.
• Nonlinear Optimization.
• Applications to Machine Learning.
• An appendix consisting of two chapters; one on Hilbert bases and the Riesz–Fischer theorem, the other one containing Matlab code.

This chapter contains a review of basic topological concepts. First metric spaces are defined. Next normed vector spaces are defined. Closed and open sets are defined, and their basic properties are stated. The general concept of a topological space is defined. The closure and the interior of a subset are defined. The subspace topology and the product topology are defined. Continuous maps and homeomorphisms are defined. Limits of sequences are defined. Continuous linear maps and multilinear maps are defined and studied briefly. Cauchy sequences and complete metric spaces are defined. We prove that every metric space can be embedded in a complete metric space called its completion. A complete normed vector space is called a Banach space. We prove that every normed vector space can be embedded in a complete normed vector space. We conclude with the contraction mapping theorem in a complete metric space.

This chapter contains a review of basic notions of differential calculus. First we review the definition of the derivative of a function f: ℝ → ℝ. Next we define directional derivatives and the total derivative of a function f: E → F between normed vector spaces. Basic properties of derivatives are shown, including the chain rule. We show how derivatives are represented by Jacobian matrices. The mean value theorem is stated, as well as the implicit function theorem and the inverse function theorem. Diffeomorphisms and local diffeomorphisms are defined. Higher-order derivatives are defined, as well as the Hessian. Schwarz’s lemma (about the commutativity of partials) is stated. Several versions of Taylor’s formula are stated, and a famous formula due to Faà di Bruno’s is given.

This chapter deals with extrema of real-valued functions. In most optimization problems, we need to find necessary conditions for a function J: Ω → ℝ to have a local extremum with respect to a subset U of Ω (where Ω is open). This can be done in two cases:

• The set U is defined by a set of equations,
  $$U=\left\{x\in \Omega |{\phi }_i\left(x\right)=0,1\le i\le m\right\},$$
  where the functions φ_i: Ω → ℝ are continuous (and usually differentiable).
• The set U is defined by a set of inequalities,
  $$U=\left\{x\in \Omega |{\phi }_i\left(x\right)\le 0,1\le i\le m\right\},$$
  where the functions φ_i: Ω → ℝ are continuous (and usually differentiable).

In Chapter 4 we investigated the problem of determining when a function J: Ω → ℝ defined on some open subset Ω of a normed vector space E has a local extremum. Proposition 4.1 gives a necessary condition when J is differentiable: if J has a local extremum at u ∈ Ω, then we must have

In this chapter we consider two classes of quadratic optimization problems that appear frequently in engineering and in computer science (especially in computer vision):

• Minimizing
  $$Q\left(x\right)=\frac{1}{2}{x}^{\top }Ax-x^{\top }b$$
  over all x ∈ ℝⁿ, or subject to linear or affine constraints.
• Minimizing
  $$Q\left(x\right)=\frac{1}{2}{x}^{\top }Ax-x^{\top }b$$
  over the unit sphere.

In both cases, A is a symmetric matrix. We also seek necessary and sufficient conditions for f to have a global minimum.

Schur complements arise naturally in the process of inverting block matrices of the form

The following sections are included:

• What is Linear Programming?
• Affine Subsets, Convex Sets, Affine Hyperplanes, Half-Spaces
• Cones, Polyhedral Cones, and ℋ-Polyhedra
• Summary
• Problems

In this chapter we introduce linear programs and the basic notions relating to this concept. We define the ℋ-polyhedron $\mathcal{P}\left(A,b\right)$ of feasible solutions. Then we define bounded and unbounded linear programs and the notion of optimal solution. We define slack variables and the important notion of linear program in standard form…

The following sections are included:

• The Idea Behind the Simplex Algorithm
• The Simplex Algorithm in General
• How to Perform a Pivoting Step Efficiently
• The Simplex Algorithm Using Tableaux
• Computational Efficiency of the Simplex Method
• Summary
• Problems

The following sections are included:

• Variants of the Farkas Lemma
• The Duality Theorem in Linear Programming
• Complementary Slackness Conditions
• Duality for Linear Programs in Standard Form
• The Dual Simplex Algorithm
• The Primal-Dual Algorithm
• Summary
• Problems

Most of the “deep” results about the existence of minima of real-valued functions proven in Chapter 13 rely on two fundamental results of Hilbert space theory:

• The projection lemma, which is a result about nonempty, closed, convex subsets of a Hilbert space V.
• The Riesz representation theorem, which allows us to express a continuous linear form on a Hilbert space V in terms of a vector in V and the inner product on V

This chapter is devoted to some general results of optimization theory. A main theme is to find sufficient conditions that ensure that an objective function has a minimum which is achieved. We define the notion of a coercive function. The most general result is Theorem 13.1, which applies to a coercive convex function on a convex subset of a separable Hilbert space. In the special case of a coercive quadratic functional, we obtain the Lions–Stampacchia theorem (Theorem 13.4), and the Lax–Milgram theorem (Theorem 13.5). We define elliptic functionals, which generalize quadratic functions defined by symmetric positive definite matrices. We define gradient descent methods, and discuss their convergence. A gradient descent method looks for a descent direction and a stepsize parameter, which is obtained either using an exact line search or a backtracking line search. A popular technique to find the search direction is steepest descent. In addition to steepest descent for the Euclidean norm, we discuss steepest descent for an arbitrary norm. We also consider a special case of steepest descent, Newton’s method. This method converges faster than the other gradient descent methods, but it is quite expensive since it requires computing and storing Hessians. We also present the method of conjugate gradients and prove its correctness. We briefly discuss the method of gradient projection and the penalty method in the case of constrained optima.

This chapter contains the most important results of nonlinear optimization theory.

In Chapter 4 we investigated the problem of determining when a function J: Ω → ℝ defined on some open subset Ω of a normed vector space E has a local extremum in a subset U of Ω defined by equational constraints, namely

In this chapter we consider some deeper aspects of the theory of convex functions that are not necessarily differentiable at every point of their domain. Some substitute for the gradient is needed. Fortunately, for convex functions, there is such a notion, namely subgradients. Geometrically, given a (proper) convex function f, the subgradients at x are vectors normal to supporting hyperplanes to the epigraph of the function at (x; f(x)). The subdifferential ∂f(x) to f at x is the set of all subgradients at x. A crucial property is that f is differentiable at x iff ∂f(x) = {∇f_x}, where ∇f_x is the gradient of f at x. Another important property is that a (proper) convex function f attains its minimum at x iff 0 ∈ ∂f(x). A major motivation for developing this more sophisticated theory of “differentiation” of convex functions is to extend the Lagrangian framework to convex functions that are not necessarily differentiable…

This chapter is devoted to the presentation of one of the best methods known at the present for solving optimization problems involving equality constraints. In fact, this method can also handle more general constraints, namely, membership in a convex set. It can also be used to solve a range of problems arising in machine learning including lasso minimization, elastic net regression, support vector machine (SVM), and ν-SV regression. In order to obtain a good understanding of this method, called the alternating direction method of multipliers, for short ADMM, we review two precursors of ADMM, the dual ascent method and the method of multipliers…

This chapter is an introduction to positive definite kernels and the use of kernel functions in machine learning. Let X be a nonempty set. If the set X represents a set of highly nonlinear data, it may be advantageous to map X into a space F of much higher dimension called the feature space, using a function φ: X → F called a feature map. This idea is that φ “unwinds” the description of the objects in F in an attempt to make it linear. The space F is usually a vector space equipped with an inner product 〈–, –〉. If F is infinite dimensional, then we assume that it is a Hilbert space…

In Sections 14.5 and 14.6 we considered the problem of separating two nonempty disjoint finite sets of p blue points ${\left\{u_i\right\}}_{i=1}^p$ and q red points ${\left\{v_j\right\}}_{j=1}^q$ in ℝⁿ. The goal is to find a hyperplane H of equation w^⊤x−b=0 (where w ∈ ℝⁿ is a nonzero vector and b ∈ ℝ), such that all the blue points u_i are in one of the two open half-spaces determined by H, and all the red points v_j are in the other open half-space determined by H. SVM picks a hyperplane which maximizes the minimum distance from these points to the hyperplane. See Figure 18.1…

In this chapter we discuss linear regression. This problem can be cast as a learning problem. We observe a sequence of (distinct) pairs ((x₁; y₁), …, (x_m; y_m)) called a set of training data (or predictors), where x_i ∈ ℝⁿ and y_i ∈ ℝ, viewed as input-output pairs of some unknown function f that we are trying to infer. The simplest kind of function is a linear function f(x) = x^⊤w, where w ∈ ℝⁿ is a vector of coefficients usually called a weight vector. Since the problem is overdetermined and since our observations may be subject to errors, we can’t solve for w exactly as the solution of the system Xw = y, where X is the m × n matrix

The following sections are included:

• ν-SV Regression; Derivation of the Dual
• Existence of Support Vectors
• Solving ν-Regression Using ADMM
• Kernel ν-SV Regression
• ν-Regression Version 2; Penalizing b
• Summary
• Problems

The following sections are included:

• Appendix A Total Orthogonal Families in Hilbert Spaces
  • Total Orthogonal Families (Hilbert Bases), Fourier Coefficients
  • The Hilbert Space ℓ²(K) and the Riesz–Fischer Theorem
  • Summary
  • Problems
• Appendix B Matlab Programs
  • Hard Margin (SVM_h2)
  • Soft Margin SVM (SVM_s2′)
  • Soft Margin SVM (SVM_s3)
  • ν-SV Regression

The following sections are included:

• Bibliography
• Index