Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structures

Abstract:
Conditional gradient methods (CGM) are widely used in modern machine learning. CGM’s overall running time usually consists of two parts: the number of iterations and the cost of each iteration. Most efforts focus on reducing the number of iterations as a means to reduce the overall running time. In this work, we focus on improving the per iteration cost of CGM. The bottleneck step in most CGM is maximum inner product search (MaxIP), which requires a linear scan over the parameters. In practice, approximate MaxIP data-structures are found to be helpful heuristics. However, theoretically, nothing is known about the combination of approximate MaxIP data-structures and CGM. In this work, we answer this question positively by providing a formal framework to combine the locality sensitive hashing type approximate MaxIP data-structures with CGM algorithms. As a result, we show the first algorithm, where the cost per iteration is sublinear in the number of parameters, for many fundamental optimization algorithms, e.g., Frank-Wolfe, Herding algorithm, and policy gradient.

heading: 1 Introduction
text: Conditional gradient methods (CGM), such as Frank-Wolfe and its variants, are well-known optimization approaches that have been extensively used in modern machine learning. For example, CGM has been applied to kernel methods [1, 2], structural learning [3] and online learning [4, 5, 6]. Running Time Acceleration in Optimization: Recent years have witnessed the success of largescale machine learning models trained on vast amounts of data. In this learning paradigm, the computational overhead of most successful models is dominated by the optimization process [7, 8]. Therefore, reducing the running time of the optimization algorithm is of practical importance. The total running time in optimization can be decomposed into two components: (1) the number of iterations towards convergence, (2) the cost spent in each iteration. Reducing the number of iterations requires a better understanding of the geometric proprieties of the problem at hand and the invention of better potential functions to analyze the progress of the algorithm [9, 10, 11, 12, 13, 14, 15]. Reducing the cost spent per iteration usually boils down to designing problem-specific discrete data-structures. In the last few years, we have seen a remarkable growth of using data-structures to reduce iteration cost [16, 17, 18, 19, 20, 21, 22, 23, 24]. MaxIP Data-structures for Iteration Cost Reduction: A well-known strategy in optimization, with CGM, is to perform a greedy search over the weight vectors [9, 10, 13, 16, 25] or training
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
samples [26, 27] in each iteration. In this situation, the cost spent in each iteration is linear in the number of parameters. In practical machine learning, recent works [28, 29, 30, 31, 32] formulate this linear cost in iterative algorithms as an approximate maximum inner product search problem (MaxIP). They speed up the amortized cost per iteration via efficient data-structures from recent advances in approximate MaxIP [33, 34, 35, 36, 37, 38, 39, 40, 41, 42]. In approximate MaxIP data-structures, locality sensitive hashing (LSH) achieves promising performance with efficient random projection based preprocessing strategies [33, 34, 35, 36]. Such techniques are widely used in practice for cost reduction in optimization. [28] proposes an LSH based gradient sampling approach that reduces the total empirical running time of the adaptive gradient descent. [29] formulates the forward propagation of deep neural network as a MaxIP problem and uses LSH to select a subset of neurons for backpropagation. Therefore, the total running time of neural network training could be reduced to sublinear in the number of neurons. [31] extends this idea with system-level design for further acceleration, and [30] modifies the LSH with learning and achieves promising acceleration in attention-based language models. [32] formulates the greedy step in iterative machine teaching (IMT) as a MaxIP problem and scale IMT to large datasets with LSH. Challenges of Sublinear Iteration Cost CGM: Despite the practical success of cost-efficient iterative algorithms with approximate MaxIP data-structure, the theoretical analysis of its combination with CGM is not well-understood. In this paper, we focus on this combination and target answering the following questions: (1) how to transform the iteration step of CGM algorithms into an approximate MaxIP problem? (2) how does the approximate error in MaxIP affect CGM in the total number of iterations towards convergence? (3) how to adapt approximate MaxIP data structure for iterative CGM algorithms? Our Contributions: We propose a theoretical formulation for combining approximate MaxIP and convergence guarantees of CGM. In particular, we start with the popular Frank-Wolfe algorithm over the convex hull where the direction search in each iteration is a MaxIP problem. Next, we propose a sublinear iteration cost Frank-Wolfe algorithm using LSH type MaxIP data-structures. We then analyze the trade-off of approximate MaxIP and its effect on the number of iterations needed by CGM to converge. We show that the approximation error caused by LSH only leads to a constant multiplicative factor increase in the number of iterations. As a result, we retain the sub-linearly of LSH, with respect to the number of parameters, and at the same time retain the same asymptotic convergence as CGMs.
We summarize our complete contributions as follows.
• We give the first theoretical CGM formulation that achieves provable sublinear time cost per iteration. We also extend this result into Frank-Wolfe algorithm, Herding algorithm, and policy gradient method. • We propose a pair of efficient transformations that formulates the direction search in FrankWolfe algorithm as a projected approximate MaxIP problem. • We present the theoretical results that the proposed sublinear Frank-Wolfe algorithm asymptotically preserves the same order in the number of iterations towards convergence. Furthermore, we analyze the trade-offs between the saving in iteration cost and the increase in the number of iterations to accelerate total running time. • We identify the problems of LSH type approximate MaxIP for cost reduction in the popular CGM methods and propose corresponding solutions.
The following sections are organized as below: Section 2 introduces the related works on datastructures and optimization, Section 3 introduces our algorithm associated with the main statements convergence, Section 4 provides the proof sketch of the main statements, Section 5 presents the societal impact and Section 6 concludes the paper.

heading: 2 Related work

heading: 2.1 Maximum Inner Product Search for Machine Learning
text: Maximum Inner Product Search (MaxIP) is a fundamental problem with applications in machine learning. Given a query x ∈ Rd and an n-vector dataset Y ⊂ Rd, MaxIP targets at searching for y ∈ Y that maximizes the inner product x>y. The naive MaxIP solution takes O(dn) by comparing x with each y ∈ Y . To accelerate this procedure, various algorithms are proposed to reduce the running time of MaxIP [33, 34, 36, 35, 37, 38, 43, 44, 39, 45, 40, 41, 42]. We could categorize
the MaxIP approaches into two categories: reduction methods and non-reduction methods. The reduction methods use transformations that transform approximate MaxIP into approximate nearest neighbor search (ANN) and solve it with ANN data-structures. One of the popular data-structure is locality sensitive hashing [46, 47]. Definition 2.1 (Locality Sensitive Hashing). Let c > 1 denote a parameter. Let p1, p2 ∈ (0, 1) denote two parameters and p1 > p2. We say a function family H is (r, c · r, p1, p2)-sensitive if and only if, for any vectors x, y ∈ Rd, for any h chosen uniformly at random fromH, we have:
• if ‖x− y‖2 ≤ r, then Prh∼H[h(x) = h(y)] ≥ p1,
• if ‖x− y‖2 ≥ c · r, then Prh∼H[h(x) = h(y)] ≤ p2.
Here we define the LSH functions for euclidean distance. LSH functions could be used for search in cosine [48, 49] or Jaccard similarity [50, 51]. [33] first shows that MaxIP could be solved by `2 LSH and asymmetric transformations. After that, [34, 36, 35, 43] propose a series of methods to solve MaxIP via LSH functions for other distance measures. Besides LSH, graph-based ANN approaches [38] could also be used after reduction.
On the other hand, the non-reduction method directly builds data-structures for approximate MaxIP. [37, 42] use quantization to approximate the inner product distance and build codebooks for efficient approximate MaxIP. [38, 44] propose a greedy algorithm for approximate MaxIP under computation budgets. [39, 40, 41] directly construct navigable graphs that achieve state-of-the-art empirical performance.
Recently, there is a remarkable growth in applying data-structures for machine learning [52, 53, 54]. Following the paradigm, approximate MaxIP data-structures have been applied to overcome the efficiency bottleneck of various machine learning algorithms. [38] formulates the inference of a neural network with a wide output layer as a MaxIP problem and uses a graph-based approach to reduce the inference time. In the same inference task, [55] proposes a learnable LSH data-structure that further improves the inference efficiency with less energy consumption. In neural network training, [29, 30, 31] uses approximate MaxIP to retrieve interested neurons for backpropagation. In this way, the computation overhead of gradient updates in neural networks could be reduced. In linear regression and classification models, [28] uses approximate MaxIP data-structures to retrieve the samples with large gradient norm and perform standard gradient descent, which improves the total running time for stochastic gradient descent. [32] proposes a scalable machine teaching algorithm that enables iterative teaching in large-scale datasets. In bandit problem, [56] proposes an LSH based algorithm that solves linear bandits problem with sublinear time complexity.
Despite the promising empirical results, there is little theoretical analysis on approximate MaxIP for machine learning. We summarize the major reasons as: (1) Besides LSH, the other approximate MaxIP data-structures do not provide theoretical guarantees on time and space complexity. (2) Current approaches treat data-structures and learning dynamics separately. There is no joint analysis on the effect of approximate MaxIP for machine learning.

heading: 2.2 Projection-free Optimization
text: Frank-Wolfe algorithm [25] is a projection-free optimization method with wide applications in convex [9, 10] and non-convex optimizations [11, 12]. The procedure of Frank-Wolfe algorithm could be summarized as two steps: (1) given the gradient, find a vector in the feasible domain that has the maximum inner product, (2) update the current weight with the retrieved vector. Formally, given a function g : Rd → R over a convex set S, starting from an initial weight w0, the Frank-Wolfe algorithm updates the weight with learning rate η follows:
st ← arg min s∈S 〈s,∇g(wt)〉
wt+1 ← (1− ηt) · wt + ηt · st. Previous literature focuses on reducing the number of iterations for Frank-Wolfe algorithm over specific domains such as `p balls [9, 10, 13, 14]. The cost reduction in the iterative procedure of Frank-Wolfe algorithm is hardly discussed except [57]. In this work, we focus on the Frank-Wolfe algorithm over the convex hull of a finite feasible set. This formulation is more general and it includes recent Frank-Wolfe applications in probabilistic modeling [1, 2], structural learning [3] and policy optimization [5].

heading: 3 Our Sublinear Iteration Cost Algorithm
text: In this section, we formally present our results on the sublinear iteration cost CGM algorithms. We start with the preliminary definitions of the objective function. Then, we present the guarantees on the number of iteration and cost per iterations for our sublinear CGM algorithms to converge.

heading: 3.1 Preliminaries
text: We provide the notations and settings for this paper. We start with basic notations for this paper. For a positive integer n, we use [n] to denote the set {1, 2, · · · , n}. For a vector x, we use ‖x‖2 := ( ∑n i=1 x 2 i ) 1/2 to denote its `2 norm.
We say a function is convex if
L(x) ≥ L(y) + 〈∇L(y), x− y〉.
We say a function is β-smooth if
L(y) ≤ L(x) + 〈∇L(x), y − x〉+ β 2 ‖y − x‖22.
Given a set A = {xi}i∈[n] ⊂ Rd, we say its convex hull B(A) is the collection of all finite linear combinations y that satisfies y = ∑ i∈[n] ai · xi, where ai ∈ [0, 1] for all i ∈ [n] and ∑ i∈[n] ai = 1. Let Dmax denote the maximum diameter of B(A) so that ‖x− y‖2 ≤ Dmax for all (x, y) ∈ B(A). We present the detailed definitions in Appendix A.
Next, we present the settings of our work. Let S ⊂ RD denote a n-point finite set. Given a convex and β-smooth function g : Rd → R defined over the convex hull B(S), our goal is to find a w ∈ B(S) that minimizes g(w). Given large n in the higher dimension, the dominant complexity of iteration cost lies in finding the MaxIP of ∇g(w) with respect to S. In this setting, the fast learning rate of Frank-Wolfe in `p balls [9, 13, 16] can not be achieved. We present the detailed problem setting of the Frank-Wolfe algorithm in Appendix C.

heading: 3.2 Our Results
text: We present our main results with comparison to the original algorithm in Table 2. From the table, we show that with near-linear preprocessing time, our algorithms maintain the same number of iterations towards convergence while reducing the cost spent in each iteration to be sublinear in the number of possible parameters.
Next, we introduce the statement of our sublinear iteration cost algorithms. We start by introducing our result for improving the running time of Frank-Wolfe. Theorem 3.1 (Sublinear time Frank-Wolfe, informal of Theorem D.1). Let g : Rd → R denote a convex and β-smooth function. Let the complexity of calculating ∇g(x) to be Tg . Let S ⊂ Rd denote a set of n points. Let B ⊂ Rd denote the convex hull of S with maximum diameter Dmax. Let ρ ∈ (0, 1) denote a fixed parameter. For any parameters , δ, there is an iterative algorithm (Algorithm 2) that takes O(dn1+o(1)) time in pre-processing, takes T = O(βD2max/ ) iterations and O(dnρ + Tg) cost per iteration, starts from a random w0 from B as its initialization point,and outputs wT ∈ Rd from B such that
g(wT )−min w∈B g(w) ≤ ,
holds with probability at least 1− 1/ poly(n).
Next, we show our main result for the Herding algorithm. Herding algorithm is widely applied in kernel methods [58]. [1] shows that the Herding algorithm is equivalent to a conditional gradient method with the least-squares loss function. Therefore, we extend our results and obtain the following statement. Theorem 3.2 (Sublinear time Herding algorithm, informal version of Theorem E.3). Let X ⊂ Rd denote a feature set and Φ : Rd → Rk denote a mapping. Let Dmax denote the maximum diameter of Φ(X ) and B be the convex hull of Φ(X ). Given a distribution p(x) over X , we denote µ = Ex∼p(x)[Φ(x)]. Let ρ ∈ (0, 1) denote a fixed parameter. For any parameters , δ, there is an iterative algorithm (Algorithm 3) that takes O(dn1+o(1)) time in pre-processing, takes T = O(D2max/ ) iterations and O(dnρ) cost per iteration, starts from a random w0 from B as its initialization point, and outputs wT ∈ Rk from B such that
1 2 ‖wT − µ‖22 −min w∈B 1 2 ‖w − µ‖22 ≤ ,
holds with probability at least 1− 1/poly(n).
Finally, we present our result for policy gradient. Policy gradient [59] is a popular algorithm with wide applications in robotics [60] and recommendation [61]. [5] proposes a provable Frank-Wolfe method that maximizes the reward functions with policy gradient. However, the optimization requires a linear scan over all possible actions, which is unscalable in complex environments. We propose an efficient Frank-Wolfe algorithm with per iteration cost sublinear in the number of actions. Our statement is presented below. Theorem 3.3 (Sublinear time policy gradient, informal version of Theorem F.3). Let TQ denote the time for computing the policy graident. LetDmax denote the maximum diameter of action space and β is a constant. Let γ ∈ (0, 1). Let ρ ∈ (0, 1) denote a fixed parameter. Let µmin denote the minimal density of states in S. There is an iterative algorithm (Algorithm 5) that spends O(dn1+o(1)) time in preprocessing, takes O( βD 2 max
2(1−γ)3µ2min ) iterations and O(dnρ + TQ) cost per iterations, starts from a
random point π0θ as its initial point, and outputs π T θ that has the average gap √∑ s∈S gT (s)
2 < holds with probability at least 1− 1/poly(n), where gT (s) is defined in Eq. (6).

heading: 4 Proof Overview
text: We present the overview of proofs in this section. We start with introducing the efficient MaxIP datastructures. Next, we show how to transform the direction search in a conditional gradient approach into a MaxIP problem. Finally, we provide proof sketches for each main statement in Section 3. The detailed proofs are presented in the supplement material.
4.1 Approximate MaxIP Data-structures
We present the LSH data-structures for approximate MaxIP in this section. The detailed description is presented in Appendix A. We use the reduction-based approximate MaxIP method with LSH data-structure to achieve sublinear iteration cost. Note that we choose this method due to its clear
theoretical guarantee on the retrieval results. It is well-known that an LSH data-structures is used for approximate nearest neighbor problem. The following definition of approximate nearest neighbor search is very standard in literature [62, 46, 47, 63, 64, 65, 66, 67, 68, 69, 70]. Definition 4.1 (Approximate Nearest Neighbor (ANN)). Let c > 1 and r ∈ (0, 2) denote two parameters. Given an n-vector set Y ⊂ Sd−1 on a unit sphere, the objective of the (c, r)-Approximate Nearest Neighbor (ANN) is to construct a data structure that, for any query x ∈ Sd−1 such that miny∈Y ‖y − x‖2 ≤ r, it returns a vector z from Y that satisfies ‖z − x‖2 ≤ c · r.
In the iterative-type optimization algorithm, the cost per iteration could be dominated by the Approximate MaxIP problem (Definition 4.2), which is the dual problem of the (c, r)-ANN. Definition 4.2 (Approximate MaxIP). Let c ∈ (0, 1) and τ ∈ (0, 1) denote two parameters. Given an n-vector dataset Y ⊂ Sd−1 on a unit sphere, the objective of the (c, τ)-MaxIP is to construct a data structure that, given a query x ∈ Sd−1 such that maxy∈Y 〈x, y〉 ≥ τ , it retrieves a vector z from Y that satisfies 〈x, z〉 ≥ c ·maxy∈Y 〈x, y〉.
Next, we present the the primal-dual connection between ANN and approximate MaxIP. Given to unit vectors x, y ∈ Rd with both norm equal to 1, ‖x − y‖22 = 2 − 2〈x, y〉. Therefore, we could maximizing 〈x, y〉 by minimizing ‖x − y‖22. Based on this connection, we present how to solve (c, τ)-MaxIP using (c, r)-ANN. We start with showing how to solve (c, r)-ANN with LSH. Theorem 4.3 (Andoni, Laarhoven, Razenshteyn and Waingarten [67]). Let c > 1 and r ∈ (0, 2) denote two parameters. One can solve (c, r)-ANN on a unit sphere in query time O(d · nρ) using preprocessing time O(dn1+o(1)) and space O(n1+o(1) + dn), where ρ = 2
c2 − 1 c4 + o(1).
Next, we solve (c, τ)-MaxIP by solving (c, r)-ANN using Theorem 4.3. We have Corollary 4.4 (An informal statement of Corollary B.1). Let c ∈ (0, 1) and τ ∈ (0, 1) denote two parameters. One can solve (c, τ)-MaxIP on a unit sphere Sd−1 in query time O(d · nρ), where ρ ∈ (0, 1), using LSH with both preprocessing time and space in O(dn1+o(1)).
In our work, we consider a generalized form of approximate MaxIP, denoted as projected approximate MaxIP. Definition 4.5 (Projected approximate MaxIP). Let φ, ψ : Rd → Rk denote two transforms. Given an n-vector dataset Y ⊂ Rd so that ψ(Y ) ⊂ Sk−1, the goal of the (c, φ, ψ, τ)-MaxIP is to construct a data structure that, given a query x ∈ Rd and φ(x) ∈ Sk−1 such that maxy∈Y 〈φ(x), ψ(y)〉 ≥ τ , it retrieves a vector z ∈ Y that satisfies 〈φ(x), ψ(z)〉 ≥ c · (φ, ψ)-MaxIP(x, Y ).
For details of space-time trade-offs, please refer to Appendix B. The following sections show how to use projected approximate MaxIP to accelerate the optimization algorithm by reducing the cost per iteration.

heading: 4.2 Efficient Transformations
text: We have learned from Section 4.1 that (c, τ)-MaxIP on a unit sphere Sd−1 using LSH for ANN. Therefore, the next step is to transform the direction search procedure in iterative optimization algorithm into a MaxIP on a unit sphere. To achieve this, we formulate the direction search as a projected approximate MaxIP (see Definition A.5). We start with presenting a pair of transformation φ0, ψ0 : Rd → Rd+1 such that, given a function g : Rd → R, for any x, y in a convex set K, we have
φ0(x) :=[∇g(x)>, x>∇g(x)]>, ψ0(y) := [−y>, 1]>. (1)
In this way, we show that
〈y − x,∇g(x)〉 = − 〈φ0(x), ψ0(y)〉, arg min
y∈Y 〈y − x,∇g(x)〉 = arg max y∈Y 〈φ0(x), ψ0(y)〉 (2)
Therefore, we could transform the direction search problem into a MaxIP problem.
Next, we present a standard transformations [36] that connects the MaxIP to ANN in unit sphere. For any x, y ∈ Rd, we propose transformation φ1, ψ1 : Rd → Rd+2 such that
φ1(x) = [ (D−1x x) > 0 √ 1− ‖xD−1x ‖22 ]>
ψ1(y) = [ (D−1y y) > √ 1− ‖yD−1y ‖22 0 ]>
(3)
Here Dx, Dy are some constant that make sure both x/Dx and y/Dy have norms less than 1. Under these transformations, both φ1(x) and ψ1(y) have norm 1 and arg maxy∈Y 〈φ1(x), ψ1(y)〉 = arg maxy∈Y 〈x, y〉.
Combining transformations in Eq. (1) and Eq. (3), we obtain query transform φ : Rd → Rd+3 with form φ(x) = φ1(φ0(x)) and data transform φ : Rd → Rd+3 with form ψ(y) = ψ1(ψ0(y)). Using φ and ψ, we transform the direction search problem in optimization into a MaxIP in unit sphere. Moreover, given a set Y ⊂ Rd and a query x ∈ Rd, the solution z of (c, φ, ψ, τ)-MaxIP over (x, Y ) has the propriety that 〈z − x,∇g(x)〉 ≤ c · miny∈Y 〈y − x,∇g(x)〉. Thus, we could approximate the direction search with LSH based MaxIP data-structure.
Note that only MaxIP problem with positive inner product values could be solved by LSH. We found the direction search problem naturally satisfies this condition. We show that if g is convex, given a set S ⊂ Rd, we have mins∈S〈∇g(x), s − x〉 ≤ 0 for any x ∈ B(S), where B is the convex hull of S. Thus, maxy∈Y 〈φ0(x), ψ0(y)〉 is non-negative following Eq. (2).

heading: 4.3 Proof of Theorem 3.1
text: We present the proof sketch for Theorem 3.1 in this section. We refer the readers to Appendix D for the detailed proofs.
Let g : Rd → R denote a convex and β-smooth function. Let the complexity of calculating ∇g(x) to be Tg . Let S ⊂ Rd denote a set of n points, and B ⊂ Rd be the convex hull of S with maximum diameter Dmax. Let φ, ψ : Rd → Rd+3 denote the tranformations defined in Section 4.2. Starting from a random vector w0 ∈ B(S). Our sublinear Frank-Wolfe algorithm follows the update following rule that each step
st ← (c, φ, ψ, τ)-MaxIP of wt with respect to S wt+1 ← wt + η · (st − wt)
We start with the upper bounding 〈st − wt,∇g(wt)〉. Because st is the (c, φ, ψ, τ)-MaxIP of wt with respect to S, we have
〈st − wt,∇g(wt)〉 ≤ cmin s∈S 〈s− wt,∇g(wt) ≤ c〈w∗ − wt,∇g(wt)〉 (4)
For convenient of the proof, for each t, we define ht = g(wt)− g(w∗). Next, we upper bound ht+1 as
ht+1 ≤ g(wt) + ηt〈st − wt,∇g(wt)〉+ β
2 η2t ‖st − wt‖22 − g(w∗)
≤ g(wt) + cηt〈w∗ − wt,∇g(wt)〉+ β
2 η2t ‖st − wt‖22 − g(w∗)
≤ g(wt) + cηt〈w∗ − wt,∇g(wt)〉+ βD2max
2 η2t − g(w∗)
≤ (1− ηt)g(wt) + cηtg(w∗) + βD2max
2 η2t − g(w∗)
= (1− cηt)ht + βD2max
2 η2t
(5)
where the first step follows from the definition of β-smoothness, the second step follows from Eq. (4), the third step follows from the definition of Dmax, the forth step follows from the convexity of g.
Let η = 2c(t+2) and At = t(t+1) 2 . Combining them with Eq.(5), we show that
At+1ht+1 −Atht = c−2 t+ 1
t+ 2 βD2max
< c−2βD2max
Using induction from 1 to t, we show that
Atht < c −2tβD2max
Taken At = t(t+1)
2 into consideration, we have
ht < 2βD2max c2(t+ 1)
Given constant approximation ratio c, t should be in O(βD 2 max
) so that ht ≤ . Thus, we complete the proof.
Cost Per Iteration After we take O(dn1+o(1)) preprocessing time, the cost per iteration consists three pairs: (1) it takes Tg to compute ∇g(wt), (2) it takes O(d) to perform transform φ and ψ, (3) it takes O(dnρ) to retrieve st from LSH. Thus, the final cost per iteration would be O(dnρ + Tg). Next, we show how to extend the proof to Herding problem. Following [1], we start with defining function g = 12‖w
T − µ‖22. We show that this function g is a convex and 1-smooth function. Therefore, the Herding algorithm is equivalent to the Frank-Wolfe Algorithm over function g. Using the proof of Theorem 3.1 with β = 1, we show that it takes T = O(D2max/ ) iterations and O(dn
ρ) cost per iteration to reach the -optimal solution. Similar to Theorem 3.1, we show that the cost per iteration would be O(dnρ) as it takes O(d) to compute∇g(wt).

heading: 4.4 Proof of Theorem 3.3
text: We present the proof sketch for Theorem 3.3 in this section. We refer the readers to Appendix F for the detailed proofs.
In this paper, we focus on the action-constrained Markov Decision Process (ACMDP). In this setting, we are provided with a state S ∈ Rk and action space A ∈ Rd. However, at each step t ∈ N, we could only access a finite n-vector set of actions C(s) ⊂ A. Let us assume the C(s) remains the same in each step. Let us denote Dmax as the maximum diameter of A. When you play with this ACMDP, the policy you choose is defined as πθ(s) : S → Awith parameter θ. Meanwhile, there exists a reward function r : S × A ∈ [0, 1]. Then, we define the Q function as below,
Q(s, a|πθ) = E [ ∞∑ t=0 γtr(st, at)|s0 = s, a0 = a, πθ ] .
where γ ∈ (0, 1) is a discount factor. Given a state distribution µ, the objective of policy gradient is to maximize J(µ, πθ) = Es∼µ,a∼πθ [Q(s, a|πθ)] via policy gradient [59] denoted as:
∇θJ(µ, πθ) = E s∼dπµ
[ ∇θπθ(s)∇aQ(s, πθ(s)|πθ)| ] .
[5] propose an iterative algorithm that perform MaxIP at each iteration k over actions to find
gk(s) = max a∈C(s)
〈aks − πkθ (s),∇aQ(s, πkθ (s)|πkθ ))〉. (6)
In this work, we approximate Eq. (6) using (c, φ, ψ, τ)-MaxIP. Here define φ : S × Rd → Rd+1 and ψ : Rd → Rd+1 as follows:
φ(s, πkθ ) := [∇aQ(s, πkθ (s)|πkθ )>, (πkθ )>Q(s, πkθ (s)|πkθ )]>, ψ(a) := [a>,−1]>.
Then, we have gk(s) = 〈φ(s, πkθ ), ψ(a)〉. Note that we still require transformations in Eq. (3) to generate unit vectors.
Next, we show that if we retrieve an action âks using (c, φ, ψ, τ)-MaxIP, the gap ĝk(s) would be lower bounded by
ĝk(s) = 〈âks − πkθ (s),∇aQ(s, πkθ (s)|πkθ ))〉 ≥ cgk(s) (7)
Combining Eq. (7) the standard induction in [5], we upper bound ∑ s∈S gT (s)
2 as∑ s∈S gT (s) 2 ≤ 1 T + 1 2βD2max c2(1− γ)3µ2min . (8)
where µmin denotes the minimal density of sates in S and β is the smoothness factor. In this way, given a constant factor c, if we would like to minimize the gap ∑ s∈S gT (s) 2 < 2, T should be O( βD 2 max
2(1−γ)3µ2min ).
Cost Per Iteration After we take O(dn1+o(1)) preprocessing time, the cost per iteration consists three pairs: (1) it takes TQ to compute policy gradient, (2) it takes O(d) to perform transform φ and ψ, (3) it takes O(dnρ) to retrieve actions from LSH. Thus, the final cost per iteration would be O(dnρ + TQ).

heading: 4.5 Quantization for Adaptive Queries
text: In optimization, the gradient computed in every iteration is not independent of each other. This would generate a problem for MaxIP data-structures. If we use a vector containing the gradients as a query for MaxIP data-structures, the query failure probability in each iteration is not independent. Therefore, the total failure probability could not be union bounded. As previous MaxIP data-structures focus on the assumptions that queries are independent, the original failure analysis could not be directly applied.
This work uses a standard query quantization method to handle the adaptive query sequence in optimization. Given the known query space, we quantize it by lattices [71]. This quantization is close to the Voronoi diagrams. In this way, each query is located into a cell with a center vector. Next, we perform a query using the center vector in the cell. Therefore, the failure probability of the MaxIP query sequence is equivalent to the probability that any center vector in the cell fails to retrieve its approximate MaxIP solution. As the centers of cells are independent, we could union bound this probability. On the other hand, as the maximum diameter of the cell is λ, this query quantization would introduce a λ additive error in the inner product retrieved. We refer the readers to Appendix G for the detailed quantization approach.

heading: 4.6 Optimizing Accuracy-Efficiency Trade-off
text: In this work, we show that by LSH based MaxIP data-structure, the cost for direction search is O(dnρ), where ρ ∈ (0, 1). In Section D.2 of the supplementary material, we show that ρ is a function of constant c and parameter τ in approximate MaxIP (see Definition 4.2). Moreover, we also show in Section D.2 that LSH results in only a constant multiplicative factor increase in the number of iterations. Considering the cost per iteration and the number of iterations, we show that when our algorithms stop at the -optimal solution, LSH could achieve acceleration in the overall running time. Therefore, we could set c and τ parameters to balance the accuracy-efficiency tradeoff of CGM to achieve the desired running time.

heading: 5 Potential Negative Societal Impact
text: This paper discusses the theoretical foundation of data-structures for conditional gradient methods. We believe that this paper does not have negative societal impact in the environment, privacy, and other domains.

heading: 6 Concluding Remarks
text: In this work, we present the first Frank-Wolfe algorithms that achieve sublinear linear time cost per iteration. We also extend this result into Herding algorithm and policy gradient methods. We formulate the direction search in Frank-Wolfe algorithm as a projected approximate maximum inner product search problem with a pair of efficient transformations. Then, we use locality sensitive hashing data-structure to reduce the iteration cost into sublinear over the number of possible parameters. Our theoretical analysis shows that the sublinear iteration cost Frank-Wolfe algorithm preserves the same order in the number of iterations towards convergence. Moreover, we analyze and optimize the trade-offs between saving iteration cost and increasing the number of iterations to achieve sublinear total running time. Furthermore, we identify the problems of existing MaxIP data-structures for cost reduction in iterative optimization algorithms and propose the corresponding solutions. We hope this work can be the starting point of future study on sublinear iteration cost algorithms for optimization.

heading: Acknowledgements
text: This work was supported by National Science Foundation IIS-1652131, BIGDATA-1838177, AFOSR-YIP FA9550-18-1-0152, ONR DURIP Grant, and the ONR BRC grant on Randomized Numerical Linear Algebra. The authors would like to thank Beidi Chen for the helpful discussion on optimization. The authors would like to thank Lichen Zhang for valuable discussions about data-structures.

Review summaries:
The paper proposes a strategy to reduce the per-iteration cost of Frank-Wolfe, Herding and policy gradient methods. The algorithm is based on maximum inner product search (MIPS), equipped with proper projection and data transformations. These techniques transforms the problem into an ANN problem, where LSH is applied to achieve improved sublinear complexity. Theorems with rigorous statements on the improvement in complexity are provided on three algorithms, with clearly sketched proof to follow. Practical tricks using quantization and the utility-efficiency tradeoff is also discussed.

The paper formally proves the correctness and efficiency of using Locality Sensitive Hashing to reduce the runtime-per-iteration of Conditional Gradient based algorithms when the feasible space is the convex hull of $n$ points. Owing to this convex hull, finding the conditional gradient update vector at every iteration involves solving a Maximum Inner Product (MaxIP) problem: > Given a set $S$ of $n$ vectors (i.e. the convex hull) and a query vector $q$ (i.e. the gradient), find which vector in $S$ has maximum inner product with $q$. The paper approximately solves the MaxIP problem by transforming it to an Approximate Nearest Neighbors problem, which is solved black-box by Locality Sensitive Hashing problems. The paper then gives formal guarantees on convergence, showing that this approximation lets each iteration runs asymptotically faster while the total number of iterations needed is asymptotically unchanged.  Guarantees are specifically given for Frank-Wolfe, Herding, and Policy Gradient algorithms. The policy gradient algorithm is constrained to a Markov Decision Process where the states and actions are real vectors, and there exists a finite set of actions.

This paper focuses on the iterative conditional gradient methods and proposes a way to improve the per-iteration cost of such methods without significantly improving the number of iterations needed for convergence. The paper presents a way to pose the computational bottleneck in each iteration as a maximum inner product search (MaxIP) problem and leverages existing LSH-based approximate MaxIP schemes to theoretically improve the per-iteration cost while also quantifying the convergence rate of such a conditional gradient method that introduces approximation in each iteration. Specifically, the conditional gradient method involved in the Frank-Wolfe scheme, the kernel herding scheme and the Policy gradient scheme are studied.