Showing 1–50 of 61 results for author: Rojas, C

Positional versus Symbolic Attention Heads: Learning Dynamics, RoPE Geometry, and Length Generalization

Authors: Felipe Urrutia, Juan José Alegría, Cinthia Sanchez Macias, Jorge Salas, Cristian B. Calderon, Cristobal Rojas

Abstract: Transformer-based language models are widespread in today's society. As such, understanding the mechanisms by which they solve structured tasks and predicting how they may behave in novel scenarios is of great importance for safe deployment. We study the learning dynamics of attention heads in a controlled setting by training a decoder-only Transformer (GPT-J) on two structurally equivalent multi-… ▽ More Transformer-based language models are widespread in today's society. As such, understanding the mechanisms by which they solve structured tasks and predicting how they may behave in novel scenarios is of great importance for safe deployment. We study the learning dynamics of attention heads in a controlled setting by training a decoder-only Transformer (GPT-J) on two structurally equivalent multi-hop reasoning tasks: a number task requiring positional reasoning and a letter task requiring symbolic reasoning. Using a recently introduced metric that classifies attention-head behavior as positional or symbolic for a given prompt, we show that successful learning is associated with the emergence of pure heads, i.e., heads that express themselves as either positional or symbolic. Despite the tasks' structural equivalence, they impose different mechanistic demands: the number task requires both positional and symbolic heads, whereas the letter task requires only symbolic heads. We then identify the computational roles of these heads, characterize the basic functions they implement, and give theoretical constructions showing how single-layer RoPE-based attention can realize these functions through geometrically interpretable query, key, and value operations. This analysis yields a quantitative separation between positional and symbolic mechanisms in their robustness to longer sequences, formalized through a novel notion of discrepancy. We empirically validate the resulting predictions in both controlled and real-world models, showing that symbolic mechanisms extrapolate more reliably to longer sequences while positional mechanisms face sharper limitations. △ Less

Submitted 29 May, 2026; originally announced May 2026.

Computationally lightweight classifiers with frequentist bounds on predictions

Authors: Shreeram Murali, Cristian R. Rojas, Dominik Baumann

Abstract: While both classical and neural network classifiers can achieve high accuracy, they fall short on offering uncertainty bounds on their predictions, making them unfit for safety-critical applications. Existing kernel-based classifiers that provide such bounds scale with $\mathcal O (n^{\sim3})$ in time, making them computationally intractable for large datasets. To address this, we propose a novel,… ▽ More While both classical and neural network classifiers can achieve high accuracy, they fall short on offering uncertainty bounds on their predictions, making them unfit for safety-critical applications. Existing kernel-based classifiers that provide such bounds scale with $\mathcal O (n^{\sim3})$ in time, making them computationally intractable for large datasets. To address this, we propose a novel, computationally efficient classification algorithm based on the Nadaraya-Watson estimator, for whose estimates we derive frequentist uncertainty intervals. We evaluate our classifier on synthetically generated data and on electrocardiographic heartbeat signals from the MIT-BIH Arrhythmia database. We show that the method achieves competitive accuracy $>$\SI{96}{\percent} at $\mathcal O(n)$ and $\mathcal O(\log n)$ operations, while providing actionable uncertainty bounds. These bounds can, e.g., aid in flagging low-confidence predictions, making them suitable for real-time settings with resource constraints, such as diagnostic monitoring or implantable devices. △ Less

Submitted 9 April, 2026; v1 submitted 23 March, 2026; originally announced March 2026.

Comments: 9 pages, references, checklist, and appendix. Total 23 pages. Accepted to AISTATS2026

Evaluating Generalization Capabilities of LLM-Based Agents in Mixed-Motive Scenarios Using Concordia

Authors: Chandler Smith, Marwa Abdulhai, Manfred Diaz, Marko Tesic, Rakshit S. Trivedi, Alexander Sasha Vezhnevets, Lewis Hammond, Jesse Clifton, Minsuk Chang, Edgar A. Duéñez-Guzmán, John P. Agapiou, Jayd Matyas, Danny Karmon, Akash Kundu, Aliaksei Korshuk, Ananya Ananya, Arrasy Rahman, Avinaash Anand Kulandaivel, Bain McHale, Beining Zhang, Buyantuev Alexander, Carlos Saith Rodriguez Rojas, Caroline Wang, Chetan Talele, Chenao Liu , et al. (61 additional authors not shown)

Abstract: Large Language Model (LLM) agents have demonstrated impressive capabilities for social interaction and are increasingly being deployed in situations where they might engage with both human and artificial agents. These interactions represent a critical frontier for LLM-based agents, yet existing evaluation methods fail to measure how well these capabilities generalize to novel social situations. In… ▽ More Large Language Model (LLM) agents have demonstrated impressive capabilities for social interaction and are increasingly being deployed in situations where they might engage with both human and artificial agents. These interactions represent a critical frontier for LLM-based agents, yet existing evaluation methods fail to measure how well these capabilities generalize to novel social situations. In this paper, we introduce a method for evaluating the ability of LLM-based agents to cooperate in zero-shot, mixed-motive environments using Concordia, a natural language multi-agent simulation environment. Our method measures general cooperative intelligence by testing an agent's ability to identify and exploit opportunities for mutual gain across diverse partners and contexts. We present empirical results from the NeurIPS 2024 Concordia Contest, where agents were evaluated on their ability to achieve mutual gains across a suite of diverse scenarios ranging from negotiation to collective action problems. Our findings reveal significant gaps between current agent capabilities and the robust generalization required for reliable cooperation, particularly in scenarios demanding persuasion and norm enforcement. △ Less

Submitted 2 December, 2025; originally announced December 2025.

Comments: Published at NeurIPS Datasets and Benchmarks 2025, 10 pages

MSC Class: 68T42 ACM Class: I.2.6

Decoupling Positional and Symbolic Attention Behavior in Transformers

Authors: Felipe Urrutia, Jorge Salas, Alexander Kozachinskiy, Cristian Buc Calderon, Hector Pasten, Cristobal Rojas

Abstract: An important aspect subtending language understanding and production is the ability to independently encode positional and symbolic information of the words within a sentence. In Transformers, positional information is typically encoded using Positional Encodings (PEs). One such popular PE, namely Rotary PE (RoPE), has been widely used due to its empirical success. Recently, it has been argued tha… ▽ More An important aspect subtending language understanding and production is the ability to independently encode positional and symbolic information of the words within a sentence. In Transformers, positional information is typically encoded using Positional Encodings (PEs). One such popular PE, namely Rotary PE (RoPE), has been widely used due to its empirical success. Recently, it has been argued that part of RoPE's success emerges from its ability to encode robust positional and semantic information using large and small frequencies, respectively. In this work, we perform a deeper dive into the positional versus symbolic dichotomy of attention heads behavior, both at the theoretical and empirical level. We provide general definitions of what it means for a head to behave positionally or symbolically, prove that these are two mutually exclusive behaviors and develop a metric to quantify them. We apply our framework to analyze Transformer-based LLMs using RoPE and find that all heads exhibit a strong correspondence between behavior and frequency use. Finally, we introduce canonical tasks designed to be either purely positional or symbolic, and demonstrate that the Transformer performance causally relates to the ability of attention heads to leverage the appropriate frequencies. In particular, we show that we can control the Transformer performance by controlling which frequencies the attention heads can access. Altogether, our work provides a detailed understanding of RoPE, and how its properties relate to model behavior. △ Less

Submitted 2 October, 2025; originally announced November 2025.

Comments: 32 pages, 12 figures, repository available

MSC Class: 03D78 ACM Class: I.2.0; F.1.0

Region-Aware Reconstruction Strategy for Pre-training fMRI Foundation Model

Authors: Ruthwik Reddy Doodipala, Pankaj Pandey, Carolina Torres Rojas, Manob Jyoti Saikia, Ranganatha Sitaram

Abstract: The emergence of foundation models in neuroimaging is driven by the increasing availability of large-scale and heterogeneous brain imaging datasets. Recent advances in self-supervised learning, particularly reconstruction-based objectives, have demonstrated strong potential for pretraining models that generalize effectively across diverse downstream functional MRI (fMRI) tasks. In this study, we e… ▽ More The emergence of foundation models in neuroimaging is driven by the increasing availability of large-scale and heterogeneous brain imaging datasets. Recent advances in self-supervised learning, particularly reconstruction-based objectives, have demonstrated strong potential for pretraining models that generalize effectively across diverse downstream functional MRI (fMRI) tasks. In this study, we explore region-aware reconstruction strategies for a foundation model in resting-state fMRI, moving beyond approaches that rely on random region masking. Specifically, we introduce an ROI-guided masking strategy using the Automated Anatomical Labelling Atlas (AAL3), applied directly to full 4D fMRI volumes to selectively mask semantically coherent brain regions during self-supervised pretraining. Using the ADHD-200 dataset comprising 973 subjects with resting-state fMRI scans, we show that our method achieves a 4.23% improvement in classification accuracy for distinguishing healthy controls from individuals diagnosed with ADHD, compared to conventional random masking. Region-level attribution analysis reveals that brain volumes within the limbic region and cerebellum contribute most significantly to reconstruction fidelity and model representation. Our results demonstrate that masking anatomical regions during model pretraining not only enhances interpretability but also yields more robust and discriminative representations. In future work, we plan to extend this approach by evaluating it on additional neuroimaging datasets, and developing new loss functions explicitly derived from region-aware reconstruction objectives. These directions aim to further improve the robustness and interpretability of foundation models for functional neuroimaging. △ Less

Submitted 1 November, 2025; originally announced November 2025.

LSTM-Based Forecasting and Analysis of EV Charging Demand in a Dense Urban Campus

Authors: Zak Ressler, Marcus Grijalva, Angelica Marie Ignacio, Melanie Torres, Abelardo Cuadra Rojas, Rohollah Moghadam, Mohammad Rasoul narimani

Abstract: This paper presents a framework for processing EV charging load data in order to forecast future load predictions using a Recurrent Neural Network, specifically an LSTM. The framework processes a large set of raw data from multiple locations and transforms it with normalization and feature extraction to train the LSTM. The pre-processing stage corrects for missing or incomplete values by interpola… ▽ More This paper presents a framework for processing EV charging load data in order to forecast future load predictions using a Recurrent Neural Network, specifically an LSTM. The framework processes a large set of raw data from multiple locations and transforms it with normalization and feature extraction to train the LSTM. The pre-processing stage corrects for missing or incomplete values by interpolating and normalizing the measurements. This information is then fed into a Long Short-Term Memory Model designed to capture the short-term fluctuations while also interpreting the long-term trends in the charging data. Experimental results demonstrate the model's ability to accurately predict charging demand across multiple time scales (daily, weekly, and monthly), providing valuable insights for infrastructure planning, energy management, and grid integration of EV charging facilities. The system's modular design allows for adaptation to different charging locations with varying usage patterns, making it applicable across diverse deployment scenarios. △ Less

Submitted 19 October, 2025; originally announced October 2025.

Message Passing on the Edge: Towards Scalable and Expressive GNNs

Authors: Pablo Barceló, Fabian Jogl, Alexander Kozachinskiy, Matthias Lanzinger, Stefan Neumann, Cristóbal Rojas

Abstract: Graph neural networks (GNNs) are widely used in graph learning and most architectures propagate information by passing messages between vertices. In this work, we shift our attention to GNNs that perform message passing on edges and introduce EB-1WL, an edge-based color-refinement test, and a corresponding architecture, EB-GNN. Our EB-GNN architecture is inspired by the classic triangle-counting a… ▽ More Graph neural networks (GNNs) are widely used in graph learning and most architectures propagate information by passing messages between vertices. In this work, we shift our attention to GNNs that perform message passing on edges and introduce EB-1WL, an edge-based color-refinement test, and a corresponding architecture, EB-GNN. Our EB-GNN architecture is inspired by the classic triangle-counting algorithm of Chiba and Nishizeki and passes messages along edges and triangles. Our contributions are as follows: (1) Theoretically, we show that EB-1WL is significantly more expressive than 1WL. We provide a complete logical characterization of EB-1WL in first-order logic, along with distinguishability results via homomorphism counting. To the best of our knowledge, EB-GNN has the strongest theoretical expressivity guarantees among edge-based message-passing GNNs in the literature. (2) Unlike many GNN architectures that are more expressive than 1WL, we prove that EB-1WL and EB-GNN admit near-linear time and memory usage on practical graph learning workloads. (3) We show in experiments that EB-GNN is a highly efficient general-purpose architecture: it substantially outperforms simple MPNNs and remains competitive with task-specialized state-of-the-art GNNs at substantially lower computational cost. △ Less

Submitted 30 January, 2026; v1 submitted 15 October, 2025; originally announced October 2025.

Networks Multiscale Entropy Analysis

Authors: Sebastián Brzovic, Cristóbal Rojas, Andrés Abeliuk

Abstract: Understanding the structural complexity and predictability of complex networks is a central challenge in network science. Although recent studies have revealed a relationship between compression-based entropy and link prediction performance, existing methods focus on single-scale representations. This approach often overlooks the rich hierarchical patterns that can exist in real-world networks. In… ▽ More Understanding the structural complexity and predictability of complex networks is a central challenge in network science. Although recent studies have revealed a relationship between compression-based entropy and link prediction performance, existing methods focus on single-scale representations. This approach often overlooks the rich hierarchical patterns that can exist in real-world networks. In this study, we introduce a multiscale entropy framework that extends previous entropy-based approaches by applying spectral graph reduction. This allows us to quantify how structural entropy evolves as the network is gradually coarsened, capturing complexity across multiple scales. We apply our framework to real-world networks across biological, economic, social, technological, and transportation domains. The results uncover consistent entropy profiles across network families, revealing three structural regimes$\unicode{x2013}$stable, increasing, and hybrid$\unicode{x2013}$that align with domain-specific behaviors. Compared to single-scale models, multiscale entropy significantly improves our ability to determine network predictability. This shows that considering structural information across scales provides a more complete characterization of network complexity. Together, these results position multiscale entropy as a powerful and scalable tool for characterizing, classifying, and assessing the structure of complex networks. △ Less

Submitted 13 October, 2025; originally announced October 2025.

ACE: Adapting sampling for Counterfactual Explanations

Authors: Margarita A. Guerrero, Cristian R. Rojas

Abstract: Counterfactual Explanations (CFEs) interpret machine learning models by identifying the smallest change to input features needed to change the model's prediction to a desired output. For classification tasks, CFEs determine how close a given sample is to the decision boundary of a trained classifier. Existing methods are often sample-inefficient, requiring numerous evaluations of a black-box model… ▽ More Counterfactual Explanations (CFEs) interpret machine learning models by identifying the smallest change to input features needed to change the model's prediction to a desired output. For classification tasks, CFEs determine how close a given sample is to the decision boundary of a trained classifier. Existing methods are often sample-inefficient, requiring numerous evaluations of a black-box model -- an approach that is both costly and impractical when access to the model is limited. We propose Adaptive sampling for Counterfactual Explanations (ACE), a sample-efficient algorithm combining Bayesian estimation and stochastic optimization to approximate the decision boundary with fewer queries. By prioritizing informative points, ACE minimizes evaluations while generating accurate and feasible CFEs. Extensive empirical results show that ACE achieves superior evaluation efficiency compared to state-of-the-art methods, while maintaining effectiveness in identifying minimal and actionable changes. △ Less

Submitted 30 September, 2025; originally announced September 2025.

Comments: 15 pages

Mass conservation analysis of extrusion-based 3D printing simulations based on the level-set method

Authors: Carlos J. G. Rojas, Md. Tusher Mollah, C. A. Gómez-Pérez, Leyla Özkan

Abstract: Accurate numerical simulation of material extrusion additive manufacturing requires reliable tracking of evolving material interfaces while preserving mass conservation. Inaccurate mass conservation can lead to significant discrepancies between simulated and deposited strand geometries, undermining the predictive capability of the model. In this work, we investigate the mass conservation performan… ▽ More Accurate numerical simulation of material extrusion additive manufacturing requires reliable tracking of evolving material interfaces while preserving mass conservation. Inaccurate mass conservation can lead to significant discrepancies between simulated and deposited strand geometries, undermining the predictive capability of the model. In this work, we investigate the mass conservation performance of the conservative level-set (CLS) method in extrusion-based 3D printing simulations. A systematic parametric study is conducted to quantify the influence of the interface thickness and reinitialization parameters on mass conservation, using the steady-state cross-sectional area of deposited strands as a quantitative metric. Simulated cross-sections are compared against reference values obtained from analytical mass balance relations. The results show that reducing both the interface thickness and the reinitialization parameter improves mass conservation accuracy, although diminishing returns and increased computational cost are observed beyond certain thresholds. In addition, appropriate tuning of the interface thickness can relax mesh refinement requirements while maintaining acceptable accuracy. The proposed parameter selection strategy is validated across a range of printing conditions, materials, and nozzle geometries, including multilayer deposition of viscoplastic fluids. The simulations show reasonable agreement with experimentally validated data from the literature, confirming that careful CLS parameter tuning enables accurate and computationally efficient prediction of strand geometry in extrusion-based 3D printing. △ Less

Submitted 28 April, 2026; v1 submitted 28 August, 2025; originally announced August 2025.

Private GPTs for LLM-driven testing in software development and machine learning

Authors: Jakub Jagielski, Consuelo Rojas, Markus Abel

Abstract: In this contribution, we examine the capability of private GPTs to automatically generate executable test code based on requirements. More specifically, we use acceptance criteria as input, formulated as part of epics, or stories, which are typically used in modern development processes. This gives product owners, or business intelligence, respectively, a way to directly produce testable criteria… ▽ More In this contribution, we examine the capability of private GPTs to automatically generate executable test code based on requirements. More specifically, we use acceptance criteria as input, formulated as part of epics, or stories, which are typically used in modern development processes. This gives product owners, or business intelligence, respectively, a way to directly produce testable criteria through the use of LLMs. We explore the quality of the so-produced tests in two ways: i) directly by letting the LLM generate code from requirements, ii) through an intermediate step using Gherkin syntax. As a result, it turns out that the two-step procedure yields better results -where we define better in terms of human readability and best coding practices, i.e. lines of code and use of additional libraries typically used in testing. Concretely, we evaluate prompt effectiveness across two scenarios: a simple "Hello World" program and a digit classification model, showing that structured prompts lead to higher-quality test outputs. △ Less

Submitted 31 July, 2025; v1 submitted 6 June, 2025; originally announced June 2025.

Comments: 5 pages, 10 figures

ACM Class: I.2.1

Continuity and Isolation Lead to Doubts or Dilemmas in Large Language Models

Authors: Hector Pasten, Felipe Urrutia, Hector Jimenez, Cristian B. Calderon, Cristóbal Rojas, Alexander Kozachinskiy

Abstract: Understanding how Transformers work and how they process information is key to the theoretical and empirical advancement of these machines. In this work, we demonstrate the existence of two phenomena in Transformers, namely isolation and continuity. Both of these phenomena hinder Transformers to learn even simple pattern sequences. Isolation expresses that any learnable sequence must be isolated f… ▽ More Understanding how Transformers work and how they process information is key to the theoretical and empirical advancement of these machines. In this work, we demonstrate the existence of two phenomena in Transformers, namely isolation and continuity. Both of these phenomena hinder Transformers to learn even simple pattern sequences. Isolation expresses that any learnable sequence must be isolated from another learnable sequence, and hence some sequences cannot be learned by a single Transformer at the same time. Continuity entails that an attractor basin forms around a learned sequence, such that any sequence falling in that basin will collapse towards the learned sequence. Here, we mathematically prove these phenomena emerge in all Transformers that use compact positional encoding, and design rigorous experiments, demonstrating that the theoretical limitations we shed light on occur on the practical scale. △ Less

Submitted 15 May, 2025; originally announced May 2025.

Safety and optimality in learning-based control at low computational cost

Authors: Dominik Baumann, Krzysztof Kowalczyk, Cristian R. Rojas, Koen Tiels, Pawel Wachel

Abstract: Applying machine learning methods to physical systems that are supposed to act in the real world requires providing safety guarantees. However, methods that include such guarantees often come at a high computational cost, making them inapplicable to large datasets and embedded devices with low computational power. In this paper, we propose CoLSafe, a computationally lightweight safe learning algor… ▽ More Applying machine learning methods to physical systems that are supposed to act in the real world requires providing safety guarantees. However, methods that include such guarantees often come at a high computational cost, making them inapplicable to large datasets and embedded devices with low computational power. In this paper, we propose CoLSafe, a computationally lightweight safe learning algorithm whose computational complexity grows sublinearly with the number of data points. We derive both safety and optimality guarantees and showcase the effectiveness of our algorithm on a seven-degrees-of-freedom robot arm. △ Less

Submitted 12 May, 2025; originally announced May 2025.

Comments: Accepted final version to appear in the IEEE Transactions on Automatic Control

Foundation models for electronic health records: representation dynamics and transferability

Authors: Michael C. Burkhart, Bashar Ramadan, Zewei Liao, Kaveri Chhikara, Juan C. Rojas, William F. Parker, Brett K. Beaulieu-Jones

Abstract: Foundation models (FMs) trained on electronic health records (EHRs) have shown strong performance on a range of clinical prediction tasks. However, adapting these models to local health systems remains challenging due to limited data availability and resource constraints. In this study, we investigated what these models learn and evaluated the transferability of an FM trained on MIMIC-IV to an ins… ▽ More Foundation models (FMs) trained on electronic health records (EHRs) have shown strong performance on a range of clinical prediction tasks. However, adapting these models to local health systems remains challenging due to limited data availability and resource constraints. In this study, we investigated what these models learn and evaluated the transferability of an FM trained on MIMIC-IV to an institutional EHR dataset at the University of Chicago Medical Center. We assessed their ability to identify outlier patients and examined representation-space patient trajectories in relation to future clinical outcomes. We also evaluated the performance of supervised fine-tuned classifiers on both source and target datasets. Our findings offer insights into the adaptability of FMs across different healthcare systems, highlight considerations for their effective implementation, and provide an empirical analysis of the underlying factors that contribute to their predictive performance. △ Less

Submitted 14 April, 2025; originally announced April 2025.

On Word-of-Mouth and Private-Prior Sequential Social Learning

Authors: Andrea Da Col, Cristian R. Rojas, Vikram Krishnamurthy

Abstract: Social learning constitutes a fundamental framework for studying interactions among rational agents who observe each other's actions but lack direct access to individual beliefs. This paper investigates a specific social learning paradigm known as Word-of-Mouth (WoM), where a series of agents seeks to estimate the state of a dynamical system. The first agent receives noisy measurements of the stat… ▽ More Social learning constitutes a fundamental framework for studying interactions among rational agents who observe each other's actions but lack direct access to individual beliefs. This paper investigates a specific social learning paradigm known as Word-of-Mouth (WoM), where a series of agents seeks to estimate the state of a dynamical system. The first agent receives noisy measurements of the state, while each subsequent agent relies solely on a degraded version of her predecessor's estimate. A defining feature of WoM is that the final agent's belief is publicly broadcast and subsequently adopted by all agents, in place of their own. We analyze this setting theoretically and through numerical simulations, noting that some agents benefit from using the belief of the last agent, while others experience performance deterioration. △ Less

Submitted 2 September, 2025; v1 submitted 3 April, 2025; originally announced April 2025.

Comments: Accepted for publication at the 64th Conference on Decision and Control (CDC)

Strassen Attention, Split VC Dimension and Compositionality in Transformers

Authors: Alexander Kozachinskiy, Felipe Urrutia, Hector Jimenez, Tomasz Steifer, Germán Pizarro, Matías Fuentes, Francisco Meza, Cristian B. Calderon, Cristóbal Rojas

Abstract: We propose the first method to show theoretical limitations for one-layer softmax transformers with arbitrarily many precision bits (even infinite). We establish those limitations for three tasks that require advanced reasoning. The first task, Match 3 (Sanford et al., 2023), requires looking at all possible token triplets in an input sequence. The second and third tasks address compositionality-b… ▽ More We propose the first method to show theoretical limitations for one-layer softmax transformers with arbitrarily many precision bits (even infinite). We establish those limitations for three tasks that require advanced reasoning. The first task, Match 3 (Sanford et al., 2023), requires looking at all possible token triplets in an input sequence. The second and third tasks address compositionality-based reasoning: function composition (Peng et al., 2024) and binary relations composition, respectively. We formally prove the inability of one-layer softmax Transformers to solve any of these tasks. To overcome these limitations, we introduce Strassen attention and prove that, equipped with this mechanism, a one-layer transformer can in principle solve all these tasks. Importantly, we show that it enjoys sub-cubic running-time complexity, making it more scalable than similar previously proposed mechanisms, such as higher-order attention (Sanford et al., 2023). To complement our theoretical findings, we experimentally studied Strassen attention and compared it against standard (Vaswani et al, 2017), higher-order attention (Sanford et al., 2023), and triangular attention (Bergen et al. 2021). Our results help to disentangle all these attention mechanisms, highlighting their strengths and limitations. In particular, Strassen attention outperforms standard attention significantly on all the tasks. Altogether, understanding the theoretical limitations can guide research towards scalable attention mechanisms that improve the reasoning abilities of Transformers. △ Less

Submitted 25 September, 2025; v1 submitted 31 January, 2025; originally announced January 2025.

Comments: Accepted at NeurIPS 2025

Slow Convergence of Interacting Kalman Filters in Word-of-Mouth Social Learning

Authors: Vikram Krishnamurthy, Cristian Rojas

Abstract: We consider word-of-mouth social learning involving $m$ Kalman filter agents that operate sequentially. The first Kalman filter receives the raw observations, while each subsequent Kalman filter receives a noisy measurement of the conditional mean of the previous Kalman filter. The prior is updated by the $m$-th Kalman filter. When $m=2$, and the observations are noisy measurements of a Gaussian r… ▽ More We consider word-of-mouth social learning involving $m$ Kalman filter agents that operate sequentially. The first Kalman filter receives the raw observations, while each subsequent Kalman filter receives a noisy measurement of the conditional mean of the previous Kalman filter. The prior is updated by the $m$-th Kalman filter. When $m=2$, and the observations are noisy measurements of a Gaussian random variable, the covariance goes to zero as $k^{-1/3}$ for $k$ observations, instead of $O(k^{-1})$ in the standard Kalman filter. In this paper we prove that for $m$ agents, the covariance decreases to zero as $k^{-(2^m-1)}$, i.e, the learning slows down exponentially with the number of agents. We also show that by artificially weighing the prior at each time, the learning rate can be made optimal as $k^{-1}$. The implication is that in word-of-mouth social learning, artificially re-weighing the prior can yield the optimal learning rate. △ Less

Submitted 10 October, 2024; originally announced October 2024.

Augmented CARDS: A machine learning approach to identifying triggers of climate change misinformation on Twitter

Authors: Cristian Rojas, Frank Algra-Maschio, Mark Andrejevic, Travis Coan, John Cook, Yuan-Fang Li

Abstract: Misinformation about climate change poses a significant threat to societal well-being, prompting the urgent need for effective mitigation strategies. However, the rapid proliferation of online misinformation on social media platforms outpaces the ability of fact-checkers to debunk false claims. Automated detection of climate change misinformation offers a promising solution. In this study, we addr… ▽ More Misinformation about climate change poses a significant threat to societal well-being, prompting the urgent need for effective mitigation strategies. However, the rapid proliferation of online misinformation on social media platforms outpaces the ability of fact-checkers to debunk false claims. Automated detection of climate change misinformation offers a promising solution. In this study, we address this gap by developing a two-step hierarchical model, the Augmented CARDS model, specifically designed for detecting contrarian climate claims on Twitter. Furthermore, we apply the Augmented CARDS model to five million climate-themed tweets over a six-month period in 2022. We find that over half of contrarian climate claims on Twitter involve attacks on climate actors or conspiracy theories. Spikes in climate contrarianism coincide with one of four stimuli: political events, natural events, contrarian influencers, or convinced influencers. Implications for automated responses to climate misinformation are discussed. △ Less

Submitted 24 April, 2024; originally announced April 2024.

Kernel-based learning with guarantees for multi-agent applications

Authors: Krzysztof Kowalczyk, Paweł Wachel, Cristian R. Rojas

Abstract: This paper addresses a kernel-based learning problem for a network of agents locally observing a latent multidimensional, nonlinear phenomenon in a noisy environment. We propose a learning algorithm that requires only mild a priori knowledge about the phenomenon under investigation and delivers a model with corresponding non-asymptotic high probability error bounds. Both non-asymptotic analysis of… ▽ More This paper addresses a kernel-based learning problem for a network of agents locally observing a latent multidimensional, nonlinear phenomenon in a noisy environment. We propose a learning algorithm that requires only mild a priori knowledge about the phenomenon under investigation and delivers a model with corresponding non-asymptotic high probability error bounds. Both non-asymptotic analysis of the method and numerical simulation results are presented and discussed in the paper. △ Less

Submitted 15 April, 2024; originally announced April 2024.

On dimensionality of feature vectors in MPNNs

Authors: César Bravo, Alexander Kozachinskiy, Cristóbal Rojas

Abstract: We revisit the classical result of Morris et al.~(AAAI'19) that message-passing graphs neural networks (MPNNs) are equal in their distinguishing power to the Weisfeiler--Leman (WL) isomorphism test. Morris et al.~show their simulation result with ReLU activation function and $O(n)$-dimensional feature vectors, where $n$ is the number of nodes of the graph. By introducing randomness into the arch… ▽ More We revisit the classical result of Morris et al.~(AAAI'19) that message-passing graphs neural networks (MPNNs) are equal in their distinguishing power to the Weisfeiler--Leman (WL) isomorphism test. Morris et al.~show their simulation result with ReLU activation function and $O(n)$-dimensional feature vectors, where $n$ is the number of nodes of the graph. By introducing randomness into the architecture, Aamand et al.~(NeurIPS'22) were able to improve this bound to $O(\log n)$-dimensional feature vectors, again for ReLU activation, although at the expense of guaranteeing perfect simulation only with high probability. Recently, Amir et al.~(NeurIPS'23) have shown that for any non-polynomial analytic activation function, it is enough to use just 1-dimensional feature vectors. In this paper, we give a simple proof of the result of Amit et al.~and provide an independent experimental validation of it. △ Less

Submitted 14 February, 2024; v1 submitted 6 February, 2024; originally announced February 2024.

Comments: 15 pages, 2 figures. Changes to the previous version: added reference to Amir et al.~(NeurIPS'23)

On the algorithmic descriptive complexity of attractors in topological dynamics

Authors: Cristobal Rojas, Mathieu Sablik

Abstract: We study the computational problem of rigorously describing the asymptotic behaviour of topological dynamical systems up to a finite but arbitrarily small pre-specified error. More precisely, we consider the limit set of a typical orbit, both as a spatial object (attractor set) and as a statistical distribution (physical measure), and prove upper bounds on the computational resources of computing… ▽ More We study the computational problem of rigorously describing the asymptotic behaviour of topological dynamical systems up to a finite but arbitrarily small pre-specified error. More precisely, we consider the limit set of a typical orbit, both as a spatial object (attractor set) and as a statistical distribution (physical measure), and prove upper bounds on the computational resources of computing descriptions of these objects with arbitrary accuracy. We also study how these bounds are affected by different dynamical constrains and provide several examples showing that our bounds are sharp in general. In particular, we exhibit a computable interval map having a unique transitive attractor with Cantor set structure supporting a unique physical measure such that both the attractor and the measure are non computable. △ Less

Submitted 14 June, 2024; v1 submitted 26 November, 2023; originally announced November 2023.

Comments: 25 pages, 3 figures

MSC Class: 37B02; 37B10; 68Q17

Unraveling the Control Engineer's Craft with Neural Networks

Authors: Braghadeesh Lakshminarayanan, Federico Dettù, Cristian R. Rojas, Simone Formentin

Abstract: Many industrial processes require suitable controllers to meet their performance requirements. More often, a sophisticated digital twin is available, which is a highly complex model that is a virtual representation of a given physical process, whose parameters may not be properly tuned to capture the variations in the physical process. In this paper, we present a sim2real, direct data-driven contr… ▽ More Many industrial processes require suitable controllers to meet their performance requirements. More often, a sophisticated digital twin is available, which is a highly complex model that is a virtual representation of a given physical process, whose parameters may not be properly tuned to capture the variations in the physical process. In this paper, we present a sim2real, direct data-driven controller tuning approach, where the digital twin is used to generate input-output data and suitable controllers for several perturbations in its parameters. State-of-the art neural-network architectures are then used to learn the controller tuning rule that maps input-output data onto the controller parameters, based on artificially generated data from perturbed versions of the digital twin. In this way, as far as we are aware, we tackle for the first time the problem of re-calibrating the controller by meta-learning the tuning rule directly from data, thus practically replacing the control engineer with a machine learning model. The benefits of this methodology are illustrated via numerical simulations for several choices of neural-network architectures. △ Less

Submitted 20 November, 2023; originally announced November 2023.

Comments: 6 pages

DRCFS: Doubly Robust Causal Feature Selection

Authors: Francesco Quinzan, Ashkan Soleymani, Patrick Jaillet, Cristian R. Rojas, Stefan Bauer

Abstract: Knowing the features of a complex system that are highly relevant to a particular target variable is of fundamental interest in many areas of science. Existing approaches are often limited to linear settings, sometimes lack guarantees, and in most cases, do not scale to the problem at hand, in particular to images. We propose DRCFS, a doubly robust feature selection method for identifying the caus… ▽ More Knowing the features of a complex system that are highly relevant to a particular target variable is of fundamental interest in many areas of science. Existing approaches are often limited to linear settings, sometimes lack guarantees, and in most cases, do not scale to the problem at hand, in particular to images. We propose DRCFS, a doubly robust feature selection method for identifying the causal features even in nonlinear and high dimensional settings. We provide theoretical guarantees, illustrate necessary conditions for our assumptions, and perform extensive experiments across a wide range of simulated and semi-synthetic datasets. DRCFS significantly outperforms existing state-of-the-art methods, selecting robust features even in challenging highly non-linear and high-dimensional problems. △ Less

Submitted 5 July, 2023; v1 submitted 12 June, 2023; originally announced June 2023.

PathFinder: A unified approach for handling paths in graph query languages

Authors: Benjamín Farías, Wim Martens, Carlos Rojas, Domagoj Vrgoč

Abstract: Path queries are a core feature of modern graph query languages such as Cypher, SQL/PGQ, and GQL. These languages provide a rich set of features for matching paths, such as restricting to certain path modes (shortest, simple, trail) and constraining the edge labels along the path by a regular expression. In this paper we present PathFinder, a unifying approach for dealing with path queries in all… ▽ More Path queries are a core feature of modern graph query languages such as Cypher, SQL/PGQ, and GQL. These languages provide a rich set of features for matching paths, such as restricting to certain path modes (shortest, simple, trail) and constraining the edge labels along the path by a regular expression. In this paper we present PathFinder, a unifying approach for dealing with path queries in all these query languages. PathFinder leverages a compact representation of the (potentially exponential number of) paths that can match a given query, extends it with pipelined execution, and supports all commonly used path modes. In the paper we describe the algorithmic backbone of PathFinder, provide a reference implementation, and test it over a large set of real-world queries and datasets. Our results show that PathFinder exhibits very stable behavior, even on large data and complex queries, and its performance is an order of magnitude better than that of many modern graph engines. △ Less

Submitted 14 July, 2026; v1 submitted 3 June, 2023; originally announced June 2023.

Decentralized diffusion-based learning under non-parametric limited prior knowledge

Authors: Paweł Wachel, Krzysztof Kowalczyk, Cristian R. Rojas

Abstract: We study the problem of diffusion-based network learning of a nonlinear phenomenon, $m$, from local agents' measurements collected in a noisy environment. For a decentralized network and information spreading merely between directly neighboring nodes, we propose a non-parametric learning algorithm, that avoids raw data exchange and requires only mild \textit{a priori} knowledge about $m$. Non-asym… ▽ More We study the problem of diffusion-based network learning of a nonlinear phenomenon, $m$, from local agents' measurements collected in a noisy environment. For a decentralized network and information spreading merely between directly neighboring nodes, we propose a non-parametric learning algorithm, that avoids raw data exchange and requires only mild \textit{a priori} knowledge about $m$. Non-asymptotic estimation error bounds are derived for the proposed method. Its potential applications are illustrated through simulation experiments. △ Less

Submitted 5 May, 2023; originally announced May 2023.

Diagnosing and Augmenting Feature Representations in Correctional Inverse Reinforcement Learning

Authors: Inês Lourenço, Andreea Bobu, Cristian R. Rojas, Bo Wahlberg

Abstract: Robots have been increasingly better at doing tasks for humans by learning from their feedback, but still often suffer from model misalignment due to missing or incorrectly learned features. When the features the robot needs to learn to perform its task are missing or do not generalize well to new settings, the robot will not be able to learn the task the human wants and, even worse, may learn a c… ▽ More Robots have been increasingly better at doing tasks for humans by learning from their feedback, but still often suffer from model misalignment due to missing or incorrectly learned features. When the features the robot needs to learn to perform its task are missing or do not generalize well to new settings, the robot will not be able to learn the task the human wants and, even worse, may learn a completely different and undesired behavior. Prior work shows how the robot can detect when its representation is missing some feature and can, thus, ask the human to be taught about the new feature; however, these works do not differentiate between features that are completely missing and those that exist but do not generalize to new environments. In the latter case, the robot would detect misalignment and simply learn a new feature, leading to an arbitrarily growing feature representation that can, in turn, lead to spurious correlations and incorrect learning down the line. In this work, we propose separating the two sources of misalignment: we propose a framework for determining whether a feature the robot needs is incorrectly learned and does not generalize to new environment setups vs. is entirely missing from the robot's representation. Once we detect the source of error, we show how the human can initiate the realignment process for the model: if the feature is missing, we follow prior work for learning new features; however, if the feature exists but does not generalize, we use data augmentation to expand its training and, thus, complete the correction. We demonstrate the proposed approach in experiments with a simulated 7DoF robot manipulator and physical human corrections. △ Less

Submitted 13 April, 2023; v1 submitted 11 April, 2023; originally announced April 2023.

Comments: 8 pages, 4 figures

Optimal Transport for Correctional Learning

Authors: Rebecka Winqvist, Inês Lourenco, Francesco Quinzan, Cristian R. Rojas, Bo Wahlberg

Abstract: The contribution of this paper is a generalized formulation of correctional learning using optimal transport, which is about how to optimally transport one mass distribution to another. Correctional learning is a framework developed to enhance the accuracy of parameter estimation processes by means of a teacher-student approach. In this framework, an expert agent, referred to as the teacher, modif… ▽ More The contribution of this paper is a generalized formulation of correctional learning using optimal transport, which is about how to optimally transport one mass distribution to another. Correctional learning is a framework developed to enhance the accuracy of parameter estimation processes by means of a teacher-student approach. In this framework, an expert agent, referred to as the teacher, modifies the data used by a learning agent, known as the student, to improve its estimation process. The objective of the teacher is to alter the data such that the student's estimation error is minimized, subject to a fixed intervention budget. Compared to existing formulations of correctional learning, our novel optimal transport approach provides several benefits. It allows for the estimation of more complex characteristics as well as the consideration of multiple intervention policies for the teacher. We evaluate our approach on two theoretical examples, and on a human-robot interaction application in which the teacher's role is to improve the robots performance in an inverse reinforcement learning setting. △ Less

Submitted 4 April, 2023; originally announced April 2023.

Three iterations of $(d-1)$-WL test distinguish non isometric clouds of $d$-dimensional points

Authors: Valentino Delle Rose, Alexander Kozachinskiy, Cristóbal Rojas, Mircea Petrache, Pablo Barceló

Abstract: The Weisfeiler--Lehman (WL) test is a fundamental iterative algorithm for checking isomorphism of graphs. It has also been observed that it underlies the design of several graph neural network architectures, whose capabilities and performance can be understood in terms of the expressive power of this test. Motivated by recent developments in machine learning applications to datasets involving thre… ▽ More The Weisfeiler--Lehman (WL) test is a fundamental iterative algorithm for checking isomorphism of graphs. It has also been observed that it underlies the design of several graph neural network architectures, whose capabilities and performance can be understood in terms of the expressive power of this test. Motivated by recent developments in machine learning applications to datasets involving three-dimensional objects, we study when the WL test is {\em complete} for clouds of euclidean points represented by complete distance graphs, i.e., when it can distinguish, up to isometry, any arbitrary such cloud. %arbitrary clouds of euclidean points represented by complete distance graphs. % How many dimensions of the Weisfeiler--Lehman test is enough to distinguish any two non-isometric point clouds in $d$-dimensional Euclidean space, assuming that these point clouds are given as complete graphs labeled by distances between the points? This question is important for understanding, which architectures of graph neural networks are capable of fully exploiting the spacial structure of a point cloud. Our main result states that the $(d-1)$-dimensional WL test is complete for point clouds in $d$-dimensional Euclidean space, for any $d\ge 2$, and that only three iterations of the test suffice. We also observe that the $d$-dimensional WL test only requires one iteration to achieve completeness. Our paper thus provides complete understanding of the 3-dimensional case: it was shown in previous works that 1-WL is not complete in $\mathbb{R}^3$, and we show that 2-WL is complete there. We also strengthen the lower bound for 1-WL by showing that it is unable to recognize planar point clouds in $\mathbb{R}^3$. Finally, we show that 2-WL is not complete in $\mathbb{R}^6$, leaving as an open question, whether it is complete in $\mathbb{R}^{d}$ for $d = 4,5$. △ Less

Submitted 12 June, 2025; v1 submitted 22 March, 2023; originally announced March 2023.

Comments: Changes to previous version: new results, inability of 1-WL to recognize planar point clouds in R^3, and incompleteness of 2-WL in R^6

MSC Class: 05C60; 68R12; 68R10 ACM Class: F.2.2; G.2.2

Find a witness or shatter: the landscape of computable PAC learning

Authors: Valentino Delle Rose, Alexander Kozachinskiy, Cristobal Rojas, Tomasz Steifer

Abstract: This paper contributes to the study of CPAC learnability -- a computable version of PAC learning -- by solving three open questions from recent papers. Firstly, we prove that every improperly CPAC learnable class is contained in a class which is properly CPAC learnable with polynomial sample complexity. This confirms a conjecture by Agarwal et al (COLT 2021). Secondly, we show that there exists a… ▽ More This paper contributes to the study of CPAC learnability -- a computable version of PAC learning -- by solving three open questions from recent papers. Firstly, we prove that every improperly CPAC learnable class is contained in a class which is properly CPAC learnable with polynomial sample complexity. This confirms a conjecture by Agarwal et al (COLT 2021). Secondly, we show that there exists a decidable class of hypothesis which is properly CPAC learnable, but only with uncomputably fast growing sample complexity. This solves a question from Sterkenburg (COLT 2022). Finally, we construct a decidable class of finite Littlestone dimension which is not improperly CPAC learnable, strengthening a recent result of Sterkenburg (2022) and answering a question posed by Hasrati and Ben-David (ALT 2023). Together with previous work, our results provide a complete landscape for the learnability problem in the CPAC setting. △ Less

Submitted 23 February, 2023; v1 submitted 5 February, 2023; originally announced February 2023.

Comments: 12 pages, 1 figure (corrected version)

No Agreement Without Loss: Learning and Social Choice in Peer Review

Authors: Pablo Barceló, Mauricio Duarte, Cristóbal Rojas, Tomasz Steifer

Abstract: In peer review systems, reviewers are often asked to evaluate various features of submissions, such as technical quality or novelty. A score is given to each of the predefined features and based on these the reviewer has to provide an overall quantitative recommendation. It may be assumed that each reviewer has her own mapping from the set of features to a recommendation, and that different review… ▽ More In peer review systems, reviewers are often asked to evaluate various features of submissions, such as technical quality or novelty. A score is given to each of the predefined features and based on these the reviewer has to provide an overall quantitative recommendation. It may be assumed that each reviewer has her own mapping from the set of features to a recommendation, and that different reviewers have different mappings in mind. This introduces an element of arbitrariness known as commensuration bias. In this paper we discuss a framework, introduced by Noothigattu, Shah and Procaccia, and then applied by the organizers of the AAAI 2022 conference. Noothigattu, Shah and Procaccia proposed to aggregate reviewer's mapping by minimizing certain loss functions, and studied axiomatic properties of this approach, in the sense of social choice theory. We challenge several of the results and assumptions used in their work and report a number of negative results. On the one hand, we study a trade-off between some of the axioms proposed and the ability of the method to properly capture agreements of the majority of reviewers. On the other hand, we show that dropping a certain unrealistic assumption has dramatic effects, including causing the method to be discontinuous. △ Less

Submitted 3 August, 2023; v1 submitted 3 November, 2022; originally announced November 2022.

Comments: accepted for ECAI 2023

MSC Class: 91B14

A Teacher-Student Markov Decision Process-based Framework for Online Correctional Learning

Authors: Inês Lourenço, Rebecka Winqvist, Cristian R. Rojas, Bo Wahlberg

Abstract: A classical learning setting typically concerns an agent/student who collects data, or observations, from a system in order to estimate a certain property of interest. Correctional learning is a type of cooperative teacher-student framework where a teacher, who has partial knowledge about the system, has the ability to observe and alter (correct) the observations received by the student in order t… ▽ More A classical learning setting typically concerns an agent/student who collects data, or observations, from a system in order to estimate a certain property of interest. Correctional learning is a type of cooperative teacher-student framework where a teacher, who has partial knowledge about the system, has the ability to observe and alter (correct) the observations received by the student in order to improve the accuracy of its estimate. In this paper, we show how the variance of the estimate of the student can be reduced with the help of the teacher. We formulate the corresponding online problem - where the teacher has to decide, at each time instant, whether or not to change the observations due to a limited budget - as a Markov decision process, from which the optimal policy is derived using dynamic programming. We validate the framework in numerical experiments, and compare the optimal online policy with the one from the batch setting. △ Less

Submitted 29 March, 2022; v1 submitted 15 November, 2021; originally announced November 2021.

Comments: 8 pages, 7 figures

MillenniumDB: A Persistent, Open-Source, Graph Database

Authors: Domagoj Vrgoc, Carlos Rojas, Renzo Angles, Marcelo Arenas, Diego Arroyuelo, Carlos Buil Aranda, Aidan Hogan, Gonzalo Navarro, Cristian Riveros, Juan Romero

Abstract: In this systems paper, we present MillenniumDB: a novel graph database engine that is modular, persistent, and open source. MillenniumDB is based on a graph data model, which we call domain graphs, that provides a simple abstraction upon which a variety of popular graph models can be supported. The engine itself is founded on a combination of tried and tested techniques from relational data manage… ▽ More In this systems paper, we present MillenniumDB: a novel graph database engine that is modular, persistent, and open source. MillenniumDB is based on a graph data model, which we call domain graphs, that provides a simple abstraction upon which a variety of popular graph models can be supported. The engine itself is founded on a combination of tried and tested techniques from relational data management, state-of-the-art algorithms for worst-case-optimal joins, as well as graph-specific algorithms for evaluating path queries. In this paper, we present the main design principles underlying MillenniumDB, describing the abstract graph model and query semantics supported, the concrete data model and query syntax implemented, as well as the storage, indexing, query planning and query evaluation techniques used. We evaluate MillenniumDB over real-world data and queries from the Wikidata knowledge graph, where we find that it outperforms other popular persistent graph database engines (including both enterprise and open source alternatives) that support similar query features. △ Less

Submitted 2 November, 2021; originally announced November 2021.

Asymptotically Optimal Bandits under Weighted Information

Authors: Matias I. Müller, Cristian R. Rojas

Abstract: We study the problem of regret minimization in a multi-armed bandit setup where the agent is allowed to play multiple arms at each round by spreading the resources usually allocated to only one arm. At each iteration the agent selects a normalized power profile and receives a Gaussian vector as outcome, where the unknown variance of each sample is inversely proportional to the power allocated to t… ▽ More We study the problem of regret minimization in a multi-armed bandit setup where the agent is allowed to play multiple arms at each round by spreading the resources usually allocated to only one arm. At each iteration the agent selects a normalized power profile and receives a Gaussian vector as outcome, where the unknown variance of each sample is inversely proportional to the power allocated to that arm. The reward corresponds to a linear combination of the power profile and the outcomes, resembling a linear bandit. By spreading the power, the agent can choose to collect information much faster than in a traditional multi-armed bandit at the price of reducing the accuracy of the samples. This setup is fundamentally different from that of a linear bandit -- the regret is known to scale as $Θ(\sqrt{T})$ for linear bandits, while in this setup the agent receives a much more detailed feedback, for which we derive a tight $\log(T)$ problem-dependent lower-bound. We propose a Thompson-Sampling-based strategy, called Weighted Thompson Sampling (\WTS), that designs the power profile as its posterior belief of each arm being the best arm, and show that its upper bound matches the derived logarithmic lower bound. Finally, we apply this strategy to a problem of control and system identification, where the goal is to estimate the maximum gain (also called $\mathcal{H}_\infty$-norm) of a linear dynamical system based on batches of input-output samples. △ Less

Submitted 28 May, 2021; originally announced May 2021.

Comments: 9 content pages, 3 references pages, 22 appendix pages, 4 figures, 34 total pages

A Finite-Sample Deviation Bound for Stable Autoregressive Processes

Authors: Rodrigo A. González, Cristian R. Rojas

Abstract: In this paper, we study non-asymptotic deviation bounds of the least squares estimator in Gaussian AR($n$) processes. By relying on martingale concentration inequalities and a tail-bound for $χ^2$ distributed variables, we provide a concentration bound for the sample covariance matrix of the process output. With this, we present a problem-dependent finite-time bound on the deviation probability of… ▽ More In this paper, we study non-asymptotic deviation bounds of the least squares estimator in Gaussian AR($n$) processes. By relying on martingale concentration inequalities and a tail-bound for $χ^2$ distributed variables, we provide a concentration bound for the sample covariance matrix of the process output. With this, we present a problem-dependent finite-time bound on the deviation probability of any fixed linear combination of the estimated parameters of the AR$(n)$ process. We discuss extensions and limitations of our approach. △ Less

Submitted 25 May, 2020; v1 submitted 17 December, 2019; originally announced December 2019.

Comments: 15 pages

Bayesian Model Selection for Change Point Detection and Clustering

Authors: Othmane Mazhar, Cristian R. Rojas, Carlo Fischione, Mohammad R. Hesamzadeh

Abstract: We address the new problem of estimating a piece-wise constant signal with the purpose of detecting its change points and the levels of clusters. Our approach is to model it as a nonparametric penalized least square model selection on a family of models indexed over the collection of partitions of the design points and propose a computationally efficient algorithm to approximately solve it. Statis… ▽ More We address the new problem of estimating a piece-wise constant signal with the purpose of detecting its change points and the levels of clusters. Our approach is to model it as a nonparametric penalized least square model selection on a family of models indexed over the collection of partitions of the design points and propose a computationally efficient algorithm to approximately solve it. Statistically, minimizing such a penalized criterion yields an approximation to the maximum a posteriori probability (MAP) estimator. The criterion is then analyzed and an oracle inequality is derived using a Gaussian concentration inequality. The oracle inequality is used to derive on one hand conditions for consistency and on the other hand an adaptive upper bound on the expected square risk of the estimator, which statistically motivates our approximation. Finally, we apply our algorithm to simulated data to experimentally validate the statistical guarantees and illustrate its behavior. △ Less

Submitted 3 December, 2019; originally announced December 2019.

Comments: 37 page, 4 figures, Proceedings of the 35th International Conference on Machine Learning (ICML), PMLR 80:3433-3442, 2018

How to lose at Monte Carlo: a simple dynamical system whose typical statistical behavior is non computable

Authors: Cristobal Rojas, Michael Yampolsky

Abstract: We consider the simplest non-linear discrete dynamical systems, given by the logistic maps $f_{a}(x)=ax(1-x)$ of the interval $[0,1]$. We show that there exist real parameters $a\in (0,4)$ for which almost every orbit of $f_a$ has the same statistical distribution in $[0,1]$, but this limiting distribution is not Turing computable. In particular, the Monte Carlo method cannot be applied to study t… ▽ More We consider the simplest non-linear discrete dynamical systems, given by the logistic maps $f_{a}(x)=ax(1-x)$ of the interval $[0,1]$. We show that there exist real parameters $a\in (0,4)$ for which almost every orbit of $f_a$ has the same statistical distribution in $[0,1]$, but this limiting distribution is not Turing computable. In particular, the Monte Carlo method cannot be applied to study these dynamical systems. △ Less

Submitted 31 October, 2019; v1 submitted 21 October, 2019; originally announced October 2019.

Comments: 13 pages, 1 figure

MSC Class: 68Q17; 37E05

On the computability properties of topological entropy: a general approach

Authors: Silvere Gangloff, Alonso Herrera, Cristobal Rojas, Mathieu Sablik

Abstract: The dynamics of symbolic systems, such as multidimensional subshifts of finite type or cellular automata, are known to be closely related to computability theory. In particular, the appropriate tools to describe and classify topological entropy for this kind of systems turned out to be of computational nature. Part of the great importance of these symbolic systems relies on the role they have play… ▽ More The dynamics of symbolic systems, such as multidimensional subshifts of finite type or cellular automata, are known to be closely related to computability theory. In particular, the appropriate tools to describe and classify topological entropy for this kind of systems turned out to be of computational nature. Part of the great importance of these symbolic systems relies on the role they have played in understanding more general systems over non-symbolic spaces. The aim of this article is to investigate topological entropy from a computability point of view in this more general, not necessarily symbolic setting. In analogy to effective subshifts, we consider computable maps over effective compact sets in general metric spaces, and study the computability properties of their topological entropies. We show that even in this general setting, the entropy is always a $Σ_2$-computable number. We then study how various dynamical and analytical constrains affect this upper bound, and prove that it can be lowered in different ways depending on the constraint considered. In particular, we obtain that all $Σ_2$-computable numbers can already be realized within the class of surjective computable maps over $\{0,1\}^{\mathbb{N}}$, but that this bound decreases to $Π_{1}$(or upper)-computable numbers when restricted to expansive maps. On the other hand, if we change the geometry of the ambient space from the symbolic $\{0,1\}^{\mathbb{N}}$ to the unit interval $[0,1]$, then we find a quite different situation -- we show that the possible entropies of computable systems over $[0,1]$ are exactly the $Σ_{1}$(or lower)-computable numbers and that this characterization switches down to precisely the computable numbers when we restrict the class of system to the quadratic family. △ Less

Submitted 4 June, 2019; originally announced June 2019.

Comments: 27 pages, 5 figures

MSC Class: 37B40; 03D78; 03D28

Space-bounded Church-Turing thesis and computational tractability of closed systems

Authors: Mark Braverman, Cristobal Rojas, Jonathan Schneider

Abstract: We report a new limitation on the ability of physical systems to perform computation -- one that is based on generalizing the notion of memory, or storage space, available to the system to perform the computation. Roughly, we define memory as the maximal amount of information that the evolving system can carry from one instant to the next. We show that memory is a limiting factor in computation ev… ▽ More We report a new limitation on the ability of physical systems to perform computation -- one that is based on generalizing the notion of memory, or storage space, available to the system to perform the computation. Roughly, we define memory as the maximal amount of information that the evolving system can carry from one instant to the next. We show that memory is a limiting factor in computation even in lieu of any time limitations on the evolving system - such as when considering its equilibrium regime. We call this limitation the Space-Bounded Church Turing Thesis (SBCT). The SBCT is supported by a Simulation Assertion (SA), which states that predicting the long-term behavior of bounded-memory systems is computationally tractable. In particular, one corollary of SA is an explicit bound on the computational hardness of the long-term behavior of a discrete-time finite-dimensional dynamical system that is affected by noise. We prove such a bound explicitly. △ Less

Submitted 2 May, 2019; originally announced May 2019.

Comments: 6 pages

MSC Class: 68Q05; 37C40

Journal ref: Physical Review Letters. 115, 098701. August 2015

Real quadratic Julia sets can have arbitrarily high complexity

Authors: Cristobal Rojas, Michael Yampolsky

Abstract: We show that there exist real parameters $c$ for which the Julia set $J_c$ of the quadratic map $z^2+c$ has arbitrarily high computational complexity. More precisely, we show that for any given complexity threshold $T(n)$, there exist a real parameter $c$ such that the computational complexity of computing $J_c$ with $n$ bits of precision is higher than $T(n)$. This is the first known class of rea… ▽ More We show that there exist real parameters $c$ for which the Julia set $J_c$ of the quadratic map $z^2+c$ has arbitrarily high computational complexity. More precisely, we show that for any given complexity threshold $T(n)$, there exist a real parameter $c$ such that the computational complexity of computing $J_c$ with $n$ bits of precision is higher than $T(n)$. This is the first known class of real parameters with a non poly-time computable Julia set. △ Less

Submitted 18 March, 2020; v1 submitted 11 April, 2019; originally announced April 2019.

Comments: 9 pages, 1 figure. To be published in the journal Found. Comp. Math. (FoCM). arXiv admin note: text overlap with arXiv:1703.04660

MSC Class: 68Q17 and 37E05

Dihedral Rigidity and Deformation

Authors: Nina Amenta, Carlos Rojas

Abstract: We consider defining the embedding of a triangle mesh into $R^3$, up to translation, rotation, and scale, by its vector of dihedral angles. Theoretically, we show that locally, almost everywhere, the map from realizable vectors of dihedrals to mesh embeddings is one-to-one. We experiment with a heuristic method for mapping straight-line interpolations in dihedral space to interpolations between me… ▽ More We consider defining the embedding of a triangle mesh into $R^3$, up to translation, rotation, and scale, by its vector of dihedral angles. Theoretically, we show that locally, almost everywhere, the map from realizable vectors of dihedrals to mesh embeddings is one-to-one. We experiment with a heuristic method for mapping straight-line interpolations in dihedral space to interpolations between mesh embeddings and produce smooth and intuitively appealing morphs between three-dimensional shapes. △ Less

Submitted 2 October, 2018; originally announced October 2018.

Comments: Appeared in the Canadian Computational Geometry Conference, CCCG '18

Computing geometric Lorenz attractors with arbitrary precision

Authors: Daniel Graca, Cristobal Rojas, Ning Zhong

Abstract: The Lorenz attractor was introduced in 1963 by E. N. Lorenz as one of the first examples of \emph{strange attractors}. However Lorenz' research was mainly based on (non-rigourous) numerical simulations and, until recently, the proof of the existence of the Lorenz attractor remained elusive. To address that problem some authors introduced geometric Lorenz models and proved that geometric Lorenz mod… ▽ More The Lorenz attractor was introduced in 1963 by E. N. Lorenz as one of the first examples of \emph{strange attractors}. However Lorenz' research was mainly based on (non-rigourous) numerical simulations and, until recently, the proof of the existence of the Lorenz attractor remained elusive. To address that problem some authors introduced geometric Lorenz models and proved that geometric Lorenz models have a strange attractor. In 2002 it was shown that the original Lorenz model behaves like a geometric Lorenz model and thus has a strange attractor. In this paper we show that geometric Lorenz attractors are computable, as well as their physical measures. △ Less

Submitted 13 February, 2017; originally announced February 2017.

Comments: 19 pages, 4 figures

A Class of Nonconvex Penalties Preserving Overall Convexity in Optimization-Based Mean Filtering

Authors: Mohammadreza Malek-Mohammadi, Cristian R. Rojas, Bo Wahlberg

Abstract: $\ell_1$ mean filtering is a conventional, optimization-based method to estimate the positions of jumps in a piecewise constant signal perturbed by additive noise. In this method, the $\ell_1… ▽ More $\ell_1$ mean filtering is a conventional, optimization-based method to estimate the positions of jumps in a piecewise constant signal perturbed by additive noise. In this method, the $\ell_1$ norm penalizes sparsity of the first-order derivative of the signal. Theoretical results, however, show that in some situations, which can occur frequently in practice, even when the jump amplitudes tend to $\infty$, the conventional method identifies false change points. This issue is referred to as stair-casing problem and restricts practical importance of $\ell_1$ mean filtering. In this paper, sparsity is penalized more tightly than the $\ell_1$ norm by exploiting a certain class of nonconvex functions, while the strict convexity of the consequent optimization problem is preserved. This results in a higher performance in detecting change points. To theoretically justify the performance improvements over $\ell_1$ mean filtering, deterministic and stochastic sufficient conditions for exact change point recovery are derived. In particular, theoretical results show that in the stair-casing problem, our approach might be able to exclude the false change points, while $\ell_1$ mean filtering may fail. A number of numerical simulations assist to show superiority of our method over $\ell_1$ mean filtering and another state-of-the-art algorithm that promotes sparsity tighter than the $\ell_1$ norm. Specifically, it is shown that our approach can consistently detect change points when the jump amplitudes become sufficiently large, while the two other competitors cannot. △ Less

Submitted 22 April, 2016; originally announced April 2016.

Comments: Submitted to IEEE Transactions on Signal Processing

Tight space-noise tradeoffs in computing the ergodic measure

Authors: Mark Braverman, Cristobal Rojas, Jon Schneider

Abstract: In this note we obtain tight bounds on the space-complexity of computing the ergodic measure of a low-dimensional discrete-time dynamical system affected by Gaussian noise. If the scale of the noise is $\varepsilon$, and the function describing the evolution of the system is not by itself a source of computational complexity, then the density function of the ergodic measure can be approximated wit… ▽ More In this note we obtain tight bounds on the space-complexity of computing the ergodic measure of a low-dimensional discrete-time dynamical system affected by Gaussian noise. If the scale of the noise is $\varepsilon$, and the function describing the evolution of the system is not by itself a source of computational complexity, then the density function of the ergodic measure can be approximated within precision $δ$ in space polynomial in $\log 1/\varepsilon+\log\log 1/δ$. We also show that this bound is tight up to polynomial factors. In the course of showing the above, we prove a result of independent interest in space-bounded computation: that it is possible to exponentiate an $n$ by $n$ matrix to an exponentially large power in space polylogarithmic in $n$. △ Less

Submitted 21 August, 2015; originally announced August 2015.

Comments: 25 pages

MSC Class: 68Q05; 37C40 ACM Class: F.1.1

Estimator Selection: End-Performance Metric Aspects

Authors: Dimitrios Katselis, Cristian R. Rojas, Carolyn L. Beck

Abstract: Recently, a framework for application-oriented optimal experiment design has been introduced. In this context, the distance of the estimated system from the true one is measured in terms of a particular end-performance metric. This treatment leads to superior unknown system estimates to classical experiment designs based on usual pointwise functional distances of the estimated system from the true… ▽ More Recently, a framework for application-oriented optimal experiment design has been introduced. In this context, the distance of the estimated system from the true one is measured in terms of a particular end-performance metric. This treatment leads to superior unknown system estimates to classical experiment designs based on usual pointwise functional distances of the estimated system from the true one. The separation of the system estimator from the experiment design is done within this new framework by choosing and fixing the estimation method to either a maximum likelihood (ML) approach or a Bayesian estimator such as the minimum mean square error (MMSE). Since the MMSE estimator delivers a system estimate with lower mean square error (MSE) than the ML estimator for finite-length experiments, it is usually considered the best choice in practice in signal processing and control applications. Within the application-oriented framework a related meaningful question is: Are there end-performance metrics for which the ML estimator outperforms the MMSE when the experiment is finite-length? In this paper, we affirmatively answer this question based on a simple linear Gaussian regression example. △ Less

Submitted 26 July, 2015; originally announced July 2015.

Comments: arXiv admin note: substantial text overlap with arXiv:1303.4289

Evaluation of Spectral Learning for the Identification of Hidden Markov Models

Authors: Robert Mattila, Cristian R. Rojas, Bo Wahlberg

Abstract: Hidden Markov models have successfully been applied as models of discrete time series in many fields. Often, when applied in practice, the parameters of these models have to be estimated. The currently predominating identification methods, such as maximum-likelihood estimation and especially expectation-maximization, are iterative and prone to have problems with local minima. A non-iterative metho… ▽ More Hidden Markov models have successfully been applied as models of discrete time series in many fields. Often, when applied in practice, the parameters of these models have to be estimated. The currently predominating identification methods, such as maximum-likelihood estimation and especially expectation-maximization, are iterative and prone to have problems with local minima. A non-iterative method employing a spectral subspace-like approach has recently been proposed in the machine learning literature. This paper evaluates the performance of this algorithm, and compares it to the performance of the expectation-maximization algorithm, on a number of numerical examples. We find that the performance is mixed; it successfully identifies some systems with relatively few available observations, but fails completely for some systems even when a large amount of observations is available. An open question is how this discrepancy can be explained. We provide some indications that it could be related to how well-conditioned some system parameters are. △ Less

Submitted 22 July, 2015; originally announced July 2015.

Comments: This paper is accepted and will be published in The Proceedings of the 17th IFAC Symposium on System Identification (SYSID 2015), Beijing, China, 2015

Successive Concave Sparsity Approximation for Compressed Sensing

Authors: Mohammadreza Malek-Mohammadi, Ali Koochakzadeh, Massoud Babaie-Zadeh, Magnus Jansson, Cristian R. Rojas

Abstract: In this paper, based on a successively accuracy-increasing approximation of the $\ell_0$ norm, we propose a new algorithm for recovery of sparse vectors from underdetermined measurements. The approximations are realized with a certain class of concave functions that aggressively induce sparsity and their closeness to the $\ell_0$ norm can be controlled. We prove that the series of the approximatio… ▽ More In this paper, based on a successively accuracy-increasing approximation of the $\ell_0$ norm, we propose a new algorithm for recovery of sparse vectors from underdetermined measurements. The approximations are realized with a certain class of concave functions that aggressively induce sparsity and their closeness to the $\ell_0$ norm can be controlled. We prove that the series of the approximations asymptotically coincides with the $\ell_1$ and $\ell_0$ norms when the approximation accuracy changes from the worst fitting to the best fitting. When measurements are noise-free, an optimization scheme is proposed which leads to a number of weighted $\ell_1$ minimization programs, whereas, in the presence of noise, we propose two iterative thresholding methods that are computationally appealing. A convergence guarantee for the iterative thresholding method is provided, and, for a particular function in the class of the approximating functions, we derive the closed-form thresholding operator. We further present some theoretical analyses via the restricted isometry, null space, and spherical section properties. Our extensive numerical simulations indicate that the proposed algorithm closely follows the performance of the oracle estimator for a range of sparsity levels wider than those of the state-of-the-art algorithms. △ Less

Submitted 26 April, 2016; v1 submitted 26 May, 2015; originally announced May 2015.

Comments: Submitted to IEEE Trans. on Signal Processing

Upper Bounds on the Error of Sparse Vector and Low-Rank Matrix Recovery

Authors: Mohammadreza Malek-Mohammadi, Cristian R. Rojas, Magnus Jansson, Massoud Babaie-Zadeh

Abstract: Suppose that a solution $\widetilde{\mathbf{x}}$ to an underdetermined linear system $\mathbf{b} = \mathbf{A} \mathbf{x}$ is given. $\widetilde{\mathbf{x}}$ is approximately sparse meaning that it has a few large components compared to other small entries. However, the total number of nonzero components of $\widetilde{\mathbf{x}}$ is large enough to violate any condition for the uniqueness of the… ▽ More Suppose that a solution $\widetilde{\mathbf{x}}$ to an underdetermined linear system $\mathbf{b} = \mathbf{A} \mathbf{x}$ is given. $\widetilde{\mathbf{x}}$ is approximately sparse meaning that it has a few large components compared to other small entries. However, the total number of nonzero components of $\widetilde{\mathbf{x}}$ is large enough to violate any condition for the uniqueness of the sparsest solution. On the other hand, if only the dominant components are considered, then it will satisfy the uniqueness conditions. One intuitively expects that $\widetilde{\mathbf{x}}$ should not be far from the true sparse solution $\mathbf{x}_0$. We show that this intuition is the case by providing an upper bound on $\| \widetilde{\mathbf{x}} - \mathbf{x}_0\|$ which is a function of the magnitudes of small components of $\widetilde{\mathbf{x}}$ but independent from $\mathbf{x}_0$. This result is extended to the case that $\mathbf{b}$ is perturbed by noise. Additionally, we generalize the upper bounds to the low-rank matrix recovery problem. △ Less

Submitted 26 June, 2015; v1 submitted 13 April, 2015; originally announced April 2015.

Comments: Submitted to Elsevier Signal Processing

Bayesian Learning for Low-Rank matrix reconstruction

Authors: Martin Sundin, Cristian R. Rojas, Magnus Jansson, Saikat Chatterjee

Abstract: We develop latent variable models for Bayesian learning based low-rank matrix completion and reconstruction from linear measurements. For under-determined systems, the developed methods are shown to reconstruct low-rank matrices when neither the rank nor the noise power is known a-priori. We derive relations between the latent variable models and several low-rank promoting penalty functions. The r… ▽ More We develop latent variable models for Bayesian learning based low-rank matrix completion and reconstruction from linear measurements. For under-determined systems, the developed methods are shown to reconstruct low-rank matrices when neither the rank nor the noise power is known a-priori. We derive relations between the latent variable models and several low-rank promoting penalty functions. The relations justify the use of Kronecker structured covariance matrices in a Gaussian based prior. In the methods, we use evidence approximation and expectation-maximization to learn the model parameters. The performance of the methods is evaluated through extensive numerical simulations. △ Less

Submitted 23 January, 2015; originally announced January 2015.

Comments: Submitted to IEEE Transactions on Signal Processing

On the information carried by programs about the objects they compute

Authors: Mathieu Hoyrup, Cristobal Rojas

Abstract: In computability theory and computable analysis, finite programs can compute infinite objects. Presenting a computable object via any program for it, provides at least as much information as presenting the object itself, written on an infinite tape. What additional information do programs provide? We characterize this additional information to be any upper bound on the Kolmogorov complexity of the… ▽ More In computability theory and computable analysis, finite programs can compute infinite objects. Presenting a computable object via any program for it, provides at least as much information as presenting the object itself, written on an infinite tape. What additional information do programs provide? We characterize this additional information to be any upper bound on the Kolmogorov complexity of the object. Hence we identify the exact relationship between Markov-computability and Type-2-computability. We then use this relationship to obtain several results characterizing the computational and topological structure of Markov-semidecidable sets. △ Less

Submitted 24 September, 2014; originally announced September 2014.

ACM Class: F.1.1

Alternating Strategies Are Good For Low-Rank Matrix Reconstruction

Authors: Kezhi Li, Martin Sundin, Cristian R. Rojas, Saikat Chatterjee, Magnus Jansson

Abstract: This article focuses on the problem of reconstructing low-rank matrices from underdetermined measurements using alternating optimization strategies. We endeavour to combine an alternating least-squares based estimation strategy with ideas from the alternating direction method of multipliers (ADMM) to recover structured low-rank matrices, such as Hankel structure. We show that merging these two alt… ▽ More This article focuses on the problem of reconstructing low-rank matrices from underdetermined measurements using alternating optimization strategies. We endeavour to combine an alternating least-squares based estimation strategy with ideas from the alternating direction method of multipliers (ADMM) to recover structured low-rank matrices, such as Hankel structure. We show that merging these two alternating strategies leads to a better performance than the existing alternating least squares (ALS) strategy. The performance is evaluated via numerical simulations. △ Less

Submitted 12 July, 2014; originally announced July 2014.