論文の概要: Projection-Free Bandit Optimization with Privacy Guarantees
- arxiv url: http://arxiv.org/abs/2012.12138v1
- Date: Tue, 22 Dec 2020 16:19:29 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-26 07:15:16.077724
- Title: Projection-Free Bandit Optimization with Privacy Guarantees
- Title(参考訳): プライバシ保証によるプロジェクションフリー帯域最適化
- Authors: Alina Ene, Huy L. Nguyen, Adrian Vladu
- Abstract要約: プロジェクションフリー設定におけるバンディット凸最適化問題に対する微分プライベートアルゴリズムの設計を行う。
この設定は、決定集合が複素幾何学を持つときに重要であり、それへのアクセスは線型最適化オラクルを通してのみ効率的に行われる。
これはプロジェクションフリーなバンディット最適化のための最初の微分プライベートアルゴリズムであり、実際、$widetildeO(T3/4)$は最もよく知られた非プライベートなプロジェクションフリーアルゴリズムと一致する。
- 参考スコア(独自算出の注目度): 18.95253453749389
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We design differentially private algorithms for the bandit convex
optimization problem in the projection-free setting. This setting is important
whenever the decision set has a complex geometry, and access to it is done
efficiently only through a linear optimization oracle, hence Euclidean
projections are unavailable (e.g. matroid polytope, submodular base polytope).
This is the first differentially-private algorithm for projection-free bandit
optimization, and in fact our bound of $\widetilde{O}(T^{3/4})$ matches the
best known non-private projection-free algorithm (Garber-Kretzu, AISTATS `20)
and the best known private algorithm, even for the weaker setting when
projections are available (Smith-Thakurta, NeurIPS `13).
- Abstract(参考訳): プロジェクションフリー設定における帯域凸最適化問題に対して差分プライベートアルゴリズムを設計する。
この設定は、決定集合が複素幾何学を持つときに重要であり、それへのアクセスは線型最適化オラクルを通してのみ効率的に行われるので、ユークリッド射影は利用できない(例)。
マトロイドポリトープ (matroid polytope, submodular base polytope)。
これはプロジェクションフリーなバンディット最適化のための最初の微分プライベートアルゴリズムであり、実際は$\widetilde{O}(T^{3/4})$のバウンダリは、最もよく知られた非プライベートなプロジェクションフリーアルゴリズム(Garber-Kretzu, AISTATS `20)と、プロジェクションが利用可能であるときの弱い設定(Smith-Thakurta, NeurIPS `13)と一致する。
関連論文リスト
- Optimized Tradeoffs for Private Prediction with Majority Ensembling [59.99331405291337]
本稿では,データ依存型ランダム化応答行列(DaRRM)アルゴリズムを提案する。
DaRRMはデータ依存ノイズ関数$gamma$でパラメータ化され、全てのプライベートアルゴリズムのクラスに対して効率的なユーティリティ最適化を可能にする。
本稿では,DARRMが共通ベースラインよりも2倍のプライバシゲインを,固定ユーティリティで確実に享受していることを示す。
論文 参考訳(メタデータ) (2024-11-27T00:48:48Z) - Individualized Privacy Accounting via Subsampling with Applications in Combinatorial Optimization [55.81991984375959]
本研究では、以下の簡単な観察を通して、個別化されたプライバシ会計を解析する新しい手法を提案する。
我々は、分解可能な部分モジュラーおよびセットアルゴリズム被覆を含む、プライベート最適化問題に対するいくつかの改良されたアルゴリズムを得る。
論文 参考訳(メタデータ) (2024-05-28T19:02:30Z) - Fast Optimal Locally Private Mean Estimation via Random Projections [58.603579803010796]
ユークリッド球における高次元ベクトルの局所的プライベート平均推定の問題について検討する。
プライベート平均推定のための新しいアルゴリズムフレームワークであるProjUnitを提案する。
各ランダム化器はその入力をランダムな低次元部分空間に投影し、結果を正規化し、最適なアルゴリズムを実行する。
論文 参考訳(メタデータ) (2023-06-07T14:07:35Z) - Bring Your Own Algorithm for Optimal Differentially Private Stochastic
Minimax Optimization [44.52870407321633]
これらの設定の聖杯は、プライバシーと過剰な人口減少の間の最適なトレードオフを保証することです。
微分プライベート・ミニマックス最適化(DP-SMO)問題を解くための一般的なフレームワークを提供する。
我々のフレームワークは、非滑らかな微分プライベート凸最適化(DP-SCO)のための最近提案されたフェイズド・ERM法[20]から着想を得たものである。
論文 参考訳(メタデータ) (2022-06-01T10:03:20Z) - Optimal Algorithms for Mean Estimation under Local Differential Privacy [55.32262879188817]
そこで本研究では,PrivUnitが局所的プライベートな乱数化器群間の最適分散を実現することを示す。
また,ガウス分布に基づくPrivUnitの新たな変種も開発しており,数学的解析に適しており,同じ最適性保証を享受できる。
論文 参考訳(メタデータ) (2022-05-05T06:43:46Z) - Efficient Projection-Free Online Convex Optimization with Membership
Oracle [11.745866777357566]
ユークリッド球上で定義された任意のアルゴリズムAを、球に含まれる制約付き集合 C 上のアルゴリズムに変換する新しい還元法を提案する。
我々の削減には、O(T log T) を T ラウンド後に C 上で Oracle に呼び出しる必要があり、C 上の線形最適化は不要である。
論文 参考訳(メタデータ) (2021-11-10T17:22:29Z) - Adapting to Misspecification in Contextual Bandits [82.55565343668246]
我々は、$varepsilon$-misspecified contextual banditsに対して、新しいオラクル効率アルゴリズム群を導入する。
我々は、未知の不特定値に対して最適な$O(dsqrtT + varepsilonsqrtdT)$ regret boundを達成する最初のアルゴリズムを得る。
論文 参考訳(メタデータ) (2021-07-12T21:30:41Z) - No-Regret Algorithms for Private Gaussian Process Bandit Optimization [13.660643701487002]
プライバシー保護統計のレンズによるガウス過程(GP)帯域最適化の至るところでの問題点を考察する。
均一なカーネル近似器とランダムな摂動を組み合わせた差分プライベートGPバンディット最適化のためのソリューションを提案する。
我々のアルゴリズムは最適化手順を通して微分プライバシを保持し、予測のためのサンプルパスに明示的に依存しない。
論文 参考訳(メタデータ) (2021-02-24T18:52:24Z) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳(メタデータ) (2020-05-10T19:52:03Z) - Private Stochastic Convex Optimization: Efficient Algorithms for
Non-smooth Objectives [28.99826590351627]
本稿では,プライバシパラメータがサンプル数に比例する場合に,一階降下を実現する雑音ミラーに基づくアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-02-22T03:03:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。