Fugu-MT 論文翻訳(概要): Tight Bounds for Learning Polyhedra with a Margin

論文の概要: Tight Bounds for Learning Polyhedra with a Margin

arxiv url: http://arxiv.org/abs/2604.14614v1
Date: Thu, 16 Apr 2026 04:43:12 GMT
ステータス: 翻訳完了
システム内更新日: 2026-04-17 21:29:31.724254
Title: Tight Bounds for Learning Polyhedra with a Margin
Title（参考訳）: マージンを用いたポリヘドラ学習のためのタイトバウンド
Abstract要約: PAC学習交差点に$k$ハーフスペースと$$$マージンのアルゴリズムを誤差内に与える。我々のアルゴリズムは、ほとんどの点がポリヘドロンの境界から少なくとも$$の距離を持つとしか約束されていないとき、より一般的な設定にまで拡張する。
参考スコア（独自算出の注目度）: 0.2836066255205732
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We give an algorithm for PAC learning intersections of $k$ halfspaces with a $ρ$ margin to within error $\varepsilon$ that runs in time $\textsf{poly}(k, \varepsilon^{-1}, ρ^{-1}) \cdot \exp \left(O(\sqrt{n \log(1/ρ) \log k})\right)$. Notably, this improves on prior work which had an exponential dependence on either $k$ or $ρ^{-1}$ and matches known cryptographic and Statistical Query lower bounds up to the logarithmic factors in $k$ and $ρ$ in the exponent. Our learning algorithm extends to the more general setting when we are only promised that most points have distance at least $ρ$ from the boundary of the polyhedron, making it applicable to continuous distributions as well.
Abstract（参考訳）: 我々は、$k$ハーフスペースのPAC学習交差点のアルゴリズムを、エラー$\varepsilon$で、時間$\textsf{poly}(k, \varepsilon^{-1}, ρ^{-1}) \cdot \exp \left(O(\sqrt{n \log(1/ρ) \log k})\rightで走る。特に、これは$k$または$ρ^{-1}$に指数関数的依存を持ち、既知の暗号的および統計的クエリの下位境界を、指数において$k$と$ρ$の対数的要素に一致させる前の作業を改善する。学習アルゴリズムは、ほとんどの点がポリヘドロンの境界から少なくとも$ρ$の距離を持つことを約束されているだけで、連続分布にも適用できるより一般的な設定にまで拡張する。

関連論文リスト

Beyond Averaging in John Ellipsoid Approximation: High-Accuracy Algorithms in the Leverage-Score Model [37.35522173770848]
対称ポリトープ$P=mathbfxinmathbbRd:|mathbfAmathbfx|_inftyle1$, $mathbfAinmathbbRntimes d$のジョン・エリプシドは、長いレバレッジスコアアルゴリズムによって計算される。
論文参考訳（メタデータ） (2026-06-18T11:00:03Z)
Deterministic Hardness of Approximation of Unique-SVP and GapSVP in $\ell_p$ norms for $p>2$ [0.0]
我々は、$ell_p$ norm(mathsfSVP_p$)およびUnique-SVP(mathsfuSVP_p$)における最短ベクトル問題に対する近似結果の決定的困難性を確立する。すべての$p > 2$に対して、定数比硬さを証明します: no-time algorithm almosts $mathsfSVP_p$ or $mathsfuSVP_p$ in a ratio of $sqrt2 - o(1)$。
論文参考訳（メタデータ） (2025-10-19T20:17:26Z)
Actively Learning Halfspaces without Synthetic Data [34.777547976926456]
我々は、点合成なしでハーフスペースを学習するための効率的なアルゴリズムを設計する。コーナリーとして、軸整合半空間に対して最適な$O(d + log n)$クエリ決定論的学習器を得る。我々のアルゴリズムはブール関数を$f$ over $n$要素で学習するより一般的な問題を解く。
論文参考訳（メタデータ） (2025-09-25T07:39:25Z)
Learning and Computation of $Φ$-Equilibria at the Frontier of Tractability [85.07238533644636]
$Phi$-equilibriaは、オンライン学習とゲーム理論の中心にある、強力で柔軟なフレームワークだ。効率的なオンラインアルゴリズムは、$textpoly(d, k)/epsilon2$ラウンドを使用して、平均$Phi$-regretを最大$epsilon$で生成することを示す。また、オンライン設定において、ほぼ一致した下限を示し、その結果、$Phi$-regretの学習可能性を取得する偏差の族が初めて得られる。
論文参考訳（メタデータ） (2025-02-25T19:08:26Z)
Algorithms for mean-field variational inference via polyhedral optimization in the Wasserstein space [10.292118864147097]
ワッサーシュタイン空間上の有限次元多面体部分集合の理論を開発し、一階法による函数の最適化を行う。我々の主な応用は平均場変動推論の問題であり、これは分布の$pi$ over $mathbbRd$を製品測度$pistar$で近似しようとするものである。解析の副産物として,MFVIのための勾配に基づくアルゴリズムの最初のエンドツーエンド解析を求める。
論文参考訳（メタデータ） (2023-12-05T16:02:04Z)
Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。目標は、低ランク因子の積として$mathbfA$を近似することである。我々の手法はBMF問題の他の一般的な変種に一般化する。
論文参考訳（メタデータ） (2023-06-02T18:55:27Z)
Most Neural Networks Are Almost Learnable [52.40331776572531]
固定された$epsilon>0$とdeep $i$に対して、深さ$i$のランダムなXavierネットワークを学習するポリ時間アルゴリズムが存在することを示す。このアルゴリズムは時間とサンプルの複雑さが$(bard)mathrmpoly(epsilon-1)$であり、$bar d$はネットワークのサイズである。シグモイドやReLU様の活性化の場合、境界は$(bard)mathrmpolylog(eps)に改善できる。
論文参考訳（メタデータ） (2023-05-25T22:27:42Z)
Low-degree learning and the metric entropy of polynomials [44.99833362998488]
少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
論文参考訳（メタデータ） (2022-03-17T23:52:08Z)
Sampling from Log-Concave Distributions with Infinity-Distance Guarantees and Applications to Differentially Private Optimization [33.38289436686841]
本稿では,dis distributionO(varepsilon)$close から$ infinity-distance に点を出力するアルゴリズムを提案する。また、ディキンウォークの「ソフトパイ」バージョンも提示する。
論文参考訳（メタデータ） (2021-11-07T13:44:50Z)
The Curse of Passive Data Collection in Batch Reinforcement Learning [82.6026077420886]
高い利害関係のアプリケーションでは、アクティブな実験は危険すぎると考えられ、データはしばしば受動的に収集される。バンディットやパッシブ、アクティブなデータ収集などの単純な場合も同様に効果的であるが、制御された状態のシステムからデータを集める場合、パッシブサンプリングの価格ははるかに高い。
論文参考訳（メタデータ） (2021-06-18T07:54:23Z)
Infinite-Horizon Offline Reinforcement Learning with Linear Function Approximation: Curse of Dimensionality and Algorithm [46.36534144138337]
本稿では,オフライン強化学習におけるポリシー評価のサンプル複雑さについて検討する。低分布シフトの仮定の下では、最大$oleft(maxleft fracleftvert thetapirightvert _24varepsilon4logfracddelta,frac1varepsilon2left(d+logfrac1deltaright)right right)$サンプルを必要とするアルゴリズムがあることを示す。
論文参考訳（メタデータ） (2021-03-17T18:18:57Z)
$Q$-learning with Logarithmic Regret [60.24952657636464]
楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
論文参考訳（メタデータ） (2020-06-16T13:01:33Z)
Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文参考訳（メタデータ） (2020-06-06T13:34:41Z)
Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast Algorithm [100.11971836788437]
固定支持ワッサーシュタインバリセンタ問題(FS-WBP)について検討する。我々は,有望な反復的ブレグマン射影 (IBP) アルゴリズムであるtextscFastIBP の,証明可能な高速なテキスト決定論的変種を開発する。
論文参考訳（メタデータ） (2020-02-12T03:40:52Z)
Differentially Private Release and Learning of Threshold Functions [27.612916837481485]
我々は、$(epsilon, delta)$微分プライベートアルゴリズムのサンプル複雑性に対して、新しい上界と下界を証明した。完全に順序付けられたドメイン上のしきい値関数$c_x$は$c_x(y) = 1$ if $y le x$と評価され、$0$と評価される。
論文参考訳（メタデータ） (2015-04-28T16:15:01Z)

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