論文の概要: Stochastic Adaptive Line Search for Differentially Private Optimization
- arxiv url: http://arxiv.org/abs/2008.07978v2
- Date: Thu, 27 Aug 2020 05:49:54 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-27 20:55:19.711037
- Title: Stochastic Adaptive Line Search for Differentially Private Optimization
- Title（参考訳）: 微分プライベート最適化のための確率的適応線探索
- Authors: Chen Chen, Jaewoo Lee
- Abstract要約: プライベート勾配に基づく最適化アルゴリズムの性能は、選択ステップサイズ(または学習率)に大きく依存する。
ノイズ勾配の信頼性に応じて、プライバシー勾配を調整する古典的非自明な行探索アルゴリズムを提案する。
適応的に選択されたステップサイズにより、提案アルゴリズムは、プライバシ予算を効率的に利用し、既存のプライベートグラデーションと競合する性能を示すことができる。
- 参考スコア（独自算出の注目度）: 6.281099620056346
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The performance of private gradient-based optimization algorithms is highly
dependent on the choice of step size (or learning rate) which often requires
non-trivial amount of tuning. In this paper, we introduce a stochastic variant
of classic backtracking line search algorithm that satisfies R\'enyi
differential privacy. Specifically, the proposed algorithm adaptively chooses
the step size satsisfying the the Armijo condition (with high probability)
using noisy gradients and function estimates. Furthermore, to improve the
probability with which the chosen step size satisfies the condition, it adjusts
per-iteration privacy budget during runtime according to the reliability of
noisy gradient. A naive implementation of the backtracking search algorithm may
end up using unacceptably large privacy budget as the ability of adaptive step
size selection comes at the cost of extra function evaluations. The proposed
algorithm avoids this problem by using the sparse vector technique combined
with the recent privacy amplification lemma. We also introduce a privacy budget
adaptation strategy in which the algorithm adaptively increases the budget when
it detects that directions pointed by consecutive gradients are drastically
different. Extensive experiments on both convex and non-convex problems show
that the adaptively chosen step sizes allow the proposed algorithm to
efficiently use the privacy budget and show competitive performance against
existing private optimizers.
- Abstract（参考訳）: プライベート勾配に基づく最適化アルゴリズムの性能は、しばしば非自明なチューニングを必要とするステップサイズ(または学習率)の選択に大きく依存する。
本稿では,R'enyi差分プライバシーを満たす古典的バックトラックライン探索アルゴリズムの確率的変種を紹介する。
具体的には、雑音勾配と関数推定を用いて、Armijo条件(高い確率で)を満たすステップサイズを適応的に選択する。
さらに、選択したステップサイズが条件を満たす確率を改善するため、ノイズ勾配の信頼性に応じて、実行時に設定毎のプライバシー予算を調整する。
バックトラッキング探索アルゴリズムのナイーブな実装は、追加機能評価のコストで適応的なステップサイズ選択の能力が得られるため、容認できないほど大きなプライバシー予算を使用する可能性がある。
提案アルゴリズムは,近年のプライバシ増幅補題と組み合わせたスパースベクトル法を用いてこの問題を回避する。
また,連続的な勾配で示される方向が著しく異なることを検出すると,アルゴリズムが予算を適応的に増加させるプライバシー予算適応戦略を導入する。
凸問題と非凸問題の両方に関する広範な実験により、適応的に選択されたステップサイズにより、提案アルゴリズムは、プライバシ予算を効率的に利用し、既存のプライベートオプティマイザとの競合性能を示すことができる。
関連論文リスト
- On Constructing Algorithm Portfolios in Algorithm Selection for Computationally Expensive Black-box Optimization in the Fixed-budget Setting [0.0]
本稿では,アルゴリズムポートフォリオ構築におけるサンプリングフェーズにおける関数評価の回数を考慮することの重要性を論じる。
その結果,提案手法により構築されたアルゴリズムのポートフォリオは,従来の手法よりも大幅に向上していることがわかった。
論文 参考訳（メタデータ） (2024-05-13T03:31:13Z) - Dynamic Privacy Allocation for Locally Differentially Private Federated
Learning with Composite Objectives [10.528569272279999]
本稿では,強い凸性を持つが非滑らかな問題に対する差分プライベートなフェデレーション学習アルゴリズムを提案する。
提案アルゴリズムは、共有情報に人工ノイズを加えてプライバシーを確保するとともに、時間変化のノイズ分散を動的に割り当て、最適化誤差の上限を最小化する。
解析結果から,提案手法が最先端手法よりも優れていることを示す。
論文 参考訳（メタデータ） (2023-08-02T13:30:33Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳（メタデータ） (2023-02-01T08:50:48Z) - Generalizing Bayesian Optimization with Decision-theoretic Entropies [102.82152945324381]
統計的決定論の研究からシャノンエントロピーの一般化を考える。
まず,このエントロピーの特殊なケースがBO手順でよく用いられる獲得関数に繋がることを示す。
次に、損失に対する選択肢の選択が、どのようにして柔軟な獲得関数の族をもたらすかを示す。
論文 参考訳（メタデータ） (2022-10-04T04:43:58Z) - Differentially Private Stochastic Gradient Descent with Low-Noise [49.981789906200035]
現代の機械学習アルゴリズムは、データからきめ細かい情報を抽出して正確な予測を提供することを目的としており、プライバシー保護の目標と矛盾することが多い。
本稿では、プライバシを保ちながら優れたパフォーマンスを確保するために、プライバシを保存する機械学習アルゴリズムを開発することの実践的および理論的重要性について論じる。
論文 参考訳（メタデータ） (2022-09-09T08:54:13Z) - Bring Your Own Algorithm for Optimal Differentially Private Stochastic
Minimax Optimization [44.52870407321633]
これらの設定の聖杯は、プライバシーと過剰な人口減少の間の最適なトレードオフを保証することです。
微分プライベート・ミニマックス最適化(DP-SMO)問題を解くための一般的なフレームワークを提供する。
我々のフレームワークは、非滑らかな微分プライベート凸最適化(DP-SCO)のための最近提案されたフェイズド・ERM法[20]から着想を得たものである。
論文 参考訳（メタデータ） (2022-06-01T10:03:20Z) - Adaptive Differentially Private Empirical Risk Minimization [95.04948014513226]
本稿では,適応的(確率的)勾配摂動法を提案する。
ADP法は,バニラランダムノイズを付加した標準微分プライベート法と比較して,実用性保証を大幅に改善することを示す。
論文 参考訳（メタデータ） (2021-10-14T15:02:20Z) - No-Regret Algorithms for Private Gaussian Process Bandit Optimization [13.660643701487002]
プライバシー保護統計のレンズによるガウス過程(GP)帯域最適化の至るところでの問題点を考察する。
均一なカーネル近似器とランダムな摂動を組み合わせた差分プライベートGPバンディット最適化のためのソリューションを提案する。
我々のアルゴリズムは最適化手順を通して微分プライバシを保持し、予測のためのサンプルパスに明示的に依存しない。
論文 参考訳（メタデータ） (2021-02-24T18:52:24Z) - Sequential Quadratic Optimization for Nonlinear Equality Constrained
Stochastic Optimization [10.017195276758454]
この設定では、客観的関数と微分値を明示的に計算することは難しそうだと仮定する。
最先端のライン探索SQPアルゴリズムをモデルとした決定論的設定のためのアルゴリズムを提案する。
数値実験の結果は,提案手法の実用性を示すものである。
論文 参考訳（メタデータ） (2020-07-20T23:04:26Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳（メタデータ） (2020-06-11T17:43:19Z) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳（メタデータ） (2020-05-10T19:52:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。