In this article we describe and analyze sublinear-time approximation algorithms for some optimization problems arising in machine learning, such as training linear classifiers and finding minimum enclosing balls. Our algorithms can be extended to some kernelized versions of these problems, such as SVDD, hard margin SVM, and L 2 -SVM, for which sublinear-time algorithms were not known before. These new algorithms use a combination of a novel sampling techniques and a new multiplicative update algorithm. We give lower bounds which show the running times of many of our algorithms to be nearly best possible in the unit-cost RAM model. The time bounds given for our algorithms, except the Las Vegas ones, are under the assumption of constant error probability; for output guarantees that hold with probability 1 − δ, our bounds should be multiplied by log(n/δ). The time bounds also require the assumption that the input data is stored in such a way that a given entry A i, j can be recovered in constant time. This can be done by, for example, keeping each row A i of A as a hash table. (Simply keeping the entries of the row in sorted order by column number is also sufficient, incurring an O(log d) overhead in running time for binary search.) Formal Description: Classification. In the linear classification problem, the learner is given a set of n labeled examples in the form of d-dimensional vectors, comprising the input matrix A. The labels comprise a vector y ∈ {+1, −1} n . The goal is to find a separating hyperplane, that is, a normal vector x in the unit Euclidean ball B such that for all i, y(i) · A i x ≥ 0; here y(i) denotes the i'th coordinate of y. As mentioned, we will assume throughout that A i ∈ B for all i ∈ [n], where generally [m] denotes the set of integers {1, 2, . . . , m}. As is standard, we may assume that the labels y(i) are all 1, by taking A i ← −A i for any i with y(i) = −1. The approximation version of linear classification is to find a vector x ε ∈ B that is an ε-approximate solution, that is, (1) The optimum for this formulation is obtained when x = 1, except when no separating hyperplane exists, and then the optimum x is the zero vector. Note that min i A i x = min p∈ p Ax, where ⊂ R n is the unit simplex { p ∈ R n | p i ≥ 0, i p i = 1}. Thus we can regard the optimum as the outcome of a game to determine p Ax, between a minimizer choosing p ∈ , and a maximizer choosing x ∈ B, yielding where this optimum σ is called the margin. From standard duality results, σ is also the optimum of the dual problem min p∈ max x∈B p Ax, and the optimum vectors p * and x * are the same for both problems. The classical Perceptron Algorithm returns an ε-approximate solution to this problem in 1 ε 2 iterations, and total time O(ε −2 M). 2 For given δ ∈ (0, 1), our new algorithm takes O(ε −2 (n + d)(log n) log(n/δ)) time to return an ε-approximate solution with probability at least 1 − δ. Further, we show this is optimal in the unit-cost RAM model, up to polylogarithmic factors. Formal Description: Minimum Enclosing Ball (MEB). The MEB problem is to find the smallest Euclidean ball in R d containing the rows of A. It is a special case of Quadratic Programming (QP) in the unit simplex, namely, to find min p∈ p b + p AA p, where b is an n-vector. This relationship, and the generalization of our MEB algorithm to QP in the simplex, is discussed in Section 3.3; for more general background on QP in the simplex, and related problems, see for example Clarkson [2008] .
Clarkson et al. REF developed an elegant perceptron framework for solving several optimization problems arising in machine learning, such as MEB.
Sublinear optimization for machine learning
JACM
Mathematics Computer Science