Near-Optimal Algorithms for Private Online Optimization in the Realizable Regime

• URL: http://arxiv.org/abs/2302.14154v1
• Date: Mon, 27 Feb 2023 21:19:24 GMT
• Title: Near-Optimal Algorithms for Private Online Optimization in the Realizable Regime
• Authors: Hilal Asi, Vitaly Feldman, Tomer Koren, Kunal Talwar
• Abstract summary: We consider online learning problems in the realizable setting, where there is a zero-loss solution. We propose new Differentially Private (DP) algorithms that obtain near-optimal regret bounds.
• Score: 74.52487417350221
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider online learning problems in the realizable setting, where there is a zero-loss solution, and propose new Differentially Private (DP) algorithms that obtain near-optimal regret bounds. For the problem of online prediction from experts, we design new algorithms that obtain near-optimal regret ${O} \big( \varepsilon^{-1} \log^{1.5}{d} \big)$ where $d$ is the number of experts. This significantly improves over the best existing regret bounds for the DP non-realizable setting which are ${O} \big( \varepsilon^{-1} \min\big\{d, T^{1/3}\log d\big\} \big)$. We also develop an adaptive algorithm for the small-loss setting with regret $O(L^\star\log d + \varepsilon^{-1} \log^{1.5}{d})$ where $L^\star$ is the total loss of the best expert. Additionally, we consider DP online convex optimization in the realizable setting and propose an algorithm with near-optimal regret $O \big(\varepsilon^{-1} d^{1.5} \big)$, as well as an algorithm for the smooth case with regret $O \big( \varepsilon^{-2/3} (dT)^{1/3} \big)$, both significantly improving over existing bounds in the non-realizable regime.

Related papers

• Private Online Learning via Lazy Algorithms [52.772510023828744]
  We study the problem of private online learning, specifically, online prediction from experts (OPE) and online convex optimization (OCO) We propose a new transformation that transforms lazy online learning algorithms into private algorithms.
  arXiv  Detail & Related papers  (2024-06-05T20:43:05Z)
• DP-Dueling: Learning from Preference Feedback without Compromising User Privacy [32.58099924135157]
  We give the first differentially private dueling bandit algorithm for active learning with user preferences. Our algorithms are computationally efficient with near-optimal performance. We extend our results to any general decision space in $d$-dimensions with potentially infinite arms.
  arXiv  Detail & Related papers  (2024-03-22T09:02:12Z)
• Nearly Optimal Regret for Decentralized Online Convex Optimization [53.433398074919]
  Decentralized online convex optimization (D-OCO) aims to minimize a sequence of global loss functions using only local computations and communications. We develop novel D-OCO algorithms that can respectively reduce the regret bounds for convex and strongly convex functions. Our algorithms are nearly optimal in terms of $T$, $n$, and $rho$.
  arXiv  Detail & Related papers  (2024-02-14T13:44:16Z)
• Private Online Prediction from Experts: Separations and Faster Rates [74.52487417350221]
  Online prediction from experts is a fundamental problem in machine learning and several works have studied this problem under privacy constraints. We propose and analyze new algorithms for this problem that improve over the regret bounds of the best existing algorithms for non-adaptive adversaries.
  arXiv  Detail & Related papers  (2022-10-24T18:40:19Z)
• Differentially Private Stochastic Optimization: New Results in Convex and Non-Convex Settings [15.122617358656539]
  We present differentially private algorithms for convex and non-smooth general losses (GLLs) For the convex case, we focus on the family of non-smooth generalized losses (GLLs)
  arXiv  Detail & Related papers  (2021-07-12T17:06:08Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  Up to logarithmic factors the optimal excess population loss of any $(varepsilon,delta)$-differently private is $sqrtlog(d)/n + sqrtd/varepsilon n.$ We show that when the loss functions satisfy additional smoothness assumptions, the excess loss is upper bounded (up to logarithmic factors) by $sqrtlog(d)/n + (log(d)/varepsilon n)2/3.
  arXiv  Detail & Related papers  (2021-03-02T06:53:44Z)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  We study online learning with bandit feedback (i.e. learner has access to only zeroth-order oracle) where cost/reward functions admit a "pseudo-1d" structure. We show a lower bound of $min(sqrtdT, T3/4)$ for the regret of any algorithm, where $T$ is the number of rounds. We propose a new algorithm sbcalg that combines randomized online gradient descent with a kernelized exponential weights method to exploit the pseudo-1d structure effectively.
  arXiv  Detail & Related papers  (2021-02-15T08:16:51Z)

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.