Regularized Adaptive Momentum Dual Averaging with an Efficient Inexact Subproblem Solver for Training Structured Neural Network

Summary

This article proposes an optimization algorithm RAMDA for training structured neural networks, which combines a number of optimization techniques including dual averaging, momentum, and coordinate-wise preconditioners. Similar to the existing RMDA algorithm, RAMDA also has the capacity to identify the local manifold structure of the solution. The author(s) provide theoretical analyses to justify the convergence property of RAMDA, and develop an inexact subproblem solver as required by RAMDA.

Strengths

The proposed RAMDA algorithm extends the existing RMDA algorithm by adding a coordinate-wise preconditioner, and its theoretical analysis seems to be novel.

Weaknesses

I think one major weakness of the current manuscript is the **correctness** of some theoretical results presented in the article. 1. Theorem 1 suggests that the regularizer function $\psi$ can be nonconvex. However, as the RAMDA algorithm heavily relies on the proximal operator of $\psi$, how do you define the proximal operator when $\psi$ is nonconvex? For example, equation (6) is used to define the new iterate $W^t$, but when $\psi$ is nonconvex, it is likely that the "argmin" is a set and is not uniquely defined. 2. Taking a closer look at the proof of Theorem 1, I feel that the author(s) may have a misunderstanding of an existing theorem. In Appendix B, equation (11) is obtained by citing Theorem 10.15 of [1]. However, Theorem 10.15 of [1] applies to functions of the form $F(x)=f(x)+\psi(x)$, where $f$ is smooth and nonconvex, but $\psi$ is convex. In other words, the non-convexity only applies to the smooth part, not the regularizer. 3. If the findings above are valid, then the author(s) may need a thorough examination of the technical proofs to see if there is any error. 4. If we assume $\psi$ is convex, then there should be an Nesterov-accelerated version of Algorithm 2 that converges in $O(\varepsilon_t^{-1/2})$ iterations, which is faster than the rate given in Theorem 1. [1] Beck, A. (2017). First-order methods in optimization. Society for Industrial and Applied Mathematics. =============================================================== Edit: during the rebuttal the author(s) seem to have addressed the concerns above.

Questions

See the "Weaknesses" section.

Rating

5

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

The authors have discussed the limitations of the proposed algorithm in Section 5 and Appendix C.

Summary

This paper develops regularized adaptive momentum dual averaging (RAMDA) for structured neural networks. The method uses the preconditioning matrix to accelerate the convergence of a regularized momentum dual averaging (RMDA) method at the price of requiring the local solver (e.g. standard proximal gradient methods) to solve the subproblem. By the preconditioning matrix inspired by the AdaGrad stepsizes in Eq. (2), RAMDA outperforms RMDA and other existing gradient-based methods for solving structured neural networks in various learning applications.

Strengths

1. Theoretical results suggest the convergence towards the solution to the subproblem when the proximal gradient methods are used as the local solvers, and almost surely convergence of RAMDA that derives from the manifold theory under the standard $L$-smoothness assumption on the objective functions $f$. 2. Empirical results illustrate the superior performance of RAMDA over RMDA and other existing gradient-based methods for various neural network tasks. Clear criteria, e.g. for solving the subproblems, are clearly stated in the numerical experiments.

Weaknesses

1. I think there is an error in Eq. (3) where it should be the square root $\sqrt{\cdot}$ in the diagonal operator for $P^t$. This is because $P^t$ uses $U^t$ that is computed from the element-wise multiplicative product of the gradient $G^t$. Is $P^t$ inspired by the AdaGrad stepsizes? If so, then adding the justifications on using $P^t$ in RAMDA is worthwhile to better distinct RAMDA from RMDA. 2. In the experiments, can you comment on the impact of the different $\epsilon_t$ on the training performance of RAMDA? Because I believe that using $\epsilon_t$ a bit higher than $10^{-8}$ set in your experiments RAMDA might achieve far lower training time than other methods while keeping still comparable perplexity to solve Transformer-XL with WikiText-103 in Table 4, or Tacotron2 with LJSpeech in Table 5.

Questions

I listed questions as part of weaknesses.

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

The limitations of current theoretical results are clearly and fairly discussed after Theorem 2.

Summary

#### Summary The paper introduces the Regularized Adaptive Momentum Dual Averaging (RAMDA) algorithm for training structured neural networks. RAMDA addresses the challenge of solving the subproblem involved in the regularized adaptive methods, which typically lacks a closed-form solution. The paper presents an inexactness condition that retains convergence guarantees and proposes an efficient subproblem solver. The algorithm leverages manifold identification theory to ensure that the iterates of RAMDA attain the ideal structure induced by the regularizer at convergence. Extensive experiments demonstrate the effectiveness of RAMDA in various tasks, including computer vision, language modeling, and speech synthesis.

Strengths

#### Strengths 1. **Novel Algorithm**: RAMDA combines adaptive momentum dual averaging with efficient inexact subproblem solving, providing a practical and theoretically sound method for training structured neural networks. 2. **Theoretical Guarantees**: The paper provides strong theoretical support, including convergence guarantees and structure identification, ensuring the algorithm's robustness. 3. **Practical Efficiency**: The proposed inexact subproblem solver is efficient, making RAMDA feasible for large-scale applications. 4. **Empirical Validation**: Extensive experiments across multiple domains demonstrate the superior performance of RAMDA in terms of both prediction accuracy and structured sparsity.

Weaknesses

#### Weaknesses 1. **Computational Complexity**: The computational complexity of the proposed subproblem solver, especially for high-dimensional data, needs more detailed discussion. 2. **Generality**: While the paper focuses on specific types of structured neural networks, extending the methodology to other models and regularizers would enhance its generality. 3. **Comparative Analysis**: More detailed comparisons with other state-of-the-art methods, beyond the provided benchmarks, would strengthen the empirical validation. 4. **Implementation Details**: Practical guidelines for implementing RAMDA, including parameter tuning and handling different data distributions, are somewhat lacking.

Questions

#### Questions 1. **Computational Complexity**: - Could you provide more details on the computational complexity of the proposed subproblem solver? How does it scale with increasing data size and model complexity? 2. **Generality**: - The paper focuses on structured neural networks with specific regularizers. Are there any challenges in extending RAMDA to other types of models or regularizers, such as those used in different machine learning tasks? 3. **Comparison with Existing Methods**: - How does RAMDA compare empirically with other state-of-the-art methods for training structured neural networks? Are there specific scenarios where RAMDA significantly outperforms these methods? 4. **Implementation Guidelines**: - Can you offer practical guidelines for implementing RAMDA in real-world scenarios? Specifically, how should practitioners tune the parameters, such as the learning rate and the inexactness threshold? 5. **Assumptions and Limitations**: - The paper discusses some assumptions and limitations. Could you elaborate on the key assumptions that are critical for the theoretical results, and how robust the method is to violations of these assumptions?

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

no

Learning rate scheduling setup

More details regarding the learning rate scheduling setup: We begin with determining the total number of epochs, often considered as a budget, and then split them into 3 to 5 roughly equal stages. While more epochs typically lead to better performance when resources allow, in some cases, the total number of epochs should be adjusted based on validation performance to identify the optimal point.