Arrow Research search

Author name cluster

Angelika Steger

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

20 papers
2 author rows

Possible papers

20

ICLR Conference 2025 Conference Paper

Learning Randomized Algorithms with Transformers

  • Johannes von Oswald
  • Seijin Kobayashi
  • Yassir Akram
  • Angelika Steger

Randomization is a powerful tool that endows algorithms with remarkable properties. For instance, randomized algorithms excel in adversarial settings, often surpassing the worst-case performance of deterministic algorithms with large margins. Furthermore, their success probability can be amplified by simple strategies such as repetition and majority voting. In this paper, we enhance deep neural networks, in particular transformer models, with randomization. We demonstrate for the first time that randomized algorithms can be instilled in transformers through learning, in a purely data- and objective-driven manner. First, we analyze known adversarial objectives for which randomized algorithms offer a distinct advantage over deterministic ones. We then show that common optimization techniques, such as gradient descent or evolutionary strategies, can effectively learn transformer parameters that make use of the randomness provided to the model. To illustrate the broad applicability of randomization in empowering neural networks, we study three conceptual tasks: associative recall, graph coloring, and agents that explore grid worlds. In addition to demonstrating increased robustness against oblivious adversaries through learned randomization, our experiments reveal remarkable performance improvements due to the inherently random nature of the neural networks' computation and predictions.

Details

ICLR Conference 2024 Conference Paper

Discovering modular solutions that generalize compositionally

  • Simon Schug
  • Seijin Kobayashi
  • Yassir Akram
  • Maciej Wolczyk
  • Alexandra Maria Proca
  • Johannes von Oswald
  • Razvan Pascanu
  • João Sacramento

Many complex tasks can be decomposed into simpler, independent parts. Discovering such underlying compositional structure has the potential to enable compositional generalization. Despite progress, our most powerful systems struggle to compose flexibly. It therefore seems natural to make models more modular to help capture the compositional nature of many tasks. However, it is unclear under which circumstances modular systems can discover hidden compositional structure. To shed light on this question, we study a teacher-student setting with a modular teacher where we have full control over the composition of ground truth modules. This allows us to relate the problem of compositional generalization to that of identification of the underlying modules. In particular we study modularity in hypernetworks representing a general class of multiplicative interactions. We show theoretically that identification up to linear transformation purely from demonstrations is possible without having to learn an exponential number of module combinations. We further demonstrate empirically that under the theoretically identified conditions, meta-learning from finite data can discover modular policies that generalize compositionally in a number of complex environments.

Details

TCS Journal 2020 Journal Article

A general lower bound for collaborative tree exploration

  • Yann Disser
  • Frank Mousset
  • Andreas Noever
  • Nemanja Škorić
  • Angelika Steger

We consider collaborative graph exploration with a set of k agents. All agents start at a common vertex of an initially unknown graph with n vertices and need to collectively visit all other vertices. We assume agents are deterministic, moves are simultaneous, and we allow agents to communicate globally. For this setting, we give the first non-trivial lower bounds that bridge the gap between small ( k ≤ n ) and large ( k ≥ n ) teams of agents. Remarkably, our bounds tightly connect to existing results in both domains. First, we significantly extend a lower bound of Ω ( log ⁡ k / log ⁡ log ⁡ k ) by Dynia et al. on the competitive ratio of a collaborative tree exploration strategy to the range k ≤ n log c ⁡ n for any c ∈ N. Second, we provide a tight lower bound on the number of agents needed for any competitive exploration algorithm. In particular, we show that any collaborative tree exploration algorithm with k = D n 1 + o ( 1 ) agents has a competitive ratio of ω ( 1 ), while Dereniowski et al. gave an algorithm with k = D n 1 + ε agents and competitive ratio O ( 1 ), for any ε > 0 and with D denoting the diameter of the graph. Lastly, we show that, for any exploration algorithm using k = n agents, there exist trees of arbitrarily large height D that require Ω ( D 2 ) rounds, and we provide a simple algorithm that matches this bound for all trees.

Details DOI

ICML Conference 2019 Conference Paper

Optimal Kronecker-Sum Approximation of Real Time Recurrent Learning

  • Frederik Benzing
  • Marcelo Matheus Gauy
  • Asier Mujika
  • Anders Martinsson
  • Angelika Steger

One of the central goals of Recurrent Neural Networks (RNNs) is to learn long-term dependencies in sequential data. Nevertheless, the most popular training method, Truncated Backpropagation through Time (TBPTT), categorically forbids learning dependencies beyond the truncation horizon. In contrast, the online training algorithm Real Time Recurrent Learning (RTRL) provides untruncated gradients, with the disadvantage of impractically large computational costs. Recently published approaches reduce these costs by providing noisy approximations of RTRL. We present a new approximation algorithm of RTRL, Optimal Kronecker-Sum Approximation (OK). We prove that OK is optimal for a class of approximations of RTRL, which includes all approaches published so far. Additionally, we show that OK has empirically negligible noise: Unlike previous algorithms it matches TBPTT in a real world task (character-level Penn TreeBank) and can exploit online parameter updates to outperform TBPTT in a synthetic string memorization task. Code available at GitHub.

Details

TCS Journal 2019 Journal Article

The linear hidden subset problem for the (1 + 1) EA with scheduled and adaptive mutation rates

  • Hafsteinn Einarsson
  • Marcelo Matheus Gauy
  • Johannes Lengler
  • Florian Meier
  • Asier Mujika
  • Angelika Steger
  • Felix Weissenberger

We study unbiased ( 1 + 1 ) evolutionary algorithms on linear functions with an unknown number n of bits with non-zero weight. Static algorithms achieve an optimal runtime of O ( n ( ln ⁡ n ) 2 + ε ), however, it remained unclear whether more dynamic parameter policies could yield better runtime guarantees. We consider two setups: one where the mutation rate follows a fixed schedule, and one where it may be adapted depending on the history of the run. For the first setup, we give a schedule that achieves a runtime of ( 1 ± o ( 1 ) ) β n ln ⁡ n, where β ≈ 3. 552, which is an asymptotic improvement over the runtime of the static setup. Moreover, we show that no schedule admits a better runtime guarantee and that the optimal schedule is essentially unique. For the second setup, we show that the runtime can be further improved to ( 1 ± o ( 1 ) ) e n ln ⁡ n, which matches the performance of algorithms that know n in advance. Finally, we study the related model of initial segment uncertainty with static position-dependent mutation rates, and derive asymptotically optimal lower bounds. This answers a question by Doerr, Doerr, and Kötzing.

Details DOI

NeurIPS Conference 2018 Conference Paper

Approximating Real-Time Recurrent Learning with Random Kronecker Factors

  • Asier Mujika
  • Florian Meier
  • Angelika Steger

Despite all the impressive advances of recurrent neural networks, sequential data is still in need of better modelling. Truncated backpropagation through time (TBPTT), the learning algorithm most widely used in practice, suffers from the truncation bias, which drastically limits its ability to learn long-term dependencies. The Real Time Recurrent Learning algorithm (RTRL) addresses this issue, but its high computational requirements make it infeasible in practice. The Unbiased Online Recurrent Optimization algorithm (UORO) approximates RTRL with a smaller runtime and memory cost, but with the disadvantage of obtaining noisy gradients that also limit its practical applicability. In this paper we propose the Kronecker Factored RTRL (KF-RTRL) algorithm that uses a Kronecker product decomposition to approximate the gradients for a large class of RNNs. We show that KF-RTRL is an unbiased and memory efficient online learning algorithm. Our theoretical analysis shows that, under reasonable assumptions, the noise introduced by our algorithm is not only stable over time but also asymptotically much smaller than the one of the UORO algorithm. We also confirm these theoretical results experimentally. Further, we show empirically that the KF-RTRL algorithm captures long-term dependencies and almost matches the performance of TBPTT on real world tasks by training Recurrent Highway Networks on a synthetic string memorization task and on the Penn TreeBank task, respectively. These results indicate that RTRL based approaches might be a promising future alternative to TBPTT.

PDF Details

NeurIPS Conference 2017 Conference Paper

Fast-Slow Recurrent Neural Networks

  • Asier Mujika
  • Florian Meier
  • Angelika Steger

Processing sequential data of variable length is a major challenge in a wide range of applications, such as speech recognition, language modeling, generative image modeling and machine translation. Here, we address this challenge by proposing a novel recurrent neural network (RNN) architecture, the Fast-Slow RNN (FS-RNN). The FS-RNN incorporates the strengths of both multiscale RNNs and deep transition RNNs as it processes sequential data on different timescales and learns complex transition functions from one time step to the next. We evaluate the FS-RNN on two character based language modeling data sets, Penn Treebank and Hutter Prize Wikipedia, where we improve state of the art results to 1. 19 and 1. 25 bits-per-character (BPC), respectively. In addition, an ensemble of two FS-RNNs achieves 1. 20 BPC on Hutter Prize Wikipedia outperforming the best known compression algorithm with respect to the BPC measure. We also present an empirical investigation of the learning and network dynamics of the FS-RNN, which explains the improved performance compared to other RNN architectures. Our approach is general as any kind of RNN cell is a possible building block for the FS-RNN architecture, and thus can be flexibly applied to different tasks.

PDF Details

SODA Conference 2015 Conference Paper

An algorithmic framework for obtaining lower bounds for random Ramsey problems extended abstract

  • Rajko Nenadov
  • Nemanja Skoric
  • Angelika Steger

In this paper we introduce a general framework for proving lower bounds for various Ramsey type problems within random settings. The main idea is to view the problem from an algorithmic perspective: we aim at providing an algorithm that finds the desired colouring with high probability. Our framework allows to reduce the probabilistic problem of whether the Ramsey property at hand holds for random (hy-per)graphs with edge probability p to a deterministic question of whether there exists a finite graph that forms an obstruction. In the second part of the paper we apply this framework to address and solve various open problems. In particular, we provide a matching lower bound for the result of Friedgut, Rödl and Schacht (2010) and, independently, Conlon and Gowers (2014+) for the classical Ramsey problem for hypergraphs in the case of cliques. A problem that was open for more than 15 years. We also improve a result of Bohman, Frieze, Pikhurko and Smyth (2010) for bounded anti-Ramsey problems in random graphs and extend it to hypergraphs. Finally, we provide matching lower bounds for a proper-colouring version of anti-Ramsey problems introduced by Kohayakawa, Konstadinidis and Mota (2014).

Details

STOC Conference 2006 Conference Paper

A quasi-polynomial time approximation scheme for minimum weight triangulation

  • Jan Remy
  • Angelika Steger

The MINIMUM WEIGHT TRIANGULATION problem is to find a triangulation T* of minimum length for a given set of points P in the Euclidean plane. It was one of the few longstanding open problems from the famous list of twelve problems with unknown complexity status, published by Garey and Johnson [8] in 1979. Very recently the problem was shown to be NP-hard by Mulzer and Rote. In this paper, we present a quasi-polynomial time approximation scheme for MINIMUM WEIGHT TRIANGULATION.

Details

STOC Conference 2002 Conference Paper

A new average case analysis for completion time scheduling

  • Mark Scharbrodt
  • Thomas Schickinger
  • Angelika Steger

(MATH) We present a new average case analysis for the problem of scheduling n jobs on $m$ machines so that the sum of job completion times is minimized. Our analysis transfers the concept of competitive analysis --- which is a typical worst case notion --- to the average case. We show that the classic SEPT scheduling strategy with Ω( n ) worst case competitive ratio achieves ${\cal O}(1)$ on the average. Moreover, bounds on the probability distribution of the competitive ratio are derived which provide an in-depth understanding of the stochastic version of the min sum scheduling problem.

Details

TCS Journal 2001 Journal Article

Learning one-variable pattern languages very efficiently on average, in parallel, and by asking queries

  • Thomas Erlebach
  • Peter Rossmanith
  • Hans Stadtherr
  • Angelika Steger
  • Thomas Zeugmann

A pattern is a finite string of constant and variable symbols. The language generated by a pattern is the set of all strings of constant symbols which can be obtained from the pattern by substituting non-empty strings for variables. We study the learnability of one-variable pattern languages in the limit with respect to the update time needed for computing a new single hypothesis and the expected total learning time taken until convergence to a correct hypothesis. Our results are as follows. First, we design a consistent and set-driven learner that, using the concept of descriptive patterns, achieves update time O(n2 logn), where n is the size of the input sample. The best previously known algorithm for computing descriptive one-variable patterns requires time O(n4 logn) (cf. Angluin, J. Comput. Systems Sci. 21(1) (1980) 46–62). Second, we give a parallel version of this algorithm that requires time O(logn) and O(n3/log n) processors on an EREW-PRAM. Third, using a modified version of the sequential algorithm as a subroutine, we devise a learning algorithm for one-variable patterns whose expected total learning time is O(ℓ2 logℓ) provided the sample strings are drawn from the target language according to a probability distribution with expected string length ℓ. The probability distribution must be such that strings of equal length have equal probability, but can be arbitrary otherwise. Thus, we establish the first algorithm for learning one-variable pattern languages having an expected total learning time that provably differs from the update time by a constant factor only. Finally, we show how the algorithm for descriptive one-variable patterns can be used for learning one-variable patterns with a polynomial number of superset queries with respect to the one-variable patterns as query language.

Details DOI
v2026.09.13