Fugu-MT 論文翻訳(概要): Differentially Private Online Submodular Maximization

論文の概要: Differentially Private Online Submodular Maximization

arxiv url: http://arxiv.org/abs/2010.12816v1
Date: Sat, 24 Oct 2020 07:23:30 GMT
ステータス: 処理完了
システム内更新日: 2022-10-03 13:48:43.615560
Title: Differentially Private Online Submodular Maximization
Title（参考訳）: 個人別オンラインサブモジュールの最大化
Authors: Sebastian Perez-Salazar, Rachel Cummings
Abstract要約: 差分プライバシフィード(DP)を用いた基準制約下でのオンラインサブモジュラー関数の問題点について考察する。共通有限基底集合上の$T$サブモジュラー関数のストリームがオンラインに届き、各時点において、決定者は関数を観察する前に$U$のほとんどの$k$要素を選択する必要がある。意思決定者は、選択された集合で評価された関数に等しい報酬を得るとともに、期待の低い後悔を実現する一連の集合を学習することを目的とする。
参考スコア（独自算出の注目度）: 16.422215672356167
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: In this work we consider the problem of online submodular maximization under a cardinality constraint with differential privacy (DP). A stream of $T$ submodular functions over a common finite ground set $U$ arrives online, and at each time-step the decision maker must choose at most $k$ elements of $U$ before observing the function. The decision maker obtains a payoff equal to the function evaluated on the chosen set, and aims to learn a sequence of sets that achieves low expected regret. In the full-information setting, we develop an $(\varepsilon,\delta)$-DP algorithm with expected $(1-1/e)$-regret bound of $\mathcal{O}\left( \frac{k^2\log |U|\sqrt{T \log k/\delta}}{\varepsilon} \right)$. This algorithm contains $k$ ordered experts that learn the best marginal increments for each item over the whole time horizon while maintaining privacy of the functions. In the bandit setting, we provide an $(\varepsilon,\delta+ O(e^{-T^{1/3}}))$-DP algorithm with expected $(1-1/e)$-regret bound of $\mathcal{O}\left( \frac{\sqrt{\log k/\delta}}{\varepsilon} (k (|U| \log |U|)^{1/3})^2 T^{2/3} \right)$. Our algorithms contains $k$ ordered experts that learn the best marginal item to select given the items chosen her predecessors, while maintaining privacy of the functions. One challenge for privacy in this setting is that the payoff and feedback of expert $i$ depends on the actions taken by her $i-1$ predecessors. This particular type of information leakage is not covered by post-processing, and new analysis is required. Our techniques for maintaining privacy with feedforward may be of independent interest.
Abstract（参考訳）: 本研究では,微分プライバシー(dp)を持つ濃度制約の下でのオンラインサブモジュラー最大化の問題を考える。共通有限基底集合上の$T$サブモジュラー関数のストリームがオンラインに届き、各タイミングで決定者は関数を観察する前に$U$の最大$k$要素を選択する必要がある。意思決定者は、選択されたセットで評価された機能と同等の報酬を得て、期待される後悔の少ないセットのシーケンスを学習することを目指す。完全な情報設定では、$(1-1/e)$-regret の$\mathcal{o}\left( \frac{k^2\log |u|\sqrt{t \log k/\delta}}{\varepsilon} \right)$の$(\varepsilon,\delta)$-dpアルゴリズムを開発する。このアルゴリズムには,関数のプライバシを維持しながら,各項目に対する最善のマージンインクリメントを学習する,$k$順序付き専門家が含まれている。バンドイット設定では、$(\varepsilon,\delta+ o(e^{-t^{1/3}}))$-dpアルゴリズムを提供し、$(1-1/e)$-regret bound of $\mathcal{o}\left( \frac{\sqrt{\log k/\delta}}{\varepsilon} (k (|u| \log |u|)^{1/3})^2 t^{2/3} \right)$である。当社のアルゴリズムには、前任者の選択したアイテムを選択できる最善の限界アイテムを学習し、関数のプライバシを保ちながら、k$順序付けされた専門家が含まれています。この設定におけるプライバシの課題の1つは、専門家$i$の支払いとフィードバックが、前任者のアクションに依存することである。この種の情報漏洩は後処理ではカバーされず、新たな分析が必要である。フィードフォワードでプライバシーを維持する技術は、独立した関心事かもしれない。

関連論文リスト

Minimax Optimal Submodular Optimization with Bandit Feedback [13.805872311596739]
単調な部分モジュラー集合関数 $f: 2[n] rightarrow [0,1]$ をバンドイットフィードバックの下で最大化する。具体的には、$f$は学習者には知られていないが、各時点で$t=1,dots,T$は、$|S_t| leq k$でセットの$S_tサブセット[n]$を選択し、$eta_t$が平均ゼロのサブガウスノイズである場合に、$f(S_t) + eta_t$を受け取る。
論文参考訳（メタデータ） (2023-10-27T20:19:03Z)
Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。目標は、低ランク因子の積として$mathbfA$を近似することである。我々の手法はBMF問題の他の一般的な変種に一般化する。
論文参考訳（メタデータ） (2023-06-02T18:55:27Z)
Near-Optimal Algorithms for Private Online Optimization in the Realizable Regime [74.52487417350221]
オンライン学習の問題は,ゼロロスソリューションが存在する,実現可能な環境において考慮する。そこで我々は,ほぼ最適の後悔境界を求める新たなDPアルゴリズムを提案する。
論文参考訳（メタデータ） (2023-02-27T21:19:24Z)
Private Online Prediction from Experts: Separations and Faster Rates [74.52487417350221]
専門家によるオンライン予測は機械学習の基本的な問題であり、いくつかの研究がプライバシーの制約の下でこの問題を研究している。本研究では,非適応的敵に対する最良な既存アルゴリズムの残差を克服する新たなアルゴリズムを提案し,解析する。
論文参考訳（メタデータ） (2022-10-24T18:40:19Z)
Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
論文参考訳（メタデータ） (2022-02-10T16:10:41Z)
Faster Rates of Differentially Private Stochastic Convex Optimization [7.93728520583825]
人口リスク関数がTysbakovノイズ条件(TNC)をパラメータ$theta>1$で満たす場合について検討した。第2部では,人口リスク関数が強く凸する特殊な事例に着目した。
論文参考訳（メタデータ） (2021-07-31T22:23:39Z)
Improved Regret Bounds for Online Submodular Maximization [10.089520556398575]
我々は、各ステップ$tin[T]$において、固定凸からアクション$x_t$を選択し、コンパクトなドメインセット$mathcalK$を選択するオンライン最適化問題を考える。ユーティリティ関数 $f_t(cdot)$ が明らかになり、アルゴリズムはペイオフ $f_t(x_t)$ を受け取る。
論文参考訳（メタデータ） (2021-06-15T02:05:35Z)
Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文参考訳（メタデータ） (2021-03-02T06:53:44Z)
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)
Universal guarantees for decision tree induction via a higher-order splitting criterion [16.832966312395126]
本アルゴリズムは,全対象関数に対して,一様分布に対して, -1,1n から -1,1$ の証明可能な保証を実現する。我々の拡張の要点は、その属性の$f$と小さなサブセットの相関を考慮に入れた、新しい分割基準である。我々のアルゴリズムは以下の保証を満たす: すべての対象関数 $f : -1,1n to -1,1$, sizes $sin mathbbN$, error parameters $epsilon$ に対して、決定を構成する。
論文参考訳（メタデータ） (2020-10-16T21:20:45Z)

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

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