6 papers
Space-Efficient Language Generation in the Limit
Nicolas Flammarion, Chirag Pabbaraju, Hristo Papazov +2
We initiate a resource-aware theory of \textit{language generation in the limit} under the minimal constraint of space efficiency. In our framework, a learner observes an adversari…
Exact Learning of Arithmetic with Differentiable Agents
Hristo Papazov, Francesco D'Angelo, Nicolas Flammarion
We explore the possibility of exact algorithmic learning with gradient-based methods and introduce a differentiable framework capable of strong length generalization on arithmetic…
Learning Algorithms in the Limit
Hristo Papazov, Nicolas Flammarion
This paper studies the problem of learning computable functions in the limit by extending Gold's inductive inference framework to incorporate \textit{computational observations} an…
Leveraging Continuous Time to Understand Momentum When Training Diagonal Linear Networks
Hristo Papazov, Scott Pesme, Nicolas Flammarion
In this work, we investigate the effect of momentum on the optimisation trajectory of gradient descent. We leverage a continuous-time approach in the analysis of momentum gradient…
The Role of Dimension in the Online Chasing Problem
Hristo Papazov
Let be a metric space and -- a collection of special objects. In the -chasing problem, an online player receives a sequence of online requests $…
An elliptic adaptation of ideas of Carleman and Domar from complex analysis related to Levinson's log log theorem
Alexander Logunov, Hristo Papazov
Using the three balls inequality, we adapt the elegant ideas of Carleman and Domar from complex analysis to linear elliptic PDE and generalize the classical Levinson's loglog theor…