A Theoretical and Experimental Study of a Novel Adaptive Learning Algorithm

Technical Summary: A Theoretical and Experimental Study of a Novel Adaptive Learning Algorithm (C-Adam)

Problem Statement
The paper addresses a fundamental challenge in machine learning optimization: minimizing loss functions with low computational cost and minimal oscillation. While adaptive learning rate optimizers like Adam are widely used, they suffer from a lack of guaranteed convergence due to the non-monotonic nature of their second-order moment estimates. To rectify this, AMSGrad was introduced to enforce a non-decreasing second moment, ensuring convergence. However, AMSGrad introduces its own limitations: by strictly maximizing the second moment, it can become overly conservative, leading to excessively small learning rates that hinder the ability to escape saddle points or navigate complex, non-convex surfaces. Furthermore, in noisy environments, both Adam and AMSGrad may exhibit poor generalization or failure to converge to the optimal point.

Methodology
The authors propose a new optimizer, C-Adam (Customized Adam), which aims to balance the theoretical convergence guarantees of AMSGrad with the practical adaptability of Adam. The core innovation lies in a "line of sight" update approach, which accounts for transitionary gradients between discrete steps rather than relying solely on point-wise updates.

The algorithm modifies the update rule for the second moment estimate ($\tilde{v}_t$). Unlike AMSGrad, which sets $\hat{v}_t = \max(\hat{v}_{t-1}, v_t)$, C-Adam employs a convex combination:
$$\tilde{v}_t = \lambda \tilde{v}_{t-1} + (1 - \lambda) \max(\tilde{v}_{t-1}, v_t)$$
where $\lambda = \frac{\tilde{v}_{t-1}}{\max(\tilde{v}_{t-1}, v_t)}$.

This formulation creates two distinct cases:

1. Case 1 ($\tilde{v}_{t-1} > v_t$): $\lambda = 1$, resulting in $\tilde{v}_t = \tilde{v}_{t-1}$. This maintains the non-decreasing property required for convergence.
2. Case 2 ($\tilde{v}_{t-1} \leq v_t$): $\lambda < 1$, resulting in a weighted average between the previous maximum and the current second moment. This prevents the learning rate from becoming "too small for too long," a specific drawback of AMSGrad in noisy or non-linear scenarios.

Key Contributions

1. Algorithmic Proposal: The introduction of C-Adam, a variant that relaxes the aggressive maximization of AMSGrad while preserving the non-decreasing nature of the second moment.
2. Theoretical Proof: The paper provides a rigorous theoretical analysis proving that C-Adam guarantees the non-decreasing character of the term $\frac{\sqrt{\tilde{v}_t}}{\alpha_t}$, a condition necessary for convergence in online convex optimization.
3. Regret Bound Derivation: A formal regret bound is derived for C-Adam, mathematically demonstrating that its performance is either superior to or comparable with existing optimizers like Adam and AMSGrad.
4. Empirical Validation: Extensive experiments are conducted on both synthetic and real-world datasets (MNIST and CIFAR-10) using logistic regression, fully connected neural networks, and convolutional neural networks (CNNs).

Results

• Synthetic Experiments: In a specific synthetic problem where Adam converges to a highly suboptimal point ($x=1$ instead of $x=-1$) and AMSGrad converges slowly with high oscillation, C-Adam successfully converges to the optimal point with fewer epochs and lower regret.
• Logistic Regression (MNIST): C-Adam demonstrated faster loss reduction and converged to lower final values in both training and validation sets compared to Adam and AMSGrad.
• Neural Networks (MNIST & CIFAR-10): In fully connected networks and CNNs, C-Adam showed faster convergence during training.
• Early-Stage Performance: A critical finding is C-Adam's advantage in limited-training regimes. On the CIFAR-10 dataset, C-Adam achieved significantly better accuracy and prediction quality after 1,000 epochs compared to the other optimizers. While all three optimizers reached comparable accuracy after 3,500 epochs, C-Adam's ability to reach a high-quality solution earlier suggests efficiency in scenarios with restricted training time.
• C-Adam V2: The authors note a variant, C-Adam V2, which introduces a thresholding mechanism to handle cases where second moments are very small. While this variant showed improved performance on synthetic data, the authors acknowledge its practical limitation: it requires prior knowledge of a suitable threshold ($\epsilon_0$) via cross-validation, which may not be feasible for complex real-world problems.

Significance and Claims
The paper claims that C-Adam successfully addresses the trade-off between the theoretical convergence guarantees of AMSGrad and the practical efficiency of Adam. By utilizing a "line of sight" approach, the optimizer mitigates the "overly cautious" behavior of AMSGrad that leads to slow convergence in noisy environments. The authors assert that C-Adam offers a robust solution for classification tasks, particularly where data is noisy or training time is limited, providing faster convergence and reduced oscillations without sacrificing theoretical validity. The study concludes that the proposed method is a viable alternative for deep neural network optimization, offering improved performance across a variety of tested architectures.