論文の概要: Adapting to Function Difficulty and Growth Conditions in Private Optimization

• arxiv url: http://arxiv.org/abs/2108.02391v1
• Date: Thu, 5 Aug 2021 05:55:20 GMT
• ステータス: 処理完了
• システム内更新日: 2021-08-06 14:46:28.551855
• Title: Adapting to Function Difficulty and Growth Conditions in Private Optimization
• Title（参考訳）: プライベート最適化における機能障害と成長条件への適応
• Authors: Hilal Asi, Daniel Levy, John Duchi
• Abstract要約: 我々は,最適化したい特定の関数の硬さに適応する,プライベート凸最適化のためのアルゴリズムを開発した。 我々のアルゴリズムは、インスタンスの難易度に適応する逆感度メカニズムの上に構築されている。
• 参考スコア（独自算出の注目度）: 15.4049962498675
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We develop algorithms for private stochastic convex optimization that adapt to the hardness of the specific function we wish to optimize. While previous work provide worst-case bounds for arbitrary convex functions, it is often the case that the function at hand belongs to a smaller class that enjoys faster rates. Concretely, we show that for functions exhibiting $\kappa$-growth around the optimum, i.e., $f(x) \ge f(x^*) + \lambda \kappa^{-1} \|x-x^*\|_2^\kappa$ for $\kappa > 1$, our algorithms improve upon the standard ${\sqrt{d}}/{n\varepsilon}$ privacy rate to the faster $({\sqrt{d}}/{n\varepsilon})^{\tfrac{\kappa}{\kappa - 1}}$. Crucially, they achieve these rates without knowledge of the growth constant $\kappa$ of the function. Our algorithms build upon the inverse sensitivity mechanism, which adapts to instance difficulty (Asi & Duchi, 2020), and recent localization techniques in private optimization (Feldman et al., 2020). We complement our algorithms with matching lower bounds for these function classes and demonstrate that our adaptive algorithm is \emph{simultaneously} (minimax) optimal over all $\kappa \ge 1+c$ whenever $c = \Theta(1)$.
• Abstract（参考訳）: 我々は、最適化したい特定の関数の硬さに適応するプライベート確率凸最適化アルゴリズムを開発した。 以前の研究は任意の凸関数に対して最悪のケース境界を提供するが、手元の関数がより高速なレートを持つより小さなクラスに属する場合が多い。 具体的には、$f(x) \ge f(x^*) + \lambda \kappa^{-1} \|x-x^*\|_2^\kappa$ for $\kappa > 1$という最適値の周りに$\kappa$成長を示す関数に対して、アルゴリズムは標準の${\sqrt{d}}/{n\varepsilon}$プライバシレートを$({\sqrt{d}}/{n\varepsilon})^{\tfrac{\kappa}{\kappa - 1}}$に改善することを示す。 重要なことに、彼らは関数の成長定数$\kappa$を知らずにこれらのレートを達成する。 我々のアルゴリズムは、インスタンス難易度(asi & duchi, 2020)と最近のプライベート最適化におけるローカライズ技術(feldman et al., 2020)に適応する逆感度機構に基づいている。 これらの関数クラスに対する下界のマッチングでアルゴリズムを補完し、適応的アルゴリズムがすべての$\kappa \ge 1+c$に対して \emph{simultanely} (minimax) 最適であることを証明する。

関連論文リスト

• Faster Stochastic Algorithms for Minimax Optimization under Polyak--{\L}ojasiewicz Conditions [12.459354707528819]
  我々は、$min_x max_y f(x,y)triqangle frac1n sum_i=1n f_i(x,y)$という形の有限サム問題を解くためのSPIDER-GDAを提案する。 SPIDER-GDA は $mathcal Oleft((n + sqrtn,kappa_xkappa_y2)log (1/epsilon) の中で $epsilon$-optimal Solution を見つけることができる。
  論文  参考訳（メタデータ） (2023-07-29T02:26:31Z)
• On Convergence of Incremental Gradient for Non-Convex Smooth Functions [63.51187646914962]
  機械学習とネットワーク最適化では、ミスの数と優れたキャッシュを最小化するため、シャッフルSGDのようなアルゴリズムが人気である。 本稿では任意のデータ順序付けによる収束特性SGDアルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2023-05-30T17:47:27Z)
• An Optimal Algorithm for Strongly Convex Min-min Optimization [79.11017157526815]
  既存の最適な一階法には$mathcalO(sqrtmaxkappa_x,kappa_y log 1/epsilon)$nabla_x f(x,y)$と$nabla_y f(x,y)$の両方の計算が必要である。 我々は$mathcalO(sqrtkappa_x log 1/epsilon)$nabla_x f(x,
  論文  参考訳（メタデータ） (2022-12-29T19:26:12Z)
• Dueling Convex Optimization with General Preferences [85.14061196945599]
  本研究の目的は, エンフィロンリングフィードバックの弱い形を条件として, 凸関数を最小化することである。 我々の主な貢献は、滑らかな凸対象関数に対する収束$smashwidetilde O(epsilon-4p)$と、その目的が滑らかで凸であるときに効率$smashwidetilde O(epsilon-2p)を持つ効率的なアルゴリズムである。
  論文  参考訳（メタデータ） (2022-09-27T11:10:41Z)
• The First Optimal Algorithm for Smooth and Strongly-Convex-Strongly-Concave Minimax Optimization [88.91190483500932]
  本稿では,スムーズで強靭なミニマックス最適化問題を再考する。 既存の最先端メソッドは、下限の$Omegaleft(sqrtkappa_xkappa_ylog3 (kappa_xkappa_y)logfrac1epsilonright)$にマッチしない。 我々は、$mathcalOleft( sqrtkappa_xkappa_ylog)で最初のアルゴリズムを提供することで、この根本的な問題を解決する。
  論文  参考訳（メタデータ） (2022-05-11T17:33:07Z)
• Iterative Hard Thresholding with Adaptive Regularization: Sparser Solutions Without Sacrificing Runtime [17.60502131429094]
  本稿では,条件数関数としてスペーサー解を復元する反復型ハードしきい値決定アルゴリズムの簡単な修正を提案する。 提案するアルゴリズムである正規化IHTは、疎度$O(skappa)$の解を返す。 我々のアルゴリズムはARHTよりも大幅に改善され、またスパーシティ$O(skappa)$の解も見つかる。
  論文  参考訳（メタデータ） (2022-04-11T19:33:15Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。 損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
  論文  参考訳（メタデータ） (2021-03-02T06:53:44Z)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  我々は,バンディットフィードバックを用いてオンライン学習を学習する。 learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。 我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。 ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
  論文  参考訳（メタデータ） (2021-02-15T08:16:51Z)
• Parameter-free Stochastic Optimization of Variationally Coherent Functions [19.468067110814808]
  我々は$mathbbRdilon上で関数のクラスを1次最適化するためのアルゴリズムを設計・解析する。 この2つを同時に実現したのは初めてである。
  論文  参考訳（メタデータ） (2021-01-30T15:05:34Z)

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

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