- Rating
- 4(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper addresses Gaussian variance inference (GVI) which aims to approximate the given target by Gaussian distribution. There are 3 main contributions. First, a deterministic acceleration for GVI is designed, which is based on the well-studied accelerated proximal gradient algorithm and treats the mean/factor coordinates of Gaussian as optimization variables. It requires the exact Gaussian expectation to compute the gradient for each update step. Second, the authors show the impossibility of acceleration when an algorithm may only evaluate the gradient at chosen sampled points. Third, with an Lipschitz Hessian assumption, the authors analyze 4 control-variate estimators inside one stochastic accelerated framework. Experiments show the acceleration of proposed methods.
Critical strengths
- The paper provides an upper bound with exact expectations, and a lower bound showing that point wise access loses the acceleration, and an upper bound identifying small Hessian variation that can restore it.
- The main novelty of this paper from my perspective is the query-complexity Lower bound for GVI.
Critical weaknesses
- The algorithms presented are pretty standard. In particular, Theorem 2 is accelerated proximal gradient descent applied to a convex composite formulation, while Theorem 7 is accelerated proximal gradient descent with stochastic gradients. Lemma 17 and 28 are standard estimate-sequence techniques used for analyzing the convergence of accelerated gradient descent algorithms. The new technical content is in the variance bounds (Prop. 15, 19, 30 and Lemma 26), and the lower bound in Section 3.
- The lower bound in Section 3 does not depend on lambda_H, but Section 4 shows that the acceleration can be recovered by it. Is showing some dependence on Hessian variation necessary?
Questions for authors
See the weaknesses.
2 comments
Thank you for your clarification. I think it is a good work. I'd like to update my score as "accept". Good luck.
We thank the reviewer for the thoughtful assessment and for recognizing the lower bound as the main novelty of the paper.
Standard acceleration techniques. We agree with the reviewer that the accelerated updates and estimate-sequence arguments are standard, and we thank the reviewer for identifying the variance bounds and the lower bound as the main contribution. The variance bounds are what make the standard arguments work in our setting: they control the error along the accelerated iterates, since bounding the variance only at the optimum is not enough.
Hessian variation in the lower bound. Since Section 4 establishes acceleration under sufficiently small Hessian variation, we agree that it is natural to ask how much Hessian variation can be allowed while the near-linear lower bound holds. The potential Vv in Theorem 3 can be taken to have a finite Hessian-Lipschitz constant with an explicit lower (and upper) bounds. With α=1, the potential is Vv(x)=∥x∥2/2+(κ−1)(eKv∗ρτ)(x), where eKv is half the squared distance to the truncated ball Kv and τ=(κ−1)−2. By calculating the Hessian variation along the direction v near the boundary of the hidden cap, we obtain the lower bound λH≥τκ−1gρ(0) where gρ is the one-dimensional marginal density of ρ. We have some freedom in choosing the mollifier ρ. By choosing a suitable mollifier, we can ensure that $\lambda_H =\Theta(\kappa^3\sqrt d) =\Theta(\kappa^3\log\kappa)$ while preserving all the properties required for Theorem 3. Consequently, the near-linear lower bound continues to hold even under the additional restriction λH≤Cκ3logκ for some C>0. We have added this argument at the end of Section 3, with a detailed derivation in the appendix. It does not, however, identify a sharp threshold in λH.
Acceleration in sequential rounds. We also have a new result: under curvature bounds alone, an accelerated variant with large batches needs only O(κ) sequential rounds, while the total number of queries remains linear in κ, consistent with our lower bound. This may resonate with the view that VI is efficient because many evaluations can run in parallel. As in Section 4, the key technical step to prove this is the variance analysis. We would be happy to add it to the paper if the reviewer finds it valuable.
We hope these responses address the reviewer's concerns. If so, we would be grateful if the reviewer would consider updating the score, and we would be glad to clarify anything further. Thank you again for your time and thoughtful feedback.