Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structures
Authors: Zhaozhuo Xu
Zhao Song
Anshumali Shrivastava
Venue: NeurIPS 2021 Poster (2021)
Keywords: Locality Sensitive Hashing
Optimization

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.

Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structures
Zhaozhuo Xu Rice University zx220rice edu
Zhao Song Adobe Research
zsongdadobe.com com
Anshumali Shrivastava Rice University and ThirdAI Corp. anshumal Aamhumll@@rla 1i@rice......eeo edu
Abstract
Conditional gradient methods (CGM) are widely used in modern machine learn- ing. CGM's overall running time usually consists of two parts: the number of iterations and the cost of each iteration. Most efforts focus reducing the num- ber iterations as a means to reduce the overall running time. In this work, we focus improving the per iteration cost of CGM. The bottleneck step in most CGM maximum inner product search (MaxIP), which requires a linear scan over the parameters. In practice, approximate MaxIP data-structures are found be helpful heuristics. However, theoretically, nothing is known about the combi- nation of approximate MaxIP data-structures and CGM. In this work, answer this question positively by providing a formal framework to combine the locality sensitive hashing type approximate MaxlP 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-Wold Wolfe, Herding algorithm, and policy gradient.
Introduction
Conditional gradient methods (CGM), such Frank-Wolfe and its variants, are well-known opti- mization approaches that have been extensively used 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 large- scale machine learning models trained 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 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 each iteration. Reducing the number of iterations requires a better understanding of the geometric proprieties of the problem at hand and the invention 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-specie 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) 24].
MaxIP Data-structures for Iteration Cost Reduction: A well-known strategy in optimization,
with CGM, to perform greedy search over the weight vectors [9, 10, 13, 16, 25] or training
35th Conference on Neural Information Processing Systems (NcurIPS 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 ran- dom 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) 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 combi- nation 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?
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 MaxiP problem. Next, we propose 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.
Our Contributions:
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-Woo algorithm, Herding algorithm, and policy gradient method.
We propose a pair of efficient transformations that formulates the direction search in Frank- Wolfe algorithm 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-offss 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 data- structures 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 socictal impact and Section concludes the paper.
2 Related work
2.1 Maximum Inner Product Search for Machine Learning
Maximum Inner Product Search (MaxIP) is a fundamental problem with applications in machine learning. Given a query x E Rd and an n-vector dataset Y C Rdd MaxIP targets at searching for y E Y that maximizes the inner product æ The naive MaxIP solution takes O(dn) by comparing r with each y E Y. To accelerate this procedure, various algorithms are proposed 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 > 1 denote a parameter. Let P1.P2 E 1) denote two parameters and p1 > P2- We say a function family H. (r, T, P1. P1) (alPPP2ssssssse -ensitiiee if and only if. for any vectors I., y E R.d, for any h chosen uniformly random from H. we have:
if a - 2/12 S r, then Pra-H [h(z) h(y)] 2 P1.
if 1 = u|ا 2 r, then Pra-H [h(x) hyy) S p2-
Here 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 lg LSH and asymmetric transformations. After that, [34, 36, 35, 43] propose series of methods to solve MaxlP 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] 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 structrtuuttres for machine learning [52, 53, 54]. Following the paradigm, approximate MaxiP data-structures have been applied to overcome the effi- ciency bottleneck of various machine learning algorithms. [38] formulates the inference of 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 learnable LSH data-structure that further improves the inference efficiency with less energy consumption. In neural network training, [29, 30, 31] uses approximate MaxIP 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 retrieve the samples with large gradient norm and perform standard gradient descent, which improves the total running time for stochastic gradient descent. [32] proposes 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 (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.
2.2 Projection-free Optimization
Frank-Wolfe algorithm [25] is projection-free free optimization method with wide applications in con- vex [9, 10] and non-convex optimizations [11. 12]. The procedure 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 function Rd + RR over convex set S, starting from an initial weight wº, the Frank-Wolfe algorithm updates the weight with learning rate v) follows:
s f- arg min(s, Vg(w²)) sES
w 1+1 < (1 -p.) ) w² + 7/ 8
Previous literature focuses on reducing the number of iterations for Frank- Wolfe algorithm over specific domains such as E, balls [9, 10, 13, 14]. The cost reduction in the iterative procedure of Frank- Wolfe algorithm is hardly discussed except [57]. this work, we focus on the Trank-Wolft algorithm over the convex hull of 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].
3

---

3 Our Sublinear Iteration Cost Algorithm
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.
3.1 Preliminaries
We provide the notations and settings for this paper. We start with basic notations for this paper. For positive integer n, we use [n] to denote the set {1, .. (Ei=1 x²2)//2 denote its l norm.
,n). " For a vector z, we use ||||| ==
We say function is convex if
L(x) 2 L(y) + (VL(y), 3/-
We say function 3-smooth if
L(v) S L(x) (VL(x), 2) 3
x=12.
Given a set A= = (x:hie C Rd, we say its convex hull B(AA is the collection of all finite linear combinations y that satisfies y = Eiein as I4, where a; E [0, 1] for all E [n]] and Σiejo] a; 1. Let Dmax denote the maximum diameter of ((A) so that | yll2 S Dmax for all (x,, v) E B(A)- We present the detailed definitions in Appendix A.
Next, we present the settings of our work. Let S R.D. denote n-point finite set. Given a convex and 8-smooth function g Rd + I detined over the convex hull BSS). goal is to find w E BSS) that minimizes gwv). Given large n in the higher dimension, the dominant complexity of iteration cost lies in finding the MaxIP of Vg(w) with respect to S. In this setting, the fast learning rate of Frank- Wolfe in l balls [9. 13, 16] can not be achieved. We present the detailed problem setting of the Frank- Wolfe algorithm in Appendix C.
3.2 Our Results
We present our main results with comparison to the original algorithm Table 2. From the table, 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.
Statement
Preprocess
#lters
Cost per iter
Frank-Wolfe
0
O max /t)
Oldn + Tg)
Ours
Theorem 3.1
(n
O(dne + Tn)
Herding
[1]
0
O maxx /c)
O(dn)
Ours
Theorem 3,2
Io(()
O /c)
Oldne)
BD
Policy gradient
[5]
0
0 (
Oldn + TQ)
Ours
Theorem 3.3
dn!+o(1)
0(,2711 (,2(1-0)) "-- M
DD
Odne + TQ)
Table Comparison between classical algorithm and our sublinear time algorithm. We compare our algorithm with Frank-Wolfe in: (1) "Frank-Wolfs denotes Wolle algorithm [9] for convex functions over a convex hull. Let T, denote the time for evaluating the gradient for any parameter. (2) "Herding" denotes kernel Herding algorithm [1] (3) "Policy gradient" denotes the projection free policy gradient method [5]. Let To denote the time for evaluating the policy gradient for any parameter. Let Y (0, 1) denote the discount factor. Let Mmmin denote the minimum probability density of state. Note that is the number of possible parameters. n() is smaller than n for any constant e > 0. Let E (0, 1) denote a fixed parameter determined by LSH data-structure. The failure probability of our algorithm is 1/ (nly(n). / is the smoothness factor. Dmax denotes the maximum diameter of the convex hull.

---

Next, we introduce the statement of our sublinear iteration cost algorithms. We start by introducing our result for improving the running time of Frank- -olle..
Theorem 3.1 (Sublinear time Wolfe, informal of Theorem D.I), Let Rdd R denote a convex and 8-smooth function. Let the complexity of calculating Vg(z) to be Tg. Let S C IRd denote a set of n points. Let B C TRd denote the convex hull of S with maximum diameter Dmax- Let p E (0,1) denote a fixed parameter. For any parameters e, 6, there an iterative algorithm (Algorithm 2) that takes (dd2+o((1) time in pre-processing, lakes T O max//e)))) iterations and O(dn + TT) cost per iteration, starts from a random w" from B as its initialization point,and outputs w E TR.h from B such that
g(w")
min g(w) S, WEB
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 conditional gradi- ent 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 C Rd denote a feature set and c : Rd + IR denote mapping. Let Dmax denote the maximum diameter of (X') and B be the convex hull of (X)) Given a distribution p(z) over X, we denote μ Ez-pla) [ (x)). Let p E (0, 1) denote a fixed parameter. For any parameters e, 8, there is an iterative algorithu (Algorithm 3) that takes O(dn!+oUU) time in pre pre-processing. takes T ( iterations and (dd?) cost per iteration, starts from random w from B as its initialization point, and outputs w" E I2th from such that
1
2ll2
min WEB 1
ml13 Se,
SE
2
holds with probability at least 1/ poly(n).
Finally, we present result for policy gradient. Policy gradient [59] is popular algorithm with wide applications in robotics [60] and recommendation [61]. [5] proposes provable Frank-Wolfe method that maximizes the reward functions with policy gradient. However, the optimization quires a linear scan over all possible actions, which is unscalable complex environments. We propose an efficient Frank-Wolf algorithm with per iteration cost sublinear in the number of ac- tions. Our statement is presented below.
Theorem 3.3 (Sublinear time policy gradient, informal version of Theorem F.3). Let To denote the time for computing the policy graident. Let D max denote the maximum diameter of action space and 3 is a constant. Let 7 E (0, 1). Let p E (0, 1) denote a fixed parameter. Let P'mi denote the minimal density of states in S. There is an iterative algorithm (Algorithm 5) that spends O(dn' ++(()) time in 3D2
preprocessing, takes O 2(117) Pii
iterations and (dn + Tq) cost per iterations, starts from random point & as its initial point, and outputs wy that has the average gap VEves (8()) < holds with probability at least - poly(n),, where gr(() is defined Eq. (6).
4 Proof Overview
We present the overview of proofs in this section. We start with introducing the efficient MaxIP data- structures. Next, we show how to transform the direction search a conditional gradient approach into MaxIP problem. Finally, 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 presented in Appendix A. We use the reduetion-based approximate MaxIP method with LSH data-structure to achieve sublinear iteration cost. Note that we choose this method due to its clear
5

---

theoretical guarantee on the retrieval results. It 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, 70].
Definition 4.1 (Approximate Nearest Neighbor (ANN)). Let č > and r E (0.2) denote two pa- rameters. Given an n-vector set C &dd on a unit sphere, the objective of the (2, r) Apprrxximate Nearest Neighbor (ANN) to construct a data structure that, for any query x Sd-1 such that minyeY lly - x 22 S T, if returns vector 2 from Y that satisfies 2| 22 r.r.
In the iterative-typp optimization algorithm, the cost per iteration could be dominated by the Ap- proximate MaxIP problem (Definition 4.2), which is the dual problem of the r)-NNN.
Definition 4.2 (Approximate MaxIP), Let c E 10 and T E (0, 1) denote two parameters. Given an n-vector dataset Y gd-1 on a unil sphere, the objective of the (c, T-MMalP to construct data structure that, given a query E gd-1 such that maxyEY (a, y) 2 T, it retrieves a vector from Y that satisfies (z, 2) 2 c. maXyEY (z,
Next, we present the the primal-dual connection between ANN and approximate MaxIP. Given to unit vectors 2, E Isd with both norm equal to 1, x y = 2 (zz, v)- Therefore, we could maximizing (ar, y) by minimizing || y/3- Based on this connection, we present how to solve 7-ax) using (c, r-ANNN We start with showing how to solve (c. r>N-NN with LSH.
Theorem 4.3 (Andoni, Laarhoven, Razenshteyn and Waingarten [67]). Let c > 1 and r E (0,2) denote two parameters. One can solve (c, r--ANN on unit sphere in query time O(d n²) using preprocessing time Odn (d()))(l)) and space
dn), where p
+ o())
Next, we solve (c, MMaxlP by solving (2, r)NNNN using Theorem 4.3. We have
Corollary 4.4 (An informal statement of Corollary B.1). Let c E (0, 1) and t E (0, 1) denote two parameters. One can solve (c, MaxxlP on a unit sphere S in query time O(d n²), where P DE (0, 1), using LSH with both preprocessing time and space in (dd)))(l))
In our work, consider generalized form of approximate MaxIP, denoted projected approxi- mate MaxIP.
Definition 4.5 (Projected approximate MaxIP), Let o, Rd + IR* denote two transforms. Given an n-vector dataset Y c. IR' so that (YY) C Sk-1, the goal of the o, -ax)l is to construct a data structure that, given a query x E IRd and 6(x) E sk-1 such that max,ey (ø(x), (vy) 2 T, it retrieves vector z E Y that satisfies (ő(z), (b(2) c (ò, -a) Y).
For details 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.
4.2 Efficient Transformations
We have learned from Section 4.1 that (c, 7Mxxl on unit sphere Sd-1 using LSH for ANN. Therefore, the next step to transform the direction search procedure in iterative optimization al- gorithm into a MaxlP on unit sphere. To achieve this, we formulate the direction search projected approximate MaxIP (see Definition A.5). We start with presenting a pair of transforma- tion Φu, to Rdd + dd+ such that, given function g Rd - R, for any x. y in a convex set K,, have
20(x) =VV](()] Vg(a))] vo(v) =
In this way, we show that
y z. Vg(x)) (0o(z), vo(o)))
arg min (y z, Vg(x)) = arg max @o (I), vo(y)) yEY
(2)
Therefore, we could transform the direction search problem into MaxIP problem.

---

Next, we present standard transformations [36] that connects the MaxIP to ANN in unit sphere.
For any z, y E R2, we propose transformation Φ1, 2/ R + R such that
Φ1 (z) (DI
o V1 -1-1 1
1 (v) (TT
V1 V1- 11-llyDy'1 '13 0]
Here De. Dy are some constant that make sure both x z/D, and y/ y/Dy have norms less than 1. Under these transformations, both @1 (x) and 1/1 (ÿ) have norm 1 and arg maXgeY (01 (x), 1/1 arg y (zz y).
Combining transformations in Eq. (1) and Eq. (3), we obtain query transform Φ IR R2+3 with form ((x) = Φ (z)(z)) and data transform @ Rd + Rd43 with form (by) w (v)())). Using and 3 we transform the direction search problem
optimization into a MaxIP in unit sphere. Moreover, given a set Y C Rd and query x E IRd, the solution z of (c, o, v,, r>-MaxIP over (r, Y) has the propriety that (z x, Vg(z)) S c minyey (y - x, Vy(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 is convex, given a set 5 C Rdd, we have min (Vg(z)) s z) I 0 for any x E BSS), where B is the convex hull of S. Thus, mY (0o(z), (y)) is non-negative following Eq. (2).
4.3 Proof of Theorem 3.1
We present the proof sketch for Theorem 3.1 in this section. We refer the readers to Appendix D for the detailed proofs.
Let Rdd - IR denote convex and f-smooth function. Let the complexity of calculating Vg(x) to be Ty Let S C Rd denote a set of n points, and B C Rd be the convex hull of S with max- imum diameter Dmax- Let Φ, vh RRd + Rd+3 denote the tranformations defined in Section 4.2. Starting from a random vector wD B(S). Our sublinear Frank-Wolfe algorithm follows the update following rule that each step
+ (c, Φ, wh MaxlP of w with respect to S
w +1 -- w² (s" w²)
We start with the upper bounding (s" wt, Vg(w")). Because st is the (c, 16, Max of w with respect to S, we have
(s w', Vg(w")) & emin wi, Vg(w") I o/w" w', Vg(w"))
(4)
sES
For convenient of the proof, for each t, we define h, g(w") g(w"). Next, we upper bound h441
as
-/2 ni I|s f w 1122 g(w")
8
h Sg(w") n666 w', Vg(w"))
B
$ so(w") + -ni(ww w Vg(w")) + ne
11lss - w'll g(w")
BD max
S g(w') + cn (w" x w', Vg(w")) +
t g(w")
2
3D2
$ (1 (1)g(w²) + +cng(w")
max
n g(w")
2
3D2 mnxx 2
(1 cn +
2
(5)
where the first step follows from the definition of 3-smoothness, the second step follows from Eq. (4), the third step follows from the definition of Dmaxs the forth step follows from the con- vexity of g.
7

---

2 and A, 11012 Combining them with (5) we show that Let c(142]
A44 A,h, =2
t+2 3D max
< 230 max
Using induction from to show that
Aghe < c 21BD2 max
((f++1) Taken A, 2
into consideration, have
23D max h4 (t +1)
Given constant approximation ratio c, t should be in 0 (DD so that h, S Thus, complete the proof.
Cost Per Iteration After take O(dn++a()) preprocessing time, the cost per iteration consists three pairs: (1) it takes Tg to compute Vg(w"), (2) it takes ( to perform transform á and s/. (3) takes (ddn) retrieve 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 ! 1 n1.. We show that this function g is convex and 1-smooth function. Therefore, the Herding algorithm is equivalent to the Frank- show that it takes T D iterations and (dn?) cost iteration to reach the e-optimal solution. Similar to Theorem 3.1, we show that the cost per iteration would be (dn?) as it takes (cd) to compute Vg(w").
Algorithm over function Using
the proof of Theorem 3.1 with 3
4.4 Proof of Theorem 3.3
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). this setting, we are provided with state S E R* and action space A E RRd. However, at each step E N, we could only access finite n-vector set of actions C(s) C A. Let us assume the C(s) remains the same in each step. Let denote Dmax the maximum diameter A.
When you play with this ACMDP, the policy you choose is defined as (s) S A with parameter Meanwhile, there exists a reward function r : x A E []. Then, we define the Q function as below,
OC Σ t=
Q(s, ()))
E
Ar(s,, =s a, na
where 7 E (0, 1) is discount factor.
Given a state distribution μ. the objective policy gradient is to maximize J(p ng) =
Eevp,awm (Q(ssa/Te)) via policy gradient [59] denoted as:
VeJ
E soudy
[5] propose an iterative algorithm that perform MaxIP at each iteration k over actions to find
g (s) = max (a - (s), VaQ(s, (5) (z) aEC(s)
(6)
In this work, we approximate Eq. (6) using (c, d, th 7) MaxiP.. Here define o: S x Rd - dd+1
and si R + Rd+1 as follows:
m = V.Q(s, (t) (+)) (Tt) Q(x, (s)) (((a) = [aT, -

---

Then, we have 9& (s) (6(s,T)) v(a)). Note that we still require transformations in Eq. (3) to generate unit vectors.
Next, we show that if we retrieve an action a using (c, o, 1/, -)-MP the gap Tu (s) would be lower bounded by
(x) = (a= T)))), V Vo 2 cgK(8)
(7)
Combining Eq. (7) the standard induction in [5]. we upper bound ESEs (r(s)²
as
2,3 max
(or S T+1 -
(8)
SES
where Mmin denotes the minimal density of sates in S and 3 is the smoothness factor.
In this way, given a constant factor c, if we would like minimize the gap Eees 9r (s)2 2
should be O (1(1-))'m Piin
AD2 max
Cost Per Iteration After take O(d))+ preprocessing time, the cost per iteration consists three pairs: (1) it takes To to compute policy gradient, (2) it takes ((d) to perform transform ø and sb (3) takes ((dn") to retrieve actions from LSH. Thus, the final cost per iteration would be
O(d + TQ).
4.5 Quantization for Adaptive Queries
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 pendent. 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.
each iteration is inde-
This work uses 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 the Voronoi diagrams. In this way, each query is located into cell with center vector. Next, we perform a query using the center vector the cell. Therefore, the failure probability of the MaxIP query sequence is equivalent the probability that any center vector in the cell fails to retrieve its approximate MaxlP solution. As the centers of cells are independent, we could union bound this probability. On the other hand, the maximum diameter of the cell is X, this query quantization would introduce a additive error in the inner product retrieved. We refer the readers Appendix for the detailed quantization approach.
4.6 Optimizing Accuracy-Efficieng Trade-off
In this work, we show that by LSH based MaxIP data-structure, the cost for direction search is (dn?), where p E (0, 1). In Section D.2 of the supplementary material, show that is function constant c and parameter 7 in approximate MaxIP (see Definition 4.2). Moreover, we also show in Section D.2 that LSH results in only 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 e-optimal solution, LSH could achieve acceleration in the overall running time. Therefore, we could set and T parameters to balance the accuracy-efficiency trade- off of CGM to achieve the desired running time.
Potential Negative Societal Impact
This paper discusses the theoretical foundation of data-structures for conditional gradient methods. We believe that this paper does not have negative societal impact the environment, privacy, and other domains.

---

Concluding Remarks
In this work, we present the first Frank-Wolff algorithms that achieve sublinear linear time cost per iteration. We also extend this result into Herding algorithm and policy gradient methods. We for- mulate the direction search in Prank-Wold algorithm as a projected approximate maximum inner product search problem with pair of efficient transformations. Then, we use locality sensitive hash- ing cata-structure to reduce the iteration cost into sublinear over the number of possible parameters. Our theoretical analysis shows that the sublinear iteration cost Frank-Wolfs algorithm preserves the same order in 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 sub- linear total running time. Furthermore, we identify the problems 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 future study on sublinear iteration cost algorithms for optimization.
Acknowledgements
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 thank Lichen Zhang for valuable discussions about data-structures.
References
[1] Francis Bach, Simon Lacoste-Julien, and Guillaume Obozinski. On the equivalence between herding and conditional gradient algorithms. arXiv preprint arXiv:1203.4523 2012.
[2] Paxton Turner, Jingbo Liu, and Philippe Rigollet. A statistical perspective coreset density estimation. In International Conference on Artificial Intelligence and Statistics (AISTATS), pages 2512-2520. 2021.
[3] Simon Lacoste-Julien, Martin Jaggi, Mark Schmidt, and Patrick Pletscher. Block-coordinate fralk-wolfe optimization for structural svms. In International Conference on Machine Learn- ing (ICML), pages 53-61, 2013.
[4] Robert M Freund, Paul Grigas, and Rahul Mazumder. extended frank-wolfe method with "in-face" directions, and its application to low-rank matrix completion. SIAM Journal on optimization, 27(1):319-346, 2017.
[5] Jyun-Li Lin, Wei Hung, Shang- Hsuan Yang. Ping-Chun Hsieh, and Xi Liu. Escaping from zero gradient: Revisiting conttnnconstrained reinforcement learning via frank-wolfe policy op- timization. Proceedings of the Thirty-Sevent Conference on Uncertainty in Artificial Intelli- gence (UAI), 2021.
[6] Elad Hazan and Satyen Kale. Projection free online learning. In 29th International Conference on Machine Learning, ICMI. 2012, pages 521-528, 2012.
[7] Jacob Devlin, Ming-Wes Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1880.044: 2018.
[8] Tom B Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, al. Language models are few-shot learners. arXiv preprint 1,015:20005.11155, 2020.
2020.
[9] Martin Jaggi. Revisiting frank-wolfe: Projection-free sparse convex optimization. In Interna- tional Conference on Machine Learning (ICML), pages 427-435 2013.
[10] Dan Garber and Elad Hazan. Faster rates for the frank-wolfe method over strongly-convex sets. In International Conference Machine Learning (ICMIJ, pages 541-549, 2015.
10

---

[11] Sashank Reddi, Suvrit Sra. Barnabás Póczos, and Alex Smola. Stochastic wolke meth- ods for nonconvex optimization. In 2016 54th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 1244-1251. IEEF, 2016.
[12] Sashank J Reddi, Ahmed Hefny, Suvrit Sra, Barnabas Poczos, and Alex Smola. Stochastic variance reduction for nonconvex optimization. International conference on machine learn- ing (ICML), pages 314-323, 2016.
[13] Zeyuan Allen-Zhu, Elad Hazan, Wei Hu, and Yuanzhi Li. Linear convergence of frank-wolfe type algorithm over trace-norm balls. In NIPS, 2017.
[14) Qi Lei, Jiacheng Zhuo, Constantine Caramanis, Inderjit S Dhillon, and Alexandros G Dimakis. Primal-dual block generalized frank-wolfe. Advances in Neural Information Processing Sys- tems (NewrIPS), 12:11866-11 1111663666775 2019.
[15] Ruosong Wang, Peilin Zhong, Simon S Du, Russ R Salakhutdinov, and Lin F Yang. Planning with general objective functions: Going beyond total rewards. In Annual Conference on Neural Information Processing Systems, 2020.
[16] Yin Tat Lee, Zhao Song, and Qiuyi Zhang, Solving empirical risk minimization in the current matrix multiplication time. COLT. attps:///ariie org/ /ptp//df//// 1905. 04447, 2019.
[17] Shunhua Jiang, Zhao Song, Omri Weinstein, and Hengjie Zhang. Faster dynamic matrix in- verse for faster lps. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC). arxiv preprint arXiv:2004.07470, 2021.
[18] Zhao Song and Zheng Yu. Oblivious sketching-based central path method for solving linear programming problems. In 38th International Conference Machine Learning (ICML), 2021.
[19] Jan den Brand, Binghui Peng, Zhao Song, and Omri Weinstein. Training (over- parametrized) neural networks in near-linear time. In 12th Innovations in Theoretical Com- puter Science Conference (ITCS), 2021.
[20] Michael B Cohen, Yin Tat Lee, and Zhao Song. Solving linear programs in the current matrix multiplication time. In STOC, 2019.
[21] Jan van den Brand, Yin Tat Lee, Aaron Sidford, and Zhao Song. Solving tall dense linear programs nearly linear time. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 775-788, 2020.
[22] Sally Dong, Yin Tat Lee, and Guanghao Ye. A nearly- linear time algorithm for linear programs with small treewidth: A multiscale representation of robust central path. In Proceedings of the 53rd Annual ACM SIGACT Symposium Theory of Computing (STOC). arXiv preprint
arXiv:201 1.05365, 2021.
[23] Jan van den Brand. A deterministic linear program solver in current matrix multiplication time. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium Discrete Algorithms (SODA), pages 259-278. SIAM, 2020.
[24] Jan van den Brand, Yin- Tat Lee, Danupon Nanongkai, Richard Peng. Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang. Bipartite matching in nearly-linear time on mod- erately dense graphs. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 919-930. IEEE, 2020.
[25] Marguerite Frank, Philip Wolfe, et al. An algorithm for quadratic programming. Naval re- search logistics quarterly, 3(1- 3(1-2):95-100, 1956.
[26] Weiyang Liu, Bo Dai, Ahmad Humayun, Charlene Tay, Chen Yu, Linda B Smith, James M Rehg, and Le Song. Iterative machine teaching. In International Conference on Machine Learning, pages 2149-2158 PMLR, 2017.
[27] Weiyang Liu, Bo Dai, Xingguo Li, Zhen Liu, James Rehg, and Le Song. Towards black-box iterative machine teaching. In International Conference on Machine Learning, pages 3141- 3149. PMLR, 2018
11

---

[28] Beidi Chen, Yingchen Xu, and Anshumali Shrivastava. Fast and accurate stochastic gradi- ent estimation. In H. Wallach, H. Larochelle, A. Beygelzimer, d'Alché-Buce E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems (NeurIPS), 2019.
[29] Beidi Chen, Tharun Medini, James Farwell, sameh gobriel. Charlie Tai, and Anshumali Shri- vastava. Slide: In defense of smart algorithms over hardware acceleration for large-scale deep learning systems. In I. Dhillon, D. Papailiopoulos, and V. Sze, editors, Proceedings of Machine Learning and Systems, pages 291-306, 2020.
[30] Beidi Chen, Zichang Liu, Binghui Peng, Zhaozhuo Xu, Jonathan Lingjie Li, Tri Dao, Zhao Song, Anshumali Shrivastava, and Christopher Re. MONGOOSE: A learnable LSH framework for efficient neural network training. In International Conference on Learning Representations (ICLR), 2021.
[31] Shabnam Daghaghi, Nicholas Meisburger, Mengnan Zhao, and Anshumali Shrivastava. Accel- erating slide deep learning on modern cpus: Vectorization, quantizations, memory optimiza- tions, and more. Proceedings of Machine Learning and Systems, 3, 2021.
[32] Zhaozhuo Xu, Beidi Chen, Chaojian Li, Weiyang Liu, Le Song, Yingyan Lin, and Anshumali Shrivastava. Locality sensitive teaching. Advances in Neural Information Processing Systems, 2021.
[33] Anshumali Shrivastava and Ping Li. Asymmetric Ish (alsh) for sublinear time maximum inner product search (mips). Advances in Neural Information Processing Systems (NIPS), pages 2321-2329, 2014.
[34] Anshumali Shrivastava and Ping Li. Improved asymmetric locality sensitive hashing (alsh) for maximum inner product search (mips). In Proceedings of the Thirty-First Conference on Uncertainty in Artificial Intelligence (UAI), pages 812-821, 2015.
[35] Anshumali Shrivastava and Ping Li. Asymmetric minwise hashing for indexing binary inner products and set containment. In Proceedings of the 24th international conference on world wide web (WWW), pages 981-991, 2015.
[36] Behnam Neyshabur and Nathan Srebro. On symmetric and asymmetric Ishs for inner product search. In International Conference on Machine Learning (ICML), pages 1926-1934, PMLR, 2015.
[37] Ruiqi Guo, Sanjiv Kumar, Krzysztof Choromanski, and David Simcha. Quantization based fast inner product search. In Artificial Intelligence and Statistics (AISTATS), pages 482-490. PMLR, 2016.
[38] Hsiang-Fu Yu, Cho-Jui Hsieh, Qi Lei, and Inderjit Dhillon. A greedy approach for budgeted maximum inner product search. In Proceedings of the 31st International Conference on Neural Information Processing Systems (NIPS), pages 5459-5463 2017.
[39] Stanislav Morozov and Artem Babenko. Non-metric similarity graphs for maximum inner product search. Advances in Neural Information Processing Systems (NeurIPS), 31:4721- 4730, 2018
[40] Zhixin Zhou, Shulong Tan, Zhaozhuo Xu, and Ping Li. Möbius transformation for fast inner product search on graph. Advances in Neural Information Processing Systems (NeurIPS), 32, 2019.
[41] Shulong Tan, Zhixin Zhou, Zhaozhuo Xu, and Ping Li. On efficient retrieval of top similar- ity vectors. Proceedings of the 2019 Conference on Empirical Methods in Natural Lan- guage Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pages
2019.
[42] Ruiqi Guo, Philip Sun, Erik Lindgren, Quan Geng, David Simcha, Felix Chern, and Sanjiv Ku- mar. Accelerating large-scale inference with anisotropic vector quantization. In International Conference Machine Learning (ICML), pages 3887-3896. PMLR, 2020.
12

---

[43] Xiao Yan, Jinfeng Li, Xinyan Dai, Hongzhi Chen, and James Cheng. Norm fomm-ranging Ish for maximum inner product search. Advances in Neural Information Processing Systems (NeurIPS), 31:2952-2999 2018.
[44] Qin Ding, Hsiang-Fu Yu, and Cho-Jui Hsieh. A fast sampling algorithm for maximum inner product search. In The 22nd International Conference on Artificial Intelligence and Statistics (AISTATS), pages 3004-3012. PMLR. 2019.
[45] Minjia Zhang, Xiaodong Liu, Wenhan Wang, Jianfeng Gao, and Yuxiong He. Navigating with graph representations for fast and scalable decoding of neural language models. arXiv preprint 1rX.v:1806.04/88 2018.
[46] Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality. In Proceedings of the thirtieth annual ACM symposium on Theory of com- puting (STOC), pages 604 613, 1998.
[47] Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S Mirrokni. Locality-sensitive hashing scheme based p-stable distributions. In Proceedings of the twentieth annual symposium Computational geometry (SoCG), pages 253-262, 2004.
[48] Moses Charikar. Similarity estimation techniques from rounding algorithms. In Proceedings of the thiry-fourth annual ACM symposium Theorr of computing, pages 380-388, 2002.
[49] Xiaoyun Li and Ping Li. Random projections with asymmetric quantization. Advances in Neural Information Processing Systems, 32: 12:10838-10867, 2019.
[50] Ping Li, Xiaoyun Li, and Cun Hui Zhang. Re-randomized densification for one permutation hashing and bin-wise consistent weighted sampling. Advances Neural Information Process- ing Systems, 32, 2019.
[51] Xiaoyun Li and Ping Li. Rejection sampling for weighted jaccard similarity revisited. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 2021.
[52] Arturs Backurs, Piotr Indyk, and Tal Wagner. Space and time efficient kernel density estimation in high dimensions. NeurIPS, 2019.
[53] Amir Zandieh, Navid Nouri, Ameya Velingker, Michael Kapralov, and Ilya Razenshteyn. Scal- ing up kernel ridge regression via locality sensitive hashing. In International Conference on Artificial Intelligence and Statisties, pages 4088 0088-499. PMLR, 2020.
[54] Arturs Backurs, Yihe Dong, Piotr Indyk, Ilya Razenshteyn, and Tal Wagner. Scalable nearest neighbor search for optimal transport. In International Conference Machine Learning, pages 497-506. PMLR, 2020.
[55] Zichang Liu, Zhaozhuo Xu, Alan Ji, Jonathan Li, Beidi Chen, and Anshumali Shrivastava. Climbing the wol: Training for cheaper inference. arXiv preprint arXiv:2007.012388 2020.
[56] Shuo Yang. Tongzheng Ren, Sanjay Shakkottai, Eric Price, Inderjit S Dhillon, and Su- jay Sanghavi. Linear bandit algorithms with sublinear time complexity. arXiv preprint arXiv:2103.02729, 2021.
[57] Francesco Locatello, Rajiv Khanna, Michael Tschannen, and Martin Jaggi. A unified opti- mization view on generalized matching pursuit and wolfe- In Artificial Intelligence and Statistics (AISTATS), pages 860-868, 2017.
[58] Yutian Chen, Max Welling, and Alex Smola. Super-samples from kernel herding. arXiv preprint arXiv: /203. 2012.
[59] David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra. and Martin Ried- miller. Deterministic policy gradient algorithms. In International conference on machine learning (ICML). pages 387-395 2014.
(60] Jan Peters and Stefan Schaal. Policy gradient methods for robotics. In 2006 IEFF/RSJ Inter- national Conference on Intelligent Robots and Systems, pages 2219-2225. IEEE, 2006.
13

---

[61] Haokun Chen, Xinyi Dai, Han Cai, Weinan Zhang, Xuejian Wang, Ruiming Tang, Yuzhou Zhang, and Yong Yu. Large-scale interactive recommendation with tree-structured policy gra- dient. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 3312-3320, 2019.
[62] Sunil Arya and David M Mount. Approximate nearest neighbor queries in fixed dimensions. In SODA, volume 93, pages 271-280. Citeseer, 1993.
[63] Alexandr Andoni, Piotr Indyk, Huy L Nguyen, and Ilya Razenshteyn. Beyond locality- sensitive hashing. In Proceedings of the /wenty-fisth annual ACM-SIAM symposium on Discrete algorithms, pages 1018-1028. SIAM, 2014.
[64] Alexandr Andoni, Piotr Indyk, TMM Laarhoven, Ilya Razenshteyn, and Ludwig Schmidt. Practical and optimal Ish for angular distance. In Advances in Neural Information Process- ing Systems (NIPS), pages 1225-1233. Curran Associates, 2015.
[65] Alexandr Andoni and Ilya Razenshteyn. Optimal data-dependent hashing for approximate near neighbors. In Proceedings of the forty-seventh annual ACM symposium Theory of computing (STOC), pages 793-801, 2015.
[66] Piotr Indyk and Tal Wagner. Approximate nearest neighbors in limited space. In Conference PMLR, 2018.
On Learning Theory, pages
[67] Alexandr Andoni, Thijs Laarhoven, Ilya Razenshteyn, and Erik Waingarten. Optimal hashing- based time-space trade-offs for approximate near neighbors. In Proceedings of the Twenty- Eighth Annual ACM-SIAM Symposium on Discrete Algorithmss (SODA), pages 47-66. SIAM, 2017.
[68] Alexandr Andoni, Piotr Indyk, and Ilya Razenshteyn. Approximate nearest neighbor search in high dimensions. arXiv preprint arXiv: 1806. 7, 2018.
[69] Yihe Dong, Piotr Indyk, Ilya Razenshteyn, and Tal Wagner. Learning space partitions for nearest neighbor search. In International Conference Learning Representations, 2019.
[70] Hao Chen, Ilaria Chillotti, Yihe Dong, Oxana Poburinnaya, Ilya Razenshteyn, and M Sadegh Riazi. (SANNS}: Scaling up secure approximate k-nearest neighbors search. In 29th
[USENIX) Security Symposium (LUSENIX) Security 20), pages 21 2111-2128, 2020.
[71] Jerry D Gibson and Khalid Sayood. Lattice quantization. Advances in electronics and electron physics, 72:259-330, 1988.
[72] William B Johnson and Joram Lindenstrauss. Extensions of lipschitz mappings into hilbert space. Contemporary mathematics, 26(189-206):1, 1984.
[73] Lijie Chen. On the hardness of approximate and exact (bichromatic) maximum inner product. In 33rd Computational Complexity Conference (CCC), 2018.
[74] Anshumali Shrivastava, Zhao Song, and Zhaozhuo Xu. Sublinear least- equares value iteration via locality sensitive hashing, arXiv preprint arXiv:2105.08285, 2021.
14


Reviews:
[{"review_id": "cCjbL36SLU-", "reviewer": "Reviewer_UDJZ", "summary": "The authors demonstrate a theoretical analysis for conditional gradient methods with sublinear per iteration complexity. Extension to Frank-Wolfe algorithm, Herding algorithm, and policy gradient methods are also provided with the same argument.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The proposed analysis for CGM in terms of the per iteration time complexity is first type (as the authors claim) of such result that can be applied to related problems (e.g., Frank-Wolfe algorithm as shown in the paper). This is an interesting and also important result, which can help further help quantify the overall time complexity for related algorithms as most existing theoretical efforts were about the outer loop complexity. \n\nThe proposed analysis is based on transformation of direction search into a projected approximate maximum inner product search problem, with the asymptotic behavior of the same order in the iteration complexity towards convergence for the proposed sublinear Frank-Wolfe algorithm, which is an interesting approach and can be extended in the analysis of related problems.\n\nThe paper is relatively easy to follow and clearly presented. The presented proof sketch is mostly clear and seems correct, though I did not check all detailed analysis for the proof. Overall, I think the paper overall shows an interesting result.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "XuFaVXCaOru", "reviewer": "Reviewer_krev", "summary": "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:\n> 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$.\nThe 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.\n\nGuarantees 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.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Overall Impression\n\nThe paper is fine. It delivers on an interesting direction of improvement, but needs some clarity fixes.\n\nNotably, this paper is also further from my area of expertise than I originally expected.\n\n### Detailed Review\n\nThe paper also is ***littered*** with minor typographical and grammatical errors after the introduction. While this is not grounds for rejection, this was extraordinarily frustrating to read, and the authors should be sure to properly proofread their writing. After the introduction, I found about 8 paragraphs *without* at least one such typo. A full list of typos I found in the first 200 lines is at the end of this review.\n\nThe paper has a clear goal: theoretically analyze how LSH can speedup conditional gradient methods. The restricted setting of convex hulls of a finite set of vectors seems reasonable and interesting. The proofs seems simple and approachable. The guarantees as stated in Section 3.2 lack some clarity (details later), but are overall interesting and appear to be an improvement.\n\nThe significance of this paper is hard for me to comment on, as I am not particularly well versed in the Conditional Gradient literature. Taking the introduction as gospel, it seems publication-worthy to provide the first sublinear-in-$n$ runtime-per-iteration Frank Wolfe algorithm.\n\nI have a couple clarity questions on the main results, as stated in Section 3.2:\n\n- The role of $\\rho$ is unclear:\n    - Does the user set LSH parameter $\\rho$ or is it defined by other parameters? I understood it to be user-set, but this is not clear to me. If it is not user set, then you should state it's rate, so we can better interpret the $O(dn^\\rho)$ runtime. *i.e. Just how sublinear is this setting?*\n        - [Line 159] The description in Table 1 makes $\\rho$ sound defined by other parameters.\n        - [Line 164] makes $\\rho$ sound user-set.\n        - [Line 788 of the appendix] makes $\\rho$ sound defined by other parameters, and further that $\\rho \\approx 2\\frac{(1-\\tau)^2}{(1-c\\tau)^2} + o(1)$, where $\\tau$ depends on the vectors in $S$ and $c$ is the approximation quality in LSH. The dependence of $o(1)$ is also unclear here; does it depend on $n$ or $\\tau$ or $c$? Is $\\rho<1$ always, or just asymptotically?\n    - If $\\rho$ is user-set, the cost of making $\\rho$ small should be stated. If the per-iteration-cost of your algorithm is $O(dn^\\rho)$ for user-fixed parameter $\\rho\\in(0,1)$, why not make $\\rho$ arbitrarily small? Glancing at citation [66], I believe the answer lies in both the space complexity and preprocessing time?\n\nI have one last technical question:\n- [Line 249] In Section 4.2, what is meant by $D_x$ being the diameter of vector $x$? Is this different from the norm of $x$? If so, where is this defined? If not, why not use the norm symbol instead?\n\n---\n\n### The long list of typos\n\nRemember, this is just the first 200 lines of the 350 line paper.\n\n1. [Line 78] Should be \"**concludes** the paper\"\n1. [Line 92] Should be \"any two **points**\"\"\n1. [Line 92] I recommend writing \"uniformly at random from $H$\", but it's not vital\n1. [Line 96] Should be \"first **shows** that\"\n1. [Lines 100, 102] Should be \"directly\" not \"direct\"\n1. [Line 107] Should be \"networks\" not \"network\"\n1. [Line 108] Confusion between singular vs. plural in the sentence starting with \"In same task\"\n1. [Line 108] Should be \"In the same task\" not \"In same task\"\n1. [Line 111] Should be \"updates\" not \"update\"\n1. [Line 115] The sentence starting with \"In bandit problem\" is broken. I'm 100% sure what it's trying to say.\n1. [Line 126] Replace the period after \"maximum inner product\" with a comma\n1. [Line 128] Should be \"updates\" not \"performs update\"\n1. [Line 138] Should be \"iteration\" not \"iterations\"\n1. [Lines 149, 162, 164, 177, 188, 189, 190, 191] Should be \"denote\" not \"denotes\"\n1. [Line 150] Should be one sentence with a comma instead of a period.\n1. [Line 153] Should be \"cannot\" not \"could not\"\n1. [Line 153-154] Broken sentence.\n1. [Line 158] \"iteration to be sublinear\" not \"iteration to sublinear\"\n1. [Line 159: Table 1 Description] Should be \"denote\" not \"denotes\" after both $T_g$ and $\\gamma$. Should be \"$T_Q$ denotes the time\" not \"$T_Q$ the time\". Should be \"convex\" not \"coonvex\".\n1. [Line 164] \"be the convex hull of $S$\" not \"is the convex hull of $S$\"\n1. [Line 166] \"with that takes\" should be \"that takes\"\n1. [Line 167] should be \"as its initialization point, and\" not \"as initialization point,and\"\n1. [Line 170] \"The Herding Algorithm\" not \"Herding algorithm\"\n1. [Line 179] \"as its initialization point\" not \"as initialization point\"\n1. [Line 193] should be \"iteration, starts from a random pint $\\pi_\\theta^0$ as its initial point, and outputs $\\pi_\\theta^T$ that has average gap\"\n1. [Line 198] \"into a MaxIP\" not \"as a MaxIP\"\n1. [Line 199] \"detailed proofs are\" not \"detailed proof is\"\n\nCounting repeated errors, that's about one typo every 5 or 6 lines, which is biased by the first 70 lines being typo-free. After section 1, it's about one typo every 3 or 4 lines. This typo rate continues through the end of the paper.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors do not seem to directly discuss the limitations of their work anywhere.\n\nSocietal Impact: Not Applicable", "review_text": "", "extra_scores": {"ethical_concerns": "Not Applicable", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "GTStmAJq0D", "reviewer": "Reviewer_QnkL", "summary": "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.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is clearly presented and organized and is easy to follow. The theoretical results are solid and novel. The paper discusses three algorithms, which would be interesting to audiences from different communities. The theoretical contribution of this work is strong. The main result that applying LSH leads to reduced complexity but same convergence rate is also very interesting to me.\n\nLSH is an useful tool that can be used in many aspects of computer science. I think it is a good paper presenting an novel and effective application of LSH to Frank-Wolfe type optimization methods. This could lead to more meaningful works in this direction.\n\nDetailed comments:\n\n1) I notice that the rates in Table 2, 3, 4 in the Appendix have two more constants $c$ and $\\kappa$. They are determined by what factors? Also, what is $\\rho$ commonly in practice? \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "9IGB9f8sC2q", "reviewer": "Reviewer_Tjo5", "summary": "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.\n", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Positives:\n\nThe paper clear presents the research questions being focused on. These questions are of high importance since they address the efficiency of widely used optimization algorithms such as Frank-Wolfe and Policy Gradient. The authors leverage the existing theoretical guarantees for LSH-based MaxIP solutions to provide concrete computational gains from leveraging approximate MaxIP for direction search problem in these optimization algorithms.\n\nThe idea of posing the direction search in conditional gradient methods as a MaxIP problem by leveraging properties of a convex hull is a very interesting way of looking at this problem that allows us to leverage the efficient solutions for approximate MaxIP.\n\n## Issues/concerns:\n\n### Clarity and notational consistency/main vs. supplemental\n\nThe paper in its current version has a lot of notational issues and many parts are not clear or very incomplete in the main paper. Beyond proofs and such, it seems like various crucial information regarding problem setup and notation and algorithms have been placed in the supplement and it is hard to judge the significance of the contribution in the current form of the main paper. I needed the supplementary material to even understand the problem setup and the main contributions. Here are some specific examples:\n\n- The theorem statements are not very well presented with some of the crucial parts of the theorems in the supplement or in other parts of the paper, which often leaves the theorems ill-stated.\n- In my opinion, more important to have the Algorithms 1-3 in the main paper than the proof sketch.\n- Table 1 says $n$ is the number of parameters while lines 145 and line 149 use $n$ to describe number of points in the set $A$ or $S$ over whose convex hull $\\mathcal{B}(S)$ we are optimizing? This is confusing -- my assumption was that the number of parameters is $d$ since $S \\subset \\mathbb{R}^d$ and $w \\in \\mathcal{B}(S)$\n- Theorem 3.2 appears mis-stated since $w^T \\in \\mathbb{R}^d$ while $\\mu \\in \\mathbb{R}^k$ and hence the bound is meaningless without definitions of the l2-norm.\n- In Theorem 3.3, what is $D_\\max$ over action space for discrete action spaces -- in case of continuous action spaces, noone uses linear scan over action spaces ...\n- In Def 4.5, again notional issues where the inner-product is being computed between vectors of different dimensionalities ($d$ vs $k$).\n- The direction search described after line 128 appears to be over a convex set $S$ while the search defined in (2) is a direction search but does not ensure anything about the direction being in some convex set -- the mapping of notations and terms is not clear.\n- The definition of \"maximum diameters $D_x$ and $D_y$\" are not clear and needs to be corrected/clarified. These quantities should be independent of specific $y$ or else the parity is not true.\n- There is no $x,y \\in \\mathbb{R}^d$ used in line 306 -- we care about $s \\in \\mathbb{R}^k$ and $a \\in \\mathbb{R}^d$.\n\n\n### Motivation for problem setup\n\nUsually in an optimization problem, we have the definition of the convex set $\\mathcal{B}$. In the problem setup for this paper, to leverage the MaxIP operation, we need to select the set $S$ of $n$ points such that $\\mathcal{B} \\subseteq \\mathcal{B}(S)$. Once we have that set $S$, the results of this paper follow, but getting the set $S$ seems non-trivial in general convex optimization (or non-convex optimization) -- this could require $n = O(2^d)$, making the per-iteration cost quite prohibitive overall. For example, it would be good to understand what the size of $S$ needs to be to include a $\\ell_p$-ball. Given this concern regarding the problem setup, here are some specific questions/comment:\n\n\n- Line 131-132: why is the problem setup claimed to be more general while it seems to be less general. We might need precise details derivation of why \"finite feasible $S$\" is sufficient.\n- Line 152-153 \"In this setting ..\": What is the motivation for studying this setup if we cannot get the \"fast learning rates of Frank-Wolfe\"?\n\nThe use of the MaxIP solver in the Policy Gradient algorithm appears very unclear. Upon parsing the supplement, I understand that we would need to generate LSH per state $s \\in S \\subset \\mathbb{R}^d$. For continuous state spaces, this seems infeasible -- the preprocessing costs might be prohibitive -- it is not clear how the size of $S$ is considered in the preprocessing time. Is this a common setup in Policy Gradient algorithm where the size of $S$ is small and the set $\\mathcal{C}(s)$ of possible actions for some state $s \\in S$ is also a small convex set.\n\n- The \"Cost per iteration\" discussion in lines 314-317 appear to be wrong given the description of the problem setup where $\\mathcal{C}(s)$ would change with the state $s$, leading to different preprocessing for different states $s \\sim \\mu$. This needs to be clarified. \n- Also, in the policy gradient part, it is not clear how the failure probability over all $|S|$-LSHs are handled given the state transitions can cause issues with independences. The size of set of states $S$ does not appear anywhere.\n\n### Clarification regarding adaptive nature of the queries\n\nRegarding section 4.5:\n- This section addresses an important issue regarding the adaptive nature of the queries instead of the usual assumption of independence among queries.\n- However, based on the discussion in the main paper, the independence aspect is not clear since the centers might not be independent as claimed -- the gradient method drives the selection of the query which in turn selects the hypercube in the lattice and the center of this hypercube is not random. So the selection of the hypercubes are not independent and hence the centers do not intuitively appear to be independent. Can this be clarified?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This paper focuses on improving the efficiency of general optimization algorithms and hence has no negative societal impact.\n\nThe paper does not explicitly discuss any limitations even though the checklist points to section 3, which just states the problem setting and the main theoretical results without any discussion of limitations. Beyond the clarity issues, there are various limitations that I have highlighted in the **Main Review** which could have been listed as limitations.\n", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Overall, the majority of the reviewers thought that the combination of MaxIP data structures with conditional gradient methods for continues optimization, even though some of the main derivations are somewhat straightforward and not particularly difficult, is interesting enough to justify publication in NeurIPS, and may encourage further research along these line. I also agree with this view.
Decision: Accept (Poster)