論文の概要: Learning Union of Integer Hypercubes with Queries (Technical Report)

• arxiv url: http://arxiv.org/abs/2105.13071v1
• Date: Thu, 27 May 2021 11:39:10 GMT
• ステータス: 処理完了
• システム内更新日: 2021-05-28 16:04:53.382101
• Title: Learning Union of Integer Hypercubes with Queries (Technical Report)
• Title（参考訳）: クエリによる整数ハイパーキューブの学習連合(技術報告)
• Authors: Oliver Markgraf, Daniel Stan, and Anthony W. Lin
• Abstract要約: 本稿では,d次元整数格子上での整数ハイパーキューブの有限和を求める問題について検討する。 非固定次元において、問題はDNF式を学習する問題を仮定する。 我々の問題には、量化子なし整数線型算術公式のモナディック分解問題への自然な応用がある。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of learning a finite union of integer (axis-aligned) hypercubes over the d-dimensional integer lattice, i.e., whose edges are parallel to the coordinate axes. This is a natural generalization of the classic problem in the computational learning theory of learning rectangles. We provide a learning algorithm with access to a minimally adequate teacher (i.e. membership and equivalence oracles) that solves this problem in polynomial-time, for any fixed dimension d. Over a non-fixed dimension, the problem subsumes the problem of learning DNF boolean formulas, a central open problem in the field. We have also provided extensions to handle infinite hypercubes in the union, as well as showing how subset queries could improve the performance of the learning algorithm in practice. Our problem has a natural application to the problem of monadic decomposition of quantifier-free integer linear arithmetic formulas, which has been actively studied in recent years. In particular, a finite union of integer hypercubes correspond to a finite disjunction of monadic predicates over integer linear arithmetic (without modulo constraints). Our experiments suggest that our learning algorithms substantially outperform the existing algorithms.
• Abstract（参考訳）: 我々は、d次元整数格子(つまり、エッジが座標軸に平行な)上の整数(軸方向の)ハイパーキューブの有限和を求める問題を研究する。 これは、矩形学習の計算学習理論における古典問題の自然な一般化である。 最小限の適切な教師(すなわち教師)にアクセスできる学習アルゴリズムを提供する。 多項式時間において、任意の固定次元 d に対してこの問題を解決する会員と等価オラクル) 非固定次元では、問題は DNF ブール式を学習する問題を仮定する。 また、連合における無限のハイパーキューブを扱うための拡張や、サブセットクエリが実際に学習アルゴリズムの性能をどのように改善するかを示した。 この問題は、近年活発に研究されている量化子なし整数線形算術公式のモナディック分解問題への自然な応用がある。 特に、整数超キューブの有限和は、(モジュラー制約なしで)整数線型算術上のモナディック述語有限和に対応する。 我々の実験は、学習アルゴリズムが既存のアルゴリズムを大きく上回っていることを示唆している。

関連論文リスト

• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• 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)
• Quantum Multiplication Algorithm Based on the Convolution Theorem [0.0]
  時間複雑性を持つ整数乗算の量子アルゴリズムをO(sqrtnlog2 n)$で提案する。 Harveyアルゴリズムとは異なり、我々のアルゴリズムは極大数にのみ適用できるという制限はない。 また、古典的乗法アルゴリズムの歴史と発展を概観し、量子資源がこの根本的な問題に対してどのように新たな視点と可能性を提供できるかを探求する動機付けとなる。
  論文  参考訳（メタデータ） (2023-06-14T12:40:54Z)
• Exponential Hardness of Reinforcement Learning with Linear Function Approximation [20.066210529358177]
  指数時間仮説に基づく線形強化学習において,特徴・地平線で指数関数的な計算下界を示す。 また、地平線依存に最適化された下界が$exp(sqrtH)$の最もよく知られた上界とほぼ一致することを示す。
  論文  参考訳（メタデータ） (2023-02-25T00:19:49Z)
• Minimizing low-rank models of high-order tensors: Hardness, span, tight relaxation, and applications [26.602371644194143]
  この基本テンソル問題は 1 以上のテンソル階数に対して NP-hard であることを示す。 低次ランクの場合、提案された連続的な再構成は低複素度勾配に基づく最適化に有効である。 低密度パリティチェックコードや一般復号パリティチェックコードなど,多くの難題に対する有望な結果を示す。
  論文  参考訳（メタデータ） (2022-10-16T11:53:42Z)
• Power of human-algorithm collaboration in solving combinatorial optimization problems [0.0]
  最適化問題のクラスは、$epsilon$ が任意の定数であるような乗法係数 $epsilon$ を期待して、効率的に解けることを示す。 提案手法は単に理論的なものであるに過ぎないが、通常は難解であると考えられるこれらの問題を解決する方法に新たな光を当てた。
  論文  参考訳（メタデータ） (2021-07-25T11:21:59Z)
• Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
  この研究は、未知の報酬関数が非可逆であるようなバンドイット問題の大群を考察する。 我々のアルゴリズムは、非常に一般化されたゼロ階最適化のパラダイムに基づいている。 標準的な楽観的アルゴリズムは次元因子によって準最適であることを示す。
  論文  参考訳（メタデータ） (2021-07-09T16:04:24Z)
• Dynamic programming by polymorphic semiring algebraic shortcut fusion [1.9405875431318445]
  動的プログラミング(動的プログラミング、英: Dynamic Programming、DP)は、難解問題の効率的かつ正確な解法のためのアルゴリズム設計パラダイムである。 本稿では,セミリングに基づくDPアルゴリズムを体系的に導出するための厳密な代数形式について述べる。
  論文  参考訳（メタデータ） (2021-07-05T00:51:02Z)
• Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks [48.32532049640782]
  ガウス境界の下で, 1層ReLUネットワークを$k$の隠れ単位で学習する問題をmathbbRd$で研究する。 正の係数の場合、この学習問題の初回アルゴリズムを$k$から$tildeOOmega(sqrtlog d)$まで与える。
  論文  参考訳（メタデータ） (2020-06-22T17:53:54Z)
• Sparsified Linear Programming for Zero-Sum Equilibrium Finding [89.30539368124025]
  我々は、この問題に対して全く異なるアプローチを示し、それは競争力があり、しばしば、以前の最先端技術よりも桁違いに優れている。 ポーカーエンドゲームの実験により、現代の線形プログラムソルバは、ゲーム固有のCFRの現代的な変種でさえも競合することを示した。
  論文  参考訳（メタデータ） (2020-06-05T13:48:26Z)
• Second-order Conditional Gradient Sliding [79.66739383117232]
  本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。 SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。 実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
  論文  参考訳（メタデータ） (2020-02-20T17:52:18Z)

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

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