On the Statistical Query Complexity of Learning Semiautomata: a Random Walk Approach

• URL: http://arxiv.org/abs/2510.04115v1
• Date: Sun, 05 Oct 2025 09:35:35 GMT
• Title: On the Statistical Query Complexity of Learning Semiautomata: a Random Walk Approach
• Authors: George Giapitzakis, Kimon Fountoulakis, Eshaan Nichani, Jason D. Lee,
• Abstract summary: We show that Statistical Query hardness can be established when both the alphabet size and input length are in the number of states.<n>Our result is derived solely from the internal state-transition structure of semiautomata.
• Score: 59.589793281734636
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Semiautomata form a rich class of sequence-processing algorithms with applications in natural language processing, robotics, computational biology, and data mining. We establish the first Statistical Query hardness result for semiautomata under the uniform distribution over input words and initial states. We show that Statistical Query hardness can be established when both the alphabet size and input length are polynomial in the number of states. Unlike the case of deterministic finite automata, where hardness typically arises through the hardness of the language they recognize (e.g., parity), our result is derived solely from the internal state-transition structure of semiautomata. Our analysis reduces the task of distinguishing the final states of two semiautomata to studying the behavior of a random walk on the group $S_{N} \times S_{N}$. By applying tools from Fourier analysis and the representation theory of the symmetric group, we obtain tight spectral gap bounds, demonstrating that after a polynomial number of steps in the number of states, distinct semiautomata become nearly uncorrelated, yielding the desired hardness result.

Related papers

• Bisimulation Learning [55.859538562698496]
  We compute finite bisimulations of state transition systems with large, possibly infinite state space. Our technique yields faster verification results than alternative state-of-the-art tools in practice.
  arXiv  Detail & Related papers  (2024-05-24T17:11:27Z)
• An Analysis of On-the-fly Determinization of Finite-state Automata [65.268245109828]
  We establish an abstraction of on-the-fly determinization of finite-state automata and demonstrate how it can be applied to bound the automatons. A special case of our findings is that automata with many non-deterministic transitions almost always admit a determinization of complexity.
  arXiv  Detail & Related papers  (2023-08-27T11:51:27Z)
• Automata Cascades: Expressivity and Sample Complexity [90.53326983143644]
  We show that cascades allow for describing the sample complexity of automata in terms of their components. Our results show that one can in principle learn automata with infinite input alphabets and a number of states that is exponential in the amount of data available.
  arXiv  Detail & Related papers  (2022-11-25T11:02:33Z)
• A Single-Timescale Analysis For Stochastic Approximation With Multiple Coupled Sequences [21.50207156675195]
  We study the finite-time convergence of nonlinear approximation with multiple coupled sequences. At the heart of our analysis is the smoothness property of the fixed points in multi-sequence SA that holds in many applications.
  arXiv  Detail & Related papers  (2022-06-21T14:13:20Z)
• Computing the quantum guesswork: a quadratic assignment problem [6.445605125467573]
  Previous approaches to the computation of the guesswork were based on standard semi-definite programming techniques. We show that computing the quantum guesswork of qubit ensembles with uniform probability distribution leads to a more-than-quadratic speedup. As examples, we compute the guesswork of regular and quasi-regular sets of qubit states.
  arXiv  Detail & Related papers  (2021-12-03T01:24:57Z)
• Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers [50.85524803885483]
  This work proposes a formal definition of statistically meaningful (SM) approximation which requires the approximating network to exhibit good statistical learnability. We study SM approximation for two function classes: circuits and Turing machines.
  arXiv  Detail & Related papers  (2021-07-28T04:28:55Z)
• Induction and Exploitation of Subgoal Automata for Reinforcement Learning [75.55324974788475]
  We present ISA, an approach for learning and exploiting subgoals in episodic reinforcement learning (RL) tasks. ISA interleaves reinforcement learning with the induction of a subgoal automaton, an automaton whose edges are labeled by the task's subgoals. A subgoal automaton also consists of two special states: a state indicating the successful completion of the task, and a state indicating that the task has finished without succeeding.
  arXiv  Detail & Related papers  (2020-09-08T16:42:55Z)

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.