Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: 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. 
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.
2. 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."
3. 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.
questions: 1. There seems to be a mismatch between the experiments and the theory. Is there an experiment that has nonzero H?
2. Is this an actual parallelized algorithm or does it simply have a parallel step (computation of a stochastic gradient)?
limitations: N/A
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: In this paper, the authors consider convex minimization problem over bounded domain. 
First, they propose a new accelerated gradient method that has several distinguising assumptions and features: 
- it works with stochastic gradients of the smooth part; 
- it uses strong convexity of the composite part; 
- it employs an arbitrary strongly convex prox function as a regularizer. 

Then, 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.
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. 

In 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.

In my opinion, there are several limitations of this technique. Probably, it might be benefitial for the presentation to address some of them:

1. 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$). 

2. 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.


------------------
After rebuttal:
------------------

I vote for accepting this paper since I believe that the contribution of the paper and the new methods are solid.

questions: Minor questions and remarks:

1. Algorithm 2: this is not clear, what is $du$ from which $\Delta$ is sampled.

2. 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).

3. Is it correct that $m = 1$ does not correspond to the 'pure' Frank-Wolfe method? The method seems to be always stochastic.

4. Is it possible to use some line search in experiments?  
limitations: --
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.
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.
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?
- There's another factor of $(1-e^{-z_1})$ missing on the last line of page 24?
limitations: Yes.
review_title: null

Meta-review: metareview: The authors design an algorithm for composite stochastic optimization that leverages both smoothness and strong convexity with respect to the same (general) norm, using a stochastic counterpart to recent work by Diakonikolas and Guzman. They then show how to leverage this algorithm and randomized smoothing in order to create an algorithm for constrained smooth convex optimization based on exact gradient evaluations and linear optimization computations. Compared to Frank-Wolfe, the algorithm requires strictly less gradient evaluations and parallelizes the same amount of linear optimization computations.

The paper received generally favorable reviews, with the exception of reviewer 3QVT who did not engage in discussion and whose critique I found unclear. I agree with reviewer rQnJ’s assessment that even though “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.” Consequently, I recommend acceptance.
confidence: Certain
Decision: Accept