論文の概要: Minimalist Softmax Attention Provably Learns Constrained Boolean Functions
- arxiv url: http://arxiv.org/abs/2505.19531v1
- Date: Mon, 26 May 2025 05:33:26 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-05-27 16:58:43.19011
- Title: Minimalist Softmax Attention Provably Learns Constrained Boolean Functions
- Title（参考訳）: 制約付きブール関数を学習するミニマリストSoftmax Attention
- Authors: Jerry Yao-Chieh Hu, Xiwen Zhang, Maojiang Su, Zhao Song, Han Liu,
- Abstract要約: 単純な$mathrmAND$と$mathrmOR$関数は、シングルヘッドソフトマックスアテンション機構だけでは解決できないことを示す。
教師の強制によって、同じミニマリストの注意がそれらを解決することができる。
- 参考スコア（独自算出の注目度）: 11.701612413596482
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: We study the computational limits of learning $k$-bit Boolean functions (specifically, $\mathrm{AND}$, $\mathrm{OR}$, and their noisy variants), using a minimalist single-head softmax-attention mechanism, where $k=\Theta(d)$ relevant bits are selected from $d$ inputs. We show that these simple $\mathrm{AND}$ and $\mathrm{OR}$ functions are unsolvable with a single-head softmax-attention mechanism alone. However, with teacher forcing, the same minimalist attention is capable of solving them. These findings offer two key insights: Architecturally, solving these Boolean tasks requires only minimalist attention, without deep Transformer blocks or FFNs. Methodologically, one gradient descent update with supervision suffices and replaces the multi-step Chain-of-Thought (CoT) reasoning scheme of [Kim and Suzuki, ICLR 2025] for solving Boolean problems. Together, the bounds expose a fundamental gap between what this minimal architecture achieves under ideal supervision and what is provably impossible under standard training.
- Abstract（参考訳）: 我々は、$k$-bit Boolean関数(具体的には$\mathrm{AND}$, $\mathrm{OR}$, and their noisy variants)の計算限界について、最小限の単一ヘッドソフトマックスアテンション機構を用いて研究し、$k=\Theta(d)$関連ビットを$d$入力から選択する。
これらの単純な $\mathrm{AND}$ と $\mathrm{OR}$ 関数は、シングルヘッドソフトマックスアテンション機構だけでは解決できないことを示す。
しかし、教師の強制によって、同じミニマリストの注意がそれらを解決することができる。
アーキテクチャ的には、これらのブールタスクを解くには、深いトランスフォーマーブロックやFFNを使わずに、最小限の注意しか必要としない。
方法論的には, ブーリアン問題を解くため, 多段階のチェーン・オブ・ソート (CoT) 推論スキーム (Kim and Suzuki, ICLR 2025) を置き換えた。
同時に、この最小限のアーキテクチャが理想的な監督の下で達成するものと、標準トレーニング下では証明不可能なものの間に、根本的なギャップが浮かび上がっています。
関連論文リスト
- Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization [77.3396841985172]
我々は、構造化された非極小最適化問題の解法として、2時間勾配上昇(TTGDA)を統一的に解析する。
我々の貢献はTTGDAアルゴリズムを設計することであり、設定を超えて効果的です。
論文 参考訳（メタデータ） (2024-08-21T20:14:54Z) - No-Regret M${}^{\natural}$-Concave Function Maximization: Stochastic Bandit Algorithms and NP-Hardness of Adversarial Full-Information Setting [23.188831772813103]
オンラインM$natural$-concave関数問題について検討し,Murota と Shioura (1999) によるインタラクティブ版について検討した。
バンドイット設定では、$O(T-1/2)$-simple regretと$O(T2/3)$-regretアルゴリズムを、M$natural$-concave関数のノイズ値オーラクルに$T$倍のアクセスで提示する。
完全な情報フィードバックであっても,ラウンド毎に実行されたアルゴリズムは,任意の一定の$cに対して,O(T1-c)$後悔を達成できないことを証明しています。
論文 参考訳（メタデータ） (2024-05-21T01:31:44Z) - Online $\mathrm{L}^{\natural}$-Convex Minimization [31.045112870480537]
オンライン意思決定問題は、プレイヤーが長期的損失に対して繰り返し意思決定を行う学習問題である。
既存の最小化のための一般的なフレームワークは、オンラインのサブモジュール化である。
本稿では,オンラインの$mathrmLnatural$-サブセットをサブモジュール関数として導入し,ドメインサブセットが単位ハイパーキューブのサブセットとなるようにする。
論文 参考訳（メタデータ） (2024-04-26T05:03:48Z) - Learning to Solve the Constrained Most Probable Explanation Task in Probabilistic Graphical Models [10.603378323312809]
我々は、制約された最も予測可能な説明(CMPE)問題に対して、ほぼ最適解を出力することを学ぶディープニューラルネットワークを訓練する。
提案手法の特性を解析し,その有効性をいくつかのベンチマーク問題で実験的に実証する。
論文 参考訳（メタデータ） (2024-04-17T17:55:17Z) - Horizon-Free and Variance-Dependent Reinforcement Learning for Latent
Markov Decision Processes [62.90204655228324]
我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。
我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
論文 参考訳（メタデータ） (2022-10-20T21:32:01Z) - Efficient Online-Bandit Strategies for Minimax Learning Problems [21.300877551771197]
いくつかの学習問題は、例えば、実験的な分散ロバスト学習や、非標準集約的損失による最小化といった、min-max問題の解決に関係している。
具体的には、これらの問題は、モデルパラメータ$winmathcalW$と、トレーニングセットの実証分布$pinmathcalK$で学習を行う凸線型問題である。
効率的な手法を設計するために、オンライン学習アルゴリズムを(組合せ)帯域幅アルゴリズムと対戦させる。
論文 参考訳（メタデータ） (2021-05-28T16:01:42Z) - Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits
with Linear Payoff Functions [53.77572276969548]
我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。
一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-20T04:29:18Z) - A New Minimax Theorem for Randomized Algorithms [1.2284934135116514]
新しいタイプのミニマックス定理を導入し、全てのバイアスレベルに一度に作用するハード分布の$mu$を提供する。
ランダム化クエリの複雑性,ランダム化通信の複雑性,近似度数,近似対数に対して有効であることを示す。
また、Impagliazzoのハードコアの改良版も証明した。
論文 参考訳（メタデータ） (2020-02-25T11:46:08Z) - Near-optimal Regret Bounds for Stochastic Shortest Path [63.029132134792555]
最短経路 (SSP) は計画と制御においてよく知られた問題であり、エージェントは最小の総コストで目標状態に到達する必要がある。
任意の学習アルゴリズムは、最悪の場合、少なくとも$Omega(B_star sqrt|S| |A|K)$後悔しなければならない。
論文 参考訳（メタデータ） (2020-02-23T09:10:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。