Fast Stochastic Composite Minimization and an Accelerated Frank-Wolfe Algorithm under Parallelization
Authors: Benjamin Dubois-Taine
Francis Bach
Quentin Berthet
Adrien Taylor
Venue: NeurIPS 2022 Accept (2022)
Keywords: Frank-Wolfe
Conditional Gradient
Acceleration
Randomized Smoothing
Convex Optimization

Abstract: We consider the problem of minimizing the sum of two convex functions. One of those functions has Lipschitz-continuous gradients, and can be accessed via stochastic oracles, whereas the other is ``simple''. We provide a Bregman-type algorithm with accelerated convergence in function values to a ball containing the minimum. The radius of this ball depends on problem-dependent constants, including the variance of the stochastic oracle. We further show that this algorithmic setup naturally leads to a variant of Frank-Wolfe achieving acceleration under parallelization. More precisely, when minimizing a smooth convex function on a bounded domain, we show that one can achieve an $\epsilon$ primal-dual gap (in expectation) in $\tilde{O}(1 /\sqrt{\epsilon})$ iterations, by only accessing gradients of the original function and a linear maximization oracle with $O(1 / \sqrt{\epsilon})$ computing units in parallel. We illustrate this fast convergence on synthetic numerical experiments.

Fast Stochastic Composite Minimization and an Accelerated Trank-Wolff Algorithm under Parallelization
Benjamin Jubois-Taine
Francis Bach
DI ENS, Ecole normale supérieure, Université PSL, CNRS, INRTA 75005 Paris, France
DI ENS, Ecole normale supérieure, Université PSL, CNRS, INRIA 75005 Paris, France francis. bach@inria.f fr
benj amin saauul-ddduoii-ttteennriaaae
Quentin Berthet
Adrien Taylor
Google Research, Brain team, Paris qberthet@google.com com
DI ENS, Ecole normale supérieure, Université PSL, CNRS, INRIA 75005 Paris, France adrien. adrien. taylomnnaaylrrdiiii.....
Abstract
We consider the problem of minimizing the sum of two convex functions. One of those functions has casschit--ontinuuuss gradients, and can be accessed via stochastic oracles, whereas the other "simple". We provide Bregman-type algorithm with accelerated convergence in function values to ball containing the minimum. The radius of this ball depends on problem-dependen constants, including the variance of the stochastic oracle. We further show that this algorith- mic setup naturally leads to a variant of Frank-Wore achieving acceleration under parallelization. More precisely, when minimizing a smooth convex function on bounded domain, wc show that one can achieve an primal-dual gap (in expecta- tion) in Ó(1/ /c) iterations, by only accessing gradicnts of the original function and linear maximization oracle with O(1/ /c) computing units in parallel. We illustrate this fast convergence on synthetic numerical experiments.
Introduction
We consider the composite minimization problem
min
(F = + + V
(1)
where V is some real vector space equipped with norm ||-|| and an inner product :) see Section 2 for details. For instance, one can consider V = R2 or V = R2* equipped with the standard Euclidean inner product and norm. The function is convex and 8-smooth and the function H is p-strongly convex, both with respect to (w.r.t.) some norm ||-II on V (see Section 2 for precise definitions). We assume that H "simple", meaning that one can efficiently solve
arg min yEV
{(z, v) H(y) + aD, 20)
where D... is the Bregman divergence induced by strongly convex function w. For instance, when the standard squared Euclidean norm, this amounts to computing the proximal operator H.
36th Conference on Neural Information Processing Systems (NeurIPS 2022).

---

When deterministic gradients of G are available, an accelerated method relying on (2) and achieving was proposed by Diakonikolas and Guzmán [13, AGD+].
rates of the form O exp k
In this work, we are interested in the case where G only available through a stochastic oracle. In particular, we provide an accelcrated algorithm converging in function values to neighborhood of the minimum with the same rate as above. The size of the neighborhood is of order VHB
where o² is the variance of the stochastic gradients. The dependence of the noise term on 1/VJuB 1 is similar to that of previous stochastic accelerated methods in simpler settings, see, e.g., [3]. Although our rate is an extension of the result in [13], the parameters are different and tailored for the stochastic setup.
In Section 4, we focus on minimization problems over a compact convex set K for which we have access to a linear optimization oracle, just as in the Frank-Wole algorithm. Formally, we consider gradicnts. In that case, the dual
solving min fx) where f is convex with Lipschitz-continuonn problem can be seen as a particular instance of (1) where H := f is the Fenchel conjugate of f, and only be accessed
G' is smoothed version of the support function of K. Such smoothed functions through a stochastic oracle whose computation boils down to solving a linear optimization problem on K. An appropriate choice of to allows us use the algorithmic framework by only computing gradients of f and solving linear optimization subproblems over K. In short, minimizing / over the set K with an c primal-dual gap requires Ô |max Ve em
. }) iterations when m computing units can be used in parallel (cach of them only solving linear optimization subproblems on K). In particular, when m 1/vi, this effectively yiclds an accelerated rate of Ô (1/vz) iterations with a single gradient evaluation per ileration to achieve the required accuracy.
We emphasize that the first contribution of this work is to provide an accelerated method for general stochastic composite problems (in Section 3). In Section 4, we then show that can be used for obtaining an accelerated Frank-Wolfe algorithm.
1.1 Related Work
As previously emphasized, the main algorithmic ingredients which inspired this work were devel- opped by [13] and [19]. For further references on acceleration and gradient-baset composite convex minimization, we refer to the original works [38, 40] or to recent survey [15]. For the stochastic sctup, we refer [32]. We refer to [39, 12] for further references and pointers on those topics.
Let us briefly describe the main differences between this work and [13, 19]. First, Gasnikov and Nesterov [19] obtain accelerated rates similar to ours when the strong convexity assumption is placed on G instead of H here (which has practical consequences, including well-posedness of (2) and the size of the constants and μa, see discussion in [13, Introduction)). When the gradients of G are stochastic, [19] provides convergence rates, but only when the underlying norm is the Euclidean norm. Finally, whereas Diakonikolas and Guzmán [13] consider more general assumptions in the deterministic non-Euclidean casc, our work also covers stochastic approximations. We emphasize that each assumption we make (namely accelerated, stochastic, proximal Bregman methods) necessary to yield accelcration of Frank-Wolfe under parallelization in Section 4.
Two key observations underlying this work are on the one hand the duality link between Frank-Woll methods and Bregman methods [4], and on the other hand randomized smoothing techniques [41, 14, 1, 2, 7, 8] which can be naturally computed using linear optimization steps. The main question of interest was whether accelerated Bregman methods should naturally give rise to accelerated Frank-Wolfe methods on the dual.
The Frank-Wolfe (FW) method (a.k.a. conditional gradient method) and its variants were first introduced by Frank and Wolfe [16] (see also [27, 26] for more modern presentations). When considering optimization over a convex set K, classical first-order methods are often naturally embedded with a projection operator (onto K). Depending on K, those projections are potentially costly. An alternate approach for taking constraints into account within first-order method consists in using línear optimization oracles (a. Frank-Wolfe techniques). In many applications, such linear minimizations are much cheaper than projecting onto the feasible set, see for example [17, 23]. Despite its wide use in practical applications, the main drawback of the Frank-Woll method lies in its slow convergence rate of O(1/s), standing in sharp contrast with the (1/ve) convergence of Nesterov's 's accelcrated gradient descent [38] relying on projections.
2

---

As "purely accelerated rates of convergence are out of reach for vanilla Frank- Wolfe methods (see lower complexity bound in [33]), most works on accelerating Frank-Wolfe have focused on exploiting specific additional assumptions on the problems at hand. Common such assumptions include strong convexity of the feasible set [11, 35, 18], and strong convexity of the objective function along with the assumption that the minimizer lies in the interior of the feasible set [21, 31]. In both cases, Frank-Wolfe is known to improve on the O()+) rate. Some efforts have also gone into finding rates matching performances of Nesterov's 's accelerated gradient descent [38] without strong convexity. In particular, when K is a polytope and when a certain type of constraint qualification is satisfied, Frank- Wolfe converges asymptotically at rate (1/x²) [5]. Adding momentum to Frank-Wolf has also been studied, and accelerated rates are attained on some E--norm balls when the minimizer is on the boundary of the feasible set [36]. Our approach in this work is orthogonal to the aforementioned results, in that we do not make additional assumptions on the objective function or the feasible set, but instead show that parallclization can help reaching accelerated rales for a variant of Frank-Wolle Note that [34] manages to reach a similar rate of (()v=)) iterations for a variant of Frank-Wolfe, where each iteration requires one gradient evaluation and ((1/v)) calls to a linear optimization oracle. However, in contrast with our algorithm, their approach is non- non-parallelizable as the calls to the linear optimization oracle need be made sequentially.
The rest of the paper is organized as follows. In Section 2 we define notations and review some classical definitions from convex analysis. In Section 3 we provide worst-case rates for stochastic algorithm, along with some intuitions and proof sketches. In Section 4 we show how a Frank-Woll, method directly fits within this framework, thereby obtaining accelerated worst-case guarantees on the primal-dual gap. In Section 5, we illustrate our theoretical findings on a set of simple numerical examples.
Bregman dual-averaging-Vy
2 Notation and definitions
Formally, we consider a real finite-dimensional vector space V and its dual space V consisting of all lincar functions on V, as well as a dual pairing denoted by (,, V x V + R, and a norm II-11 V + R. We also consider the corresponding dual norm Il-Il. : V - induced by the
choice of ||-1| and - using | = supp||>/s (z, z.). For instance, one can use V V Rd or
V = R equipped with the standard Euclidean inner product and norm. We insist on the fact that the formal notation V and V is used mostly for emphasizing differences between primal and dual spaces/problems below. For a closed, proper, convex function V/ V - R. we denote N (x) the set of all subgradients of V at When (x:) is singleton, we denote its single element by (vr)..
=
Definition 1. V V -> IR is L-smooth w.r.f. |1-I1 for all x. y E V,
[V) V S || vll-
(3)
The following proposition will be helpful throughout the paper (see [39] for a proof). Proposition V. V >> L-smooth w.r.f. ||-I| if and only for all a. y E V,
L
Vxx) < (v)) + (V)()), v)
211²
2
Definition 2. V: V - R is p-strongly convex w.E.t |1-11 for all xr E V and any go(v) E (v).
(x) 2 (y) + (ov (v), x - y) + / | y11²
(4)
2
Definition 3. For a closed, proper, convex function V + R. its conjugate function is defined as V (>())
sup (z, x) V(x). =EV
(5)
For later references, we need few results related to smoothing the support function of set K C V (K' will appear as convex set in the dual problem to (1)).
Definition 4. For a set K C V we define I as the indicator function of K, ie., Ix(x) = 0 for K and I (x) = 0o for x V K. The support function of K is defined as
s(y) = sup (x,, V)-
(6)

---

If K is non-empty, convex and closed, the indicator and support functions of K are conjugates of each other, i.e., (Ix)* = and s' = (Ix)** |K [42]. The support function is convex yet not differentiable in general applicationn.. For the purpose of our work, we consider smoothing the support function via randomization. Such stochastic smoothing has recently gained popularity in the optimization literature, see for example [41, 14, 1, 2, 7]. We define the main tools and state the relevant properties behind this idea.
Definition 5. For set K C V scalar 0 and random variable A, define the smoothed support function of K as
Sa (v) = Es (s(y + aa)]] = Es
sup LEEK
(z, + +aA)
We will use the following proposition on the smoothed support function, proved in [7].
Proposition 2. Suppose K C V is convex compact and let Rx maXxeK || Suppose the random variable A has positive differentiable density dz(z) x exp( (oo(-n(2)] (z)(d= for some function ny-),
and let 2 = E { [IV [
Then So is convex, Rg -smooth w.r.f. ||-I| and for any y E V,
(y) = EA
arg arg (a, y + +as) and s(y) S s2 S s(y) a. (0). =EK
Fast Stochastic Composite Minimization
In this section we focus on solving the composite problem
min yEV (F(y): : G + Hy)),
(8)
where G is convex and B-smooth, and H is p-strongly convex w.r.t. ||-I], Algorithm 1 summarizes our proposed algorithm, which resembles the general AGD+ algorithm from [13]. Notable differences include access to gradients G through a stochastic oracle, and explicit dependencies on the smoothness and strong convexity constants for the different updates. Moreover, the presented analysis is different and specifically tailored to handle stochasticity in the gradients of G.
An actual implementation of Algorithm 1 requires the ability to efficiently solve the minimization step (13), which should well-defined. This intermediate minimization subproblem often referred to as a Bregman proximal problem, and a sufficient condition for this operation to be well-defined is to require w to be strongly convex. In the case where w is the Euclidean norm, (13) amounts to computing the proximal operator of H. Considering general regularizer has several benefits, in that the Euclidean norm might not well capture the geometry of the problem, and because particular choices of might make (13) casily solvable. The latter will become particularly clear in Section 4.
Before we move on to the analysis, let us emphasize that the first step of Algorithm consisting in picking =o E arg min, w(y) is not restrictive. Indeed one could instead pick any 2o E V and set (ūyy) = w(y) (gw,(2)). ; y) where (20) E @w(z One could then run Algorithm with the "shifted" v instead w. Doing so does not change the complexity of the minimization step (13), and the following analysis remains unchanged.
We are now ready analyse Algorithm For this purpose let us define
A-1
Ch =
- A.) - (VG(), va))-
1=0
where the sequences {Aa heess and {yK)AEN are defined in Algorithm 1. We also use the notation E, for denoting the expectation at iteration h: conditioned on the previous iterations (that is, E, shortens E = E[[ yk: =k: de, ct)), while E denotes the total expectation. Before we can state our results, we need one more assumption on the stochastic gradients.
Assumption 1. For any k N, the stochastic gradients satisfy Ea[gx] Eg l19+ Vl( 0².
VG(vk) and
The assumption on the variance of the stochastic gradients is common when studying stochastic first-order methods, and allows proving the next proposition, which relates consecutive iterations.

---

Algorithm Stochastic Composite Minimization
Input: (5, jr, 2). 3-smooth function G, ju-strongly convex function H, v-strongly convex function u.
all w.r.t. the same norm ||-Il-
Pick 20 C arg min, y w(y) and set y/ = 2p.
Set Ao 0 and dg = 0.
for k = 0, 1,... do
Ax+1 1 (alu+23+vn0)--- +B++ ( + (20
(9)
2(3+vaB)
Th Av-1
(10)
Ub (1 Th Wi Tk2R
(11)
Compute a stochastic gradient of function G at iterate
dx+1 = d3 + (AN+1 - Ax)gk
(12)
2k-1 E arg min {14++1, y) + A Bw(y)}
(13)
NEV
Mk+1 (1 (1-Ti) Tz)yik Th+2++1
(14)
end
Proposition 3. Suppose Assumption holds and let mx(y) = (dk: y) + AgH(y) + (w(y). At iteration k, the iterates of Algorithm I satisfy
o²
Eg [Ax+ + 1 (1k+1)) mx+1 (Zx+1)) S A+F(yx)) my (Zx) + (AR+1 Ax) 2/p3
(15)
We defer the full proof Appendix A, but highlight the main steps here. This way we also hope to shed light on the update of A&+1- The first step is to compute an upper bound on (et+G(y+++) depending on Gyyk) The second step is similar, and computes upper bound AR+ H (ux+1) depending
on A₁ H (Jk). Summing up the two inequalities and taking expectations yields inequality (15) with
an additional term in || =ull.. To exactly obtain inequality (15) we set A&+1 so to cancel
out the coefficient multiplying | 2x 1² This turns out to be equivalent to setting Ak+1 the root of a quadratic polynomial, explaining the form of update (9) in Algorithm 1.
Proposition 3 allows us to get the final rate of convergence of Algorithm 1. We again defer the proof to Appendix The idea here is first to unroll the recursion (15) so as to get constant term on the right-hand side of the inequality. We then relate (NNZN) mn (y.) and to the minimum of F and
finally, we show that A&t1 2 A (1+ ((VB-VH)
V/ which gives the exponential decay term.
Theorem 1. Suppose Assumption 1 holds, let y- E arg min and define Dw yo) = w(y+) un(y)) 0. The convergence rate of Algorithm after l iterations is
((F())) - F(y.)) S exp ( 2
(
o²
3 (v.
(16)
VP)
2vBB
This rate typical accelerated rate, In the (usual) case where μ S 3, exponential decay bounded above by exp (- which shows the natural dependence /5. In addition,
the neighborhood term is of the form x² which is again typical of accelcrated stochastic VHS
methods [3]. Note that w w(y+) (yo) is equal to the Bregman divergence (w yo) = w(y+)
w(No) (g., (vo); V+ - yo) (with (y0) E @wr(y)) through the choice 9av (Jn) = 0 E (w))))
which valid as yo minimizes wr.). We emphasize that we do not require differentiability the function anywhere.
In the next section, we show how the above algorithm can be directly applied a smoothed dual of a minimization problem over a compact convex set, yielding a variant of the Frank-Wolfe algorithm which can achieve accelerated rates under parallclization.
5

---

4 Accelerating Trank-Wolft with parallelization
We consider the following minimization problem over a compact convex set K C V
min #
{f(z) [x))),
(17)
where f is convex and L-smooth w.r.t. ll-1l,. Its Fenchel-Rockafellan dual [42] reads
max
{d(y) : s(- ( (v)) #EV
(18)
The smoothness of f implies that f* is 1/n-strongly convex w.r.t. ||-I| [43, Proposition 12.60]. The term in is however smooth w.r.t. II-I1, which prevents from directly applying results from the previous section. Instead, we choose some smoothing parameter a > 0 and, following Definition 5 and Proposition 2, we consider the smoothed minimization problem
min
(sa(-v) + (v)) yeV
(19)
Problem (19) fits within the framework of (8) with G(y) sa(-v). H()) f 1/2 and Rx M Using Proposition 2, see that an unbiased stochastic gradient 9 of G at some point y can be obtained by sampling A and computing g = arg m (u, oA) This boils down linear optimization oracle over K, the same oracle that of the Frank-Wolfe algorithm.
We now show how to pick the distance generating function w such that the minimization step of Algorithm 1 has closed form. Recalling that must minimize w, we set w(y) = (v) (gr- (2o), y) where (z0) E
(z)) Clearly, w is 1/L-strongly convex w.r.t. ||-I| and is minimized 2p. Moreover, first-order optimality conditions for the minimization step (13) of Algorithm read
Rx (0f*(EN+1) gy- (20))
0 E dk+1 + *A+100f (Ex+1) +
(20)
a
Mx
dx+1
(2+(1) Att1 + R 95- (2a)
(21)
A + R
Choosing some To K and setting 25 V fxxx) for all k, one can replace (21) by
R M
ds+1
Ak+1 + RxM To
A + Rx
(22)
Doing this allows to avoid computing subgradients of f". Instead, whenever the value of 2 is needed, compute V (xxx). We summarize this fully primal algorithm in Algorithm Note that similar tricks to obtain "dual-free" methods have already been used, see for example [32, 46, 25, 10, 28).
Observe that each itcration of Algorithm 2 requires the computation of one gradient of f. and calls to linear maximization oracle. When m = 1, an iteration Algorithm 2 is as costly as one itcration of -ollfe. We now show how further exploit parallelization. To do so, need to ensure that using multiple samples appropriately improves the quality the approximation of the true gradient. This the point of the following assumption.
Assumption 2. There exists norm-dependent constant Pli ll. such that the variance verifies
AR
0²
Ex
Σ gk, - VG(m))
(23)
m
Remark 1. few examples are in order. For the standard Euclidean norm holds that Pll-Ila 1. For Ey norms a space of dimension d, we have
|| -1-
||+ = || lll it
(8/v-1 1
for S <
Pll-1p
for S < oo for co.
(24)
e² (log [log++1) 1)
In the general case, as all norms are equivalent in finite dimensional spaces, there exist constants C. > 0 such that c 1ll-112 < Il. - C 11-112 Then P1-11. I -. We refer to Appendix B.3 for more details and references.
C²
6

---

Algorithm 2 Parallel Frank-Wolfe (PFW)
Input: (L, To, Rg: ; M, m, a, T). L-smooth convex function w.r.t. |l 2o E K, Rx
m K ||,]|,, distribution with density (z) & exp(-n(2))ds such that M = EA [V
m computing units in parallel, smoothing parameter a, number of iterations T.
Set Ao 0, do 0, R 1
2. yo fx(o)).
for k 0, T do
A&+1 A +B
2(3+/p8)
Th 1 Apt1
At
0k- = (1 - -T + Tk V
For all E [m] parallel, sample A di, compule gk.i arg max (u, - + aa.))
m
9k Σ g
dx+1 d2 + (Ak+1 Ax)gı
1k+1 ARt:t N0 A++I+H d2
3k+1 = (1-Tk)yk + V (
end
As mentioned earlier. one can directly obtain convergence of the dual problem (19) by applying The- orem 1. The next theorem states that not only are the iterates { always feasible, but also that the previous rate of convergence also holds for the primal-dual gap between the iterates (Ix JAN and {uk jken. For simplicity of the exposition we assume that Rx M 2 +. In practice this is not an issue since we will choose small values of a.
Theorem 2. Suppose f is convex and L-smooth w.r.t |1.11. and let so E K. Under Algorithm 2, the primal iterates are always feasible, i.e., Ty E K for all N. Moreover, after k iterations, we have
E (xxx) - d(yr)) & exp (- (-k: (-kiav --iAVLRR RxM (S(zo) f(x=))
Va
2R
al
+ (0))
Rg
The above convergence result is oblained by first plugging the smoothness and strong convexity constants of this section within the result of Proposition 3. Then, one has relate my (zx) the primal objective fæx)). The first term in the upper bound then follows by recursion. The second
term comes from the variance, which can be bounded by 4Rke1-1 when m stochastic gradients are computed parallel. The last term as (0) due the error induced by the smoothing of the dual. The full proof can be found in Appendix B. From Theorem 2 we are able to show that Algorithm 2 achieves acceleration under parallelization.
Theorem 3. Suppose f is convex and L-smooth w.r.t. ||-|1, and let zo K. Under Algorithm with
min
Mc2m²
the number of iterations required to achieve an primal-duu dual gap,
(0) 36LR
ie., ([S(TA) d(yx)) S 6,
1 LLRKMM
(3RxM(f(zo) (xxx)) s(x.)))
k
log
(25)
Va
6a
The complexity is therefore ò maxx
The above complexity result shows that (i) when m = 1/V7, we get an accelerated rate 0(//z). (ii) when m = 1, we recover the classical ((//)) complexity of Frank-Wolfe (up to logarithmic terms), (iii) there is no theoretical gain in going beyond m 1/ve computing units in parallel.
Moreover, while the total number of calls to the linear optimization oracle to reach an primal-dual gap the same Frank-Wolfe for any value of m. in the case where m > 1, the number of required

---

gradients of f is strictly less than in Frank-Wolf This is because in each iteration of Algorithm 2 we compute one gradient of no matter what the value of m is. In particular, when m = 1/v5, we need only (1/VA) gradients of f in total, compared to (f/e) in Frank-Wolfe.
One can nole that the proposed algorithm in not as universal as the classical Frank- Frank-Wolfe method, as it requires upper bounds on several problem-specine constants. However, acceleration of Frank-Wolfe has been extensively studied in the literature (see Section 1) and to the best of our knowledge our work is the first to provide accelerated rates (under parallelization) without further assumptions on the constraint set and/or the objective function. We argue next that estimating upper bounds on most parameters does not pose significant challenges. Indeed, as the user is free to pick any distribution to sample A from (up to the assumptions of Proposition 2), one can choose distribution for which the constant M is casy to compute (we give two examples in Section 5). Moreover, the user typically knows the set over which the optimization is carried over, and from such knowledge upper bound on the diameter can often be casily computed. Finally, we also need to upper bound the Lipschitz constant L of the gradient. This seems to be more of a limiting factor compared to classical Frank-Wolle although an upper bound on L is often (but not always) necessary to implement other accelerated versions of Frank-Wolls problem using some sort of line search within our method, it is not straightforward as the smoothing of the dual induces stochasticity, and obtaining theoretical rates for line search techniques on stochastic objectives is notoriously tedious [9, 44, 45].
[18, 34] well. While it might be possible circumvent this
Finally, note that it might seem like small modification to Algorithm 2 could give variant of Frank- Wolfe capable of handling stochastic gradients of f (for previous works on stochastic Frank- Wolfe, [24, 20, 37] and references therein). Indeed, one could the noise in V fxxx in the update of " as the random variable A itself and study the resulting algorithm. However, the current analysis would only work if the noise on V (xxx does not depend on the current iterate. Moreover, even under this simplifying assumption, the result does not follow immediately as the stochasticity would appear in both the updates of uk and + 1, in contrast with the current analysis.
5 Experiments
We first consider minimizing a quadratic function in Rd over the simplex
min (f(x)) = || b1l2) where K₁ sc K
Rd
x 2
0,
(26)
where Raxd and b R.. We choose A have the Gumbel distribution [22] with location and scale parameters equal to and respectively. In this case Rx, = 1 and M = vdl (see Appendix C for details). We set n = 200, d 50 and compare the bound from Theorem 2 with the practical performance of Algorithm 2 for both m = 1 and m 1/va parallel computer(s). Fig. 1 shows that our upper bound captures well the speed of convergence to a neighborhood.
10a
Primal-dual --dual gap
101
10
10-3 3
10a
10a
10a
10
10a
10a
Iteration
Itcration
Algo 2 (m = 1) --- Thm. 2 (m = 1) Algo 2 (m = +
Thm. 2 (m-
<a
Figure 1: Comparisons between the behavior of Algorithm 2 and that of its theoretical upper bound (see Theorem 2) on least-squares problem on the simplex for a = 10-2 (left) and a = 10-3 (right). The plots report the value of the best primal-dual gap incurred the current iteration.
8

---

Next, in order to circumvent the inevitable stalling due to the fixed value of a observed above, we suggest restarted algorithm which decreases the value during training. Starting from a and some z0 K, we run Algorithm 2 for To iterations with m computers in parallel to obtain some approximate solution Za K. We then decrease a by a constant factor c < and run Algorithm 2 again with the new value of a starting from Z We repeat this process until satisfying solution is obtained. We formalize this procedure in Algorithm 3. In practice we choose c 0.5 and set
Ta
4 log 1 as a simplified version of the bound (25), and run the above procedure for both ma and ma 1/va computers in parallel.
Algorithm Restarted Parallel Frank- Wolfe (R-PFW)
Input: 20, Rx, M, c). L-smooth convex function f, f. E K, Rg max |||| with density dr (2) & nd) such that M EA |// A) II Set a = for i 1........ do
distribution decreasing factor
Set Ta -/= log and either set ma Ta Algorithm 2(L, To, RK, M, ma Ta) Set 3o Fa and a co. end
1 or ma Ja
Return Zo..
We the restarted scheme on problem (26) as well as on generalized matrix completion problem over the trace norm ball,
min (f2(z):- |IC D1 where K2 (X E RPx4 |X = XCR2
(27)
where C' E RRx2 and D E RPxq, Here || stands for the Frobenius norm and ||-Ile-- is the trace, nuclear, norm. We choose A have entries distributed according to standard normal distribution. In this case Rx₃ = 1 and M = /pg. We compare the restarted scheme with the Frank- Wolfe algorithm 2 (denoted FW in the plots) and with exact line search (denoted FW-LS in the plots). We set = 10, 8 and plot the results in Fig. 2. For both problems, we observed that using M = instead of the theoretical value (M = vd for (26) and M /Pq for (27)) led to significant speedups. We consequently plot both strategies. We observe that for m, = 1/va, Algorithm 3 significantly outperforms Frank- Wolfc, and for m. 1 the performance is similar to Frank- Wolfe, which was expected from the discussion at the end of Section 4. Full code to reproduce the experiments can be found at the following link: https // ///gtttttbbb com/bpauld/PPW.
with step-size π I
(a) M = Vd
(b) M= =1
(c) M
Pq
(d) M =
10a
10
Gap
10 2
10 8
10a
10a
10a
10
10a
10a
10a
10a
10a
10a
10a
10a
Iteration
Iteration
Iteration
Iteration
FW-LS
Algo (ma = 1)
Algo 3 (m
Figure 2: Comparisons between Frank-Wolfe and the restarting scheme (Algorithm 3): a least-squares problem on the simplex ((a) and (b)), and a generalized matrix completion problem on the trace ball ((c) and (d)). The plots report the value of the best primal-dual gap incurred at the current iteration.

---

Conclusion
In this work we introduced stochastic proximal Bregman algorithm able to converge neighbor- hood of the solution the same accelerated rate as its deterministic counterpart. We then used to design variant of the Frank-Wolfe algorithm able to achieve accelerated rates under parallelization. One drawback that the resulting algorithm is not "any time", in the sense that the desired precision e must be given
input to the algorithm. We circumvent this by designing simple heuristic which slowly decreases the value of e. We plan to investigate the theory for this restarted algorithm the future. We also hope to use randomized smoothing techniques similar to the ones used in the work to obtain stochastic Frank- Wolfe methods.
7 Acknowledgements
The authors acknowledge support from the European Research Council (grant SEQUOIA 724063). This work was funded in part by the french government under management of Agence Nationale de la recherche part of the "Investissements d' d'avenir" program, reference ANR- ANR-19-P3IA-000 (PRAIRIE 31A Institute).
The authors would like to warmly thank Alexander Gasnikov for very constructive remarks and for pointing out the existence and relationship our work with [34, 20, 28, 10].
References
[1] Jacob Abernethy, Chansoo Lee, Abhinav Sinha, and Ambuj Tewari. Online linear optimization via smoothing. In Conference on Learning Theory (COLT). 2014.
[2] Jacob Abernethy, Chansoo Lee, and Ambuj Tewari. Perturbation techniques in online learning and optimization. Perturbations, Optimization, and Statistics, page 223, 2016.
[3] Necdet S. Aybat, Alireza Fallah, Mert Gurbuzbalaban, and Asuman Ozdaglar. A universally optimal multistage accelerated stochastic gradient method. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
[4] Francis Bach. Duality between subgradient and conditional gradient methods. SIAM Journal on Optimization, 25 2015.
[5] Francis Bach. On the effectiveness of Richardson extrapolation in data science. SIAM Journal on Mathematics of Data Science, 3(4): 2021.
[6] Keith Ball, Eric Carlen, and Elliott H Lieb. Sharp uniform convexity and smoothness inequalities for trace norms. Inventiones mathematicae, 115(1):463-482 1994.
[7] Quentin Berthet, Mathieu Blondel, Olivier Teboul, Marco Cuturi, Phinlpph Vert, and Francis Bach. Learning with diffcrentiable pertubed optimizers. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
[8] Mathieu Blondel, Quentin Berthet, Marco Cuturi, Roy Frostig, Stephan Hoyer, Felipe Llinares- López, Fabian Pedregosa, and Jean-Philiphs Vert. Elficient and modular implicit diffcrentiation. arXiv preprint arXiv:2105.15183 2021.
[9] Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. Siam Review, 60(2):223-311, 2018.
[10] Michael B Cohen, Aaron Sidford, and Kevin Tian. Relative lipschitzness in extragradient methods and a direct recipe for acceleration. In 12th Innovations in Theoretical Computer Science Conference (ITCS 202/), volume 185, 2021.
[11] Vladimir Fedorovich Demyanov and Aleksandr Moiseevich Rubinov. Approximate methods in optimization problems. Elsevier Publishing Company, 1970.
10

---

[12] Olivier Devolder. Exaciness, inexactness and stochasticity in first-order methods for large-scale convex optimization. PhD thesis, PhD thesis, ICTEAM and CORE, Université Catholique de Louvain, 2013.
[13] Jelena Diakonikolas and Cristóbal Guzmán. Complementary composite minimization, small gradients in general norms, and applications to regression problems. arXiv preprint 2101.11041, 2021.
[14] John C. Duchi, Peter L. Bartlett, and Martin Wainwright. Randomized smoothing for stochastic optimization. SIAM Journal on Optimization, 22(2):674-701, 2012.
[15] Alexandre d' Aspremont, Damien Scieur, and Adrien Taylor. Accelcration methods. Foundations and Trends@ in Optimization, 5(1-2):1 245, 2021.
[16] Marguerite Frank and Philip Wolfe. An algorithm for quadratic programming. Naval research logistics quarterly. 3(1-2):95-110, 1956.
[17] Robert M. Freund, Paul Grigas, and Rahul Mazumder. An extended TrankWolffe method with "in-face" directions, and its application to low-rank matrix completion. SIAM Journal on optimization, 27(1):319-346, 2017.
[18] Dan Garber and Elad Hazan. Faster rates for the frank-wolfe method over strongly-convex sets. In International Conference on Machine Learning, pages 541-549, PMLR, 2015.
[19] Alexander Gasnikov and Yurii Nesterov. Universal method for stochastic composite op- timization problems. Computational Mathematics and Mathematical Physics, 58(1):48-64, 2018.
[20] Saeed Ghadimi. Conditional gradient type methods for composite nonlinear and stochastic optimization. Mathematical Programminng, 173(1):431-464 2019.
[21] Jacques Guélat and Patrice Marcotte. Some comments on Wolfe's 'away step'. Mathematical Programming. 35(1):110-119 10-119, 1986.
[22] Emil J. Gumbel. Statistical theory of extreme values and some practical applications: series of lectures, volume 33. US Government Printing Office, 1954.
[23] Zaid Harchaoui, Anatoli Juditsky, and Arkadi Nemirovski. Conditional gradient algorithms for norm-regularized smooth convex optimization. Mathematical Programming, 152(1))75-112, 2015.
[24] Elad Hazan and Haipeng Luo. Variance-reduced and projection-free stochastic optimization. In International Conference on Machine Learning, pages 1263-1271. PMLR, 2016.
[25) Hadrien Hendrikx, Francis Bach, and Laurent Massoulié. Dual-free stochastic decentralized optimization with variance reduction. Advances in Neural Information Processing Systems (NeurIPS), 2020.
[26] Martin Jaggi. Sparse Convex Optimization Methods for Machine Learning. PhD thesis, ETH Zurich, 2011.
[27] Martin Jaggi. Revisiting frank-wolfe: Projection-free sparse convex optimization. In Interna- tional Conference on Machine Learning (ICML), 2013.
[28] Yujia Jin, Aaron Sidford, and Kevin Tian. Sharper rates for separable minimax and finite sum optimization via primal-dual extragradient methods. arXiv preprint arXiv:2202 200..2200,,4440 2022.
[29] Sham Kakade, Shai Shalev-Shwartz, Ambuj Tewari, et al. On the duality of strong convexity and strong smoothness: Learning applications and matrix regularization. Unpublished Manuscript, http://ttic. uchicago.
pdf. 2(1), 2009.
[30] Sham M Kakade, Karthik Sridharan, and Ambuj Tewari. On the complexity linear prediction: Risk bounds. margin bounds, and regularization. Advances in neural information processing systems, 21, 2008.
11

---

[31] Simon Lacoste-Julien and Martin Jaggi. On the global linear convergence of frank-wolfe optimization variants. Advances in Neural Information Processing Systems (NIPS), 2015.
[32] Guanghui Lan. An optimal method for stochastic composite optimization. Mathematical Programming, 133(1):365 397, 2012.
[33] Guanghui Lan. The complexity of large-scale convex programming under a lincar optimization oracle. arXiv preprint 1309.5550, 2013.
[34] Guanghui Lan and Zhou. Conditional gradient sliding for convex optimization. SIAM Journal on Optimization, 26(2):1399-1499, 2016.
[35] Evgeny S. Levitin and Boris Polyak. Constrained minimization methods. USSR Computa- tional mathematics and mathematical physics, 6(5):1-50, 1966.
[36] Bingcong Li, Mario Coutino, Georgios B. Giannakis, and Geert Leus. How does momentum help Frank Wolfe? arXiv preprint 2006. 11116, 2020.
[37] Geoffrey Négiar, Gideon Dresdner, Alicia Tsai, Laurent El Ghaoui, Francesco Locatello, Robert Freund, and Fabian Pedregosa. Stochastic frank-wolfe for constrained finite-sum minimization. In International Conference on Machine Learning, pages 7253-7262. PMLR, 2020.
[38] Yurii Nesterov. method for unconstrained convex minimization problem with the rate of convergence OL1/k²). In Doklady an USSR, volume 269, pages 543-547, 1983.
[39] Yurii Nesterov. Introductory Lectures Convex Optimization: A Basic Course. Springer Science Business Media, 2003.
[40] Yurii Nesterov. Gradient methods for minimizing composite functions. Mathematical Program- ming, 140(1):125-16)) 1611 2013.
[41] Yurii Nesterov and Vladimir Spokoiny. Random gradient-free minimization of convex functions. Foundations of Computational Mathematics, 17(2):527-566, 2017.
[42] Ralph T. Rockafellar. Convex Analysis. Princcton University Press, 2015.
[43] Ralph T. Rockafellar and Roger J.-B. Wets. Variational Analysis. Springer Science & Business Media, 2009.
[44] Sharan Vaswani, Aaron Mishkin, Issam Laradji, Mark Schmidt, Gauthier Gidel, and Simon Lacoste-Julien. Painless stochastic gradient: Interpolation, line-search, and convergence rates. Advances in neural information processing systems, 32, 2019.
[45] Sharan Vaswani, Benjamin Dubois-Taine and Reza Babanezhad. Towards noise-adaptive. problem-adaptive (accelerated) stochastic gradient descent. In International Conference on Machine Learning, pages 22015 22059. PMLR, 2022.
[46] Jialei Wang and Lin Xiao. Exploiting strong convexity from data with primal-dual first-order algorithms. In International Conference on Machine Learning (ICML), 2017.
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]
(b) Did you describe the limitations of your work? [Yes] See conclusion.
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including thcoretical results...
12

---

(a) Did you state the full set of assumptions of all theoretical results? [Yes] See proposition and theorem statements.
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix.
If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material or as a URL)? [Yes] The code is available at https: / ht///gttbbb/// com/ wttpbpaallld//eaaa d/PFW.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(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)? [N/A]
4. If you are using existing assets code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable
information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "nEDRpQkusGe", "reviewer": "Reviewer_rQnJ", "summary": "In this paper, the authors consider convex minimization problem over bounded domain. \nFirst, they propose a new accelerated gradient method that has several distinguising assumptions and features: \n- it works with stochastic gradients of the smooth part; \n- it uses strong convexity of the composite part; \n- it employs an arbitrary strongly convex prox function as a regularizer. \n\nThen, the authors demonstrate that this method can be applied for solving a smoothed dual problem of miniminizing a smooth function over a compact convex set. In this case, the new method has an interpretation of Frank-Wolfe algorithm. To decrease the variance of the stochastic estimation of the dual gradients, one can use a parallel mini-batching, which provides the method with a provable acceleration given a set of parallel computational units. Numerical experiments on synthetic data are provided.", "questions": "Minor questions and remarks:\n\n1. Algorithm 2: this is not clear, what is $du$ from which $\\Delta$ is sampled.\n\n2. It might be worth to move the choice of $\\alpha$ into the beginning of Theorem 3 (e.g. Let $\\alpha = ...$. Now it is easy to miss it).\n\n3. Is it correct that $m = 1$ does not correspond to the 'pure' Frank-Wolfe method? The method seems to be always stochastic.\n\n4. Is it possible to use some line search in experiments?  ", "limitations": "--", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well written. I found the results very interesting and significant. Although, all the building block are quite known in optimization community (accelerated methods, duality, bregman distances, smoothing, etc.), the whole approach fits perfectly together and provides the reader with a number of nice and useful observations. \n\nIn particular, it is shown that minibatching for improving stochastic estimation of the gradient of the smoothed support function results in doing in parallel several linear minimization oracle calls for the corresponding convex set. The last operation is the most expensive in the Frank-Wolfe method. Then, the authors demonstrate that choosing the 'batchsize' of size $m$, the resulting complexity is $O( \\frac{1}{\\sqrt{\\epsilon}} + \\frac{1}{m \\epsilon} )$. Hence, for $m = \\frac{1}{\\sqrt{\\epsilon}}$, this gives the optimal rate. The most imporant feature of this result is that this 'minibatching' is done in parallel, which means that we can get a significant acceleration having several computational units.\n\nIn my opinion, there are several limitations of this technique. Probably, it might be benefitial for the presentation to address some of them:\n\n1. The main requirement of the approach is to have an access to a probability distribution with 'positive differentiable density'. It is not thoroughly discussed how difficult is it to find such a distribution, which is suitable for a given problem. Assumption 2 on the variance decrease seems to be also related. It defines a certain constant $\\rho$ that depends on the distribution and needs to be known by the method (as for the choice of $\\alpha$). \n\n2. Also, the method needs to be given several other paramers (Lipschitz constant of the gradient, diameter of the set, parameter of the distribution $M$). The classical Frank-Wolfe method known to be quite universal: no knowledege of any of this parameters is required. Morevore, it is possible to use a line search in each iteration, that improves convergence significantly. This is not clear, how practical the requirement of knowing all these parameters for the new method, and is it possible to eliminate them.\n\n\n------------------\nAfter rebuttal:\n------------------\n\nI vote for accepting this paper since I believe that the contribution of the paper and the new methods are solid.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "QGjH3nVq5G", "reviewer": "Reviewer_3QVT", "summary": "The authors propose a Frank-Wolfe-based algorithm for solving partially stochastic composite minimization problems over general convex constraints which admit a regularized linear minimization oracle. This general algorithm is applied to the case where the stochastic part of the objective is a finite sum and propose a parallelized step in which all components of the finite sum are computed in parallel. There are numerical results on least squares with L1-norm constraint and matrix factorization. ", "questions": "1. There seems to be a mismatch between the experiments and the theory. Is there an experiment that has nonzero H?\n2. Is this an actual parallelized algorithm or does it simply have a parallel step (computation of a stochastic gradient)?", "limitations": "N/A", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "1. The paper is difficult to parse. The significance is unclear, especially given what appears to be a significant gap between the theory and the experiments.\n2. The presentation of the parallelized algorithm has the flavor of being dishonest since it does appear to be a truly parallel algorithm. If I understand correctly, with the authors view, classical SGD on a finite-sum problem can all be trivially \"parallelized.\"\n3. The experiments are very far away from the theory. Interestingly, this would enable the comparison to more recent stochastic FW algorithms rather than vanilla FW.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Ixuan0zTW6S", "reviewer": "Reviewer_BdLs", "summary": "In this paper, the authors start with a general framework that can solve composite problem G(y)+H(y) where G can only be accessed via a stochastic gradient oracle, with a proximal Bregman-type algorithm. Explicit rate is given along with the final radius of convergence for the framework. This is in turn applied to solving a constrained convex function, where the framework is evoked for its smoothed dual problem. The requirement on stochastic gradient boils down to a linear optimization oracle over the set, which is amenable to parallelization thanks to the smoothing operation. The resulting Frank-Wolfe-type algorithm is shown to have a convergence rate in the duality gap of O(1/sqrt(eps)) with 1/sqrt(eps) parallel queries. Numerical experiments are also conducted on the proposed algorithm.", "questions": "- This is probably just confusion on my part. Right before (22), $z_k$ is set to be $\\nabla f(x_k)$ for all k, so the resulting Algorithm 2 only involves $x_k,y_k$ and $v_k$. But is the reason I should think of $x_k$ as being the current primal iterate because $y_k^* = \\nabla f(x_k^*)$ for the optimal primal-dual pair on (17) and (18), and both $y_k,z_k$ live in the dual space?\n- There's another factor of $(1-e^{-z_1})$ missing on the last line of page 24?", "limitations": "Yes.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I find the paper generally well-written and think the result is of interest to the community. This reduction from accelerated Bregman method to accelerated Frank-Wolfe algorithm based on parallelization is a nice addition to the literature.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept