{'fraction_non_alphanumeric': 0.03166590178981184, 'fraction_numerical': 0.005048187241854061, 'mean_word_length': 4.956284153005464, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Private Stochastic Optimization in the Presence of Outliers: Optimal Rates for (Non-Smooth) Convex Losses and Extension to Non-Convex Losses

We study diﬀerentially private (DP) stochastic optimization (SO) with data containing outliers and loss functions that are not Lipschitz continuous. To date, the vast majority of work on DP SO assumes that the loss is Lipschitz (i.e. stochastic gradients are uniformly bounded), and their error bounds scale with the Lipschitz parameter of the loss. While this assumption is convenient, it is often unrealistic: in many practical problems where privacy is required, data may contain outliers and/or be unbounded, causing some stochastic gradients to have large norm. In such cases, the Lipschitz parameter may be prohibitively large, leading to vacuous excess risk bounds. Thus, building on a recent line of work [WXDX20, KLZ22], we make the weaker assumption that stochastic gradients have bounded k -th moments for some k ě 2 . Compared with works on DP Lipschitz SO, our excess risk scales with the k -th moment bound instead of the Lipschitz parameter of the loss, allowing for signiﬁcantly faster rates in the presence of outliers. For convex and strongly convex loss functions, we provide the ﬁrst asymptotically optimal excess risk bounds (up to a logarithmic factor). Moreover, in contrast to the prior works [WXDX20, KLZ22], our bounds do not require the loss function to be diﬀerentiable/smooth. We also devise an accelerated algorithm that runs in linear time and yields improved (compared to prior works) and nearly optimal excess risk for smooth losses. Additionally, our work is the ﬁrst to address non-convex non-Lipschitz loss functions satisfying the Proximal-PL inequality ; this covers some classes of neural nets, among other practical models. Our Proximal-PL algorithm has nearly optimal excess risk that almost matches the strongly convex lower bound. Lastly, we provide shuﬄe DP variations of our algorithms, which do not require a trusted curator (e.g. for distributed learning). for stochastic optimization results in the same excess risk bounds as one would get by using Algorithm 12, up to logarithmic factors.