論文の概要: Differentially Private Quasi-Concave Optimization: Bypassing the Lower Bound and Application to Geometric Problems

• arxiv url: http://arxiv.org/abs/2504.19001v1
• Date: Sat, 26 Apr 2025 19:04:00 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-02 19:15:54.08231
• Title: Differentially Private Quasi-Concave Optimization: Bypassing the Lower Bound and Application to Geometric Problems
• Title（参考訳）: 微分プライベート準凸最適化:下界をバイパスして幾何学的問題への応用
• Authors: Kobbi Nissim, Eliad Tsfadia, Chao Yan,
• Abstract要約: 準凹関数の微分プライベート最適化のサンプル複雑性について検討する。 我々は、下界が一連の自然問題に対してバイパス可能であることを示す。
• 参考スコア（独自算出の注目度）: 10.228439000828722
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: We study the sample complexity of differentially private optimization of quasi-concave functions. For a fixed input domain $\mathcal{X}$, Cohen et al. (STOC 2023) proved that any generic private optimizer for low sensitive quasi-concave functions must have sample complexity $\Omega(2^{\log^*|\mathcal{X}|})$. We show that the lower bound can be bypassed for a series of ``natural'' problems. We define a new class of \emph{approximated} quasi-concave functions, and present a generic differentially private optimizer for approximated quasi-concave functions with sample complexity $\tilde{O}(\log^*|\mathcal{X}|)$. As applications, we use our optimizer to privately select a center point of points in $d$ dimensions and \emph{probably approximately correct} (PAC) learn $d$-dimensional halfspaces. In previous works, Bun et al. (FOCS 2015) proved a lower bound of $\Omega(\log^*|\mathcal{X}|)$ for both problems. Beimel et al. (COLT 2019) and Kaplan et al. (NeurIPS 2020) gave an upper bound of $\tilde{O}(d^{2.5}\cdot 2^{\log^*|\mathcal{X}|})$ for the two problems, respectively. We improve the dependency of the upper bounds on the cardinality of the domain by presenting a new upper bound of $\tilde{O}(d^{5.5}\cdot\log^*|\mathcal{X}|)$ for both problems. To the best of our understanding, this is the first work to reduce the sample complexity dependency on $|\mathcal{X}|$ for these two problems from exponential in $\log^* |\mathcal{X}|$ to $\log^* |\mathcal{X}|$.
• Abstract（参考訳）: 準凹関数の微分プライベート最適化のサンプル複雑性について検討する。 固定入力領域 $\mathcal{X}$, Cohen et al (STOC 2023) に対して、低感度準凹函数に対する任意の一般的なプライベートオプティマイザはサンプル複雑性 $\Omega(2^{\log^*|\mathcal{X}|})$ でなければならないことを示した。 我々は、下界が一連の `natural'' 問題に対してバイパス可能であることを示す。 準凹函数の新しいクラスを定義し、サンプル複雑性$\tilde{O}(\log^*|\mathcal{X}|)$ で近似された準凹函数に対する一般微分プライベートオプティマイザを示す。 応用として、オプティマイザを用いて、$d$次元の点の中心点をプライベートに選択し、 \emph{probably approximately correct} (PAC)は$d$次元のハーフスペースを学習する。 以前の研究で、 Bun et al (FOCS 2015) は両方の問題に対して$\Omega(\log^*|\mathcal{X}|)$の低い境界を証明した。 Beimel et al (COLT 2019) と Kaplan et al (NeurIPS 2020) はそれぞれ2つの問題に対して$\tilde{O}(d^{2.5}\cdot 2^{\log^*|\mathcal{X}|}) の上限を与えた。 我々は、両方の問題に対して $\tilde{O}(d^{5.5}\cdot\log^*|\mathcal{X}|)$ という新しい上限を提示することにより、領域の濃度に対する上限の依存性を改善する。 我々の理解を最大限に活用するために、この2つの問題を指数関数的に$\log^* |\mathcal{X}|$から$\log^* |\mathcal{X}|$へ還元する最初の試みである。

関連論文リスト

• The Space Complexity of Approximating Logistic Loss [11.338399194998933]
  a general $tildeOmega(dcdot mu_mathbfy(mathbfX))$ space lower bound if $epsilon$ is constant。 また、$mu_mathbfy(mathbfX)$は計算が難しいという事前予想も否定する。
  論文  参考訳（メタデータ） (2024-12-03T18:11:37Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Complexity of Minimizing Projected-Gradient-Dominated Functions with Stochastic First-order Oracles [38.45952947660789]
  本稿では,$(alpha,tau,mathcal)$-projected-dominanceプロパティの下で関数を最小化する一階法の性能限界について検討する。
  論文  参考訳（メタデータ） (2024-08-03T18:34:23Z)
• Partially Unitary Learning [0.0]
  ヒルベルト空間の最適写像 $IN$ of $left|psirightrangle$ と $OUT$ of $left|phirightrangle$ が提示される。 この最適化問題の大域的な最大値を求める反復アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2024-05-16T17:13:55Z)
• Optimal and Efficient Algorithms for Decentralized Online Convex Optimization [51.00357162913229]
  分散オンライン凸最適化(D-OCO)は、局所計算と通信のみを用いて、グローバルな損失関数の列を最小化するように設計されている。 我々は,凸関数と強凸関数の残差を$tildeO(nrho-1/4sqrtT)$と$tildeO(nrho-1/2log T)$に削減できる新しいD-OCOアルゴリズムを開発した。 我々の分析によると、射影自由多様体は$O(nT3/4)$と$O(n)を達成できる。
  論文  参考訳（メタデータ） (2024-02-14T13:44:16Z)
• Dueling Optimization with a Monotone Adversary [35.850072415395395]
  凸最適化の一般化である単調逆数を用いたデュエル最適化の問題点について検討する。 目的は、最小値$mathbfx*$の関数$fcolon XをmathbbRdに変換するために、オンラインアルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2023-11-18T23:55:59Z)
• \~Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization [23.547605262139957]
  しきい値関数の学習問題は、機械学習の基本的な問題である。 Kaplan et al による $tildeO(log* |X|)1.5) のほぼタイトな上界を提供する。 また、プライベート準凹の加法誤差(関連するより一般的な問題)に対して$tildeTheta(2log*|X|)$の上限と下限のマッチングも提供する。
  論文  参考訳（メタデータ） (2022-11-11T18:16:46Z)
• Private Isotonic Regression [54.32252900997422]
  部分順序集合 (poset) $mathcalX$ と任意のリプシッツ損失関数に対する等調回帰の問題を考察する。 約$mathrmwidth(mathcalX) cdot log|mathcalX| / n$, ここで$mathrmwidth(mathcalX)$はポーズの幅である。 上記の境界は本質的に最良であることを示す。
  論文  参考訳（メタデータ） (2022-10-27T05:08:07Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。 学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
  論文  参考訳（メタデータ） (2022-06-17T17:55:43Z)
• 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)
• DIPPA: An improved Method for Bilinear Saddle Point Problems [18.65143269806133]
  本稿では,min_bfx max_bfy g(fracx) + bfxtop bfbftop fracbfa kappa_x kappa_x (kappa_x + kappa_y) kappa_y (kappa_x + kappa_y) kappa_y (kappa_x + kappa_y) kappa_y (kappa_x + kappa_y)について述べる。
  論文  参考訳（メタデータ） (2021-03-15T10:55:30Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。 同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
  論文  参考訳（メタデータ） (2020-02-09T03:39:46Z)

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

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