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-Wolfer 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(rt11)
(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 (T1). 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 I, 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), J 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) supzezt (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..........FF
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 cool-adjacent-violator 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 is also a light set for T. L.e. (S) ((5).
U F3 j E [K- 11, then the set S = Fr U...U
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..... ub} 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 (h(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² =*.) 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(tt), }. 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 (A))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 neew: (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()")), 1)
D use toolkit
10:
Compute aeay-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 ||x(0) x=1| S /2g Let F1, Fg...., Fg be a partition of the ground set such that (Vh(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(((t+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
Sruatinn 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
b00
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 Aiguresmmidda 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 a polymatroid with respect 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-3366, 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 groximal-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//occuunnttoo///....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": "k_NjkomMpx", "reviewer": "Reviewer_HxTZ", "summary": "This paper investigates Frank-Wolfe and Mirror Descent generalizations for combinatorial problems where projections and linear oracles can be efficiently computed or estimated using combinatorial methods. In particular, they look at enhancements when 1) limiting to the active set, which can greatly reduce search space per iteration, 2) relaxations of the combinatorial set, which combined with the first can give convergence if the new iterates are the same. ", "questions": "", "limitations": "", "rating": 7, "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": "The problem is interesting and the contribution seems interesting and novel, and very well written. However I am not an expert in this area, and cannot easily catch fundamental issues or closely related existing work.\n\nOriginality: Some of these operations, especially over cardinality based objectives, are well-known or easy / intuitive to derive. However, their mixing with frank wolfe and AFW + convergence rates seems novel, and is very interesting. Additionally, the enhancements of rounding or restricting to active set shows interesting benefits in practice. \n\nQuality: I have carefully looked through Lemma 4 proof and it looks reasonable. Lemma 5 proof does not make sense, but I think there are a lot of typos and it may not be a serious problem. Proof of theorem 2 looks reasonable. I did not check the remaining proofs very carefully.\n\nClarity: I am not 100% in this area but it was not easy for me to verify everything. I do think the paper benefits by spelling out more blatantly what are the key contributions, especially which rates are new, etc. The duality observation for cardinality --> isotonic was also interesting, but it's not clear what the dual can be used for. (That's not really a serious issue though, since duality gaps in FW are usually pretty useful to have together.) An easy example that would make several results more intuitive is to just put in the 0-norm as f and show the calculations there. \n\nSignificance: If everything is correct and novel, I think it is a significant enough contribution as the questions posed and strategies given seem very interesting and not that heavily studied. Moreover, submodular optimization has many applications in machine learning.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper has no negative societal impacts.", "review_text": "", "extra_scores": {"ethical_concerns": "The paper raises no ethical concerns. ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "KrM0x7ZAqU", "reviewer": "Reviewer_j61r", "summary": "This paper studies projections over submodular base polytopes, which appear as a subroutine of many iterative optimization algorithms. For efficient projections, the authors propose to reuse previous minimizers computed in outer iterations and to exploit combinatorial structures of submodular base polytopes. Some tools for realizing the idea are presented, and those are incorporated into Away-steps Frank--Wolfe to obtain a fast projection method, named Adaptive Away-steps Frank--Wolfe (A2FW). A convergence guarantee and experiments validate the effectiveness of A2FW. A faster projection method based on isotonic optimization is also presented for a special case of cardinality-based submodular polytopes. \n\n--- After rebuttal ---\nI appreciate the authors' kind response. After the discussion, I agreed with other reviewers that the experiments are not convincing enough and the contribution is limited. Therefore, I decreased my score to 7, though the technical contribution seems great and I think the paper can be accepted. ", "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": "Computing projections over submodular base polytopes is a fundamental subroutine of many iterative optimization methods. To my knowledge, and as mentioned in the paper, the idea of utilizing combinatorial properties of previous projections has not been well studied. I think this paper is great since it addresses an important research subject, introduces an interesting idea, and presents solid theoretical results together with a demonstration of practical utilities. \n\nBelow is a list of my comments and questions:  \n\n1. In Theorem 6, an advantage over the original AFW seems to be in the pyramidal width, and it is said that this can strictly improve convergence in the case of the unit cube. Is it possible to obtain such lower bounds on the pyramidal width for other common submodular base polytopes? \n\n2. In l. 301, the strong convexity constant, $\\mu$, is used when finding tight faces. Since $\\mu$ is defined so that the condition of the $\\mu$-strong convexity holds globally over $\\mathcal{D}$, I guess that the condition, $\\tilde{c}_{j+1} - \\tilde{c}_j \\ge 4L\\sqrt{g_t^{\\rm FW}} / \\mu$, in l. 301 is somewhat pessimistic in practice. Is it possible (and promising) to replace $\\mu$ with some parameter that characterizes local strong convexity? \n\nMinor comments: \n\n- In l. 33, it is said that \"online Frank-Wolfe is computationally efficient, but has a suboptimal regret of $O(T^{3/4})$ [23, 8]\". However, the regret bound is improved to $O(T^{2/3})$ in [8].  \n\n- I could not find the definition of $E$ before l. 103, where $1/(2|E|^2)$ appears. It is better to define $E$ somewhere before l. 103. \n\n- l. 140: $\\nabla (y)$ -> $\\nabla \\phi(y)$  \n\n- l. 243: doing restricting -> restricting\n\n- l. 276: we instead we just -> instead we just\n\n- l. 406: lipschitz -> Lipschitz\n\n- l. 413: polyak-lojasiewicz -> Polyak-Łojasiewicz\n\n- ll. 446 and 465: wolfe -> Wolfe\n\n- l. 487: frank-wolfe -> Frank-Wolfe", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations are adequately discussed. The paper seems to have no negative societal impacts. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "EzbgStaaUFp", "reviewer": "Reviewer_fArf", "summary": "Iterative methods like gradient (and more generally mirror) descent require a projection step which can be expensive. This paper studies how to re-use information from previous projection steps to speed up a projection at the current iteration. In particular, authors focus on the setting where the underlying convex constraint set is a submodular polytope. In this way, the current paper differs from previous work on re-using projection information by working in a combinatorial framework, given by the submodular polytope. \n\nThere are two main contributions. First, a $O(n log n)$ time algorithm is given for computing projections over a submodular polytope where the submodular function is so-called cardinality based, i.e. $f(S) = g(|S|)$ for a concave function $g$, which improves upon the best known time of $O(n^2)$. The second contribution is a suite of subroutines for using previous projection information to improve the runtime of current projection. An away-FW variant is proposed which uses these subroutines. Finally, these methods are shown to improve the runtime of mirror descent compared to when vanilla FW is used for the projection step.\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": "The authors clearly explain the research problem (including its significance), the methods used to address the problem, and the extent to which these methods improve current state of the art. \nIn this sense, the paper is well organized, although there are a number of typos, several of which I list below.\n\nThis work is interesting and insightful, as it addresses the broader algorithmic question of moving beyond viewing certain subroutines (here, the projection step) as black boxes. It is unlikely that this “toolkit” provides improvements in worst-case runtime of mirror descent over submodular polytopes, but authors demonstrate how it does indeed improve performance on a simulated example.\n\nThere are a few minor downsides to the paper. The first is that while the main contribution seems to be practical algorithmic variants, no open source software is provided. The second downside is that the experimental section is not well-discussed. For example, it is not clear which submodular polytope is being used in the first simulation. The details of the second simulation appear in the appendix and not the main body (although I understand that space constraints may have been an issue here). Finally, I do not understand what the shaded regions in the plots are referring to. Because the main results of the paper are practical algorithmic variants, I think that the paper would benefit if slightly more emphasis was placed on the empirical results.\n\nThere are a number of typos or confusing aspects in the paper and I list some here. Authors should review carefully before a camera ready submission.\n1. P1 and P2 are often references but never explicitly, mathematically defined. Consider writing them as display equations with tags.\n2. Line 64: “and their exist instances” should be “there”\n3. Line 75: the current best known runtime can be listed as “O(n^2)” for brevity rather than “O(n log n + n^2)”.\n4. Line 101: “The second one rounding tool is algebraic” remove “one”\n5. Line 101: “is useful for base polytopes of integral submodular functions”. I believe you should replace “useful for” with “applicable only to”\n6. Line 134-138: In definitions of $mu$-strongly convex and $L$-smooth, put the dash outside math mode so that it is short, do not put it inside math mode, i.e. $L-$smooth looks bad but $L$-smooth looks better.\n7. Footnote: I believe the definition of strictly convex should have a strict inequality there.\n8. Line 189: What does “EO” mean here?\n9. Line 216: “We will show this theorem infers a near-optimal number of tight inequalities” what do you mean “near-optimal”? Perhaps use the phrase “most of the tight inequalities” instead.\n10. Line 221: “Let $f$ be a monotone submodular with” either add “function” or remove “a”.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "All ethical concerns have been addressed and acknowledged.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "36RDs8xHhFA", "reviewer": "Reviewer_AdYT", "summary": "The paper considers the problem of computing a Bregman projection onto the base polytope of a submodular function. The paper makes two main contributions. The first contribution is to extend existing work for the permutahedron to the base polytope of any cardinality-based submodular function, i.e., a function of the form f(S) = g(|S|) where g is a concave function. Compared to prior work, this results is faster by a factor of n in the number of function evaluations. The second contribution is to design a faster implementation of the Frank-Wolfe algorithm with away steps. This is achieved via a sequence of step optimizations that are designed to reuse information gained in previous iterations in order to detect tight inequalities, reuse active sets, use tight inequalities in the linear optimization step, and round approximate projections to exact projections. The paper evaluates the effectiveness of the proposed speedups on very small scales instances (n=25) where one uses the Bregman projection algorithm as part of an online learning algorithm with the feasible domain being the permutahedron.", "questions": "", "limitations": "", "rating": 5, "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": "Significance: Computing projections onto the submodular base polytope is a challenging problem in practice, and existing algorithms do not scale to large problem instances. The current paper introduces a series of tools that aim to use the combinatorial structure together with the Frank-Wolfe algorithm and obtain improved running times in practice. The correctness of the proposed step optimizations is established via principled proofs. On the negative side, the empirical evaluation is conducted on very small instances (n = 25) and only Frank-Wolfe variants are considered in the experimental evaluation. Thus it remains unclear whether the proposed algorithms scale to larger instances and other choices of base polytopes.\n\nNovelty/originality: The main algorithmic novelty is in the design of the step optimizations used to speed up the Frank-Wolfe algorithm. The result for cardinality-based functions seems to be an extension of prior work for the permutahedron. On a technical level, the proof of correctness for the step optimizations seem to be relatively straightforward. Although the optimizations are a valuable and solid contribution, the paper seems to have somewhat limited algorithmic innovations and the experimental evaluation is quite limited as well.", "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": "I did not track the hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The majority of reviewers thought that the contributions of this paper in terms of efficient projection onto important submodular polytopes and combinatorially-inspired tool-kit for optimization over an important class of such polytopes, which is demonstrated via the introduction of a new Frank-Wolfe method with a novel convergence rate, are interesting and novel beyond the acceptance bar, and may arouse further research along these lines.
I encourage the authors the take the reviewers comments into consideration in the revised version.
Decision: Accept (Poster)