論文の概要: 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（参考訳）: 安全確率凸最適化問題について検討する。
学習者は(確率的な)勾配オラクルを逐次クエリすることで凸関数の最適点を学ぶことを目指している。
その間,学習者の学習結果を学習者のクエリを観察することから解放し,推論することを目的とした敵が存在する。
相手はクエリのポイントのみを観察するが、オラクルからのフィードバックは監視しない。
学習者の目標は、精度を最適化すること、すなわち、最適な点の正確な推定を得ること、そして彼女のプライバシーを確保すること、すなわち、敵が最適な点を推測することを困難にすることである。
我々は,学習者の精度とプライバシのトレードオフを正式に定量化し,学習者のクエリ複雑性の下位と上位の境界を,望ましいレベルの精度とプライバシの関数として特徴づける。
下限解析のために、情報理論的解析に基づく一般的なテンプレートを提供し、確率凸最適化や(ノイズの多い)二分探索など、いくつかの問題にテンプレートを合わせる。
また,対数要素に対する上位値のマッチングを実現する汎用的セキュア学習プロトコルを提案する。
関連論文リスト
- Accelerated zero-order SGD under high-order smoothness and overparameterized regime [79.85163929026146]
凸最適化問題を解くための新しい勾配のないアルゴリズムを提案する。
このような問題は医学、物理学、機械学習で発生する。
両種類の雑音下で提案アルゴリズムの収束保証を行う。
論文 参考訳（メタデータ） (2024-11-21T10:26:17Z) - Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。
本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
論文 参考訳（メタデータ） (2024-06-28T02:56:22Z) - Learning-Rate-Free Stochastic Optimization over Riemannian Manifolds [1.6385815610837167]
そこで本研究では,リーマン数に対する最適化のための革新的な学習速度自由アルゴリズムを提案する。
我々は、決定論的設定において最もよく知られた最適調整率と比較して、対数的要因まで最適である高い確率収束を保証する。
提案手法は数値実験によって検証され,学習速度依存アルゴリズムに対する競合性能が実証された。
論文 参考訳（メタデータ） (2024-06-04T13:17:24Z) - 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) - High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。
そこで我々は,勾配クリッピングを伴う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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。