Stochasticity Is Not the Hard Part: Reduction and Complexity in Instructional Sequencing over Prerequisite DAGs

• URL: http://arxiv.org/abs/2608.05455v1
• Date: Wed, 05 Aug 2026 23:00:28 GMT
• Title: Stochasticity Is Not the Hard Part: Reduction and Complexity in Instructional Sequencing over Prerequisite DAGs
• Abstract summary: We study sequencing as a shortest-path problem in which attempting a concept succeeds with a state-dependent probability and failure leaves the learner state unchanged.<n>We first prove that thisity can be eliminated exactly: the problem collapses to a deterministic shortest-path problem on the lattice of prerequisite order ideals.
• Score: 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.

Related papers

• MoSSP: A Momentum-Based Single-Loop Stochastic Penalty Method for Nonconvex Constrained DC-Regularized Optimization [6.024178662558234]
  We show a class of non constrained problems with difference-of-an- oracle (DC regularization) regularization.<n>We propose a Momentum Mo Mo Penalty method for such problems with provable complexity guarantees.
  arXiv  Detail & Related papers  (2026-05-28T09:06:26Z)
• Stochastic Trust-Region Methods for Over-parameterized Models [3.1231899978018824]
  We propose a unified trust-region framework that eliminates manual step-size tuning and extends naturally to equality-constrained problems.<n>For unconstrained optimization, we develop a first-order trust-region algorithm and show that it achieves a first-order oracle complexity of $O(varepsilon-2 log (1/varepsilon)$ for finding an $varepsilon$-stationary point.<n>For equality-constrained problems, we introduce a quadratic-penalty-based trust-region method with penalty parameter $$, and establish an iteration and oracle complexity of $O(
  arXiv  Detail & Related papers  (2026-04-15T15:57:34Z)
• Stochastic Momentum Methods for Non-smooth Non-Convex Finite-Sum Coupled Compositional Optimization [68.22688819802622]
  We propose a new state-of-the-art complexity of $O(/epsilon)$ for finding an (nearly) $'level KKT solution.<n>By applying our hinge-of-the-art complexity of $O(/epsilon)$ for finding an (nearly) $'level KKT solution, we achieve a new state-of-the-art complexity of $O(/epsilon)$ for finding an (nearly) $'level KKT solution.
  arXiv  Detail & Related papers  (2025-06-03T06:31:59Z)
• A single-loop SPIDER-type stochastic subgradient method for expectation-constrained nonconvex nonsmooth optimization [18.38962516619021]
  We present a novel method for building exact penalty models.<n>We use the subgradients of the objective and functions as well as the constraint function value at each.<n>We find that our method is significantly faster than two-man-constrained problems.
  arXiv  Detail & Related papers  (2025-01-31T15:18:52Z)
• Optimal PAC Bounds Without Uniform Convergence [11.125968799758436]
  We provide optimal high probability risk bounds through a framework that surpasses the limitations of uniform convergence arguments. Our framework converts the leave-one-out error of permutation invariant predictors into high probability risk bounds. Specifically, our result shows that certain aggregations of one-inclusion graph algorithms are optimal.
  arXiv  Detail & Related papers  (2023-04-18T17:57:31Z)
• Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization [88.0031283949404]
  Many real-world problems have complicated non functional constraints and use a large number of data points. Our proposed method outperforms an existing method with the previously best-known result.
  arXiv  Detail & Related papers  (2022-12-19T14:48:54Z)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  Inspired by regularization techniques in statistics and machine learning, we study complementary composite minimization. We provide novel excess risk bounds, both in expectation and with high probability. Our algorithms are nearly optimal, which we prove via novel lower complexity bounds for this class of problems.
  arXiv  Detail & Related papers  (2022-11-03T12:40:24Z)
• Instance-optimality in optimal value estimation: Adaptivity via variance-reduced Q-learning [99.34907092347733]
  We analyze the problem of estimating optimal $Q$-value functions for a discounted Markov decision process with discrete states and actions. Using a local minimax framework, we show that this functional arises in lower bounds on the accuracy on any estimation procedure. In the other direction, we establish the sharpness of our lower bounds, up to factors logarithmic in the state and action spaces, by analyzing a variance-reduced version of $Q$-learning.
  arXiv  Detail & Related papers  (2021-06-28T00:38:54Z)
• Tighter Analysis of Alternating Stochastic Gradient Method for Stochastic Nested Problems [31.02472517086767]
  This paper unifies SGD-type updates for nested problems into a single approach that we term ALternating dEscenT (ALSET) method. Under the new analysis, to achieve an $epsilon$-stationary point of the nested problem, it requires $cal O(epsilon-2)$ samples. Applying our results to compositional, min-max and reinforcement learning problems either improves or matches the best-known sample complexity in the respective cases.
  arXiv  Detail & Related papers  (2021-06-25T17:33:51Z)
• Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
  We present a meta-algorithm that adapts to the optimal complexity with $tildeO(L5/6 T2/3)$ regret. We also show that the meta-algorithm automatically admits significantly improved instance-dependent regret bounds.
  arXiv  Detail & Related papers  (2020-11-19T10:00:54Z)
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization [98.0595480384208]
  We propose a generalization extraient spaces which converges to a stationary point. The algorithm applies not only to general $p$-normed spaces, but also to general $p$-dimensional vector spaces.
  arXiv  Detail & Related papers  (2020-10-31T21:35:42Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.