Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The authors propose a projection-free method to solve the multi-level optimization problem, and analyse the number of calls to the stochasic first-order oracle and the linear-minimization oracle. The complexity is comparable with exisiting results for single-level problems. For single-level case (T=1), they also give a high-probability convergence result. Another merit of the proposed method is that it dose not require large batchsize and is parameter-free.
strengths_and_weaknesses: Strengths: 

1. The proposed method is projection-free and parameter-free. It also does not require any increasing order of mini-batches. This paper is clear-written and analyses are supported by proofs that are sound to me.

Weaknesses:

1. As pointed out by the authors, the LMO complexity of the proposed method is worse than the single-level problem, i.e., $\mathcal{O}(\epsilon^{-3})$ vs $\mathcal{O}(\epsilon^{-2})$. Whether this rate is improvable is an important problem.

2. The algorithm proposed is not novel enough. As mentioned in Section 2, the techniques used are already known in other literature. Especially, the method is a bit similar to existing multi-level work, i.e., [4], although the latter uses the projection operation to ensure the final point in the domain.

3. Experiment results are not provided to show the practical performance of the proposed method.
questions: 1. Since this paper is about multi-level optimization, why not compare the complexity of the algorithm with other multi-level methods, such as [4],[7],[50],[52]?
limitations: No problems here. The authors discuss the limitations in Section 5, and I think they are proper.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper studies stochastic multi-level composition optimization problem, and especially focus on the class of projection-free algorithms. By combining the linearized NASA in existing works on multi-level composition problem and the existing conditional gradient algorithms, this paper propose a new algorithm that theoretically outperform other existing projection-free algorithms in the stochastic multi-level composition optimization problem.
strengths_and_weaknesses: Strength:
1. I think one major theoretical novelty in this paper is that their proposed algorithm does not need an increasing batchsize and extra assumptions.

Weakness:
1. This paper appears to be incremental, and the problem setting seems contrive to me. First, it seems that the independence of the levels is due to the linearized NASA technique in existing works. Second, the theoretical analysis (Using gradient mapping as criterion and the moving averaging technique) seems standard in the existing literatures on SCG. Therefore, it looks like this paper is a direct combination of the existing results in multi-level composition optimization and conditional gradient algorithms.
questions: 1. Could the author provide some insights for their proofs on why the algorithms can work without increasing batchsize, comparing to existing results.?

2. I am confused on why the authors says that the bound in equation (13) is independent of T. From equation (42), it seems like the the bound should be exponentially dependent on T (There are summations over T and comulative product over T in the constant \hat \sigma^2.)?
limitations: See my comments above.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: In this work, the authors proposed a projection-free algorithm (LiNASA-ICG) to solve the constrained stochastic multi-level optimization problem. The oracle complexities are derived for the algorithm and the algorithm is shown to be parameter-free. In addition, improvements in the T=1,2 case are provided and a high-probability bound is derived for the T=1 case.
strengths_and_weaknesses: The topic of this paper is interesting to audiences in the optimization and machine learning fields. As the authors mentioned, the proposed algorithm has the advantage that it is projection-free and parameter-free. In addition, the algorithm does not require mini-batch, which will enable its application to the online optimization case. The paper is also well written and easily to follow. 

My major concern is the contributions compared to [4]. It seems to me that many components in this work were already proposed in [4]. For example, the LiNASA algorithm and the construction of the merit function. Additionally, the comparison to [4] is not sufficient, which makes it hard to judge the contribution of this work. Hence, I would like to stay borderline and wait for the authors' response at this time.
questions: Major:
(1) The comparison to [4] is not sufficient. Maybe I missed something, I think the major difference between the proposed algorithm and the algorithm in [4] is the generation of the next iteration point. Namely, sub-problem (5) in this work and sub-problem (3) in [4], which is the same as sub-problem (2) in this work. Since both this work and [4] aimed at solving (2), it is unclear how much advantage one can gain by utilizing the "projection-free" ICG procedure. Therefore, I would suggest the authors provide a more detailed comparison to [4] and numerical experiments, which will also help highlight the contributions of this work.


Minor: 
(1) It would be better to clarify the difference between "stochastic conditional gradient-type algorithms" and "stochastic gradient-type algorithms". I guess the second term refers to the gradient descent-type algorithms?

(2) The sentence at ln.135-138 is confusing and hard to parse. I would suggest the authors revise this sentence.

(3) Ln.144 and ln.146: "assume" -> "assumed".

(4) Ln.187-188: I do not understand why \xi_i could be independent of u_i? I think they are related by relation (8) and cannot be independent. It would be better if more details can be included.

(5) Ln.251: "beta" -> "\beta".

(6) It would be better if the authors could mention the difficulty of deriving high-probability bounds for the general T case. Alternatively, I wonder if it is possible to derive a (possibly worse) high-probability bound using the proof technique of the T=1 case.
limitations: See my comments in the "questions" section.
review_title: null

Meta-review: metareview: There is general agreement that this paper is a borderline accept and after my own reading I feel similar. 
confidence: Less certain
Decision: Accept