Large Deviations of Vector-valued Martingales in 2-Smooth Normed Spaces

Abstract

We derive exponential bounds on probabilities of large deviations for "light tail" martingales taking values in finite-dimensional normed spaces. Our primary emphasis is on the case where the bounds are dimension-independent or nearly so. We demonstrate that this is the case when the norm on the space can be approximated, within an absolute constant factor, by a norm which is differentiable on the unit sphere with a Lipschitz continuous gradient. We also present various examples of spaces possessing the latter property.

Cited by in corpus (18)

• Fast and Robust Recursive Algorithms for Separable Nonnegative Matrix Factorization
• Regularization for Cox's proportional hazards model with NP-dimensionality
• Loss minimization and parameter estimation with heavy tails
• Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming
• A Universal Algorithm for Variational Inequalities Adaptive to Smoothness and Noise
• Projection-Free Optimization on Uniformly Convex Sets
• Exponentiated Gradient Meets Gradient Descent
• On Primal-Dual Approach for Distributed Stochastic Convex Optimization over Networks
• Differentially Private Stochastic Optimization: New Results in Convex and Non-Convex Settings
• Faster PAC Learning and Smaller Coresets via Smoothed Analysis
• Heuristic adaptive fast gradient method in stochastic optimization tasks
• Streaming k-PCA: Efficient guarantees for Oja's algorithm, beyond rank-one updates
• Non-asymptotic confidence bounds for the optimal value of a stochastic program
• An $\tilde{\mathcal{O}}(m/{\epsilon }^{3.5})$-Cost Algorithm for Semidefinite Programs with Diagonal Constraints
• Implicit Regularization in Matrix Sensing via Mirror Descent
• An Optimal Affine Invariant Smooth Minimization Algorithm
• On solving large scale polynomial convex problems by randomized first-order algorithms
• Adaptive fast gradient method in stochastic optimization tasks