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 the Gaussian homotopy method for finding stationary points for non-convex optimization problems. Novel deterministic and stochastic single loop Gaussian homotopy algorithms are proposed, where the decision variable $x$ and the smoothing parameter $t$ are simultaneously updated, in contrast to the double loop Gaussian homotopy algorithms in the existing literature. Also, the corresponding zeroth-order algorithms are developed based on zeroth-order estimators of gradient and Hessian. The convergence rates of the proposed algorithms are analyzed. Empirical evaluations are provided to corroborate the theory.
strengths_and_weaknesses: This paper is well-motivated and well-written, and overall the content is easy to follow. The idea to simultaneously update $(x,t)$ is intuitive and natural. The convergence analysis seems to be standard, and I don't see much novelty in this regard (maybe the authors can highlight if there is any special difficulty). The empirical study looks good to me.
questions: 1. For $\text{SLGH}_{\mathrm{d}}$, the update of $t_k$ depends on some small $\epsilon > 0$. What's the role of this $\epsilon$? What's the relationship between this $\epsilon$ and the one in the theorems as the error guarantee on the gradient norm?

2. Following the above question, it seems to me that the proof for Theorem 3.4 only works for $SLGH_r$. 
This is because in line 83 in the appendix, the proof requires $\sum_{k=1}^T t_k \leq \sum_{k=1}^T t_1\gamma^{k-1}$, which is not necessarily true for $\text{SLGH}_{\mathrm{d}}$, as $t_k$ there is always at least $\epsilon$. 

3. In the theorem statements, the $\hat x$ should be more specified. According to the proofs, the guarantee should be $\max_{k\in[T]} \|\nabla f(x_k)\|\leq \epsilon$.

4. From the intuition behind the Gaussian homotopy method, this kind of algorithm should perform better than the vanilla gradient descent because it is expected to find a better solution by smoothing the geometry. However, this is not reflected in the theory proved in this paper. 
limitations: The authors have adequately addressed the limitations of their work.
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: The paper proposes a single loop framework to deal with Gaussian Homotopy (GH) method for non-convex (deterministic and stochastic) optimization $f(x)$. GH approach aims to solve successively smooth surrogates $F(x,t)$ of $f(x)$ for $t \geq 0$ such that at convergence the minimization of $F(x,0)$ corresponds to a stationnary point of the initial problem. The proposed method coined SLGH (single loop GH) relies on a gaussian smoothing convolution $F(x,t)$ of $f$ that is simultaneously optimized w.r.t to $x$ and $t$ using a (projected-like) gradient descent. SLGH differs from classical approaches that optimizes $F(x,t)$ for pre-specified values of $t$. Two variants of SLGH are provided based respectively on first-order and zeroth-order gradient descent. Convergence analyses in terms of iteration complexity are conducted in each setting. Experimental evaluations on adversarial image crafting illustrate the behaviour of the methods.
strengths_and_weaknesses: * The paper is well written and  well  organized. The rationale behind the proposed SLGH is justified and the new aspects brought by  the approach are stated clearly.

* As for a strength, the paper proposes a principled way to design the smoothing function $F(x,t)$ using Gaussian convolution applied to $f(x)$. It also establishes that the minimum of $F(x,t)$ w.r.t $t$ is achieved at $t=0$ giving then the solution to the minimization of $f(x)$. However computing $F(x,t)$ will be a hard task in general leaving the first order optimization method non-applicable in practice. This is mitigated by the proposition of a zeroth-order approach.

* The optimization scheme in Algorithm 2 is rather standard for solving $\min_{x, t \geq 0} F(x,t)$. The interesting fact is that $F(x,t)$ inherits boundness and Lipschitzness properties of $f$ that helps implementing Algorithm 2. Key results of the papers are the theoretical iteration complexities to reach an $\epsilon$ convergence on the gradient norm. Similar results are derived for zeroth-order methods. Generally speaking the first-order methods exhibit reduced iteration complexity.

* GH methods aim to provide solution to the original problem as the minimizer of $F(x,t=0)$ at convergence. However Algorithms 2 and 3 ouput the sought solution as a minimizer of $F(x,t=\epsilon)$ for some non-null positive $\epsilon$. It would be interesting to analyze convergence in the iterates $x_k$.

* Reported empirical evaluations in Section 5 are questionable and to argue for the proposed methods. As for the average number of iterations to reach the first successful attack, SGD algorithms perform better than GH methods. Regarding pediction peformance the paper reports the average of total loss $f(x)$ which is meaningless in the context of adversarial attack. The most relevant metric might be the fooling rate as one is interested in the success of attack not in the value of the loss function. Also the performances are compared for different levels of L2 distortion which is highly questionable. As a fair comparison, the considered methods should be evaluated for the same L2 distortion error. 

* The authors provide relevant feedback to most reviewers' concerns. Nevertheless the reported experiments on adversarial attack in Section 5 do not prove the effectiveness of the GH approaches. Indeed,  the proposed GH methods lead to a smaller objective value compared to competitors (SGD algos). However they lead to higher fooling rates of the network but at the price of a higher perturbation. Therefore the attacks by GH cannot be claimed better than the ones by SGD algos.
questions: * In practice the choice of the step-sizes $\beta$  and $\eta$ may not be obvious. Is a line-search strategy used to appropriately estimate those parameters?
* Algorithms 2 and 3 use the parameter $\epsilon$. Is it the same parameter that is applied in Theorems 3.4, 3.5, 4.1 and 4.2?
* The paper claims that empirically, settings of $\gamma$ close to 1, e.g., $\gamma= 0.999$ work well in practice. Is such a choice efficient computationally? Because it probably induces a slow decrease of $t$ and hence a high iteration complexity.
* Why the same update policy is not applied to $t$ for SLGH_r in Algorithms 2 and 3?
* Computation of the Gaussian convolution $F(x,t)$ of $f(x)$ can be computationally demanding, rendering per iteration costly in Algorihm2. Are there typical obbjective functions that are suited for firs-order SLGH?
* When dealing with stochastic setting of SLGH, does the convergence improve when using a batch size greater than 1?
* Can the paper provide empirical evaluations of the methods illustrating the derived convergence rates? Also it would be interesting to show convergence results in terms of computation time and compared to plain gradient descent method for instance.
* Can the authors report fooling rate for different levels of L2 distortion to allow a fair and easy comparison of the methods? 
limitations: The paper  discusses the broader impact of the proposed approaches. On my view point the work does not raise any specific issues.
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 studied the Gaussian homotopy (GH) method for non-convex optimization problems in deterministic and stochastic settings. Compared to the existing GH-based method with the two-loop scheme, they proposed a single-loop GD method that can update the smoothing parameter and optimization variable at the same time. In particular, they showed the computational complexity of the proposed methods in different settings. Finally, experimental results are reported to demonstrate the potential of the proposed methods. 
strengths_and_weaknesses: 
Strengths: (${\bf 1}$)  This work has a good contribution to the Gaussian homotopy (GH) methods. The authors not only developed a single-loop GD method but also extended it to the stochastic and zeroth-order settings. Moreover, the complexity analysis of the proposed methods is provided. 

(${\bf 2}$) Overall, the paper is well-written and I think that the authors made good enough technical contributions. 

Weaknesses: (${\bf 1}$) It seems that Assumption A.1 (i) is rather strict, which requires the objective function $f$ to be bounded. Many functions arising in applications don't satisfy this assumption. Thus, this really limits the applications of the GH methods. Note that in [8], no such assumption is imposed. Could this assumption be relaxed? 

(${\bf 2}$) In Figure (1), to better compare function values of the tested method, the authors should use the log-scale plot on the y-axis. From the current figures, the loss function values of most of the tested methods look the same. 
questions: 
(${\bf 1}$) The idea of the Gaussian smoothed function in Definition 2.1 is very similar to that in Eq (17) of [8]. Could the authors elaborate on the connections and differences between the gaussian homotopy method and the smoothing gradient descent method in [8] and the related paper, like the iteration complexity?

(${\bf 2}$) In the introduction part, the authors mentioned that "The Gaussian homotopy is designed to avoid poor stationary points...". However, in the remaining part of the paper, it seems that the authors cannot illustrate this advantage of the GH method. Could the authors demonstrate this point theoretically or empirically?

(${\bf 3}$) The smoothing methods usually employ the fixed-ratio update rule for updating the smoothing parameter $t$. In Section 3.2, the authors proposed an interesting derivative update rule. Compared to the fixed-ratio update rule, what is the benefit of the derivative update rule? Can this significantly improve algorithm performance?

(${\bf 4}$) Could the proposed method be easily extended to the constrained setting? 

limitations: No
review_title: null

Meta-review: metareview: All reviewers agree that it is a well-written paper.
confidence: Certain
Decision: Accept