論文の概要: Differentially Private Bilevel Optimization: Efficient Algorithms with Near-Optimal Rates

• arxiv url: http://arxiv.org/abs/2506.12994v1
• Date: Sun, 15 Jun 2025 23:21:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-17 17:28:47.203502
• Title: Differentially Private Bilevel Optimization: Efficient Algorithms with Near-Optimal Rates
• Title（参考訳）: 微分プライベートな二値最適化: ほぼ最適速度の効率的なアルゴリズム
• Authors: Andrew Lowy, Daogao Liu,
• Abstract要約: 双レベル最適化問題は別の内部にネストされ、多くの機械学習アプリケーションにハイパーラーニング構造が組み込まれている。 両レベル最適化により、最適境界を求めるための最先端のアルゴリズムを開発した。
• 参考スコア（独自算出の注目度）: 9.07536816900443
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Bilevel optimization, in which one optimization problem is nested inside another, underlies many machine learning applications with a hierarchical structure -- such as meta-learning and hyperparameter optimization. Such applications often involve sensitive training data, raising pressing concerns about individual privacy. Motivated by this, we study differentially private bilevel optimization. We first focus on settings where the outer-level objective is \textit{convex}, and provide novel upper and lower bounds on the excess risk for both pure and approximate differential privacy, covering both empirical and population-level loss. These bounds are nearly tight and essentially match the optimal rates for standard single-level differentially private ERM and stochastic convex optimization (SCO), up to additional terms that capture the intrinsic complexity of the nested bilevel structure. The bounds are achieved in polynomial time via efficient implementations of the exponential and regularized exponential mechanisms. A key technical contribution is a new method and analysis of log-concave sampling under inexact function evaluations, which may be of independent interest. In the \textit{non-convex} setting, we develop novel algorithms with state-of-the-art rates for privately finding approximate stationary points. Notably, our bounds do not depend on the dimension of the inner problem.
• Abstract（参考訳）: 双レベル最適化は、ある最適化問題が別の内部にネストされた場合、メタラーニングやハイパーパラメータ最適化のような階層構造を持つ多くの機械学習アプリケーションの基礎となる。 このようなアプリケーションは、敏感なトレーニングデータを伴って、個人のプライバシに関する懸念を喚起することが多い。 これに触発された我々は、差分プライベートな二レベル最適化について研究する。 まず、外的目標がtextit{convex} であるような設定に焦点をあて、純粋かつ近似的な差分プライバシーの両方に対する過大なリスクを、経験的および人口レベルでの損失をカバーし、新しい上限と下限を提供する。 これらの境界はほぼ厳密であり、基本的に標準の単層微分プライベートEMMと確率凸最適化(SCO)の最適速度と一致する。 境界は指数的および正則化された指数的機構の効率的な実装を通じて多項式時間で達成される。 重要な技術的貢献は、不正確な関数評価の下でのログコンケーブサンプリングの新しい手法と分析である。 textit{non-convex} 設定では、近似定常点をプライベートに見つけるための最先端のアルゴリズムを開発する。 特に、我々の境界は内部問題の次元に依存しない。

関連論文リスト

• Accelerated First-Order Optimization under Nonlinear Constraints [61.98523595657983]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• On Implicit Bias in Overparameterized Bilevel Optimization [38.11483853830913]
  双レベル問題は、それぞれ外問題と内問題と呼ばれる、ネストした2つのサブプロブレムから構成される。 本稿では,2レベル最適化のための勾配に基づくアルゴリズムの暗黙バイアスについて検討する。 ウォームスタートBLOによって得られる内部解は、外的目的に関する驚くべき量の情報を符号化できることを示す。
  論文  参考訳（メタデータ） (2022-12-28T18:57:46Z)
• Bring Your Own Algorithm for Optimal Differentially Private Stochastic Minimax Optimization [44.52870407321633]
  これらの設定の聖杯は、プライバシーと過剰な人口減少の間の最適なトレードオフを保証することです。 微分プライベート・ミニマックス最適化(DP-SMO)問題を解くための一般的なフレームワークを提供する。 我々のフレームワークは、非滑らかな微分プライベート凸最適化(DP-SCO)のための最近提案されたフェイズド・ERM法[20]から着想を得たものである。
  論文  参考訳（メタデータ） (2022-06-01T10:03:20Z)
• A Constrained Optimization Approach to Bilevel Optimization with Multiple Inner Minima [49.320758794766185]
  そこで本研究では,両レベル問題を等価な制約付き最適化に変換する手法を提案する。 このようなアプローチには、(a)多重内極小問題への対処、(b)ジャコビアン計算のない完全一階効率など、いくつかの利点がある。
  論文  参考訳（メタデータ） (2022-03-01T18:20:01Z)
• The Minimax Complexity of Distributed Optimization [0.0]
  分散最適化に適用可能な古典的なオラクルフレームワークの拡張である「グラフオラクルモデル」を紹介します。 私は「間欠的コミュニケーション設定」の具体例に焦点をあてる コンベックス設定におけるSGD(Local Descent)アルゴリズムの理論的特性を解析する。
  論文  参考訳（メタデータ） (2021-09-01T15:18:33Z)
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization [98.0595480384208]
  定常点に収束する一般化外空間を提案する。 このアルゴリズムは一般の$p$ノルド空間だけでなく、一般の$p$次元ベクトル空間にも適用される。
  論文  参考訳（メタデータ） (2020-10-31T21:35:42Z)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  本稿では,深層学習(深層AUC)により注目度が高まっている,円滑な非凹部min-max問題の解法に焦点をあてる。
  論文  参考訳（メタデータ） (2020-06-12T00:32:21Z)

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

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