Reusing Combinatorial Structure: Faster Iterative Projections over Submodular Base Polytopes
Authors: Jai Moondra
Hassan Mortagy
Swati Gupta
Venue: NeurIPS 2021 Poster (2021)
Keywords: Convex optimization
Conditional Gradients
Bregman Projections
Submodular base polytopes
Online learning

Abstract: Optimization algorithms such as projected Newton's method, FISTA,  mirror descent and its variants enjoy near-optimal regret bounds and convergence rates, but suffer from a computational bottleneck of computing ``projections" in potentially each iteration (e.g., $O(T^{1/2})$ regret of online mirror descent). On the other hand, conditional gradient variants solve a linear optimization in each iteration, but result in suboptimal rates (e.g., $O(T^{3/4})$ regret of online Frank-Wolfe). Motivated by this trade-off in runtime v/s convergence rates, we consider iterative projections of close-by points over widely-prevalent submodular base polytopes $B(f)$. We develop a toolkit to speed up the computation of projections using both discrete and continuous perspectives. We subsequently adapt the away-step Frank-Wolfe algorithm to use this information and enable early termination. For the special case of cardinality based submodular polytopes, we improve the runtime of computing certain Bregman projections by a factor of $\Omega(n/\log(n))$. Our theoretical results show orders of magnitude reduction in runtime in preliminary computational experiments.

Reusing Combinatorial Structure: Faster Iterative Projections over Submodular Base Polytopes
Jai Moondra
Hassan Mortagy Georgia Institute of Technology hmortagy@gatech. edu
Georgia Institute of Technology jmoondra30gatech.co
Swati Gupta
Georgia Institute of Technology
swatigōgatech. edu
Abstract
Optimization algorithms such as projected Newton's method, FISTA, mirror de- scent and its variants enjoy near-optimal regret bounds and convergence rates, but suffer from a computational bottleneck of computing "projections" in potentially each iteration (e.g.. (TT!/2) regret of online mirror descent) [
On the other hand, conditional gradient variants solve linear optimization in each iter- ation, but result in suboptimal rates (e.g., O(T2/3) regret of online Frank-Wolfe 7 Motivated by this trade-off in runtime v/s convergence rates, we consider iterative projections of close-by points polytopes B(f). We develop a toolkit to speed up the computation of projections using both discrete and continuous perspectives (e.g., g 9 (0). We subsequently adapt the away-step Frank-Wolfe algorithm to use this information and enable early termination. For the special case of cardinality based submodular polytopes, we improve the runtime of computing certain Bregman projections by factor of Q(n/ log(n)). Our theoretical results show orders of magnitude reduction in runtime in preliminary computational experiments.
andely-prevalleed submodular base
Introduction
Though the theory of discrete and continuous optimization methods has evolved independently over the last many years, machine learning applications have often brought the two regimes together to solve structured problems such as combinatorial online learning over rankings and permutations
12 13 14, shortest-paths [15] and trees [16] [7]. regularized structured regression (5), MAP inference, document summarization [8] (and references therein). One of the most prevalent forms of constrained optimization in machine learning is the use of iterative optimization methods such as online stochastic gradient descent, mirror descent variants, projected Newton's 's method, conditional algorithm (FISTA). These methods
gradient descent variants, fast iterative weriingge-thresooodde repeatedly compute two main subproblems: either projection (i.e., a convex minimization) or linear optimization each iteration. The former class of algorithms known as projection- optimization methods (c.g., projected Newton's method, see Table D and they enjoy netr-optimal regret bounds in online optimization and near-optimal convergence rates in convex optimization compared projection-free methods. These projection- based methods however suffer form high computational complexity per iteration due to the projection subproblem I
20
4 21]. E.g.,
online mirror descent near-optimal in terms of regret (i.e., O(VT)) for most online learning problems, however it is computationally restrictive for large scale problems B. On the other hand, online Frank- Wolfe is computationally efficient, but has a suboptimal regret of ((22/3) 77.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Algorithm
Subproblem solved
Steps for c-error
Vanilla Frank-Wolfe 5
I. over polytope
LD
Away-steps Frank-Wolfe f6
LO over polytope and active sets
16 (x) (2)
log
*Projected gradient descent 24
Euclidean projection over polytope
(w =
"Mirror descent (MD) [25]
Bregman Projection
Iry log ) ((x3)) log log 4)
*Projected Newton's 's method
24
Euclidean projection
polytope
scaled by (approximate) Hessian
*Accelerated Proximal Gradient [26]
Euclidean projection over polytope
Vk log V log
*Fast Iterative Shrinkage-Three Thresholding Al- gorithm (FISTA) 27
Euclidean projection over polytope
Table 1:
Some iterative optimization algorithms which solve linear or convex optimization problem in each iteration. Here, K = L/ ju is the condition number of the main optimization, v is condition number of the mirror map used in MD, D is the diameter of the domain, ó is the pyramidal width, 3 > 1 measures on how well the Hessian is approximated. Starred algorithms have dimension independent optimal convergence rates.
Discrete optimizers, in parallel, have developed beautiful characterizations of properties of convex minimizers over combinatorial polytopes, which typically results in non-iterative exact algorithms (upto solution of a univariate equation) for such polytopes. This theory however has not been properly integrated within the iterative optimization framework. Each subproblem within the above-mentioned iterative methods is typically solved from scratch, using a black-box subroutine, leaving a significant opportunity to speed-up "perturbed" subproblems using combinatorial structure. Motivated by these trade-offs in convergence guarantees and computational complexity, we ask if:
Is it possible to speed up iterative subproblems of computing projections over combinatorial polytopes by reusing structural information from previous minimizers?
This question becomes important in settings where the rate of convergence is more impactful than the time for computation, for e.g.. regret impacts revenue for online retail platforms. However, the computational cost of solving a non-trivial projection sub-problem from scratch every iteration is the reason why these methods have remained of "theoretical" nature. We investigate if one can speed up iterative projections by reusing combinatorial information from past projections. Our techniques apply to iterative online and offline optimization methods such as Projected Newton's Method, Accelerated Proximal Gradient, FISTA, and mirror descent variants.
To give an example setup of our iterative framework, we consider the overarching optimization problem of minimizing a convex function P + R" over a constrained set P C R" be (P1), which wish to solve using regularized optimization method such mirror descent and its variants. Typically, in such methods, iterates x, are obtained by taking an unconstrained gradient step, followed by projection onto P. We will refer (P2). Note that (P1) can be replaced by an online optimization problem as well, and similarly the iterative method to solve (P1) can be any one of those in Table
subproblem of computing single projection as
min Mxx) subject to I E
1. Vt = It Vh(rt-1)
(P1)
(PI) can be solved iteratively using, e.g., mirror descent:
2. x, arg min D (2, (2) (P2)
=EP
To solve (P2), we will typically aim for convex and discrete methods that can obtain arbitrary accuracy, to be able to bound errors in (PI). We will refer to iterates in (PI) as 2 22 It, and if (P2) is solved using an iterative method like Away-step Frank-Wolfe 22 23] we will refer those iterates as (1) , (*) (depicted in Figure (left, middle)). Our goal is to speed up the computation of ar by using the combinatorial structure of Zi...., Tt-1, (11) ..... (1),, ./...... Vt. To the best of our knowledge, we are the first to consider using the structure of previously projected points.
To capture broad class of interesting combinatorial polytopes, we focus on submodular base polytopes. Submodularity is a discrete analogue of convexity, and captures the notion of diminishing returns. Submodular polytopes have been used in a wide variety of online and machine learning applications (see Table 2 in appendix). typical example when B(f) permutahedron, polytope whose vertices are the permutations of (I,..., n.. and is used for learning over rankings. Other machine learning applications include learning over spanning trees to reduce communication
delays in networks, [12). permutations to model scheduling delays [13, and k-sets for principal

---

31
hhe
famting proeeiirs draret:
Vo
I9t) Sehpmedeen cover simple probetiers ratorn nuthods pway dit PM
Gradient Space
2c
Ut
(t)
Lt
82
i
(1)
t
outpet uaf. mamiaiiio
outest over
2cs
S
Ca e2
Elements e E
Figure 1: Left: (PI) represents an iterative optimization algorithm that computes projections 2; for points y: in every iteration (see Table ! Middle: (P2) represents subproblem of computing single projection of ye using iterative method with easier subproblems, e-g., away-step Trank-Woffs where 2 iterates during single run of AFW and converge to projection æ; (of yt). The goal speed up the subproblems using both past projections 21,...,
well as iterates z ..... (()) Right: We show how to detect tight sets S1 and Sa for close-by points by looking the maximum in Vh(It) (tools INFER INFER2).
1t-1, ,
component analysis 228] background subtraction video processing and topographic dictionary
learning (29), and structured sparse PCA [0).. Other example applications of convex minimization over submodular polytopes include computation of densest subgraphs [31, bounds on the partition
function of oog-uuuooullar distributions
32 and distributed routing [33]-
Though (Bregman) projections can be computed efficiently in closed form for certain simple polytopes (such as the n-dimennional simplex), the submodular base polytopes pose unique challenge since they are defined using 2n linear inequalities [34], and there exist instances with exponential extension complexity as well [35] (i.e., there exists no extended formulation with polynomial number of constraints for some submodular polytopes). Existing combinatorial algorithms for minimizing separable convex functions over base polytopes typically require iterative submodular function minimizations (SFM) ( 14, which are quite expensive in practice [36 37 However, these combinatorial methods highlight important structure in convex minimizers which can be exploited to speed up the continuous optimization methods.
In this paper, we bridge discrete and continuous optimization insights to speed up projections over submodular polytopes as follows:
(i) Bregman Projections over cardinality-base polytopes: We first show that the results of Lim and Wright (38] extend to all cardinality- submodular polytopes (where f(S) = g((S)) for concave function g) give On log n)-time algorithm for computing Bregman projection, improving the current best-known O(n log n + n²) algorithm [1], in Section 3 These are exact algorithms (up to the solution of univariate equation), compared to iterative continuous optimization methods.
(ii Toolkit for Exploiting Combinatorial Structure: We next develop toolkit (tools T1-T6) of provable ways for detecting tight inequalities, reusing active sets, restrict to optimal inequalities and rounding approximate projections enable early termination:
(a) INFER: We first show that for "close" points y, ÿ where the projection i of ÿ B(f) is known, we can infer some tight sets for x using the structure of é without explicitly computing (TT). Further, suppose that projection subproblem (P2) for Ye to compute z4, then given any iterate (k) in such a method, we know that (4) z, < is bounded for strongly convex functions. Using this, we show how to infer some tight sets (provably) for 2, for small enough és. (T2), Section 4.1
convergent iterative optimization method to solve the
(b) REUSE:
compute the projection ž of ÿ on B(f) using AFW, and obtain active set of vertices A for ă. Our next tool (T3) gives conditions under which A is also an active set for æ. Thus, can be computed by projecting y onto Conv(A) instead of B(J) in Section 4.2
Suppose
(c) RESTRICT: While solving the subproblem (P2), we show that discovered tight inequalities for the optimum solution can be incorporated into the linear optimization (LO) oracle over submodular polytopes, in Section 4.2 We modify Edmonds' greedy algorithm to do LO over any lower dimensional face of the submodular base polytope, while maintaining its efficient (n log n)) running time. Note that in general, while there may exist efficient algorithms to do
3

---

(TA): INFER1
y1
[T2): INFER2
(T3): REUSE
yi
yt
(t)
yt
Zt
Di
tt
Figure 2: Toolkit to Speed Up Projections: INFER I (TI) uses previously projected points infer tight sets defining the optimal face of Iy and formally described by Theorem (see also Figure[[tRigh On the other hand, INFER2 (T2) uses the closeness of iterates 20 of algorithm solving the projection subproblems (c.g. AFW) to the optimal 22, to find more tight sets at 2 (than those found by (T1) (Lemma 4.. REUSE (T3) uses active sets of previous projections computed using AFW (Lemma])
LO over the entire polytope (e.g. shortest-paths polytope), restricting to lower dimensional faces may not be trivial.
(d) RELAX and ROUND: We give two approaches for rounding approximate projection to an exact one in Section[4.3) which helps terminate iterative algorithms early. The first method uses INFER to iteratively finds tight sets at projection Iı, and then checks if we have found all such tight sets defining the optimal face by projecting onto the affine space of tight inequalities. If the affine projection zp is feasible in the base polytope, then this is optimal projection. The second rounding tool is algebraic in nature, and applicable only to base polytopes of integral submodular functions. It only requires guarantee that the approximate projection be within (Euclidean) distance of 1/(2n²) ) to the optimal for Euclidean projections.
(i Adaptive Away-Step Frank- Wolfe (A² FW): We combine the above-mentiones tools to give a novel adaptive away-step Frank-Wole variant in Section [5] We first use INFER (T1) to detect tight inequalities using past projections of æt-1- Next, we start away-step FW to compute projection at in iteration i by REUSING the optimal active set from computation of æę-1. During the course of A FFW, we INFER tight inequalities iteratively using distance of iterates (*) from optimal (T2). To adapt to discovered tight inequalities, we use the modified greedy oracle (T4). We check in each iteration if RELAX allows us to terminate early (T5). In case of Euclidean projections, we also detect if rounding to lattice of feasible points is possible (T6). We finally show an order of magnitude reduction in running time of online mirror descent by using F as a subroutine for computing projections in Section 5. and conclude with limitations in Section 5.2
Although we show that our toolkit can help speed up iterative continuous optimization algorithms like mirror descent, the tools are more general and can be used to speed up other combinatorial algorithms like Groenvelt's Decomposition algorithm, Fujishige's minimum norm point, and Gupta et.
al's Inc-Fit -ix [39 9 14] A special case of our rounding approach is used within the Fujishige- Wolfe
minimum norm point algorithm to find approximate submodular function minimizers 44 41.
Minimizing separable convex functions over submodular base polytopes was first studied by Fujishige 10 in 1980, followed by series of results by Groenevelt (9] Hochbaum 442. and recently by Nagano and Aihara [8) and Gupta et. al. (33 Each of these approaches considers different problem classes, but uses (n) calls to either parametric submodular function or submodular function minimization, with each computation discovering a tight set and reducing the subproblem size for future iterations. Both subroutines, however, can be expensive in practice. Frank-Wolff variants on the other hand have attempted at incorporating geometry of the problem in various ways: restricting or restricting away vertices to best possible active sets [47], or theoretical results such as [23] and 49 show that FW variants must use active sets that containing the optimal solution after crossing a polytope dependent radius of convergence. These results, however, do not use combinatorial properties of previous minimizers or detect tight sets with provable guarantees and round to those. To the best of our knowledge, we are the first to adapt away-step Trank-Wolff to consider combinatorial structure from previous projections, and accordingly obtain improvements over the basic AFW algorithm. Although our AFFW algorithm is most effective for computing projections (since can invoke all our toolkit for projections, i.c. (TI-T6))) it is a standalone algorithm for convex optimization over base polytopes that enables early termination with the exact optimal solution (compared to the basic AFW) via rounding (T5) and improved convergence rates visa restricting (T4). This might be of independent interest given the various applications mentioned above.
FW vertices to norm balls 44 45
46).
or prioritizing fn-face steps 48

---

2 Preliminaries
Consider a compact and convex set X' C R", and let D S R be convex set such that A' is included in its closure. A mirror map D + is strictly (or μt- strongly) convex and continuously differentiable function over D, and satisfies additional properties of divergence of the gradient on the boundary of D, i.e., limg-aa || [ = oo (see [ 20 for more details). We further assume that the mirror map Φ is unifornly separable: Φ = Σe &e where de De - R is the same function for all E E. We use 1-1| to denote the Euclidean norm unless otherwise stated. We say Ø is L- smooth 'D. The Bregman divergence generated by mirror map Φ defined as Do(x, y) == (xx)) <(y) y) - (Vély), x y). For example, the Euclidean mirror map is given by ø [|==1] for = 8 and is 1 -sstrongyy convex with respect to the lg norm. In this case (z y) = 22 v112 reduces to the Euclidean squared distance (see Table 3 We denote the Fenchel-conjuaate of the divergence by (2 y) supzepi (2, æ) (z y) } for any E D', where D is the dual space to D (in our case since DD C R", DD can also be identified with IR").
(VV - [=)=)] < L.| =|| for all x,
Submodularity and Convex Minimizers over Base Polytopes
Let f : + R be a submodular function defined on a ground set of elements E (E) = n). i.e. f(A) + f(B) 2 f(A B) + f(A n B) for all A, B C E. Assume without loss of generality that f(0) = 0, f(A) > 0 for A * @ and that f is monotond" to evaluate f any set. For E RR, we use the shorthand z(S) for E.Eg x(e), and by both are) and Ie we mean the value of on element e. Given such submodular function f. the polymatroid is defined as P(f) = for E R x(S) S (SS)SS S C E} and the base polytope as B(f) = {a E R. x(S) S f(S)&S c E, xEE) = f(E)) (5I). A typical example is when f is the rank function of matroid, and the corresponding base polytope corresponds to the convex hull of its bases (see Table 2)
!1 We denote by EO the time taken
Consider a submodular function f 2 + R with f(0) O, and let E IR.. Edmonds gave the greedy algorithm to perform linear optimization max c² x over submodular base polytopes for monotone submodular functions. Order elements in E = {EI,..... ) such that c(e.) 2 c(e,) for all i j. Define U;- {ei,..., e;), and let x" (ez) f(U,) S(U,-)). Then, x² = max c. x. Further, we will use the following characterization of convex minimizers over base polytopes:
Theorem (Theorem in 14). Consider any continuously differentiable and strictly convex function h: D + RR and funcctioo 2 - TR. with f(0) = 0. Assume that B(f)) n & 0. For any x² E R,, let Fi, F2, .......... Fi be a partition of the ground set E such that (Vh(x")), )). for all E F4 and < ct for i < L. Then x² arg aarggin miggin h(x) if and only if x² lies the face H of F.) f(Fi U U ....U...UUF.........FFF
B(f) given by H = f2 E B(f) 2FFFFFF
To see why this holds, note that the first-order optimal condition for convex optimization gives us the following certificate x² = arg minge h(())) < Vh(x*) - x² 2 0 E B(J) + x² e arg min Vh(=*))²z. The theorem then follows by applying Edmond's greedy algorithm to arg migmin Vh(=*)z )T= obtain the levels of the partial derivatives of x²' F1, .. FR. which form the optimal face If* of x². For separable convex functions like Bregman divergences (in Table B). we can thus compute x" by solving univariate equations in a single variable if the tight sets Fi...., F& of x= are known. We equivalently refer to corresponding inequalities x(F.)) fF.) as the optimal tight inequalities.
3 Bregman Projections over Cardinality-basee Submodular Polytopes
We first improve the runtime of exact combinatorial algorithms for computing uniform Bregman projections over cardinality-basee submodular polytopes. The key observation that allows us to do that is the following generalization of Lim and Wright's result (38), which, to the best of our knowledge is the first result to explicitly state the relation between Bregman projections on general cardinality- -bssed submodular polytopes and isotonic optimization:
*A differentiable function l is said to be strictly convex over domain D h(y) > lá(z) + (Vh(z), y x) for all x, y E D. Moreover, differentiable function & is said to be u-strongly convex over domain 27 with respect a norm || || if h(y) 2 h(x) + (Vh(z). y - x) + $ flly - x12 for 2, y E
'f is monotone if f(A) & f(B) AA C B C E. For any non-negative submodular function f. we can consider corresponding monotone submodular function ff such that P(f) P(f) (see Section 44.4 of (50).
5

---

(T4): RESTRICT
(T5): RELAX
(T6): ROUND
2(4)
E B(f)?
V/h(2(t)
T
It
Wp (t)
02
()
Figure 3: Proposed Toolkit (contd): RESTRICT (T4) restricts the LO oracle in AFW to the lower dimensional face defined by the tight sets found by (TI) and (T2) (Theorems 6.. Note that the restricted vertex (t) gives better progress than the orginal FW vertex vht) RELAX (T5) enables early termination of algorithms solving projection subproblems (e.g. AFW) as soon as all tight sets defining the optimal face are found (Theorem Finally, ROUND (T6) gives an integral rounding approach for special cases (Lemma
Theorem 2 (Dual of projection is isotonic optimization), Let f :2 - R be cardinality- monotone submodular function, that is f(S) = g(SS) function for some nondecreasing concave function g. Let ej := g(i) g(i - 1). for all E [E]. Let Ø D E be strictly convex and uniformly seperable mirror map. Let B(f) + @ and consider any y E K". Let {ei,..., en) be an ordering of the ground set E such that 1/ 2 2 Ynu Then, the following problems are primal- pairs
min (1 y) subject to x E B(f)
max - (2, 1) TTTc
(P)
(D)
subject to 21 S S 2n
Moreover. from dual optimal solution z², we can recover the optimal primal solution x².
To prove this result, we derive the Fenchel dual problem (D) by using the structure of cardinality- based polytopes, and restricting the minimizer to the optimal face (see Appendix G. Problem (D) in ( is in fact separable isotonic optimization problem which highlights interesting connection
between projections on cardinality-
polytopes [8) In particular, when ((x) = 2 ||
the dual problem (D) in (I) becomes the following min= { - (c - y) 11 | 21 S ... S } isotonic regression problem. Learning over projections is therefore dual to performing isotonic regression for perturbed data sets. Using the same algorithm as Lim and Wright's, i.e., the Pool Adjaceent Violators (PAV) [54], we can solve the dual problem (D) with a faster running time of (n log EO) compared to O(n²+nEO) of [43]. We include the details about the algorithm and correctness in Appendix C It is worth noting that linear optimization over Bff) also has a running time of (n log + nEO) using Edmonds' greedy algorithm 33). Therefore, for cardinality- polytopes, when solving the projection sub-problem (P2), it better use combinatorial algorithm (e.g. PAV) than any iterative optimization method (e.g. FW). Note that any FW iteration needs to sort the gradient vector (i.e., linear optimization over the base polytope) which is also On log n) in runtime. For cardinality-bast polytopes, therefore, projection-based methods to solve (P1) are computationally competitive with conditional gradient methods.
4 Toolkit to Adapt to Previous Combinatorial Structure
In the previous section, we gave an (n log n) exact algorithm for computing Bregman projections over cardinality-basee polytopes. However, the pool-adjacent-violttor algorithm is very specific to the purdinality-basee polytopes and does not extend to general submodular polyhedra. To compute a projection over the challenging submodular base polytope, there are currently only two potential ways of doing so: (i) using Frank-Wold variants (due to simple linear sub- sub-problems), (ii) using combinatorial algorithms such as those of p g (which typically rely on submodular function minimization for detecting tight sets). In this section, we construct toolkit to speed up these approaches, and consequently speed up iterative projections over general submodular polytopes.
4.1 INFER tight inequalities
We first present our INFER tool T1 that recovers some tight inequalities of projection of ğ by using the tight inequalities of the projection of a close-by perturbed point y E IR". The motivation of this result stems from the fact that projection-ben based optimization methods often move slowly, i.e. points
A separable isotonic optimization problem is of the form min Er., h((x.) subject to S a2 S ... S an.
where h; univariate strictly convex functions

---

y. ÿ to be projected are often close to each other, and so are their corresponding projections z, Æ. Our first result is specifically for Euclidean projections.
Theorem (Recovering tight sets from previous projections (T1)). Let f :2 + R be a monotone submodular function with f()) = O. Further, let y and I E R be such that |yy - yil c, and St be the Euclidean projections of y: ÿ on B(f) respectively. Let F1. F2...., Fk be a partition of the ground set E such that z Ve Ci for all e E F; and c; < ct for < L. c Cj 4e for some U. F3 j E [K- 11, then the set S = Fr U...U
is also a light set for T. L.e. (S) ((5).
Note that Ze Ve is the partial derivative of the distance function from y at z. The proof shows that for E, _.- Ue is close F ye and relies the smoothness and non-expansivity of Euclidean projection. This helps us infer that the relative order of coordinates in ズ 5 (i.e., the coordinate-wise partial derivatives) is close to the relative order of coordinates in x y/. This relative order then determines tight sets for 2; due to first-order optimality characterization of Theorem [| See Appendix for complete proof, where we also generalize the theorem to any Bregman projection that is L-smooth and non- cana-sxasssve. In Section 5.1 we will show that this theorem infers most of the tight inequalities computationally (see Figure Fleft).
Next, consider the subproblem (P2) of computing the projection 2; of point y/: Let (x() be the iterates in the subproblem that are convergent to Z₁. The points 2(x) grow progressively closer to Te. and our next tool INFER T2 helps us recover tight sets for Te using the gradients of points e(()
Theorem 4 (Adaptively inferring the optimal face (T2)). Let 2 + I be monotone submodular with f(0) = 0, h : D - R. be a strictly convex and L-smooth function, where BJ)) n DD + U. Let x: == arg m f1(2). Consider any z E B(f) such that || - x|| S E. Let F1, F2...... F's be a partition of the ground E. such that (Vh(z)),- 2. for all F; and é < & i < 1. Suppose
3+1 033 > 2T. for some j E [k: - Then, S = Fi U...... ....U. F3 is tight for x, Le. axS) = f(S)-
The proof of this theorem, similar to Theorem 3 relies on the L-smoothness of h to show that the relative order of coordinates in Vh(xx; is close to the relative order of coordinates in Vh(2(1)), which helps infer some tight sets for x. See Appendix D.2 for complete proof and Figure I rrgght for an example. Note that while Theorem 3 is restricted to Euclidean projections, Theorem applics to any smooth strictly convex function.
4.2 ReUse and Restrict
We now consider computing a single projection (P2) using Trank-Wolfs variants, that have two main advantages: (i) they maintain an active set for their iterates a (sparse) convex combination of vertices, (ii) they only solve LO every iteration. Our first REUSE tool gives conditions under which a new projection has the same active set A as point previously projected, which allows for faster projection onto the convex hull of A (proof is included in Appendix (.2).
Lemma 1 (Reusing active sets (T3)). Let P S RD be a polytope with vertex set vert(P). Let be the Euclidean projection of some y E R. on P. Let A {VI..... [b} S vert(P) be an active set for z, i.e., x ExE(n] Aev, for [|ll = 1 and X > 0. Let F be the minimal face of and A minygaCoov(AA) |ær wll be the minimum distance between and the boundary of Conv(A). Then, is also an active set for the Euclidean projection of any point ÿ E BB n Cone(F), where BA (v) = iu E R= | vll S min(A, || - -y13} is a closed ball centered at y.
In the previous section, we presented combinatorial tools to detect tight sets at the optimal solution. We now use our RESTRICT tool to strengthen the LO oracle in FW by restricting it to the lower dimensional faces defined by the tight sets we found (instead of doing LO over the whole polytope). Note that doing linear optimization over lower dimensional faces of polytopes, in general, is signifi- cantly harder (e.g., for shortest paths polytope). For submodular polytopes however, we show that can do LO over any face of B(f) efficiently using modified greedy algorithm (Algorithm 2 in Appendix B Given a set of tight inequalities, one can uncross these to form a chain of tight sets, T.e., any face of BJ)) can be written using chain of subsets that are tight (see e.g. Section 44.6 in (55)). Given such a chain, our modified greedy algorithm then orders the cost vector in decreasing order so that it respects given tight chain family of subsets. Once it has that ordering, it proceeds in the same way as in Edmonds" greedy algorithm (34]. We include a proof of the following theorem in Appendix D.2
Theorem 5 (Linear optimization over faces of B() (T4)). Let f : 2 - R. be a monotone submodular function with f(0 = O. Further, let F = fa E B(f) x(S.) -((S) for S, E S) be
7

---

face of B(f). where S = {Si.... Sk|S; Sg... S.).. Then the modified greedy algorithm (Alg. 2 returns x² arg m (c, in logn + nEO) time.
4.3 Rounding
Approximation errors in projection subproblems often impact (adversely) the convergence rate of the overarching iterative method unless the errors decrease sufficient rate [56 577. Our goal in this section is to detect if all tight sets at the optimum have been inferred, and enable early termination by computing the exact minimizer. In 2020. [58] gave primal gap bounds after which atay-step FW reaches the optimal face, assuming strict complementarity assumption which need not hold even for computing Euclidean projection. Further, [59], showed that there exists some convergence radius R such that for any iterate (0)) of AFW, if || x=1 || S R. then any active set for 20()) must contain x², but the parameter R existential and is non-trivial to compute. We complement these results by rounding our approximate projections to an exact one based on structure in partial derivatives.
Suppose that we have a candidate chain S {S..... S of tight sets (e.g.. using INFER). We observe that if the affine minimizer over S, i.e., 5 == arg min (1(x)) x(S) = S(S) E S} is feasible in B()), then this is indeed the optimum solution = x="
with Lemma 2 (Rounding to optimal face (T5)). Let : + R be a monotone submodular
D + 0. Lei x² arg min min h(x),, and let S = . 3 contain some of the tight sets at x², i.e. x² =S.) Further, let ã == arg face defined by the tight set inequalities corresponding to S. Then, x²' = 3 iff & is feasible in B(f)- In particular, if S contains all the tight sets at x², then x² = J.
f(0) 0. Let h : D IR be strictly convex, where n
f(.) for all [k]. z(S) = f(S) VS E S} be the optimal solution restricted to the
The proof of this lemma can be found in Appendix D.3 and as a subroutine in Appendix B We note that this holds for any polytope: if we know that tight inequalities at the minimizer we can restrict the optimization problem to the face defined by those tight inequalities and ignore the other constraints defining the polytope (see Lemma 4 in Appendix C To check whether ā E BJf) in general requires an expensive submodular function minimization, but instead we just check whether ā is in the convex hull of (o(1), ..... e(t)), }. where e are the FW vertices of Bf)) that we have computed in Line 3 of Algorithm FW up to iteration 1. Using [59], we know that there will be a point at which the optimal solution is contained in the current active set.
We now present our second rounding tool ROUND for base polytopes of integral submodular functions. It only requires a guarantee that the approximate projection be within a (Euclidean) distance of 1/(2) EJ²) to the optimal projection. This generalizes the robust version of Fujishige's ' theorem given in connecting the MNP over B(f) and the set minimizing the submodular function value.
Lemma 3 (Combinatorial Integer Rounding Euclidean Projections (T6),, Let f 2 + Z (EE) n) be a monotone submodular function with f0) = O. Consider y E E and let h(x) =
vl?.
Let x²' = arg min BEJ h(xx). Consider any x E B(f) such that ||--x"" < zn Define
J, and for any r E R, let q(r) = arg me Ir s). Then, g(xx) is unique for all e E E. and the optimal solution is given by x²= q(xx)) for all E.
Q - zuzuuzzu....
This rounding algorithm runs in time O(n² lo and is given in Algorithm 5 in Appendix The proof proceeds by showing that xt E S for all e E E, and that the distance between two points in S is at least 1 [g|2 so that one always round to x= correctly (complete proof is in Appendix D.3
5 Adaptive Away-step Frank- Wolfe (F))W)
We are now ready to present our Adaptive AFW (Alg. T by combining tools presented in the previous section. First using the INFER1, we detect some of the tight sets S at the optimal solution before even running F2W, and accordingly warm-start FFFW with (0) in the tight face of S. A?FW operates similar the away-step Frank-Wolfe, but during the course of the algorithm it restricts to tight faces as it discovers them (using INFER2), adapts the linear optimization oracle (using RESTrICT), and attempts to round to optimum (using ROUND, RELAX). To apply INFER2 (subroutine included as Algorithm 3. consider an iteration of A FWW, where we have computed the FW gap gf := max < Vh(=("), v- v (see line 11 in Algorithm 1b. For p-strongly convex h, we have:
M 5 "1=000 xx x=122 < h(219)) h(x*) S max < Vh(2(0),, v- 2(1) = =.:"" p.
(2)
8

---

> use toolkit to find new tight sets Algorithm Adaptive Away-steps Frank- Wolfe FA))W)
Input: Submodular f 2 18. (u. L) -strongly convex and smooth B(f) - IR, chain of tight cuts (c.g., using INFERT), =0)) E B(f) n (x(S) f(S), 8} with active set Ag. tolerance
1:
Initialize f = 0, FW = +00, (0)) = (
2: while 9/x 2 do
3: Snew = S U (N, 20) 2L /2g /N)
4: 3. Flag= = RELAX (eew: (v })
5:
if Flag True. return T
6:
if [Snen > [S] then
7:
Set (++1) E arg min, g P(Sncw)
(h((z()), u) and Ar+1 =(+1) D round and restart P do iteration of AFW restricted to F(S)
8:
else
9:
Compute th arg win. (hh(s""), 1)
D use toolkit
10:
Compute away-vertex ( E arg max,eA. (h(( 2(++1) A 9241 = AFW-update(
11:
(0) Ar)
12: end if
13:
Update :: 1= and S = Snew
14: end while
Return: 2(()
and so ||0(0) x=1| S /2g Let F1, Fg...., Fg be a partition of the ground set such that (V)(2(())) [) = è for all e E Fj and è < à for all i < I. If 25+11 - ēj
FW /μ for some 2L 2g j E [k 1]. then Theorem immlies that S = Fi U...U. F, is tight for x², i.. x (S) = f(S).
Overall in FFW, we maintain set S containing all such tight sets S at the optimal solution that we have found so far. We use those tight sets as follows: (i) we restrict our LO oracle to the lower dimensional face we identified using the modified greedy algorithm (RESTRICT- (T4)). (ii) We use our RELAX ((T5) tool to check weather we have identified all the tight-sets defining the optimal face (Lemma 2 If yes, then round the current iterate to the optimal face and terminate the algorithm early l. For (Euclidean) projections over an integral submodular polytope, we can also use our ROUND (T6) tool to round iterate close to optimal without knowing the tight sets. Whenever the algorithm detects a new chain of tight sets Snews it is restarted from a vertex in F(Snew). which possibly has higher function value than the current iterate. However, this increase in the primal gap bounded as is finite over B(J) and can happen at most n times; thus, these restarts do not impact the convergence rate. The pseudocode of FW is included in Algorithm
As depicted in (T4) in Figure 3 restricting FW vertices to the optimal face results in better progress per iteration during the latter runs of the algorithm. The convergence rate of FF depends on a geometric constant called the pyramidal width (6). This constant is computed over the worst case face of the polytope. By iterative restricting the linear optimization oracle to optimal faces, we improve this worst case dependence in the convergence rate (proof in Appendix(F)
Convergence Rate:
Theorem 6 (Convergence rate of AFFW), Let f 2 + R be a monotone submodular function with f(0) = and f monotone. Consider any smooth strongly convex function h(-)) with unique optimal xx B(f). Let S be the tight sets found up to iteration t and F FSS) be the face defined by these tight sets. Then, the primal gap w((((+1)) ;= h(2(++1)) h(=²) of A decreases geometrically at each step that is not a drop step nor restart step:
w(2(+1)) E
F(S)
w(2( where D the diameter of B(f) and
(3)
4LD
Pr(s) is the pyramidal width of B(f) restricted to F(S) (as defined by 24 Moreover, in the worst case, the number of iterations to get an e-accurate solution is O (OILD*//(UPE(n))) log(1/e)).
Note that PF(S) can be strictly larger than the worst-case pyramidal width over the entire polytope. For example, for the probability simplex (a submodular polytope; see Table the pyramidal width restricted to face F is 2/ dim(F') (assuming dim( F)) is even for simplicity) [60]. To the best of
our knowledge, we are the first to adapt AFW tight faces as they are detected. This might be of independent interest to the SFM community.
A drop step is when we take an away step with maximal step size so that we drop a vertex from the current active set.

---

Tilli froe 1/50
Runtime for OMD AFW variands
Runtime for OMD AFW variants
Fommtng (normaalled)
10P
Fomzzngg (normasind))
10
10/
10
10-1
31111
ONID-SRAFF
ONII-TSAUT
Truatinn figit ont ponciess poats Restion lggl wiis soowrd by Theuees
OMD A/F
0Nt A/PW
250
500
7M
IC00
250
500
770
1600
100
20
Ierrations
Figure 4: (left) 15-85% percentile plot of fraction of tight sets inferred by using INFER I (blue) w/s highest number of tight sets common for ith iterate compared to previous i 1 iterates (in green) for close points generated randomly using Gaussian noise, over 500 runs. (middle) 25-75 percentile plots of normalized run times for OMD-AFW variants for first loss setting averaged over 20 runs. (right) 25-75 percentile plots of normalized run times for OMD-AFW variants with second loss setting averaged over 20 runs.
5.1 Computations
The code for our computations can be found on GitHut In our first experiment, we iteratively compute the Euclidean projections of 500 randomly generated points on the permutahedron. The cloud these 500 points is generated by fixing a random mean point and perturbing it using multivariate Gaussian noise with mean zero and standard deviation = 1/50. We compute the projections of each point in the cloud exactly, and plot percentile plots of fraction of discovered tight sets from previous projections in Figure left. The fraction of tight inequalities for each point y that were already tight for some other previous point yoo.... Vi-1 is in green, the fraction of tight sets for Y/ inferred by using Theorem is in blue. The plots average over 20 runs of this experiment. Note that our theoretical results give almost tight computational results, that is, we can recover most of the tight sets common between close points using Theorem
In our second experiment (detailed in appendix G) motivated by the trade-off in regret versus time for online mirror descent and online Frank-Wolfe (OFW) variants, we conduct an experiment on the permutahedron P with n = 50 elements. We consider a time horizon of T 1000, and construct two noisy (linear) loss settings. For each of the two loss settings, we run Online Frank- Wolfe (OFW) and five variants of Online Mirror Descent (OMD) using the toolkit proposed: (1) OMD-UAFW: OMD with projection using vanilla away-step Frank- Wolfe (baseline), (2) OMD-ASAFW. OMD with AFW with reused active sets, (3) OMD-OMMDEAEE ROUNDING, (4) OMD-A'FW OMD with FFW and (5) OMD-PAV: OMD with PAV. We call the first four "OMD-AFW variants". Recall that OMD performs projections in potentially each iteration.
OMD with AFW with INFER, RESTRICT, and
We normalized each OMD-UAFW run time to be 1000, and run times for all other variants in this run are correspondingly scaled in Figures middle and right.. Each iteration of OMD involves projecting point on the permutahedron, and the cumulative run times for these projections are plotted. The plots are averaged over 20 runs of this experiment for both the settings.
We see more than three orders of magnitude improvement in run time for OMD-ASAFY and OMD- A'FW compared to the unoptimized OMD-AFW. Both OMD-PAV and OFW run 4 to 6 orders of magnitudes faster on average than OMD-UAFW; however, OMD-PAV suffers from the limitation that it only applies to cardinality- based submodular polytopes, while OFW has significantly higher regret in computations. We summarize these results in Table 4 in Appendix G
OMD has regret 1 to 2 orders of magnitude lower than OFW on average, thus bolstering the claim that we need to invest research to speed-up this optimal learning method and its variants. This drop in regret is significant in terms of revenue for an online retail platform. The regret for all OMD variants was observed to be nearly the same. Overall, speeding up OMD is an example of the impact of our toolkit, which can be applied in the broader setting of iterative optimization methods.
5.2 Limitations and Open questions
There is still is long way from closing the computational gap with Online Frank Wolfe. Our work inspires many future research questions, e.g., procedures to infer tight sets on non-submodular polytopes such as matchings and procedures to round iterates to the nearest tight face for combinatorial polytopes. We hope that our results can inspire future work that goes beyond looking at projection subroutines black boxes. We believe that our work does not have any foresceable negative ethical or socictal impact.
10

---

6 Acknowledgments and Disclosure of Funding
The research presented in this paper was partially supported by the Georgia Institute of Technology ARC TRIAD fellowship and NSF grant CRII-1850182.
References
[T] A. S. Nemirovski and D. B. Yudin, "Problem complexity and method efficiency in optimization," Wiley--nterscience, New York, 1983.
[2] A. Beck and M. Teboulle, "Mirror descent and nonlinear projected subgradient methods for convex optimization," Operations Research Letters, vol. 31, no. 3, pp. 167-175, 2003.
[3] N. Srebro, K. Sridharan, and A. Tewari, "On the universality of online mirror descent," Advances in Neural Information Processing Systems, 2011.
[4] Audibert, S. Bubeck, and G. Lugois, "Regret online combinatorial optimization, " Mathe- matics of Operations Research, vol. 39, no. 1, pp. 31-45, 2013.
[5] M. Jaggi, "Revisiting Frank-Wolff Projection-free sparse convex optimization." in Proceedings of the 30th international conference on machine learning, 2013, pp. 427-435.
[6] S. Lacoste-Julien and M. Jaggi, "On the global linear convergence Frank-Woo optimization variants," in Advances in Neural Information Processing Systems (NIPS), 2015, pp. 496-504.
[7] E. Hazan and E. Minasyan, "Faster projection-free online learning." in Conference Learning Theory. PMLR, 2020, pp. 1877-1893.
[8] K. Nagano and K. Aihara, "Equivalence of convex minimization problems over base polytopes." Japan jourmal of industrial and applied mathematics, pp. 519-534, 2012.
[9] H. Groenevelt, "Two algorithms for maximizing a separable concave function feasible region," European journal of operational research, vol. 54, no. 2, pp. 227-236, 1991.
polymatroid
[10] S. Fujishige, "Principal structures of submodular systems," Discrete Applied Mathematics, vol. 2, pp. 77-79, 1980.
[11] D. P. Helmbold and M. K. Warmuth, "I "Learning permutations with exponential weights," " The Journal of Machine Learning Research, vol. 10, pp. 1705-1736, 2009.
[12] W. M. Koolen, M. K. Warmuth, and Kivinen, "Hedging structured concepts," COLT, 2010.
[13] S. Yasutake, K. Hatano, S. Kijima, F. Takimoto, and M. Takeda, "Online linear optimization over permutations," " in Algorithuns and Computation. Springer, 2011, pp. 534-543.
[14] Gupta, M. Goemans, and P. Jaillet, "Solving combinatorial games using products, projections and lexicographically optimal bases," arXiv preprint 11Xiv:1603.00522 2016.
[15] A. György, Т. Linder, G. Lugosi, and G. Ottucsák, "The on-line shortest path problem under partial monitoring." Journal of Machine Learning Research, vol. no. 10, 2007.
[16] N. Cesa-Bianchi, C. Gentile, F. Vitale, and G. Zappella, "Active learning on graphs via spanning trees." in NIPS Workshop on Networks Across Disciplines. Citeseer, 2010, pp. 1-27.
[17] H. Rahmanian, D. P. Helmbold, and S. Vishwanathan, "Online learning of combinatorial objects via extended formulation," " in Algorithmic Learning Theory. PMLR, 2018, pp. 702-724.
[18] Bach et al., "Learning with submodular functions: A convex optimization perspective," Foundations and Trends@ in Machine Learning, vol. 6, no. 2-3, pp. 145-373, 2013.
[19] A. Nemirovski,
with rate of convergence o11/t) for variational inequalities with Lipschitz continuous monotone operators and smooth concave saddle point problems," SIAM Journal on Optimization, vol. 15, no. 1, pp. 229-251, 2004.
[20] A. Beck, First-order methods in optimization. SIAM, 2017.
[21] S. Bubeck, "Theory of Convex Optimization for Machine Learning." arXiv preprint arXiv: 1405.4980, 2014.
[22] Wolfe, "Convergence theory in nonlinear programming." Integer and nonlinear programming, pp. 1-36, 1970.
11

---

[23] J. GuéLat and P. Marcotte, "Some comments on wolfe's 'away step': Mathematical Program- ming, vol. 35, pp. 110-119, 1986.
[24] H. Karimi, J. Nutini, and M. Schmidt, "Linear convergence of gradient and proximal-gradient methods under the Polyak-tojasiewiczcoo cotiaasieiicccoodtttoinnn condition," in European Conference on Machine Learning and Knowledge Discovery in Databases- Volume 1851, ser. ECML. PKDD 2016. Springer- Verlag, 2016, 795-811.
[25] A. Radhakrishnan, M. Belkin, and C. Uhler, "Linear convergence and implicit regularization of generalized mirror descent with time-dependent mirrors," arXiv preprint arXiv:2009.08574, 2020.
[26] Y. Nesterov, Introductory lectures on convex optimization: basic course. & Business Media, 2003, vol. 87.
Springer Science
[27] A. Beck and M. Teboulle, "A fast iterative shrinkage-threshoolinng algorithm for linear inverse problems," SIAM journal on imaging sciences, vol. 2, no. 1, pp. 183-202, 2009.
(28) M. K. Warmuth and D. Kuzmin, "Randomized PCA algorithms with regret bounds that are logarithmic the dimension," in Advances in Neural Information Processing Systems, 2006, pp. 1481-1488.
[29] J. Mairal, R. Jenatton, G. Obozinski, and F. Bach, "Convex and network flow optimization for structured sparsity." " Journal of Machine Learning Research, vol. 12, no. 9, 2011.
[30] R. Jenatton, G. Obozinski, and F. Bach, "Structured sparse principal component analysis," in Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics. JMLR Workshop and Conference Proceedings, 2010, pp. 366-373.
[31] K. Nagano, Y. Kawahara, and K. Aihara, "Size-constrained submodular minimization through minimum norm base," in Proceedings of the 28th International Conference on Machine Learning
(ICML), 2011, pp. 977-984.
[32] J. Djolonga and A. Krause, "From MAP to marginals: Variational inference in bayesian submodular models," in Advances in Neural Information Processing Systems, 2014, pp. 244- 252.
[33] W. Krichene, S. Krichene, and A. Bayen, "Convergence of mirror descent dynamics in the routing game," in European Control Conference (ECC). IEEE, 2015, pp. 569-574.
[34] J. Edmonds, "Matroids and the greedy algorithm," Mathematical Programming, vol. 1, no. 1, pp. 127-136, 1971.
[35] T. Rothvoß, "Some 0/1 polytopes need exponential size extended formulations," Mathematical Programming, vol. 142, no. 1-2, pp. 255-268, 2013.
[36] S. Jegelka, H. Lin, and J. A. Bilmes, "On fast approximate submodular minimization," " in Advances in Neural Information Processing Systems, 2011, pp. 460-468.
[37] B. Axelrod, Y. P. Liu, and A. Sidford, "Near-optimal approximate discrete and continuous submodular function minimization." in Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 2020, pp. 837-853.
[38] C. H. Lim and S. J. Wright, "Efficient bregman projections onto the permutahedron and related polytopes," in Artificial Intelligence and Statistics. PMLR, 2016, pp. 1205-1213.
[39] S. Fujishige, "Leexccorraphicall optimal base of polymatroid with respect to weight vector," Mathematics of Operations Research, 1980.
[40] S. Fujishige and S. Isotani, "A submodular function minimization algorithm based on the minimum-nore base," Pacific Journal of Optimization, vol. 7, no. 1, pp. 3-17, 2011.
[41] D. Chakrabarty, P. Jain, and P. Kothari, "Provable submodular minimization using wolfe's algorithm." in Advances in Neural Information Processing Systems, 2014, pp. 802-809.
[42] D. S. Hochbaum, "Lower and upper bounds for the allocation problem and other nonlinear optimization problems," Mathematics of Operations Research, 1994.
[43] S. Gupta al., "Combinatorial structures in online and convex optimization," " Ph.D. dissertation, Massachusetts Institute of Technology, 2017.
[44] E. Hazan and T. Koren, "The computational power of optimization online learning," arXiv preprint arXiv: 154.000900 2015.
12

---

[45] D. Garber and E. Hazan, "A linearly convergent variant of the conditional gradient algorithm under strong convexity, with applications to online and stochastic optimization." SIAM Journal on Optimization, vol. 26, no. 3, 1493-1528, 2016.
[46] G. Lan, "The complexity of large-scale convex programming under a linear optimization oracle," " arXiv preprint arXiv: /5/2061/42 2013.
[47] M. A. Bashiri and X. Zhang. "Decomposition-invvraan conditional gradient for general poly- topes with line search," " in Proceedings of the 31st International Conference on Neural Informa- tion Processing Systems, 2017, p. 2687-2697.
[48] R. Freund, P. Grigas, and R. Mazumder, "An extended Frank-Wort method with "in-face" directions, and its application to low-rank matrix completion." SIAM Journal on Optimization. vol. 27, no. 1, p. 31-3346, 2015.
[49] A. Carderera and S. Pokutta, "Second-order conditional gradient sliding," " arXiv preprint arXiv:2002.08907, 2020.
[50] A. Schrijver, Combinatorial optimization: polyhedra and efficiency. Business Media, 2003, vol. 24.
Springer Science &
[51] J. Edmonds, "Submodular functions, matroids, and certain polyhedra," Combinatorial Structures and Their Applications, pp. 69-87, 1970.
[52] A. K. Menon, X. J. Jiang, S. Vembu, C. Elkan, and L. Mashodoa "Predicting accurate probabilities with ranking loss," in Proceedings of the... International Conference on Machine Learning. International Conference on Machine Learning, vol. 2012. NIH Public Access, 2012. p. 703.
[53] A. Niculescu-Mizil and R. Caruana, "Predicting good probabilities with supervised learning," Proceedings of the 22nd international conference on Machine learning, 2005, pp. 625-632.
[54] M. J. Best, N. Chakravarti, and V. A. Ubhaya, "Minimizing separable convex functions subject to simple chain constraints," " SIAM Journal on Optimization, vol. 10, no. 3, pp. 658-672, 2000.
[55] A. Schrijver, "A combinatorial algorithm minimizing submodular functions in strongly polyno- mial time," Journal of Combinatorial Theory, Series B, vol. 80, no. 2. pp. 346-355, 2000.
[56] M. Schmidt, N. L. Roux, and F. Bach, "Convergence rates of inexact mroximal-gradienn methods for convex optimization," arXiv preprint 110X:v1110024000 2011.
[57] A. d' Aspremont, "Smooth optimization with approximate gradient," SIAM Journal Opti- mization, vol. 19, no. 3, pp. 1171-1183, 2008.
[58] D. Garber, "Revisiting frank-wolfe for polytopes: Striet complementarity and sparsity," Ad- vances in Neural Information Processing Systems, vol. 33, 2020.
[59] J. Diakonikolas, A. Carderera, and S. Pokutta, "Locally accelerated conditional gradients," in International Conference on Artificial Intelligence and Statistics. PMIR, 2020, pp. 1737-1747.
[60] J. Penă and D. Rodríguez, "Polytope conditioning and linear convergence of the frank-wolfe algorithm," " arXiv preprint arXiv:1512.06114 2015.
[61] R. T. Rockafellar, Convex analysis. Princeton University Press, 1970.
[62] D. Suehiro, K. Hatano, S. Kijima, E. Takimoto, and K. Nagano, "Online prediction under submodular constraints," in International Conference on Algorithmic Learning Theory (ALT).
Springer, 2012, pp. 260-274.
[63] D. Bertsekas, A. Nedic, and O. AE, Convex Analysis and Optimization. Athena Scientific, 2003.
[64] G. Optimization, "Gurobi optimizer reference manual version 7.5," 2017, uRL: https://www gumbh.com//dccuunnttoo///....eem
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] All our main contributions are stated detail in the introduction and summarized in the abstract.
13

---

(b) Did you describe the limitations of your work? [Yes] We have described limitations of our work in Section 5.2
(c) Did you discuss any potential negative societal impacts of your work? [Yes] We present the broader impact of our work in Section 5.2 We believe that our work does not have
any foreseeable negative ethical or societal impact.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes] We ensured that our paper conforms to the ethics review guidelines.
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] All our assumptions are stated in the preliminaries section (Section 2}. Moreover for each hold.
theorem/lemmaa we again state the necessary assumptions needed for these results to
(b) Did you include complete proofs of all theoretical results? [Yes] Detailed proofs for all results presented in this paper can be found in the appendix.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes] We uploaded the code along with the supplementary material in a zip file. We also included a Readlle note explaining how to reproduce our results in the paper.
(b) Did you specify all the training details (e.g.. ... data splits, hyperparameters, how they were chosen)? [Yes] We explained the computational setup in the main body of the paper in Section We also include more details on the computations in Appendix([ All the specifications are highlighted in our code files well as the ReadMe note created.
(c)
Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] All our plots contain confidence intervals representing the variability in the results obtained across multiple plots. The number of times each experiment was run is documented in the paper and the seeds used are highlighted in the code.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] We include all our computing details, i.e. total amount of compute and the type of resources used, in Appendix G
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A] Our work does not use existing assets. We instead use synthetic data that we created
(b) Did you mention the license of the assets? [N/A] Our work does not use existing assets.
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A] Our setup is online learning setup that is not data based. However, our setup is in the code provided and can be used for other experiments.
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A] Our work does not use existing data.
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A] Our work does not use existing data.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A] Our work does not crowdsource any data.
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A] Not applicable as our work does not crowdsource any data.
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A] Not applicable work does not crowdsource any data.
14


Reviews:
[{"review_id": "yqcUsiF_Y8I", "reviewer": "Reviewer_LoQq", "summary": "The paper focuses on projection-base methods such as mirror descent for problems, where constraint sets are defined by submodular polytopes. These problems are challenging as they contain an exponential number of constraints. These projection-based methods have superior convergence rates in comparison with their Frank-Wolfe counterparts. However, the latter optimizes a linear objective in each iteration that is easier than doing the projection required in the former. The paper precisely addresses this issue and proposes an Away Step Frank-Wolfe method that leverages the submodular structure of the problem to solve the projection step efficiently. \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": "The paper focuses on providing ways for speeding up the projection based optimization methods such as mirror descent that have superior convergence rates, but suffer from expensive projection steps. They concentrate on constraints defined by submodular polytopes. This is an interesting contribution and they provide theoretical results on their proposed Away Step Frank-Wolfe for preforming projections; however, I am not convinced that these problems are well-motivated. They briefly mention applications such as principal component analysis subject to k-sets. However, I believe these applications should be presented in more details to provide motivations for the studied algorithm. Presentation of the paper is decent; however, some notations are confusing. For instance, the main class of problems that the paper aims to solve are never explicitly presented using math, which makes following the paper hard. Moreover, the experimental results are lacking and the description of the numerical results is extremely sparse and rushed. Finally, the paper focuses all of its main sections on their Away-Step Frank-Wolf algorithm; however, this method is only interesting in conjunction with projection based optimization methods. It would be interesting to see analysis or theoretical guarantees on combinations of these methods. Moreover, the paper needs to provide more motivations for considering this class of projection-based methods; indeed, in experiments , Online Frank-Wolfe algorithm is mentioned as a competitor, but is not reported in Fig.  4.  \n\nTypos and minor issues\n\n(a) Line 64 exit→ existing \n(b) Line 138 put space before \"We\" \n(c) Line 192 “Therefore, for cardinality-based polytopes, using a combinatorial 193 algorithm is better than any iterative optimization method.” → I do not see why this method is \"better than any iterative optimization method.\" \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Despite presenting an interesting contribution, I see serious limitations for the current results.\n\n(a) As mentioned, the paper does not provide enough evidence for the interest in the studied class of problems. Moreover, it does not explicitly state the studied class of problems.\n\n(b) The paper focuses on their proposed method for performing projection more precisely; however, it needs to provide stronger  motivations on why the projection based methods are considered in the first place. I understand that the projection based methods come with a superior convergence rate. However, I do not believe that this discredits Frank-Wolfe methods altogether. A more insightful approach would be to state computation complexity along with convergence rates. In this way, we would be able to understand for which problem sizes the projection based methods are more efficient.\n\n(c) The experimental results are quite limited: first, the presentation of data and problems are extremely lacking and confusing. Second, they are reported on one dataset that is not large. Third, the results for Online Frank-Wolfe algorithm is not reported in the figure.   ", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "3 "}, "extra_text": {}}, {"review_id": "PTxC2VfigA", "reviewer": "Reviewer_EP3B", "summary": "This paper presents  new techniques to speed up projections to submodular base polytopes.   The techniques are inspired by both discrete and continuous perspectives.  Arranging the proposed tools together, they present the adaptive away-step Frank-Wolfe algorithm.  The runtime of computing certain Bregman projection is improved by a factor of $\\Omega(n/log(n))$.", "questions": "", "limitations": "", "rating": 6, "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": "Contributions:  \n\nThis paper presents several techniques to speed up projections over submodular polytopes.  They give solid theoretical proofs of the tools and algorithms.  It can be viewed as a combinations of several existing techniques, say,  Edmonds greedy algorithm, Frank-Wolfe et al.  However, the toolkit proposed surely introduces some new techniqes.  \n\nOverall, I think it is a solid work in terms theorecial exploration of fast projecting to submodular base polytopes.  \n\n\nPresentation & clarity: \n\n- Very well structured paper, main technical components are very well presented, e.g., the toolkit T1-T6.  I really like the illustrations in Figures 1 -3.   \n\n- Better to put Alg. 5 (A^2FW) in the main text,  (though I know it was defered to appendix due to space limit).  It is a pretty well designed algorithm.   \n\n\n\nExperiments:  \n\nFigure 4 clearly show computational advantages of your techniques on synthetic data. \nIt would be great to see some real-world experiments, say, some experiments from submodular function minimizaiton literature or others.   \n \n\n\nMinor typos:  \n\n- line 306:  weather -> whether \n- line  64:  their -> there ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "Hu7pBO2G8SH", "reviewer": "Reviewer_urFe", "summary": "This paper provides a faster algorithm for the Bregman projection onto submodular base polytopes.\n- For the case the submodular function is cardinality-based and the mirror map is separable convex, the authors show that the Bregman projection can be done in $O(n \\\\log n + n EO)$ time, where $n$ is the size of the ground set and $EO$ is the running time of the evaluation oracle of the submodular function. This result improved the previous $O(n^2 EO)$ time.\n- Furthermore, the authors provided a toolkit to speed up the Bregman projection in practice. In the numerical experiment, the algorithm with the toolkit runs faster in several orders of magnitudes.", "questions": "", "limitations": "", "rating": 5, "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 well-written and easy to read. The improved algorithm for cardinality-based submodular functions seems nice.\n\nOn the other hand, the second contribution is difficult to evaluate. The authors gave several interesting tools to speed up the Bregman projection. However, these are simply heuristics and do not yield an improved time complexity. Also, the authors proposed Adaptive Away-steps Frank-Wolfe (A2FW) and proved its linear convergence. But the linear convergence holds only for strongly convex and smooth mirror maps, which do not include important projection in online learning such as KL-projection. So it is unclear whether these results improve the time complexity of OMD. The present paper provides empirical evaluation only.\n\nNote that OMD is a highly theoretical algorithm with the optimal regret guarantee. For a practical purpose, one can use Follow-the-Perturbed-Leader (FPL) because each iteration is very cheap for submodular polytopes. Does FPL perform poorly in practice? How does OMD with the proposed heuristics compare with FPL in running time? The lack of theoretical improvements and comparison is a weak point of the paper.\n\nOverall, the paper has a neat result but is not strong enough from the theoretical perspective.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "GvVR01IcnCn", "reviewer": "Reviewer_2XnM", "summary": "This paper considers the problem of Bregman projections on Submodular Base polytopes. The authors present several tools that could speed up computation when this projection is computed for several nearby points, as is the case for example in iterative algorithms such as mirror descent. In particular, the authors first present an algorithm for the special case of cardinality-based submodular functions, that improve over current best known running time. Then they present tools, for general submodular functions, to detect tight inequalities, reuse active sets, restrict linear optimization to the detected tight inequalities, and round approximate projections to exact ones. They show how these tools can be incorporated into away-step Frank-Wolfe (AFW). They also provide some empirical results showing a reduction in running time of online mirror descent (OMD) when their proposed variant of AFW is used for computing projections, compared to using regular AFW.", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "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": "Originality and significance:\nThe result presented for the cardinality-based submodular functions is not really new. In particular, Theorem 2 is a special case of Proposition 8.1 in [19]. But to the best of my knowledge, this paper is the first to explicitly state the relation between Bregman projections on cardinality-based submodular polytopes and isotonic optimization, which is useful to highlight. \n\nThe tools presented for general submodular functions to accelerate Bregman projections are novel. Whether or not they indeed lead to a speed up depends on if the conditions assumed hold or not. The empirical results provided show some evidence that these tools could be helpful. Though in certain cases, one of the tools (reusing active sets) doesn't have an effect (see Figure 4, OMD-ASAFW vs OMD-UAFW), and in others some of the tools lead to worst running time (see Figure 6-right, OMD-A^2FW vs OMD-ASAFW). More comprehensive empirical evaluation is needed. \n\nQuality: I checked most proofs, they are correct. However the experimental results are not convincing enough.\nThe examples used (both in the main text and appendix) are too small (ground set size n=25). It is also not clear from the reported results how OMD with the proposed variant of AFW compares with simply using online FW. Showing plots of both regret and runtime for all compared methods (and not just variants of AFW) would better highlight this trade-off. It would be good to also compare with other methods of computing projections. I am particularly interested to see a comparison with minimum norm point algorithm, which already includes one of the proposed tools (rounding to optimal face).\nSome information about the set-up is missing: what is the submodular function and Bregman divergence in the first example?\n\nClarity: The paper is written clearly, with only few typos. \n\nOther comments/suggestions for improvements:\n\n- The proposed rounding to optimal face (T5) is a generalization of rounding done in minimum norm point algorithm. This is stated on lines 117-118, but it would be good to also restate that lemma 2 is a generalization of the same property used in MNP for $h(x) = \\tfrac{1}{2} ||x||_2^2$.\n\n- l.68: there's several more recent papers than [34] that provide faster algorithms for submodular function minimization, with the current fastest approximate algorithm having subquadratic time:\n\n\"Chakrabarty, D., Lee, Y. T., Sidford, A., and Wong, S. C.-w. Subquadratic submodular function minimization. In\nProceedings of the ACM SIGACT Symposium on Theory of Computing, STOC 2017\"  \n\n- is $n = |E|$? if yes, specify that in the preliminaries.\n\n- first footnote on p.4: this is the definition of convex functions not strictly convex\n\n-----After Rebuttal-----\nThanks for the detailed response. \nI want to clarify that by comparison with MNP I did not mean for a single projection, but a comparison of OMD with the proposed variant of AFW used for projection vs OMD with MNP used for projection.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Authors adequately addressed the limitations and potential negative societal impact of their work.\n", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6-7"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents new techniques to speed up projections to submodular base polytopes. The authors gave theoretical results and some experimental evidence regarding the speed-up. I highly appreciated the rebuttal and discussion followed for this paper. 

As reviewers indicated, there is a mismatch between the theory and practice. The experiments are quite small and miss important baselines. So, it is not clear whether the proposed method is really useful. Unless the authors address this issue, the paper may not be accepted in the current format.  
Decision: Accept (Poster)