論文の概要: Adaptive Sparse Möbius Transforms for Learning Polynomials

• arxiv url: http://arxiv.org/abs/2602.06246v1
• Date: Thu, 05 Feb 2026 22:50:49 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-09 22:18:26.146372
• Title: Adaptive Sparse Möbius Transforms for Learning Polynomials
• Title（参考訳）: 多項式学習のための適応スパースメビウス変換
• Authors: Yigit Efe Erginbas, Justin Singh Kang, Elizabeth Polito, Kannan Ramchandran,
• Abstract要約: 我々は、$s$スパース実数 Boolean を$f: 0,1n rightarrow mathbbR$ の形で正確に学習する問題を考える。 この問題は AND 基底の分解関数に対応し、Mbius 変換を取ることで知られる。
• 参考スコア（独自算出の注目度）: 11.930982959670734
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the problem of exactly learning an $s$-sparse real-valued Boolean polynomial of degree $d$ of the form $f:\{ 0,1\}^n \rightarrow \mathbb{R}$. This problem corresponds to decomposing functions in the AND basis and is known as taking a Möbius transform. While the analogous problem for the parity basis (Fourier transform) $f: \{-1,1 \}^n \rightarrow \mathbb{R}$ is well-understood, the AND basis presents a unique challenge: the basis vectors are coherent, precluding standard compressed sensing methods. We overcome this challenge by identifying that we can exploit adaptive group testing to provide a constructive, query-efficient implementation of the Möbius transform (also known as Möbius inversion) for sparse functions. We present two algorithms based on this insight. The Fully-Adaptive Sparse Möbius Transform (FASMT) uses $O(sd \log(n/d))$ adaptive queries in $O((sd + n) sd \log(n/d))$ time, which we show is near-optimal in query complexity. Furthermore, we also present the Partially-Adaptive Sparse Möbius Transform (PASMT), which uses $O(sd^2\log(n/d))$ queries, trading a factor of $d$ to reduce the number of adaptive rounds to $O(d^2\log(n/d))$, with no dependence on $s$. When applied to hypergraph reconstruction from edge-count queries, our results improve upon baselines by avoiding the combinatorial explosion in the rank $d$. We demonstrate the practical utility of our method for hypergraph reconstruction by applying it to learning real hypergraphs in simulations.
• Abstract（参考訳）: 我々は、$s$スパース実数値ブール多項式を$f:\{ 0,1\}^n \rightarrow \mathbb{R}$の次数$d$で正確に学習する問題を考える。 この問題は AND 基底の分解関数に対応し、メビウス変換を取ることで知られる。 パリティ基底の類似問題(フーリエ変換) $f: \{-1,1 \}^n \rightarrow \mathbb{R}$ はよく理解されているが、AND基底は独特な挑戦である。 我々は、スパース関数に対するメビウス変換(英語版)(Möbius inversion とも呼ばれる)の構成的でクエリ効率の良い実装を提供するために、適応群テストを利用することができると同定することによって、この課題を克服する。 この知見に基づく2つのアルゴリズムを提案する。 Fully-Adaptive Sparse Möbius Transform (FASMT)は$O(sd \log(n/d))$O((sd + n) sd \log(n/d))$timeを使用する。 さらに、部分適応スパースメビウス変換 (PASMT) も提示し、$O(sd^2\log(n/d))$クエリを使用し、適応ラウンドの数を$O(d^2\log(n/d))$に減らし、$s$に依存することなく$d$の係数を$O(d^2\log(n/d))$に交換する。 エッジ数クエリーからのハイパーグラフ再構成に適用すると、この結果は、$d$の組合せ爆発を避けることで、ベースラインを改善することができる。 シミュレーションにおける実ハイパーグラフの学習に応用して, ハイパーグラフ再構成手法の実用性を実証する。

関連論文リスト

• 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)
• Learning to Understand: Identifying Interactions via the Möbius Transform [18.987216240237483]
  学習関数の解釈可能な表現を見つけるために、M"obius transform を用いる。 このアルゴリズムの頑健なバージョンはノイズに耐え、この複雑さを維持する。 いくつかの例では、M"obius変換によって生成される表現は元の関数に最大で2倍忠実である。
  論文  参考訳（メタデータ） (2024-02-04T22:47:34Z)
• 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)
• Decomposable Non-Smooth Convex Optimization with Nearly-Linear Gradient Oracle Complexity [15.18055488087588]
  上記の凸定式化を$widetildeO(sum_i=1n d_i log (1 /epsilon))$グラデーション計算で$epsilon$-accuracyに最小化するアルゴリズムを与える。 我々の主な技術的貢献は、カットプレーン法とインテリアポイント法を組み合わせた新しい組み合わせにより、各イテレーションで$f_i$項を選択する適応的な手順である。
  論文  参考訳（メタデータ） (2022-08-07T20:53:42Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。 本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
  論文  参考訳（メタデータ） (2022-07-18T12:03:26Z)
• The Complexity of Dynamic Least-Squares Regression [11.815510373329337]
  動的最小二乗回帰の複雑さ。 ゴールは、$min_mathbfx(t)| mathbfA(t) mathbfb(t) |$ for all $tin に対する $epsilon-approximate ソリューションを維持することである。
  論文  参考訳（メタデータ） (2022-01-01T18:36:17Z)
• Practical and Parallelizable Algorithms for Non-Monotone Submodular Maximization with Size Constraint [20.104148319012854]
  サイズ制約に関して、必ずしも単調ではない部分モジュラ函数に対して存在および並列化可能である。 最適な適応性とほぼ最適な複雑性クエリを持つアルゴリズムによって達成される最適な近似係数を、0.193 - varepsilon$に改善する。
  論文  参考訳（メタデータ） (2020-09-03T22:43:55Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• 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)

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

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