論文の概要: On the Gradient Complexity of Private Optimization with Private Oracles

• arxiv url: http://arxiv.org/abs/2511.13999v1
• Date: Mon, 17 Nov 2025 23:58:11 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-19 16:23:52.844169
• Title: On the Gradient Complexity of Private Optimization with Private Oracles
• Title（参考訳）: プライベートオラクルによるプライベート最適化のグラディエント複雑性について
• Authors: Michael Menart, Aleksandar Nikolov,
• Abstract要約: 我々は,リプシッツ損失の個人的経験的/人口的リスクの1次オラクルクエリーの観点から,ランニング時間について検討した。 予測ランニングタイム$(minfracsqrtd2, fracdlog(1/))$は、$dgeq 1/2$のときの次元の問題に対して$$$過剰なリスクを達成するために必要であることを示す。
• 参考スコア（独自算出の注目度）: 51.044364532408345
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the running time, in terms of first order oracle queries, of differentially private empirical/population risk minimization of Lipschitz convex losses. We first consider the setting where the loss is non-smooth and the optimizer interacts with a private proxy oracle, which sends only private messages about a minibatch of gradients. In this setting, we show that expected running time $Ω(\min\{\frac{\sqrt{d}}{α^2}, \frac{d}{\log(1/α)}\})$ is necessary to achieve $α$ excess risk on problems of dimension $d$ when $d \geq 1/α^2$. Upper bounds via DP-SGD show these results are tight when $d>\tildeΩ(1/α^4)$. We further show our lower bound can be strengthened to $Ω(\min\{\frac{d}{\bar{m}α^2}, \frac{d}{\log(1/α)} \})$ for algorithms which use minibatches of size at most $\bar{m} < \sqrt{d}$. We next consider smooth losses, where we relax the private oracle assumption and give lower bounds under only the condition that the optimizer is private. Here, we lower bound the expected number of first order oracle calls by $\tildeΩ\big(\frac{\sqrt{d}}α + \min\{\frac{1}{α^2}, n\}\big)$, where $n$ is the size of the dataset. Modifications to existing algorithms show this bound is nearly tight. Compared to non-private lower bounds, our results show that differentially private optimizers pay a dimension dependent runtime penalty. Finally, as a natural extension of our proof technique, we show lower bounds in the non-smooth setting for optimizers interacting with information limited oracles. Specifically, if the proxy oracle transmits at most $Γ$-bits of information about the gradients in the minibatch, then $Ω\big(\min\{\frac{d}{α^2Γ}, \frac{d}{\log(1/α)}\}\big)$ oracle calls are needed. This result shows fundamental limitations of gradient quantization techniques in optimization.
• Abstract（参考訳）: 本研究では,リプシッツ凸損失の最小化を目的とし,1次オラクルクエリーのランニング時間について検討した。 まず、損失が非スムースであり、オプティマイザがプライベートプロキシのオラクルと相互作用する設定について検討し、勾配のミニバッチに関するプライベートメッセージのみを送信する。 この設定では、予想実行時間$Ω(\min\{\frac{\sqrt{d}}{α^2}, \frac{d}{\log(1/α)}\})$が、$d$が$d$であるとき、$d \geq 1/α^2$であるときに、$α$過剰なリスクを達成するために必要であることを示す。 DP-SGD による上界は、$d>\tildeΩ(1/α^4)$ の場合、これらの結果は厳密であることを示している。 さらに、我々の下界を$Ω(\min\{\frac{d}{\bar{m}α^2}, \frac{d}{\log(1/α)} \})$に拡張できることを示す。 次にスムーズな損失を考慮し、そこでは、プライベートオラクルの仮定を緩和し、オプティマイザがプライベートであることを条件に下限を与える。 ここでは、1次オラクル呼び出しの期待数を$\tildeΩ\big(\frac{\sqrt{d}}α + \min\{\frac{1}{α^2}, n\}\big)$で下げる。 既存のアルゴリズムの修正は、この境界はほぼ厳密であることを示している。 非プライベートな下限と比較して、我々の結果は、微分プライベートなオプティマイザが次元依存ランタイムペナルティを支払うことを示している。 最後に、証明手法の自然な拡張として、情報限定オラクルと相互作用するオプティマイザに対して、非滑らかな設定において低い境界を示す。 特に、プロキシオラクルがミニバッチの勾配に関する情報を少なくとも$$-bits で送信した場合、$Ω\big(\min\{\frac{d}{α^2\}, \frac{d}{\log(1/α)}\}\big)$ oraclecallが必要である。 この結果は、最適化における勾配量子化技術の基本的限界を示している。

関連論文リスト

• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Projection-free Online Exp-concave Optimization [21.30065439295409]
  LOOをベースとしたONSスタイルのアルゴリズムを提案する。これは全体$O(T)$コールを使用して,$widetildeO(n2/3T2/3)$でバウンドされた最悪のケースを保証します。 我々のアルゴリズムは、重要かつ確実な低次元データシナリオにおいて最も興味深い。
  論文  参考訳（メタデータ） (2023-02-09T18:58:05Z)
• Differentially Private Stochastic Gradient Descent with Low-Noise [49.981789906200035]
  現代の機械学習アルゴリズムは、データからきめ細かい情報を抽出して正確な予測を提供することを目的としており、プライバシー保護の目標と矛盾することが多い。 本稿では、プライバシを保ちながら優れたパフォーマンスを確保するために、プライバシを保存する機械学習アルゴリズムを開発することの実践的および理論的重要性について論じる。
  論文  参考訳（メタデータ） (2022-09-09T08:54:13Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Differentially Private Stochastic Optimization: New Results in Convex and Non-Convex Settings [15.122617358656539]
  凸および非滑らかな一般損失(GLL)に対する微分プライベートアルゴリズムを提案する。 凸の場合、非滑らかな一般化損失(GLL)の族に焦点をあてる。
  論文  参考訳（メタデータ） (2021-07-12T17:06:08Z)
• 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)
• Projection Efficient Subgradient Method and Optimal Nonsmooth Frank-Wolfe Method [54.93433440034386]
  実現可能な$epsilon$-suboptimalソリューションは、$O(epsilon-1)$ POコールと最適な$O(epsilon-2)$ FOコールのみを使用します。 提案手法は,POおよびLMOコールのコストがかかる問題に対して,最先端技術に対する大幅な高速化を実現するものであることを確認した。
  論文  参考訳（メタデータ） (2020-10-05T08:16:56Z)

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

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