論文の概要: Stochasticity Is Not the Hard Part: Reduction and Complexity in Instructional Sequencing over Prerequisite DAGs
- arxiv url: http://arxiv.org/abs/2608.05455v1
- Date: Wed, 05 Aug 2026 23:00:28 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-07 15:25:20.806852
- Title: Stochasticity Is Not the Hard Part: Reduction and Complexity in Instructional Sequencing over Prerequisite DAGs
- Title（参考訳）: 確率性は難しい部分ではない: 必須DAGによる命令シークエンシングの削減と複雑度
- Abstract要約: 提案手法は,提案手法が状態依存確率で成功し,失敗しても学習者の状態が変化しない,最短経路問題であるシークエンシングについて検討する。
問題は決定論的最短パス問題に崩壊し、前提条件の次数イデアルの格子上の問題となる。
- 参考スコア（独自算出の注目度）: 2.2660071841277962
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: When a student must learn concepts connected by prerequisite dependencies, when does the order of instruction matter, and what does it cost to find the best one? We study instructional sequencing as a stochastic shortest-path problem in which attempting a concept succeeds with a state-dependent probability and failure leaves the learner state unchanged. We first prove that this stochasticity can be eliminated exactly: the problem collapses to a deterministic shortest-path problem on the lattice of prerequisite order ideals, preserving optimal values and actions. The collapse removes stochastic complexity but not combinatorial complexity: optimal sequencing remains NP-hard -- via reduction from feedback arc set in tournaments -- even with no prerequisite edges, unit costs, uniform binary nonnegative transfer, and success probabilities at least $1/2$. Hardness is not uniform: when realizable transfer preferences remain jointly acyclic with the prerequisites, any topological order of the residual joint graph is optimal, and fixed prerequisite width yields polynomial-time exact dynamic programming. A computable diagnostic, $mΔ$, bounds the value of sequencing before optimization. On 70,893 interactions from an introductory CS course, the diagnostic certifies a doubly easy regime -- little value to optimize and little space to search -- while constructed transfer instances realize the challenging regime, where myopic sequencing suffers large regret yet exact A* with a consistent heuristic expands only linearly many states on that family.
- Abstract（参考訳）: 学生が前提条件に依存している概念を学習しなければならないとき、命令の順序はいつ重要か、最もよいものを見つけるのにどのコストがかかるか。
本研究では,概念の試行が状態依存確率で成功し,失敗しても学習者の状態が変化しない確率的最短パス問題として命令シークエンシングについて検討する。
問題は、決定論的最短経路問題に崩壊し、最適値と作用を保ちながら、前提条件のイデアルの格子上の問題となる。
最適シークエンシングは、トーナメントで設定されたフィードバック弧から減らし、必要なエッジ、ユニットコスト、均一なバイナリ非負の転送、成功確率が少なくとも1/2$であるにもかかわらず、NPハードのままである。
実現可能な移動選好が前提条件と共同で非循環であるとき、残余結合グラフの位相順序は最適であり、固定された必要条件幅は多項式時間正確な動的プログラミングをもたらす。
計算可能な診断である$mΔ$は、最適化前のシークエンシングの値にバウンドする。
導入CSコースからの70,893のインタラクションでは、診断は2つの簡単なレシエーション(最適化する価値はほとんどなく、探索するスペースも少ない)を認定する一方で、構築されたトランスファーインスタンスは、ミオピックシークエンシングが非常に後悔するが正確なA*に悩まされ、一貫したヒューリスティックな拡張はその家族の多くの状態のみを直線的に拡張する、という挑戦的なレシスタンスを実現している。
関連論文リスト
- MoSSP: A Momentum-Based Single-Loop Stochastic Penalty Method for Nonconvex Constrained DC-Regularized Optimization [6.024178662558234]
本稿では,DC正則化を用いた非制約問題のクラスを示す。
証明可能な複雑性保証を伴う問題に対してMomentum Mo Mo Penalty法を提案する。
論文 参考訳（メタデータ） (2026-05-28T09:06:26Z) - Stochastic Trust-Region Methods for Over-parameterized Models [3.1231899978018824]
本稿では,手動のステップサイズチューニングを排除し,平等に制約された問題に自然に拡張する信頼領域統合フレームワークを提案する。
制約のない最適化のために、1次信頼領域アルゴリズムを開発し、$O(varepsilon-2 log (1/varepsilon)$の1次オラクル複雑性を実現し、$varepsilon$-stationary点を求める。
等式制約問題に対して、ペナルティパラメータが$$$の2次ペナルティに基づく信頼領域法を導入し、反復とオラクルの複雑さを$O()で確立する。
論文 参考訳（メタデータ） (2026-04-15T15:57:34Z) - Stochastic Momentum Methods for Non-smooth Non-Convex Finite-Sum Coupled Compositional Optimization [68.22688819802622]
我々は、(ほぼ)$レベルのKKTソリューションを見つけるために、$O(/epsilon)$の最先端の複雑さを新たに提案する。
O(/epsilon)$ の(ほぼ) $ レベルの KKT ソリューションを見つけるための技術的複雑さを適用することで、(ほぼ) $ レベルの KKT ソリューションを見つけるための $O(/epsilon)$ の最先端の複雑さを新たに達成する。
論文 参考訳（メタデータ） (2025-06-03T06:31:59Z) - A single-loop SPIDER-type stochastic subgradient method for expectation-constrained nonconvex nonsmooth optimization [18.38962516619021]
厳密なペナルティモデルを構築するための新しい手法を提案する。
対象関数と関数の次数と各制約関数値を用いる。
その結果,本手法は2人制約問題よりもはるかに高速であることが判明した。
論文 参考訳（メタデータ） (2025-01-31T15:18:52Z) - Optimal PAC Bounds Without Uniform Convergence [11.125968799758436]
我々は、一様収束論の極限を超えるフレームワークを通して、最適な高確率リスク境界を提供する。
我々のフレームワークは、置換不変予測器の残余誤差を高い確率リスク境界に変換する。
具体的には, 1-inclusion graph アルゴリズムの特定のアグリゲーションが最適であることを示す。
論文 参考訳（メタデータ） (2023-04-18T17:57:31Z) - Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation
Constrained Optimization [88.0031283949404]
多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。
提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
論文 参考訳（メタデータ） (2022-12-19T14:48:54Z) - Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。
予測と高い確率で、新しい過剰なリスク境界を提供する。
我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
論文 参考訳（メタデータ） (2022-11-03T12:40:24Z) - Instance-optimality in optimal value estimation: Adaptivity via
variance-reduced Q-learning [99.34907092347733]
本稿では,マルコフ決定過程における最適な$Q$値関数を離散状態と動作で推定する問題を解析する。
局所的なミニマックスフレームワークを用いて、この関数は任意の推定手順の精度の低い境界に現れることを示す。
他方,Q$ラーニングの分散還元版を解析することにより,状態と行動空間の対数的要因まで,下位境界のシャープさを確立する。
論文 参考訳（メタデータ） (2021-06-28T00:38:54Z) - Tighter Analysis of Alternating Stochastic Gradient Method for
Stochastic Nested Problems [31.02472517086767]
本稿では、ネスト問題に対するSGD型更新を、ALSET(ALternating dEscenT)メソッドと呼ばれる単一のアプローチに統合する。
新しい分析では、ネストされた問題において$epsilon$-stationaryポイントを達成するには、$cal O(epsilon-2)$サンプルが必要である。
本研究の結果を合成, 分極, 強化学習問題に適用することにより, それぞれの症例において最もよく知られたサンプルの複雑さを改善または一致させる。
論文 参考訳（メタデータ） (2021-06-25T17:33:51Z) - Online Model Selection for Reinforcement Learning with Function
Approximation [50.008542459050155]
我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。
また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
論文 参考訳（メタデータ） (2020-11-19T10:00:54Z) - Efficient Methods for Structured Nonconvex-Nonconcave Min-Max
Optimization [98.0595480384208]
定常点に収束する一般化外空間を提案する。
このアルゴリズムは一般の$p$ノルド空間だけでなく、一般の$p$次元ベクトル空間にも適用される。
論文 参考訳（メタデータ） (2020-10-31T21:35:42Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。