Stochastic Optimization of Smooth Loss

Rong JinarXiv 2013 · arXiv

Abstract

Stochastic Gradient Descent (SGD) is a cornerstone of modern machine learning, yet theoretical guarantees often rely on "average-case" expectations and require prior knowledge of the optimal loss value to tune step sizes. This paper addresses these limitations by providing high-probability generalization bounds for smooth loss functions. By employing martingale analysis and a "doubling trick" for adaptive step-size selection, the proposed framework achieves optimal convergence rates without requiring an oracle for the minimum loss value.

1. Introduction

In the optimization of machine learning models, stochastic gradient descent (SGD) is typically employed to minimize smooth loss functions, such as squared loss or logistic loss. While the convergence of these algorithms is well-documented in terms of expected performance, two significant challenges persist in the theoretical literature. First, practitioners require high-probability bounds to ensure the reliability of individual optimization runs, rather than just average performance over multiple trials. Second, achieving optimal convergence rates traditionally requires an "oracle" step size—one that depends on the unknown minimum possible loss, $\ell(w_*)$. This paper bridges these gaps by introducing a robust mathematical framework for self-tuning stochastic optimization.

2. Methodology

The research introduces two primary techniques to refine the theoretical guarantees of SGD.

2.1 Martingale Analysis for High-Probability Bounds

To move beyond expectation-based results, the author utilizes Bernstein’s inequality for martingales. This approach provides a tighter bound on the noise inherent in stochastic sampling. By treating the sequence of gradients as a martingale difference sequence, the paper proves that the generalization error remains low with a probability of at least $1-\delta$, effectively controlling the "tail risks" of the optimization process.

2.2 The Doubling Trick and Adaptive Surrogate Loss

To eliminate the need for an oracle to set the step size ($\eta$), the paper proposes a multi-epoch strategy known as the doubling trick. The training process is divided into epochs of exponentially increasing length ($T_{k+1} = 2T_k$).

At the conclusion of each epoch, the algorithm calculates a surrogate loss value ($\hat{\ell}_k$) based on the empirical performance of the current solution. This surrogate serves as a proxy for the unknown $\ell(w_*)$. The step size for the subsequent epoch is then adaptively set using the formula: $$\eta_{k+1} = \frac{R}{2\sqrt{\gamma T_{k+1}\hat{\ell}_k}}$$ This mechanism allows the algorithm to converge toward the optimal solution at a rate comparable to oracle-tuned methods.

3. Key Insights

The analysis highlights the unique advantages of smoothness in loss functions. Unlike non-smooth optimization, which often scales at a rate of $1/\sqrt{T}$, smoothness allows for faster convergence terms that scale with $1/T$. The paper demonstrates that this "fast rate" is achievable even when the algorithm is forced to estimate its own parameters on the fly. Furthermore, the transition to high-probability bounds provides a more rigorous foundation for understanding the stability of SGD in practical applications.

4. Results

The primary contribution is a new generalization error bound that holds with probability $1-\delta$: $$\ell(\hat{w}) - \ell(w_*) \leq O\left(\sqrt{\frac{Ct}{T}\ell(w_*)} + \frac{Ct}{T}\right)$$ where $\ell(\hat{w})$ represents the expected loss of the average solution, $T$ is the number of iterations, and $t$ is a logarithmic factor determined by the confidence parameter $\delta$. The doubling trick ensures that this rate is maintained without prior knowledge of $\ell(w_*)$, proving that self-tuning is both theoretically sound and computationally efficient.

5. Conclusion and Limitations

While the paper provides a significant advancement in stochastic optimization theory, several constraints remain. The analysis is strictly applicable to smooth loss functions, excluding non-smooth objectives like Hinge loss. Additionally, the proofs assume a bounded domain for the solution space (radius $R$). While the doubling trick introduces some implementation complexity due to epoch-based restarts, it offers a mathematically rigorous path toward fully autonomous and robust stochastic optimization. Future work may explore extending these adaptive techniques to non-smooth domains or more complex, non-convex architectures.

Summary updated

Abstract

In this paper, we first prove a high probability bound rather than an expectation bound for stochastic optimization with smooth loss. Furthermore, the existing analysis requires the knowledge of optimal classifier for tuning the step size in order to achieve the desired bound. However, this information is usually not accessible in advanced. We also propose a strategy to address the limitation.
BibTeX
@misc{jin2013stochastic,
  author = {Rong Jin},
  title = {{Stochastic Optimization of Smooth Loss}},
  year = {2013},
  eprint = {1312.0048},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1312.0048},
}
Figure