論文の概要: Symmetric Boolean Factor Analysis with Applications to InstaHide
- arxiv url: http://arxiv.org/abs/2102.01570v1
- Date: Tue, 2 Feb 2021 15:52:52 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-03 16:17:53.095215
- Title: Symmetric Boolean Factor Analysis with Applications to InstaHide
- Title（参考訳）: 対称的ブール因子解析とInstaHideへの応用
- Authors: Sitan Chen, Zhao Song, Runzhou Tao, Ruizhe Zhang
- Abstract要約: InstaHideは、中程度に大規模なkに対する再構築攻撃に対して、ある種の「きめ細かいセキュリティ」を持っていることを示す。
我々のアルゴリズムはテンソル分解に基づいており、m は r において少なくとも準線形である必要がある。
この結果は、k-スパースベクトルの集合が任意に選択される問題の最悪のケース設定のための準ポリノミカル時間アルゴリズムで補完する。
- 参考スコア（独自算出の注目度）: 18.143740528953142
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this work we examine the security of InstaHide, a recently proposed scheme
for distributed learning (Huang et al.). A number of recent works have given
reconstruction attacks for InstaHide in various regimes by leveraging an
intriguing connection to the following matrix factorization problem: given the
Gram matrix of a collection of m random k-sparse Boolean vectors in {0,1}^r,
recover the vectors (up to the trivial symmetries). Equivalently, this can be
thought of as a sparse, symmetric variant of the well-studied problem of
Boolean factor analysis, or as an average-case version of the classic problem
of recovering a k-uniform hypergraph from its line graph.
As previous algorithms either required m to be exponentially large in k or
only applied to k = 2, they left open the question of whether InstaHide
possesses some form of "fine-grained security" against reconstruction attacks
for moderately large k. In this work, we answer this in the negative by giving
a simple O(m^{\omega + 1}) time algorithm for the above matrix factorization
problem. Our algorithm, based on tensor decomposition, only requires m to be at
least quasi-linear in r. We complement this result with a quasipolynomial-time
algorithm for a worst-case setting of the problem where the collection of
k-sparse vectors is chosen arbitrarily.
- Abstract（参考訳）: 本研究では,最近提案された分散学習手法であるInstaHideのセキュリティについて検討する(Huang et al.)。
いくつかの最近の研究は、以下の行列因子化問題への興味深い接続を利用して、InstaHideの再構築攻撃を与えている:{0,1}^rにおけるmランダムk-sparse Booleanベクトルのコレクションのグラム行列を考えると、ベクトルを回復する(自明な対称性まで)。
同様に、これはブール因子分析のよく研究された問題の疎密で対称な変種として、またはk-ユニフォームハイパーグラフを線グラフから回復する古典的な問題の平均ケースバージョンとして考えられます。
以前のアルゴリズムでは m が k で指数関数的に大きいか、あるいは k = 2 にのみ適用されるかのどちらかが必要であったため、InstaHide は適当な大きさの k に対して再構築攻撃に対して何らかの「細かいセキュリティ」を持っているかという疑問を解いた。この研究では、上記の行列分解問題に対して単純な O(m^{\omega + 1}) 時間アルゴリズムを与えることで、負の方法でこの疑問に答える。
このアルゴリズムは、k-スパースベクトルの収集が任意に選択される問題の最悪の場合の設定のための準多項式時間アルゴリズムでこの結果を補完する。
関連論文リスト
- Riemannian Optimization for Non-convex Euclidean Distance Geometry with Global Recovery Guarantees [6.422262171968397]
ユークリッド距離幾何学問題を解くために2つのアルゴリズムが提案されている。
第一のアルゴリズムは真の解に線形に収束する。
第2のアルゴリズムは、合成データと実データの両方で強い数値性能を示す。
論文 参考訳（メタデータ） (2024-10-08T21:19:22Z) - A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - Quantization of Large Language Models with an Overdetermined Basis [73.79368761182998]
本稿では,嘉心表現の原理に基づくデータ量子化アルゴリズムを提案する。
以上の結果から, カシ量子化はモデル性能の競争力や優れた品質を達成できることが示唆された。
論文 参考訳（メタデータ） (2024-04-15T12:38:46Z) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳（メタデータ） (2022-07-18T12:03:26Z) - Alternating Mahalanobis Distance Minimization for Stable and Accurate CP
Decomposition [4.847980206213335]
本稿では, テンソルの特異値とベクトルを導出するための新しい定式化を導入する。
このアルゴリズムのサブスウィープは、既知のランクの正確なCPDに対して超線形収束率を達成することができることを示す。
すると、アルゴリズムは各因子に対するマハラノビス距離を最適化するものであり、基底距離は他の因子に依存していると見なす。
論文 参考訳（メタデータ） (2022-04-14T19:56:36Z) - Sparse Quadratic Optimisation over the Stiefel Manifold with Application
to Permutation Synchronisation [71.27989298860481]
二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。
そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-09-30T19:17:35Z) - Nonlinear matrix recovery using optimization on the Grassmann manifold [18.655422834567577]
本研究では,列が部分空間の結合などの非線形構造に従う部分観測された高階クラスタリング行列の復元問題について検討する。
交代極限はクルディカ・ロジャシ性質を用いて一意点に収束することを示す。
論文 参考訳（メタデータ） (2021-09-13T16:13:13Z) - Near-Optimal Algorithms for Linear Algebra in the Current Matrix
Multiplication Time [46.31710224483631]
既存の定数係数近似のスケッチ次元における対数的要素について、Nelson and Nguyen (FOCS, 2013) の主な開問題を回避する方法を示す。
私たちが使用している重要なテクニックは、不確実性原理と抽出子に基づくIndykの明示的なマッピングです。
ランク計算と列の線形独立部分集合の探索という基本的な問題に対して、我々のアルゴリズムはCheung, Kwok, Lau (JACM, 2013)を改良し、それぞれ定数係数と$log(n)$-factorの範囲内で最適である。
論文 参考訳（メタデータ） (2021-07-16T19:34:10Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳（メタデータ） (2020-02-21T17:45:32Z) - Optimal Iterative Sketching with the Subsampled Randomized Hadamard
Transform [64.90148466525754]
最小二乗問題に対する反復スケッチの性能について検討する。
本研究では、Haar行列とランダム化されたHadamard行列の収束速度が同一であることを示し、ランダムなプロジェクションを経時的に改善することを示した。
これらの手法は、ランダム化次元還元を用いた他のアルゴリズムにも適用することができる。
論文 参考訳（メタデータ） (2020-02-03T16:17:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。