論文の概要: Fast and Accurate Homomorphic Softmax Evaluation

• arxiv url: http://arxiv.org/abs/2410.11184v1
• Date: Tue, 15 Oct 2024 02:01:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-16 14:00:11.589371
• Title: Fast and Accurate Homomorphic Softmax Evaluation
• Title（参考訳）: 高速かつ高精度な同型ソフトマックス評価
• Authors: Wonhee Cho, Guillaume Hanrot, Taeseong Kim, Minje Park, Damien Stehlé,
• Abstract要約: ホモモルフィック暗号化は、マシンラーニング・アズ・ア・サービスのためのセキュアでプライバシ保護のソリューションを構築するための主要なソリューションの1つです。 我々は、$mathrmSM(mathbfx) = left(exp(x_i) / sum_j=1n exp(x_j) right)_1le ile n$で定義されるSoftmax関数に焦点を当てる。
• 参考スコア（独自算出の注目度）: 2.5766624796160777
• License:
• Abstract: Homomorphic encryption is one of the main solutions for building secure and privacy-preserving solutions for Machine Learning as a Service. This motivates the development of homomorphic algorithms for the main building blocks of AI, typically for the components of the various types of neural networks architectures. Among those components, we focus on the Softmax function, defined by $\mathrm{SM}(\mathbf{x}) = \left(\exp(x_i) / \sum_{j=1}^n \exp(x_j) \right)_{1\le i\le n}$. This function is deemed to be one of the most difficult to evaluate homomorphically, because of its multivariate nature and of the very large range of values for $\exp(x_i)$. The available homomorphic algorithms remain restricted, especially in large dimensions, while important applications such as Large Language Models (LLM) require computing Softmax over large dimensional vectors. In terms of multiplicative depth of the computation (a suitable measure of cost for homomorphic algorithms), our algorithm achieves $O(\log n)$ complexity for a fixed range of inputs, where $n$ is the Softmax dimension. Our algorithm is especially adapted to the situation where we must compute many Softmax at the same time, for instance, in the LLM situation. In that case, assuming that all Softmax calls are packed into $m$ ciphtertexts, the asymptotic amortized multiplicative depth cost per ciphertext is, again over a fixed range, $O(1 + m/N)$ for $N$ the homomorphic ring degree. The main ingredient of our algorithms is a normalize-and-square strategy, which interlaces the exponential computation over a large range and normalization, decomposing both in stabler and cheaper smaller steps. Comparing ourselves to the state of the art, our experiments show, in practice, a good accuracy and a gain of a factor 2.5 to 8 compared to state of the art solutions.
• Abstract（参考訳）: ホモモルフィック暗号化は、マシンラーニング・アズ・ア・サービスのためのセキュアでプライバシ保護のソリューションを構築するための主要なソリューションの1つです。 このことは、AIの主要なビルディングブロック(典型的には、様々なタイプのニューラルネットワークアーキテクチャのコンポーネント)のための同型アルゴリズムの開発を動機付けている。 これらの成分のうち、$\mathrm{SM}(\mathbf{x}) = \left(\exp(x_i) / \sum_{j=1}^n \exp(x_j) \right)_{1\le i\le n}$ で定義されるソフトマックス函数に焦点を当てる。 この関数は、その多変量の性質と$\exp(x_i)$に対する非常に広い値の故に、同型性を評価するのが最も困難であると考えられている。 利用可能な同型アルゴリズムは、特に大きな次元において制限されているが、Large Language Models (LLM)のような重要な応用では、大きな次元ベクトル上での計算ソフトマックスを必要とする。 計算の乗算深度(同型アルゴリズムのコストの適切な尺度)に関して、我々のアルゴリズムは、固定範囲の入力に対して$O(\log n)$複雑さを達成し、$n$はソフトマックス次元である。 我々のアルゴリズムは、例えばLLMの状況において、多くのSoftmaxを同時に計算しなければならない状況に特に適応している。 この場合、すべてのSoftmax呼び出しが$m$ ciphtertextsに満ちていると仮定すると、暗号文あたりの漸近的償却乗算深度コストは、再び固定範囲上で$O(1 + m/N)$$$$N$である。 アルゴリズムの主な要素は正規化と二乗戦略であり、より安定なステップとより安価なステップの両方を分解して、指数計算を広い範囲にわたってインターレースし、正規化する。 我々の実験では、最先端のソリューションと比較して、精度が良く、精度が2.5から8に向上していることが示されています。

関連論文リスト

• Discretely Beyond $1/e$: Guided Combinatorial Algorithms for Submodular Maximization [13.86054078646307]
  制約のある、必ずしも単調な部分モジュラーでなくても、比が1/e$より大きい全ての既知の近似アルゴリズムは連続的な考えを必要とする。 アルゴリズムでは, 単純なランダム化グレディアルゴリズムを用いて, サイズとマトロイドの制約の双方について最もよく知られた近似比を求める。
  論文  参考訳（メタデータ） (2024-05-08T16:39:59Z)
• Certified Multi-Fidelity Zeroth-Order Optimization [4.450536872346658]
  様々な近似レベルで関数を$f$で評価できる多要素ゼロ階最適化の問題を考察する。 我々は、MFDOOアルゴリズムの証明された変種を提案し、そのコスト複雑性を任意のリプシッツ関数$f$に対して有界に導出する。 また、このアルゴリズムがほぼ最適コストの複雑さを持つことを示す$f$-dependent lower boundも証明する。
  論文  参考訳（メタデータ） (2023-08-02T07:20:37Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
  効率的なプライベート推定アルゴリズムを設計するための一般的なツール。 最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
  論文  参考訳（メタデータ） (2023-01-11T09:12:28Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Empirical Risk Minimization in the Non-interactive Local Model of Differential Privacy [26.69391745812235]
  本研究では,非対話型局所微分プライバシー(LDP)モデルにおける経験的リスク最小化(ERM)問題について検討する。 これまでの研究では、誤差$alphaを達成するためには、一般的な損失関数の次元$p$に依存する必要があることが示されている。
  論文  参考訳（メタデータ） (2020-11-11T17:48:00Z)
• Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
  HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。 損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
  論文  参考訳（メタデータ） (2020-09-18T02:18:44Z)
• Practical and Parallelizable Algorithms for Non-Monotone Submodular Maximization with Size Constraint [20.104148319012854]
  サイズ制約に関して、必ずしも単調ではない部分モジュラ函数に対して存在および並列化可能である。 最適な適応性とほぼ最適な複雑性クエリを持つアルゴリズムによって達成される最適な近似係数を、0.193 - varepsilon$に改善する。
  論文  参考訳（メタデータ） (2020-09-03T22:43:55Z)
• Revisiting Modified Greedy Algorithm for Monotone Submodular Maximization with a Knapsack Constraint [75.85952446237599]
  修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。 最適なデータ依存上界を導出する。 また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
  論文  参考訳（メタデータ） (2020-08-12T15:40:21Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)

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

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