論文の概要: Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry

• arxiv url: http://arxiv.org/abs/2103.01516v1
• Date: Tue, 2 Mar 2021 06:53:44 GMT
• ステータス: 処理完了
• システム内更新日: 2021-03-03 16:58:05.228089
• Title: Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry
• Title（参考訳）: private stochastic convex optimization: optimal rate in $\ell_1$ geometry
• Authors: Hilal Asi, Vitaly Feldman, Tomer Koren, Kunal Talwar
• Abstract要約: 対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。 損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
• 参考スコア（独自算出の注目度）: 69.24618367447101
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Stochastic convex optimization over an $\ell_1$-bounded domain is ubiquitous in machine learning applications such as LASSO but remains poorly understood when learning with differential privacy. We show that, up to logarithmic factors the optimal excess population loss of any $(\varepsilon,\delta)$-differentially private optimizer is $\sqrt{\log(d)/n} + \sqrt{d}/\varepsilon n.$ The upper bound is based on a new algorithm that combines the iterative localization approach of~\citet{FeldmanKoTa20} with a new analysis of private regularized mirror descent. It applies to $\ell_p$ bounded domains for $p\in [1,2]$ and queries at most $n^{3/2}$ gradients improving over the best previously known algorithm for the $\ell_2$ case which needs $n^2$ gradients. Further, we show that when the loss functions satisfy additional smoothness assumptions, the excess loss is upper bounded (up to logarithmic factors) by $\sqrt{\log(d)/n} + (\log(d)/\varepsilon n)^{2/3}.$ This bound is achieved by a new variance-reduced version of the Frank-Wolfe algorithm that requires just a single pass over the data. We also show that the lower bound in this case is the minimum of the two rates mentioned above.
• Abstract（参考訳）: $\ell_1$-boundedドメインに対する確率的凸最適化は、LASSOのような機械学習アプリケーションではユビキタスだが、差分プライバシーで学ぶ際には理解されていない。 対数係数まで、任意の $(\varepsilon,\delta)$-differentially private optimizationr の最適過剰人口損失は $\sqrt{\log(d)/n} + \sqrt{d}/\varepsilon n.$ 上界は、~\citet{FeldmanKoTa20} の反復的局在化アプローチと、プライベート正規化ミラー降下の新しい解析を組み合わせた新しいアルゴリズムに基づいている。 p\in [1,2]$ の $\ell_p$ 境界付きドメインに適用され、最大 $n^{3/2}$ 勾配でのクエリは、$n^2$ 勾配を必要とする $\ell_2$ の場合に対する最もよく知られたアルゴリズムよりも改善される。 さらに、損失関数が追加の平滑性仮定を満たすと、余剰損失は $\sqrt{\log(d)/n} + (\log(d)/\varepsilon n)^{2/3}.$ この境界は、データの単一のパスを必要とするフランク・ウルフアルゴリズムの新しい分散還元バージョンによって達成される。 また、この場合の下限が上記の2つのレートの最小値であることも示します。

関連論文リスト

• Online Newton Method for Bandit Convex Optimisation [28.66596225688161]
  ゼロ階帯域幅の最適化のための計算効率の良いアルゴリズムを提案する。 逆条件では、その後悔は少なくとも$d3.5 sqrtn Mathrmpolylog(n, d)$であり、d$が時間的地平線である確率が高いことを証明している。 設定において、バウンダリは$M d2 sqrtn Mathrmpolylog(n, d)$に改善され、[d-1/2, d-1 / 4]$は$Mとなる。
  論文  参考訳（メタデータ） (2024-06-10T17:44:11Z)
• Near-Optimal Distributed Minimax Optimization under the Second-Order Similarity [22.615156512223763]
  本研究では,有限サム構造を目的とする分散楽観的すべり(SVOGS)法を提案する。 我々は$mathcal O(delta D2/varepsilon)$、$mathcal O(n+sqrtndelta D2/varepsilon)$、$tildemathcal O(n+sqrtndelta+L)D2/varepsilon)$の局所呼び出しを証明している。
  論文  参考訳（メタデータ） (2024-05-25T08:34:49Z)
• A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functions [44.655316553524855]
  我々は,$d$次元ユークリッド領域あるいは単純領域上で$max_iin[n] f_i(x) を最小化するアルゴリズムを設計する。 それぞれの$f_i$が1ドルLipschitzと1ドルSmoothのとき、我々の手法は$epsilon-approximateの解を計算する。
  論文  参考訳（メタデータ） (2023-11-17T22:07:18Z)
• ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
  本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。 我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-01-01T18:51:29Z)
• Differentially Private Stochastic Optimization: New Results in Convex and Non-Convex Settings [15.122617358656539]
  凸および非滑らかな一般損失(GLL)に対する微分プライベートアルゴリズムを提案する。 凸の場合、非滑らかな一般化損失(GLL)の族に焦点をあてる。
  論文  参考訳（メタデータ） (2021-07-12T17:06:08Z)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  我々は,バンディットフィードバックを用いてオンライン学習を学習する。 learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。 我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。 ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
  論文  参考訳（メタデータ） (2021-02-15T08:16:51Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• $Q$-learning with Logarithmic Regret [60.24952657636464]
  楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
  論文  参考訳（メタデータ） (2020-06-16T13:01:33Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。 もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
  論文  参考訳（メタデータ） (2020-02-17T18:41:49Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。