Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies a class of decomposable convex optimization problem. An algorithm with optimal query complexity is proposed. In addition, the authors also improve the evaluation oracle complexity for decomposable submodular minimization.
strengths_and_weaknesses: Strengths: This paper makes solid contribution to decomposable convex optimization problem with possibly non-smooth objective. The authors propose new algorithm for this problem with optimal query complexity. The proof technique in this paper is novel.

Weaknesses: The organization and presentation of this paper needs to be improved. 
1. I believe the main algorithm should be presented more clearly and explicitly in the main text, namely one should be able to implement Algorithm 1 after reading Section 3. Currently Section 3.1 seems like a mixture of implementing details and algorithmic intuitions, but due to space limitation I think the authors are not able to present either of them clearly. For example, how to set the initialization K_in, K_out and x_initial? The readers are referred to Appendix C.1 and C.2, where they might only find theorems and proofs instead of implementing details. What is the expression of A, b and c using the quantities already introduced in the main text? Can each step in Algorithm 1 be computed efficiently?
2. I think at least some part of Section 2 is not necessary for the main text, which can be moved to the appendix and save space for presenting and explaining algorithmic details.
3. I don't see a reason why the authors only present informal theorem (Theorem 1.2) in the main text and defer the formal theorem to the appendix. It seems to me that the formal theorem is not too complicated.

---------------After rebuttal----------------------

I would like to thank the authors for their response. Given that all my comments and authors' response leads to revision in the next version of the paper, I decide to keep my score and leaning to an accept.
questions: What is the definition of $\mathcal{K}_i$ that appeared in Section 1.2 and 1.3?
limitations: This is a theory paper and I believe there is no potential negative societal impact.
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: This work developed a new algorithm with near linear gradient oracle complexity (in terms of total effective dimension) for finite-sum non-smooth convex optimization, which appears to be the first work of achieving this goal.
strengths_and_weaknesses: Strengths:

- The proposed algorithm is based on a novel combination of cutting-plane methods and interior-point methods, which is technically non-trivial. The method achieves near linear gradient oracle complexity in terms of total effective dimension, which matches the theoretical lower bound. The result drastically improves upon the complexity of directly applying cutting-plane method when the gradients are sparse. Overall the paper is well written. 

Weaknesses:

- It would be great if the authors can provide a discussion on prior works that deal with non-smooth empirical risk minimization problem (i.e., ERM with a non-smooth regularizer that admits an efficiently computable proximal operator), which helps understanding the positioning of this work.


questions: See strengths and weaknesses.
limitations: The authors have adequately addressed the limitations of their work.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper investigates the finite sum minimization problem where each function depends only on a subset of coordinates. The work combines cutting plane and interior point methods and achieves a better complexity in gradient oracles. As always, however, there is a catch.

strengths_and_weaknesses: While the paper's contribution and motivation are definitely sound and interesting, especially from a mathematical point of view, I don't see its relevance to the NeurIPS community. For instance, the algorithm relies on the entropic barrier which is not implementable in general. Thus, the proposed complexity, in my opinion, is rather theoretical, with no hope to be practical. 

This contribution also requires significant resources for review and hence for appreciation of the technique and with review workload we have this has been nearly impossible. Anyway, I think a venue with more focus on complexity would be a better fit for this work. 

questions: Some minor comments: 

1. While we start with a problem (1.1) which is unbounded, we don't actually use it. The reformulation we use already assumes compactness. I think (1.1) only confuses. Also it uses $\theta$, while later we switch to $x$ variables, and we actually never show how this reformulation to (1.4) happens.

2. Table 1: In (1.1) we didn't assume strong convexity, while some methods in the table do. Thus, it is not clear what the authors want to convey. Also, what is the purpose of the last column? Subgradient methods handle this problem under non-smoothness.

3. line 50: It is not clear what "long chain of variable dependencies" is.

4. line 126-136: I suggest to be more instructive here. How exactly do you transform (1.1) into that form? What is the role of linear constraints $Ax=b$?

5. line 144-145: Inequalities (3.3) and (3.4) at this moment are not yet established, thus the explanation looks rather void.

6. Th. 2.3: We don't explain what is centroid here, however we provide a full line of text for the elementary definition of the halfspace.

7. line 192: No need to repeate notation of the polar set: it was defined just a few paragraphs above.


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 work, the authors proposed a weakly-polynomial algorithm to minimize the finite-sum objective function, which is possibly non-smooth. The complexity of the proposed algorithm improves that of the cutting-plane methods, under the assumption that each component f_i only depends on a small subset of the components of x. The algorithm is a combination of the interior-point method and the cutting-plane method.
strengths_and_weaknesses: This work provides a novel algorithm for the non-smooth finite-sum optimization problem. In addition, the complexity is improved in certain cases. Although I haven't read the appendix, the intuitions on the technical proofs seem reasonable to me. Therefore, I think this work will be interesting to audiences in optimization and machine learning.

On the other side, given the technical complexities of this work and the page limit of the conference, it is a little hard to present the results clearly. With that said, I still suggest the authors try to revise the presentation and organization of this work. In addition, it would be better if numerical results can be provided.
questions: Major:
(1) The presentation of the paper should be improved. For example, the discussion in lns.140-149 is based on definitions/results in Section 3. The readers have to complete reading the whole paper to understand the intuition that the authors wanted to convey here. This will make this discussion less useful in "introducing" the readers to the contributions of this paper. It might be helpful to explain what are inequalities (3.3) and (3.4).

(2) In addition, it is a little confusing why the complexity of the proposed algorithm has dependence on m rather than nd. It seems to me that the dependence on m suddenly appeared on ln.325. Hence, it would be better to provide an intuition on the dependence on m.


Minor: 
(1) It would be better to mention that in the SFM problem, one can utilize the Lovasz extension to compute a sub-gradient in O(d) steps. Otherwise, readers that didn't read the appendix will be confused on the relation between the evaluation oracle and the sub-gradient oracle.

(2) Ln.94: it would be better to clarify the definition of the "polynomial factor". Namely, is this factor a polynomial of d_i and epsilon, or something else?

(3) Ln.102: since the AGD algorithm updates one coordinate in each iteration, I wonder if the complexity is proportional to d? Also, I do not understand why AGD can only update one coordinate in each iteration, and it seems that the complexity Omega(n^2) does not match the complexity in Table 1? It would be better to provide more details to this discussion.

(4) Ln.106: it would be better to use "sub-gradient" instead of "gradient" in the discussion of CPM, since it does not require the smoothness condition.

(5) Ln.127: K_i is not defined.

(6) Ln.138: please unify the usage of "sub-gradient" and "subgradient". Also, "a separation oracle K_i" -> "a separation oracle of K_i".

(7) What are c, A and b in problems (1.4) and (3.1)?

(8) Lns.140-149: it seems that the case when inequality (3.4) is violated is not discussed.

(9) Ln.175: y should be boldface letter.

(10) Ln.200: I wonder if the convex set K_i is defined by the epigraph of f_i? If so, please clarify the meaning of "does not have a closed-form expression". If not, please provide a more explicit definition of K_i.

(11) Ln.224: does the Newton step refer to Ln.23 of Algorithm 1?

(12) For the discussion around Prop.2, I wonder what is the difference between the claim here, and the classic "volume reduction" results in CPM algorithms?
limitations: See my comments in the "questions" section.
review_title: null

Meta-review: metareview: This paper studies the finite-sum optimization problem with convex yet possibly non-smooth objective functions. The authors develop an efficient algorithm that allows one to solve this problem with a nearly linear number of calls to the gradient oracle (in terms of the effective dimensionality), thus improving upon prior art.  The key idea lies in combining the cutting-plane method and the interior-point method in a novel manner. While a reviewer has raised concerns about implementation of the proposed algorithms, the theoretical contributions of this paper are solid and important, and hence I recommend acceptance. It would still be great if the authors could consider discussing practical implementation of the proposed algorithms. 
confidence: Certain
Decision: Accept