Fugu-MT 論文翻訳(概要): Fast, Parallel, Query-Efficient Binary Classification

論文の概要: Fast, Parallel, Query-Efficient Binary Classification

arxiv url: http://arxiv.org/abs/2607.04062v1
Date: Sun, 05 Jul 2026 00:18:56 GMT
ステータス: 翻訳完了
システム内更新日: 2026-07-07 22:26:29.809538
Title: Fast, Parallel, Query-Efficient Binary Classification
Title（参考訳）: 高速,並列,クエリ効率の良いバイナリ分類
Abstract要約: 正規化された$d$次元特徴を持つ2値ラベル付きデータセットに対して、分離された超平面を演算する際の分類問題について検討する。我々は、この問題を$tildeO(-2/3, operatornamennz() + -2(+1)/3)$-sequential run time (work), $tildeO(-2/3)$-parallel (computational) depthで解決し、$tildeO()を通してのみアクセスするランダム化アルゴリズムを提案する。
参考スコア（独自算出の注目度）: 16.557199104485328
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We study the fundamental classification problem of computing a separating hyperplane for a binary-labeled dataset of size $n$ with normalized $d$-dimensional features. Letting $Φ\in \mathbb{R}^{n \times d}$ denote the feature matrix and $γ$ the margin of the maximum-margin separating hyperplane, we present a randomized algorithm that solves this problem in $\tilde{O}(γ^{-2/3}\, \operatorname{nnz}(Φ) + γ^{-2(ω+1)/3})$-sequential running time (work), $\tilde{O}(γ^{-2/3})$-parallel (computational) depth, and accesses $Φ$ only through $\tilde{O}(γ^{-2/3})$-matrix-vector queries (matvecs). We also present a second, faster randomized algorithm with a $\tilde{O}(γ^{-2/3}\, \operatorname{nnz}(Φ) + γ^{-2})$-sequential running time that uses $\tilde{O}(γ^{-2/3})$-matvecs to $Φ$, but achieves only $\tilde{O}(γ^{-4/3})$-parallel depth. Both algorithms match the near-optimal deterministic matvec complexity recently established by Kornowski and Shamir [2025], Karmarkar et al. [2026] and achieve improved sequential runtime and parallel depth, albeit at the expense of using randomness.
Abstract（参考訳）: 正規化された$d$次元特徴を持つ2値ラベル付きデータセットに対して、分離された超平面を演算する基本的な分類問題について検討する。最大マージン分離超平面のマージンを$γ$で表すと、この問題を$\tilde{O}(γ^{-2/3}\, \operatorname{nnz}(\) + γ^{-2(ω+1)/3})$-sequential running time (work), $\tilde{O}(γ^{-2/3})$-parallel (computational) depth, and accesses $\tilde{O}(γ^{-2/3})$-matrix-vector query (matcs)で解くランダム化アルゴリズムを示す。また,$\tilde{O}(γ^{-2/3})$-sequential run time that using $\tilde{O}(γ^{-2/3})$-matvecs to $\tilde{O}(γ^{-4/3})$-parallel depth は$\tilde{O}(γ^{-4/3})$-parallel depth である。どちらのアルゴリズムも、Kornowski と Shamir [2025], Karmarkar et al [2026] によって最近確立されたほぼ最適決定論的マットベック複雑性と一致し、ランダム性を犠牲にして、改善されたシーケンシャルランタイムと並列深さを実現する。

関連論文リスト

High-Dimensional Procrustes Matching via Tree Counts [5.464035038606368]
Procrustes matching problem(英語版)は、2つの集合を整列する$[n]$の未知の置換を復元するように要求する。 gtrsim maxlog n/d,sqrtlog n/n$ のとき、正確な回復が可能であることを示す。また,木数計算アルゴリズムには条件2 > sqrt$ が必要であることを示唆する低次優位計算を行う。
論文参考訳（メタデータ） (2026-07-09T14:33:47Z)
Optimal Scalar Quantization for Matrix Multiplication: Closed-Form Density and Phase Transition [50.36362492608702]
乗算前の2つの行列のエントリーワイズスカラー量子化について検討した。我々は、閉形式の最適点密度 [ star(u) propto exp!left(-fracu26right)bigl( (1-2)+2u22bigr), qquad u=fracx_X を求め、相関駆動相転移を証明した。
論文参考訳（メタデータ） (2026-03-20T01:53:44Z)
Quantum Algorithms for Projection-Free Sparse Convex Optimization [32.34794896079469]
ベクトル領域に対しては、$O(sqrtd/varepsilon)$のクエリ複雑性を持つ$varepsilon$-optimal解を求めるスパース制約に対する2つの量子アルゴリズムを提案する。行列領域に対しては、時間複雑性を$tildeO(rd/varepsilon2)$と$tildeO(sqrtrd/varepsilon3)$に改善する2つの核ノルム制約の量子アルゴリズムを提案する。
論文参考訳（メタデータ） (2025-07-11T12:43:58Z)
The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文参考訳（メタデータ） (2024-10-26T06:21:42Z)
Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文参考訳（メタデータ） (2024-08-16T02:33:07Z)
Online Matrix Completion: A Collaborative Approach with Hott Items [19.781869063637387]
M$ユーザ,$N$アイテム,$T$ラウンド,未知のランク-$r$報酬行列$Rin mathbbRMtimes N$のオンライン設定における下位行列補完問題について検討する。
論文参考訳（メタデータ） (2024-08-11T18:49:52Z)
Solving Dense Linear Systems Faster Than via Preconditioning [1.8854491183340518]
我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$であることを示す。特に、我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$である。主アルゴリズムはランダム化ブロック座標降下法とみなすことができる。
論文参考訳（メタデータ） (2023-12-14T12:53:34Z)
Matrix Completion in Almost-Verification Time [37.61139884826181]
99%の行と列で$mathbfM$を完了するアルゴリズムを提供する。本稿では,この部分完備保証を完全行列補完アルゴリズムに拡張する方法を示す。
論文参考訳（メタデータ） (2023-08-07T15:24:49Z)
ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文参考訳（メタデータ） (2023-01-01T18:51:29Z)
Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
論文参考訳（メタデータ） (2022-09-30T04:15:44Z)
Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
論文参考訳（メタデータ） (2022-02-10T16:10:41Z)
Computational Complexity of Normalizing Constants for the Product of Determinantal Point Processes [12.640283469603357]
正規化定数の計算における計算複雑性について検討する。例えば、$sum_Sdet(bf A_S,S)p$は、すべての(固定された)正の偶数に対して、$p$ が UP-hard で Mod$_3$P-hard であることを示す。
論文参考訳（メタデータ） (2021-11-28T14:08:25Z)
Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文参考訳（メタデータ） (2020-07-07T17:10:00Z)
Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
論文参考訳（メタデータ） (2020-02-17T18:41:49Z)

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

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