Cover Image

Mistake-bounded online learning with operation caps

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Geneson, Jesse, Li, Meien, Tang, Linus
Format:	Preprint
Published:	2025
Subjects:	Machine Learning Computational Complexity Discrete Mathematics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Bounds on the price of feedback for mistake-bounded online learning
by: Geneson, Jesse, et al.
Published: (2024)

Complexity of Injectivity and Verification of ReLU Neural Networks
by: Froese, Vincent, et al.
Published: (2024)

On the Expressibility of the Reconstructional Color Refinement
by: Arvind, V., et al.
Published: (2024)

On the complexity of freezing automata networks of bounded pathwidth
by: Goles, Eric, et al.
Published: (2025)

Efficient Algorithm for Sparse Fourier Transform of Generalized $q$-ary Functions
by: Tsui, Darin, et al.
Published: (2025)

Asymptotic Tightness of the Pigeonhole Bound for Large-Order Davenport-Schinzel Sequences
by: Geneson, Jesse
Published: (2026)

Parameterized Hardness of Zonotope Containment and Neural Network Verification
by: Froese, Vincent, et al.
Published: (2025)

Nearest Neighbor Representations of Neural Circuits
by: Kilic, Kordag Mehmet, et al.
Published: (2024)

Nearest Neighbor Representations of Neurons
by: Kilic, Kordag Mehmet, et al.
Published: (2024)

Provably Good Solutions to the Knapsack Problem via Neural Networks of Bounded Size
by: Hertrich, Christoph, et al.
Published: (2020)

The Parameterized Complexity of Computing the VC-Dimension
by: Foucaud, Florent, et al.
Published: (2025)

The Computational Complexity of Positive Non-Clashing Teaching in Graphs
by: Ganian, Robert, et al.
Published: (2025)

A Unified Approach to Submodular Maximization Under Noise
by: Bhawalkar, Kshipra, et al.
Published: (2025)

Arithmetic Circuits and Neural Networks for Regular Matroids
by: Hertrich, Christoph, et al.
Published: (2025)

Total Variation Distance Meets Probabilistic Inference
by: Bhattacharyya, Arnab, et al.
Published: (2023)

Neural Networks and (Virtual) Extended Formulations
by: Hertrich, Christoph, et al.
Published: (2024)

The Computational Complexity of Counting Linear Regions in ReLU Neural Networks
by: Stargalla, Moritz, et al.
Published: (2025)

Complexity lower bounds for succinct binary structures of bounded clique-width with restrictions
by: Geniet, Colin, et al.
Published: (2026)

Stable non-minimal fixed points of threshold-linear networks
by: Geneson, Jesse
Published: (2025)

On Closure Properties of Read-Once Oblivious Algebraic Branching Programs
by: Armand, Jules, et al.
Published: (2025)

Monotone Bounded-Depth Complexity of Homomorphism Polynomials
by: Bhargav, C. S., et al.
Published: (2025)

Is Graph Local Complementation Inherently Sequential?
by: Concha-Vega, Pablo
Published: (2025)

How to Reconfigure Your Alliances
by: Fernau, Henning, et al.
Published: (2025)

List Decoding Quotient Reed-Muller Codes
by: Gotlib, Omri, et al.
Published: (2025)

Property Testing in Bounded Degree Hypergraphs
by: Aaronson, Hugo, et al.
Published: (2025)

Complexity of the Freezing Majority Rule with L-shaped Neighborhoods
by: Concha-Vega, Pablo, et al.
Published: (2025)

On the Incompressibility of Truth With Application to Circuit Complexity
by: Tonon, Luke
Published: (2025)

A Courcelle-Type Metatheorem for Rank-Bounded Unconstrained Binary Optimization
by: Harary, Marc
Published: (2025)

Enumeration With Nice Roman Domination Properties
by: Mann, Kevin
Published: (2025)

The PPP-completeness of the Ward-Szabo theorem
by: Ishizuka, Takashi
Published: (2025)

A Distance Amplification Lemma for Monotonicity
by: Minzer, Dor
Published: (2025)

Maximum Reachability Orientation of Mixed Graphs
by: Hörsch, Florian
Published: (2025)

Parameterized Complexity of Segment Routing
by: Bazgan, Cristina, et al.
Published: (2025)

On the enumeration of Tarski fixed points
by: Müller, Julian
Published: (2023)

Edge-Disjoint Paths in Eulerian Digraphs
by: Cavallaro, Dario, et al.
Published: (2024)

Relations between monotone complexity measures based on decision tree complexity
by: Byramji, Farzan, et al.
Published: (2024)

Gap Preserving Reductions Between Reconfiguration Problems
by: Ohsaka, Naoto
Published: (2022)

Computational complexity of the Weisfeiler-Leman dimension
by: Lichter, Moritz, et al.
Published: (2024)

Gap Amplification for Reconfiguration Problems
by: Ohsaka, Naoto
Published: (2023)

An Algorithm for Monitoring Edge-geodetic Sets in Chordal Graphs
by: Marcille, Clara, et al.
Published: (2026)