論文の概要: Optimal Query Complexity of Secure Stochastic Convex Optimization
- arxiv url: http://arxiv.org/abs/2104.01926v1
- Date: Mon, 5 Apr 2021 14:10:26 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-06 14:28:06.677322
- Title: Optimal Query Complexity of Secure Stochastic Convex Optimization
- Title(参考訳): secure stochastic convex optimizationの最適クエリ複雑性
- Authors: Wei Tang, Chien-Ju Ho, Yang Liu
- Abstract要約: 安全凸最適化問題について検討する。
学習者は(確率的な)勾配を逐次クエリすることで凸関数の最適点を学習することを目指している。
その間,学習者の学習結果を学習者のクエリを観察することから解放し,推論することを目的とした敵が存在する。
- 参考スコア(独自算出の注目度): 17.35823773611766
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the secure stochastic convex optimization problem. A learner aims to
learn the optimal point of a convex function through sequentially querying a
(stochastic) gradient oracle. In the meantime, there exists an adversary who
aims to free-ride and infer the learning outcome of the learner from observing
the learner's queries. The adversary observes only the points of the queries
but not the feedback from the oracle. The goal of the learner is to optimize
the accuracy, i.e., obtaining an accurate estimate of the optimal point, while
securing her privacy, i.e., making it difficult for the adversary to infer the
optimal point. We formally quantify this tradeoff between learner's accuracy
and privacy and characterize the lower and upper bounds on the learner's query
complexity as a function of desired levels of accuracy and privacy. For the
analysis of lower bounds, we provide a general template based on information
theoretical analysis and then tailor the template to several families of
problems, including stochastic convex optimization and (noisy) binary search.
We also present a generic secure learning protocol that achieves the matching
upper bound up to logarithmic factors.
- Abstract(参考訳): 安全確率凸最適化問題について検討する。
学習者は(確率的な)勾配オラクルを逐次クエリすることで凸関数の最適点を学ぶことを目指している。
その間,学習者の学習結果を学習者のクエリを観察することから解放し,推論することを目的とした敵が存在する。
相手はクエリのポイントのみを観察するが、オラクルからのフィードバックは監視しない。
学習者の目標は、精度を最適化すること、すなわち、最適な点の正確な推定を得ること、そして彼女のプライバシーを確保すること、すなわち、敵が最適な点を推測することを困難にすることである。
我々は,学習者の精度とプライバシのトレードオフを正式に定量化し,学習者のクエリ複雑性の下位と上位の境界を,望ましいレベルの精度とプライバシの関数として特徴づける。
下限解析のために、情報理論的解析に基づく一般的なテンプレートを提供し、確率凸最適化や(ノイズの多い)二分探索など、いくつかの問題にテンプレートを合わせる。
また,対数要素に対する上位値のマッチングを実現する汎用的セキュア学習プロトコルを提案する。
関連論文リスト
- Controlling Federated Learning for Covertness [15.878313629774269]
学習者は、ノイズの多い勾配評価を提供する分散オラクルを何度もクエリすることで、関数の$f$を最小化することを目指している。
同時に、学習者は、学習者のクエリを監視する悪意のある盗聴者から$argmin f$を隠そうとする。
本稿では,学習者が学習と難読化のどちらを動的に選択するかという,textitcovert や textitlearner-private 最適化の問題について考察する。
論文 参考訳(メタデータ) (2023-08-17T07:16:41Z) - Smoothed Analysis of Sequential Probability Assignment [16.090378928208885]
本稿では,情報理論的に最適であるminmaxレートと,最大極大推定器オラクルを含むアルゴリズム削減の枠組みについて検討する。
提案手法は,スムーズな逆数に対する逐次確率割当のためのミニマックスレートから,トランスダクティブ学習のためのミニマックスレートへの汎用的な削減を実現する。
論文 参考訳(メタデータ) (2023-03-08T19:25:57Z) - Smoothed Online Learning is as Easy as Statistical Learning [77.00766067963195]
この設定では、最初のオラクル効率、非回帰アルゴリズムを提供する。
古典的な設定で関数クラスが学習可能な場合、文脈的包帯に対するオラクル効率のよい非回帰アルゴリズムが存在することを示す。
論文 参考訳(メタデータ) (2022-02-09T19:22:34Z) - A Boosting Approach to Reinforcement Learning [59.46285581748018]
複雑度が状態数に依存しない意思決定プロセスにおける強化学習のための効率的なアルゴリズムについて検討する。
このような弱い学習手法の精度を向上させることができる効率的なアルゴリズムを提供する。
論文 参考訳(メタデータ) (2021-08-22T16:00:45Z) - Near-Optimal High Probability Complexity Bounds for Non-Smooth
Stochastic Optimization with Heavy-Tailed Noise [63.304196997102494]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
既存の非滑らか凸最適化法は、負のパワーまたは対数的な信頼度に依存する境界の複雑さを持つ。
クリッピングを用いた2つの勾配法に対して, 新たなステップサイズルールを提案する。
論文 参考訳(メタデータ) (2021-06-10T17:54:21Z) - Lower Bounds on Cross-Entropy Loss in the Presence of Test-time
Adversaries [33.53470955144013]
本論文では,テストタイムの逆数の存在下でのクロスエントロピー損失の最適下限と,それに対応する最適分類出力を決定する。
また、この下界を効率的に計算するベスポークアルゴリズムの正しさの証明を提案し、提案する。
我々は,現在のロバストなトレーニング手法の有効性を判定するための診断ツールとして下限を用い,より大きな予算での最適性とのギャップを見出した。
論文 参考訳(メタデータ) (2021-04-16T21:41:28Z) - Learner-Private Online Convex Optimization [24.204781914017758]
オンライン凸最適化において,学習者のクエリを最適に難読化する方法について検討する。
本結果は,全次フィードバックを持つ一般凸関数のよりリッチなファミリに適用できる。
論文 参考訳(メタデータ) (2021-02-23T23:00:44Z) - Online Model Selection for Reinforcement Learning with Function
Approximation [50.008542459050155]
我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。
また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
論文 参考訳(メタデータ) (2020-11-19T10:00:54Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳(メタデータ) (2020-09-28T15:22:24Z) - Exploiting Higher Order Smoothness in Derivative-free Optimization and
Continuous Bandits [99.70167985955352]
強凸関数のゼロ次最適化問題について検討する。
予測勾配降下アルゴリズムのランダム化近似を考察する。
その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
論文 参考訳(メタデータ) (2020-06-14T10:42:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。