Shuffle Private Stochastic Convex Optimization

• URL: http://arxiv.org/abs/2106.09805v1
• Date: Thu, 17 Jun 2021 20:44:00 GMT
• Title: Shuffle Private Stochastic Convex Optimization
• Abstract summary: In shuffle privacy, each user sends a collection of randomized messages to a trusted shuffler. The shuffler randomly permutes these messages, and the resulting shuffled collection of messages must satisfy differential privacy. We present interactive shuffle protocols for convex optimization.
• Score: 20.379311972125034
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: In shuffle privacy, each user sends a collection of randomized messages to a trusted shuffler, the shuffler randomly permutes these messages, and the resulting shuffled collection of messages must satisfy differential privacy. Prior work in this model has largely focused on protocols that use a single round of communication to compute algorithmic primitives like means, histograms, and counts. In this work, we present interactive shuffle protocols for stochastic convex optimization. Our optimization protocols rely on a new noninteractive protocol for summing vectors of bounded $\ell_2$ norm. By combining this sum subroutine with techniques including mini-batch stochastic gradient descent, accelerated gradient descent, and Nesterov's smoothing method, we obtain loss guarantees for a variety of convex loss functions that significantly improve on those of the local model and sometimes match those of the central model.

Related papers

• Learning to Shuffle: Block Reshuffling and Reversal Schemes for Stochastic Optimization [20.63685754619351]
  We use a large language model (LLM)-guided program evolution framework to discover an effective shuffling rule for without replacing SGD.<n>We show that block reshuffling strictly reduces prefix-gradient variance constants within the unified shuffling, yielding provable improvements over random reshuffling under mild conditions.<n>We also show that paired reversal symmetrizes the epoch map and cancels the leading order-dependent second-order term, reducing order sensitivity from quadratic to cubic in the step size.
  arXiv  Detail & Related papers  (2026-03-31T21:40:43Z)
• Convergence Rate of the Last Iterate of Stochastic Proximal Algorithms [8.636513507553504]
  We analyze two classical algorithms for solving additively composite convex optimization problems.<n>We focus on the bounded variance assumption that is common, yet stringent, for getting last iterate convergence rates.<n>Our results apply directly to graph-guided regularizers that arise in multi-task and federated learning, where the regularizer decomposes as a sum over edges of a collaboration graph.
  arXiv  Detail & Related papers  (2026-02-05T09:50:06Z)
• Zeroth-Order Methods for Stochastic Nonconvex Nonsmooth Composite Optimization [51.63258496873442]
  Previous works on composite optimization problem requires the major part to smoothness or some machine learning examples which excludes such two approximate smoothness points respectively.<n>In this work we propose two new algorithms for such problem.<n>We show that these algorithms are effective using numerical experiments.
  arXiv  Detail & Related papers  (2025-10-06T02:35:42Z)
• Improved Last-Iterate Convergence of Shuffling Gradient Methods for Nonsmooth Convex Optimization [21.865728815935665]
  We show that Random Reshuffle ($textsfRR$) and Single Shuffle ($textsfSS$) strategies are both provably faster than Proximal GD.<n>As an important implication, we give the first (nearly) optimal convergence result for the suffix average under the $textsfRR$ sampling scheme.
  arXiv  Detail & Related papers  (2025-05-29T03:53:45Z)
• Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Inequality Constraints [12.624604051853657]
  We propose smoothed primal-dual algorithms for solving nonexact optimization problems with linear inequality constraints. Our algorithms are single-loop iterations based on one gradient at each sample. Unlike existing methods, our algorithms are free sub, large sizes or increasing parameters and use dual variable updates to ensure feasibility.
  arXiv  Detail & Related papers  (2025-04-10T09:59:43Z)
• Smoothed Normalization for Efficient Distributed Private Optimization [54.197255548244705]
  Federated learning enables machine learning models with privacy of participants. There is no differentially private distributed method for training, non-feedback problems. We introduce a new distributed algorithm $alpha$-$sf NormEC$ with provable convergence guarantees.
  arXiv  Detail & Related papers  (2025-02-19T07:10:32Z)
• Efficient Fault-Tolerant Quantum Protocol for Differential Privacy in the Shuffle Model [2.0794380287086214]
  We present a quantum protocol which implicitly implements a random shuffle to realize differential privacy in the shuffle model. The shuffle model amplifies outcomes achievable from data contributors. Examples include implementing the shuffle via mix-networks, or shuffling via a trusted third-party. We propose a quantum version of the protocol using entanglement of quantum states and show that the shuffle can be implemented without these extra requirements.
  arXiv  Detail & Related papers  (2024-09-06T04:53:19Z)
• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  We consider the problem of optimizing second-order smooth and strongly convex functions where the algorithm is only accessible to noisy evaluations of the objective function it queries. We provide the first tight characterization for the rate of the minimax simple regret by developing matching upper and lower bounds.
  arXiv  Detail & Related papers  (2024-06-28T02:56:22Z)
• Fast Semisupervised Unmixing Using Nonconvex Optimization [80.11512905623417]
  We introduce a novel convex convex model for semi/library-based unmixing. We demonstrate the efficacy of Alternating Methods of sparse unsupervised unmixing.
  arXiv  Detail & Related papers  (2024-01-23T10:07:41Z)
• Distributed stochastic proximal algorithm with random reshuffling for non-smooth finite-sum optimization [28.862321453597918]
  Non-smooth finite-sum minimization is a fundamental problem in machine learning. This paper develops a distributed proximal-gradient algorithm with random reshuffling to solve the problem.
  arXiv  Detail & Related papers  (2021-11-06T07:29:55Z)
• A Stochastic Newton Algorithm for Distributed Convex Optimization [62.20732134991661]
  We analyze a Newton algorithm for homogeneous distributed convex optimization, where each machine can calculate gradients of the same population objective. We show that our method can reduce the number, and frequency, of required communication rounds compared to existing methods without hurting performance.
  arXiv  Detail & Related papers  (2021-10-07T17:51:10Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  We address the non- optimisation problem of finding a matrix on the Stiefel manifold that maximises a quadratic objective function. We propose a simple yet effective sparsity-promoting algorithm for finding the dominant eigenspace matrix.
  arXiv  Detail & Related papers  (2021-09-30T19:17:35Z)
• Parallel Stochastic Mirror Descent for MDPs [72.75921150912556]
  We consider the problem of learning the optimal policy for infinite-horizon Markov decision processes (MDPs) Some variant of Mirror Descent is proposed for convex programming problems with Lipschitz-continuous functionals. We analyze this algorithm in a general case and obtain an estimate of the convergence rate that does not accumulate errors during the operation of the method.
  arXiv  Detail & Related papers  (2021-02-27T19:28:39Z)
• On the Benefits of Multiple Gossip Steps in Communication-Constrained Decentralized Optimization [29.42301299741866]
  We show that having $O(logfrac1epsilon)$ iterations with constant step size - $O(logfrac1epsilon)$ - enables convergence to within $epsilon$ of the optimal value for smooth non- compressed gradient objectives. To our knowledge, this is the first work that derives the convergence results for non optimization under compressed communication compression parameters.
  arXiv  Detail & Related papers  (2020-11-20T21:17:32Z)
• SGD with shuffling: optimal rates without component convexity and large epoch requirements [60.65928290219793]
  We consider the RandomShuffle (shuffle at the beginning of each epoch) and SingleShuffle (shuffle only once) We establish minimax optimal convergence rates of these algorithms up to poly-log factor gaps. We further sharpen the tight convergence results for RandomShuffle by removing the drawbacks common to all prior arts.
  arXiv  Detail & Related papers  (2020-06-12T05:00:44Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.