論文の概要: Guarded Block Transfers for Polytope Distance: Linear Convergence with Explicit Constants and Gap-Certified Screening for SVM Training
- arxiv url: http://arxiv.org/abs/2610.15829v1
- Date: Sun, 11 Oct 2026 18:32:40 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-19 15:47:57.208773
- Title: Guarded Block Transfers for Polytope Distance: Linear Convergence with Explicit Constants and Gap-Certified Screening for SVM Training
- Title（参考訳）: ポリトープ距離に対するガード付きブロック転送: 明示的定数付き線形収束とSVMトレーニングのためのギャップ認定スクリーニング
- Abstract要約: ハードマージンSVMトレーニングは、Triangle Algorithm(TA)が証明された双対性ギャップで解決する2つの凸船体間の距離問題である。
k$ Mitchell--Demyanov--Malozemov (MDM) の1スキャンあたりの転送は、1つの正確なラインサーチに集約される。
我々は、明示的な定数とスワップステップ境界のない大域的線型収束を証明し、ステップごとの収縮は$k$非依存であり、
- 参考スコア（独自算出の注目度）: 0.27357894155761037
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Hard-margin SVM training is the distance problem between two convex hulls, which the Triangle Algorithm (TA) solves with a certified duality gap. We propose \emph{guarded block transfers}: $k$ Mitchell--Demyanov--Malozemov (MDM) transfers per scan are aggregated into one exact line search, guarded by a comparison with the single best transfer at a cost independent of the number of points $n$, and replaced by an away step when the leading transfer is capacity-clipped. On the Minkowski-difference polytope, where the objective is $1$-strongly convex, we prove global linear convergence with explicit constants and no combinatorial swap-step bounds; the per-step contraction is $k$-independent and only the drop-count bound grows with $k$, so aggregation is provably safe while the saving in scans is measured, not proved. Since the TA certificate is the Frank--Wolfe gap divided by the current distance, gap-safe screening applies, and we bound the iteration after which it has removed every zero-weight point off the optimal faces by $O\!\left(\tfrac{k}ρ\log\tfrac{1}τ\right)$ up to logarithmic factors in the geometry, $ρ$ the rate constant and $τ$ the optimal-face margin. On five LIBSVM benchmarks, with fairer baselines than our submission, the solver matches the baselines to four or five digits wherever both converge, ties LIBSVM on sparse-support hard margins and beats our blended pairwise conditional gradients (BPCG). But our full-cache sequential minimal optimisation (SMO) code ties or beats it on kernel $L_2$ margins, LIBLINEAR's dual solver is up to $4.5\times$ faster on the separable $L_2$ margin, and our solver is one to three orders of magnitude slower than LIBLINEAR's Newton solver on dense-support $L_2$ margins and than LIBSVM on a nearly touching kernel hull. Its edge is the certificate, not speed.
- Abstract（参考訳）: ハードマージンSVMトレーニングは、Triangle Algorithm(TA)が証明された双対性ギャップで解決する2つの凸船体間の距離問題である。
我々は,1スキャンあたりのMitchell--Demyanov--Malozemov(MDM)転送を1つの正確なラインサーチに集約し,ポイント数$n$に依存しないコストで1つのベストトランスファーと比較することにより保護し,リードトランスファーがキャパシティクラッピングされた場合の回避ステップに置き換える。
Minkowski-Difference polytopeでは、目的が1ドル強凸であり、明示定数と組合せスワップステップ境界のない大域的線形収束を証明し、ステップごとの収縮は$k$非依存であり、ドロップカウント境界のみが$k$で成長するので、スキャンの保存が測定されている間、アグリゲーションは確実に安全である。
TA証明書はフランク=ウルフギャップを現在の距離で割ったものであるので、ギャップセーフスクリーニングが適用され、その後、最適な顔からゼロウェイト点を$O\!
\left(\tfrac{k}ρ\log\tfrac{1}τ\right)$ 幾何学における対数的因子、速度定数$ρ$ および最適面マージン$τ$ まで。
5つのLIBSVMベンチマークにおいて、我々の提案よりも公平なベースラインを持つソルバは、ベースラインを4桁または5桁に一致させ、どちらも収束して、LIBSVMをスパースサポートのハードマージンに結び付け、ブレンドされたペア条件勾配(BPCG)を破る。
LIBLINEARのデュアルソルバは、分離可能な$L_2$マージンで最大4.5\times$高速で、我々のソルバは、濃密にサポートされた$L_2$マージンでLIBLINEARのNewtonソルバよりも1～3桁遅い。
そのエッジは証明書であり、スピードではない。
関連論文リスト
- Two-Point Local Optimality in $k$-Means via Boundary-Point Screening [30.362612885851444]
我々は、少なくとも$r$サンプルの再割り当てが目的関数を減少させるような$r$-point局所最適性を導入する。
BPS-2PLS(Bundary-Point-Screened Two-Point Local Search)を提案する。
論文 参考訳（メタデータ） (2026-10-05T12:02:08Z) - Scaling Federated Linear Contextual Bandits via Sketching [49.12000877146222]
本稿では,FSCLB(Federated Sketch Contextual Linear Bandits)を提案する。
合成と実世界の両方のデータセットの実験では、FSCLBは計算と通信のコストを90%以上削減している。
論文 参考訳（メタデータ） (2026-05-01T08:22:06Z) - Block-Wise Differentiable Sinkhorn Attention: Tail-Refinement Gradients with a Gap-Aware Dustbin Bridge [0.0]
本稿では,TPUハードウェア上での長期的コンテキストバランスによる最適輸送注意度を,停止ベース,固定深部テールリファインメントサロゲートを用いて検討する。
本稿では, 局所的代理バイアスバウンド, 後部バイアス証明書, および, 厳密な正の能動ブロックに対する射影収縮証明書を提供する。
合成マスク問題では、最適化された置換基の正確なオートディフは10〜5ドル-10〜10ドルである。
論文 参考訳（メタデータ） (2026-04-28T19:01:11Z) - Hardness of High-Dimensional Linear Classification [58.29089693778071]
我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。
どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
論文 参考訳（メタデータ） (2026-03-19T15:53:41Z) - Trust Region Masking for Long-Horizon LLM Reinforcement Learning [20.589897184824878]
大規模言語モデルのポリシー勾配法は、ロールアウトポリシーのサンプルから計算された代理目的を最適化する。
$_textroll ne _$ の場合、サロゲートと真の目的の間に近似誤差がある。
本稿では,トークンが信頼領域に違反した場合に,全シーケンスを勾配計算から除外するトラスト領域マスキング(TRM)を提案する。
論文 参考訳（メタデータ） (2025-12-28T20:41:59Z) - Multi-Timescale Gradient Sliding for Distributed Optimization [23.311605203774388]
凸・非平滑・分散最適化問題に対する2つの一階法を提案する。
我々のMT-GSとATT-GSは、通信ラウンドを減らすために、(局所的な)目的間の類似性を利用することができる。
これら3つの望ましい特徴はブロック分解可能な原始双対の定式化によって達成される。
論文 参考訳（メタデータ） (2025-06-18T12:03:34Z) - Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳（メタデータ） (2024-05-10T09:58:47Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Sharper Convergence Guarantees for Asynchronous SGD for Distributed and
Federated Learning [77.22019100456595]
通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。
本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。
また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
論文 参考訳（メタデータ） (2022-06-16T17:10:57Z) - Regret Lower Bound and Optimal Algorithm for High-Dimensional Contextual
Linear Bandit [10.604939762790517]
我々は、累積後悔に対して、$mathcalObig((log d)fracalpha+12Tfrac1-alpha2+log Tbig)$をミニマックス下界として証明する。
第2に,汎用的なアッパー信頼境界(UCB)戦略に着想を得た,シンプルで効率的なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-09-23T19:35:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。