More Like this

1. On the Generalization Error of Stochastic Mirror Descent for Quadratically-Bounded Losses: an Improved Analysis

   Nguyen, Ta Duy; Ene, Alina; Nguyen, Huy L (December 2023, Advances in neural information processing systems)

   In this work, we revisit the generalization error of stochastic mirror descent for quadratically bounded losses studied in Telgarsky (2022). Quadratically bounded losses is a broad class of loss functions, capturing both Lipschitz and smooth functions, for both regression and classification problems. We study the high probability generalization for this class of losses on linear predictors in both realizable and non-realizable cases when the data are sampled IID or from a Markov chain. The prior work relies on an intricate coupling argument between the iterates of the original problem and those projected onto a bounded domain. This approach enables blackbox application of concentration inequalities, but also leads to suboptimal guarantees due in part to the use of a union bound across all iterations. In this work, we depart significantly from the prior work of Telgarsky (2022), and introduce a novel approach for establishing high probability generalization guarantees. In contrast to the prior work, our work directly analyzes the moment generating function of a novel supermartingale sequence and leverages the structure of stochastic mirror descent. As a result, we obtain improved bounds in all aforementioned settings. Specifically, in the realizable case and non-realizable case with light-tailed sub-Gaussian data, we improve the bounds by a $$\log T$$ factor, matching the correct rates of $1/T$ and $$1/\sqrt{T}$$, respectively. In the more challenging case of heavy-tailed polynomial data, we improve the existing bound by a $$\mathrm{poly}\ T$$ factor. 

   more » « less
2. Improved Convergence in High Probability of Clipped Gradient Methods with Heavy Tailed Noise

   Nguyen, Ta Duy; Nguyen, Thien Hang; Ene, Alina; Nguyen, Huy L (December 2023, Advances in neural information processing systems)

   In this work, we study the convergence in high probability of clipped gradient methods when the noise distribution has heavy tails, i.e., with bounded $$p$$th moments, for some $$1< p \leq 2$$. Prior works in this setting follow the same recipe of using concentration inequalities and an inductive argument with union bound to bound the iterates across all iterations. This method results in an increase in the failure probability by a factor of $$T$$, where $$T$$ is the number of iterations. We instead propose a new analysis approach based on bounding the moment generating function of a well chosen supermartingale sequence. We improve the dependency on $$T$$ in the convergence guarantee for a wide range of algorithms with clipped gradients, including stochastic (accelerated) mirror descent for convex objectives and stochastic gradient descent for nonconvex objectives. Our high probability bounds achieve the optimal convergence rates and match the best currently known in-expectation bounds. Our approach naturally allows the algorithms to use time-varying step sizes and clipping parameters when the time horizon is unknown, which appears difficult or even impossible using existing techniques from prior works. Furthermore, we show that in the case of clipped stochastic mirror descent, several problem constants, including the initial distance to the optimum, are not required when setting step sizes and clipping parameters. 

   more » « less
3. Improved Convergence in High Probability of Clipped Gradient Methods with Heavy Tailed Noise

   Nguyen, Ta Duy; Nguyen, Thien Hang; Ene, Alina; Nguyen, Huy (September 2023, Advances in Neural Information Processing Systems)

   In this work, we study the convergence \emph{in high probability} of clipped gradient methods when the noise distribution has heavy tails, i.e., with bounded $$p$$th moments, for some $$1 

   more » « less
4. Tail-Limited Phase-Type Burstiness Bounds for Network Traffic

   https://doi.org/10.1109/CISS.2019.8692817  

   Boroujeny, Massieh Kordi; Mark, Brian L.; Ephraim, Yariv (March 2019, 2019 53rd Annual Conference on Information Sciences and Systems (CISS))

   The bursty nature of network traffic makes it difficult to characterize accurately, and may give rise to heavy-tailed queue distributions within the network. Building on prior work in stochastic network calculus, we propose traffic burstiness bounds based on the class of phase-type distributions and develop an approach to estimate the parameter of such bounds using the expectation-maximization (EM) algorithm. By limiting the tail of the burstiness bound, our approach achieves a better fit of the phase-type distribution to the empirical data from heavy-tailed traffic. The proposed tail-limited phase-type burstiness bounds fall within the framework for stochastic network calculus based on generalized stochastically bounded burstiness. We demonstrate the effectiveness of the proposed methodology with a numerical example involving a heavy-tailed M/G/1 queue. 

   more » « less
5. Uniform-in-Time Wasserstein Stability Bounds for (Noisy) Stochastic Gradient Descent

   Zhu, Lingjiong; Gurbuzbalaban, Mert; Raj, Anant; Simsekli, Umut (December 2023, Advances in neural information processing systems)

   Algorithmic stability is an important notion that has proven powerful for deriving generalization bounds for practical algorithms. The last decade has witnessed an increasing number of stability bounds for different algorithms applied on different classes of loss functions. While these bounds have illuminated various properties of optimization algorithms, the analysis of each case typically required a different proof technique with significantly different mathematical tools. In this study, we make a novel connection between learning theory and applied probability and introduce a unified guideline for proving Wasserstein stability bounds for stochastic optimization algorithms. We illustrate our approach on stochastic gradient descent (SGD) and we obtain time-uniform stability bounds (i.e., the bound does not increase with the number of iterations) for strongly convex losses and non-convex losses with additive noise, where we recover similar results to the prior art or extend them to more general cases by using a single proof technique. Our approach is flexible and can be generalizable to other popular optimizers, as it mainly requires developing Lyapunov functions, which are often readily available in the literature. It also illustrates that ergodicity is an important component for obtaining time uniform bounds – which might not be achieved for convex or non-convex losses unless additional noise is injected to the iterates. Finally, we slightly stretch our analysis technique and prove time-uniform bounds for SGD under convex and non-convex losses (without additional additive noise), which, to our knowledge, is novel. 

   more » « less