English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study differentially private (DP) stochastic optimization (SO) with lossfunctions whose worst-case Lipschitz parameter over all data points may beextremely large. To date, the vast majority of work on DP SO assumes that theloss is uniformly Lipschitz continuous over data (i.e. stochastic gradients areuniformly bounded over all data points). While this assumption is convenient,it often leads to pessimistic excess risk bounds. In many practical problems,the worst-case (uniform) Lipschitz parameter of the loss over all data pointsmay be extremely large due to outliers. In such cases, the error bounds for DPSO, which scale with the worst-case Lipschitz parameter of the loss, arevacuous. To address these limitations, this work provides near-optimal excessrisk bounds that do not depend on the uniform Lipschitz parameter of the loss.Building on a recent line of work (Wang et al., 2020; Kamath et al., 2022), weassume that stochastic gradients have bounded $k$-th order moments for some $k\geq 2$. Compared with works on uniformly Lipschitz DP SO, our excess riskscales with the $k$-th moment bound instead of the uniform Lipschitz parameterof the loss, allowing for significantly faster rates in the presence ofoutliers and/or heavy-tailed data. For convex and strongly convex lossfunctions, we provide the first asymptotically optimal excess risk bounds (upto a logarithmic factor). In contrast to (Wang et al., 2020; Kamath et al.,2022), our bounds do not require the loss function to be differentiable/smooth.We also devise a linear-time algorithm for smooth losses that has excess riskthat is tight in certain practical parameter regimes. Additionally, our work isthe first to address non-convex non-uniformly Lipschitz loss functionssatisfying the Proximal-PL inequality; this covers some practical machinelearning models. Our Proximal-PL algorithm has near-optimal excess risk.

Private Stochastic Optimization With Large Worst-Case Lipschitz  Parameter: Optimal Rates for (Non-Smooth) Convex Losses and Extension to  Non-Convex Losses