@article{18949, abstract = {Speciation research—the scientific field focused on understanding the origin and diversity of species—has a long and complex history. While relevant to one another, the specific goals and activities of speciation researchers are highly diverse, and scattered across a collection of different perspectives. Thus, our understanding of speciation will benefit from efforts to bridge scientific findings and the diverse people who do the work. In this paper, we outline two ways of integrating speciation research: (i) scientific integration, through the bringing together of ideas, data, and approaches; and (ii) social integration, by creating ways for a diversity of researchers to participate in the scientific process. We then discuss five challenges to integration: (i) the multidisciplinary nature of speciation research, (ii) the complex language of speciation; (iii) a bias toward certain study systems; (iv) the challenges of working across scales; and (v) inconsistent measures and reporting standards. We provide practical steps that individuals and groups can take to help overcome these challenges, and argue that integration is a team effort in which we all have a role to play.}, author = {Stankowski, Sean and Cutter, Asher D and Satokangas, Ina and Lerch, Brian A and Rolland, Jonathan and Smadja, Carole M and Segami Marzal, J Carolina and Cooney, Christopher R and Feulner, Philine G D and Domingos, Fabricius Maia Chaves Bicalho and North, Henry L and Yamaguchi, Ryo and Butlin, Roger K and Wolf, Jochen B W and Coughlan, Jenn and Heidbreder, Patrick and Hernández-Gutiérrez, Rebeca and Barnard-Kubow, Karen B and Peede, David and Rancilhac, Loïs and Salvador, Rodrigo Brincalepe and Thompson, Ken A and Stacy, Elizabeth A and Moyle, Leonie C and Garlovsky, Martin D and Maulana, Arif and Kantelinen, Annina and Cacho, N Ivalú and Schneemann, Hilde and Domínguez, Marisol and Dopman, Erik B and Lohse, Konrad and Rometsch, Sina J and Comeault, Aaron A and Merrill, Richard M and Scordato, Elizabeth S C and Singhal, Sonal and Pärssinen, Varpu and Lackey, Alycia C R and Kumar, Sanghamitra and Meier, Joana I and Barton, Nicholas H and Fraisse, Christelle and Ravinet, Mark and Kulmuni, Jonna}, issn = {2752-938X}, journal = {Evolutionary Journal of the Linnean Society}, number = {1}, publisher = {Oxford University Press}, title = {{Toward the integration of speciation research}}, doi = {10.1093/evolinnean/kzae001}, volume = {3}, year = {2024}, } @inproceedings{18955, abstract = {We give a simple proof that assuming the Exponential Time Hypothesis (ETH), determining the winner of a Rabin game cannot be done in time 2o(k log k) · nO(1), where k is the number of pairs of vertex subsets involved in the winning condition and n is the vertex count of the game graph. While this result follows from the lower bounds provided by Calude et al [SIAM J. Comp. 2022], our reduction is considerably simpler and arguably provides more insight into the complexity of the problem. In fact, the analogous lower bounds discussed by Calude et al, for solving Muller games and multidimensional parity games, follow as simple corollaries of our approach. Our reduction also highlights the usefulness of a certain pivot problem — Permutation SAT — which may be of independent interest.}, author = {Casares, Antonio and Pilipczuk, Marcin and Pilipczuk, Michał and Souza, Uéverton S. and Thejaswini, K. S.}, booktitle = {2024 Symposium on Simplicity in Algorithms}, isbn = {9781611977936}, location = {Alexandria, VA, United States}, pages = {160--167}, publisher = {Society for Industrial and Applied Mathematics}, title = {{Simple and tight complexity lower bounds for solving Rabin games}}, doi = {10.1137/1.9781611977936.16}, year = {2024}, } @inproceedings{18956, abstract = {Group Activity Recognition (GAR) aims to detect the activity performed by multiple actors in a scene. Prior works model the spatio-temporal features based on the RGB, optical flow or keypoint data types. On the contrary, our hypothesis is that by only using the RGB data without temporality, the performance can be maintained with a negligible loss in accuracy. To that end, we propose a novel GAR technique for volleyball videos, DECOMPL, which consists of two complementary branches. In the visual branch, it extracts the features using attention pooling. In the coordinate branch, it considers the configuration of the players and extracts the spatial information from the box coordinates. Moreover, we analyzed the Volleyball dataset that the recent literature is mostly based on, and systematically reannotated it to emphasize the group concept. Experimental results demonstrated the effectiveness of the proposed model DECOMPL, which delivered the best/second best GAR performance with the reannotations/original annotations among the comparable state-of-the-art methods. Code and new annotations are available at GitHub: https://github.com/berkerdemirel/decompl}, author = {Demirel, Berker and Ozkan, Huseyin}, booktitle = {2024 IEEE International Conference on Image Processing}, issn = {2381-8549}, location = {Abu Dhabi, United Arab Emirates}, pages = {977--983}, publisher = {IEEE}, title = {{Decompl: Decompositional learning with attention pooling for group activity recognition from a single volleyball image}}, doi = {10.1109/icip51287.2024.10647499}, year = {2024}, } @inproceedings{18957, abstract = {Sui Lutris is the first smart-contract platform to sustainably achieve sub-second finality. It achieves this significant decrease by employing consensusless agreement not only for simple payments but for a large variety of transactions. Unlike prior work, Sui Lutris neither compromises expressiveness nor throughput and can run perpetually without restarts. Sui Lutris achieves this by safely integrating consensuless agreement with a high-throughput consensus protocol that is invoked out of the critical finality path but ensures that when a transaction is at risk of inconsistent concurrent accesses, its settlement is delayed until the total ordering is resolved. Building such a hybrid architecture is especially delicate during reconfiguration events, where the system needs to preserve the safety of the consensusless path without compromising the long-term liveness of potentially misconfigured clients. We thus develop a novel reconfiguration protocol, the first to provably show the safe and efficient reconfiguration of a consensusless blockchain. Sui Lutris is currently running in production and underpins the Sui smart-contract platform. Combined with the use of Objects instead of accounts it enables the safe execution of smart contracts that expose objects as a first-class resource. In our experiments Sui Lutris achieves latency lower than 0.5 seconds for throughput up to 5,000 certificates per second (150k ops/s with transaction blocks), compared to the state-of-the-art real-world consensus latencies of 3 seconds. Furthermore, it gracefully handles validators crash-recovery and does not suffer visible performance degradation during reconfiguration.}, author = {Blackshear, Sam and Chursin, Andrey and Danezis, George and Kichidis, Anastasios and Kokoris Kogias, Eleftherios and Li, Xun and Logan, Mark and Menon, Ashok and Nowacki, Todd and Sonnino, Alberto and Williams, Brandon and Zhang, Lu}, booktitle = {Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security}, isbn = {9798400706363}, location = {Salt Lake City, UT, United States}, pages = {2606--2620}, publisher = {ACM}, title = {{Sui Lutris: A blockchain combining broadcast and consensus}}, doi = {10.1145/3658644.3670286}, year = {2024}, } @article{18958, abstract = {This workshop brought together experts on the analysis of quantum many-body problems and quantum statistical mechanics, with the goal of discussing the state-of-the-art of the field, recent developments as well as challenges for the future. The main topics of discussion concerned the equilibrium and dynamical behavior of (bosonic or fermionic) quantum gases, quantum spin systems, as well as quantum field theory models like the Nelson or Fröhlich model.}, author = {Hainzl, Christian and Schlein, Benjamin and Seiringer, Robert and Warzel, Simone}, issn = {1660-8941}, journal = {Oberwolfach Reports}, number = {3}, pages = {2247--2302}, publisher = {EMS Press}, title = {{Many-body quantum systems}}, doi = {10.4171/owr/2023/39}, volume = {20}, year = {2024}, } @article{18961, abstract = {Automated contact tracing (ACT) emerged as a promising measure to curb the spread of Covid-19. Users enable ACT on their smartphones to automatically record contacts with other users. If a user tests positive for the disease, they report their diagnosis to alert their contacts. Designing effective ACT protocols is challenging since they need to be efficient and secure while also ensuring users' privacy. As ACT protocols necessarily leak some information by design, defining privacy is difficult. For example, a user cannot deny having met another user. Ideally, however, the user can plausibly deny everything else, in particular, when they met. We call this privacy property contact-time deniability. While some early works discussed contact-time deniability informally, it has received little attention since then. We investigate deniability from a rigorous, theoretical point of view and arrive at the following impossibility result: A decentralized protocol with unidirectional communication cannot be contact-time deniable and replay-secure. This holds even if malicious users treat smartphones as black-boxes. Unidirectional protocols are usually very efficient and many proposals are unidirectional, e.g., the widely-deployed Google-Apple Exposure Notifications. So the impossibility result considerably constrains the design space of efficient, secure, and private ACT protocols. However, it can also be used as a guide; we discuss several possibilities to achieve contact-time deniability in practice.}, author = {Günther, Christoph Ullrich and Pietrzak, Krzysztof Z}, issn = {2299-0984}, journal = {Proceedings on Privacy Enhancing Technologies}, location = {Bristol, UK/Virtual}, number = {4}, pages = {636--648}, publisher = {Privacy Enhancing Technologies Symposium Advisory Board}, title = {{Deniability in automated contact tracing: Impossibilities and possibilities}}, doi = {10.56553/popets-2024-0134}, volume = {2024}, year = {2024}, } @inproceedings{18964, abstract = {Object-centric learning (OCL) extracts the representation of objects with slots, offering an exceptional blend of flexibility and interpretability for abstracting low-level perceptual features. A widely adopted method within OCL is slot attention, which utilizes attention mechanisms to iteratively refine slot representations. However, a major draw-back of most object-centric models, including slot attention, is their reliance on predefining the number of slots. This not only necessitates prior knowledge of the dataset but also overlooks the inherent variability in the number of objects present in each instance. To overcome this fundamental limitation, we present a novel complexity-aware object auto-encoder framework. Within this framework, we introduce an adaptive slot attention (AdaSlot) mecha-nism that dynamically determines the optimal number of slots based on the content of the data. This is achieved by proposing a discrete slot sampling module that is responsible for selecting an appropriate number of slots from a candidate list. Furthermore, we introduce a masked slot decoder that suppresses unselected slots during the decoding process. Our framework, tested extensively on object discovery tasks with various datasets, shows performance matching or exceeding top fixed-slot models. Moreover, our analysis substantiates that our method exhibits the capability to dynamically adapt the slot number according to each instance's complexity, offering the potential for further exploration in slot attention research. Project will be available at https://kfan21.github.io/AdaSlot/}, author = {Fan, Ke and Bai, Zechen and Xiao, Tianjun and He, Tong and Horn, Max and Fu, Yanwei and Locatello, Francesco and Zhang, Zheng}, booktitle = {2024 IEEE/CVF Conference on Computer Vision and Pattern Recognition}, location = {Seattle, WA, United States}, publisher = {IEEE}, title = {{Adaptive slot attention: Object discovery with dynamic slot number}}, doi = {10.1109/cvpr52733.2024.02176}, year = {2024}, } @misc{18967, abstract = {Background: We identified small molecule tricyclic pyrone compound CP2 as a mild mitochondrial complex I (MCI) inhibitor that induces neuroprotection in multiple mouse models of AD. One of the major concerns while targeting mitochondria is the production of reactive oxygen species (ROS). CP2 consists of two diastereoisomers, D1 and D2, with distinct activity and toxicity profiles. This study was designed to understand how structure of D1 and D2 affects their binding to MCI and the consequential impact on ROS production. Method: The X-ray crystallography and cryo-electron microscopy (cryo-EM) at global resolution of 3.25-3.27Å were employed to identify the molecular structure of D1 and D2 and the D1 binding to the isolated ovine MCI. The assessment of the MCI inhibition and the extent of ROS generation were done in isolated MCI and human neuroblastoma MC65 cells using flow cytometry, a Seahorse extracellular flux analyzer, and the kinetic studies. Result: In the closed conformation of MCI, D1 selectively binds to the deep Quinone-site (Qd) but not to the shallow Q-site (Qs), sharing the same binding pocket as rotenone. In the open MCI state, D1 exclusively binds to the Qs in contrast to rotenone, which binds Qd and Qs in both closed and open states. At the same concentrations, D1 inhibits respiration to a greater extent compared to D2 (5:1 ratio) and produces higher level of ROS. Conclusion:Cryo-EM unambiguously identified binding of D1 to both the Qd and Qs sites, contingent upon the conformational state of MCI. In contrast to rotenone, D1 binds Qd only in the closed conformation during catalytic cycle, leading to mild inhibition. Superimposing X-ray crystallography data of D1 and D2 onto cryo-EM data suggests that the orientation of the methyl group in D2 induces a flatter conformation, resulting in lower binding affinity to MCI, which correlates with lower inhibition and toxicity compared to D1. At physiologically relevant concentrations, CP2 (D1:D2 = 1:1) demonstrates low MCI inhibition yielding negligible ROS levels. This observation provides new insight into the absence of toxicity associated with CP2 treatment in vivo, further highlighting feasibility for the development of safe and efficacious MCI inhibitors.}, author = {Petrova, Olga and Trushin, Sergey A and Nguyen, Thi Kim Oanh and Ostroot, Mark and Schellenberg, Matthew and Johnson, Graham and Trushina, Eugenia and Sazanov, Leonid A}, booktitle = {Alzheimer's & Dementia}, issn = {1552-5279}, number = {S6}, publisher = {Wiley}, title = {{Structure‐activity relationship study of neuroprotective complex I inhibitor CP2}}, doi = {10.1002/alz.085971}, volume = {20}, year = {2024}, } @article{18970, abstract = {Given a smooth projective curve C, nonabelian Hodge theory gives a diffeomorphism between two different moduli spaces associated to C. The first is the moduli space of Higgs bundles on C of rank n, which is equipped with the structure of an algebraic completely integrable Hamiltonian system. The second is the character variety of representations of the fundamental group of C into GL(n). In 2012, de Cataldo, Hausel, and Migliorini [1] proposed the P=W conjecture which identifies the perverse filtration on the cohomology of the Higgs moduli space with the weight filtration on the cohomology of the character variety. Recently, in 2022, two independent proofs of the P=W Conjecture appeared, in work of Maulik &Shen [2] and Hausel, Mellit, Minets &Schiffmann [6]. The aim of the Arbeitsgemeinschaft was to understand the P=W Conjecture and these two recent proofs.}, author = {Hausel, Tamás and Maulik, Davesh and Mellit, Anton and Schiffmann, Olivier and Shen, Junliang}, issn = {1660-8941}, journal = {Oberwolfach Reports}, number = {2}, pages = {949--1004}, publisher = {EMS Press}, title = {{Arbeitsgemeinschaft: Geometry and representation theory around the P=W conjecture}}, doi = {10.4171/owr/2024/16}, volume = {21}, year = {2024}, } @inproceedings{18971, abstract = {Models prone to spurious correlations in training data often produce brittle predictions and introduce unintended biases. Addressing this challenge typically involves methods relying on prior knowledge and group annotation to remove spurious correlations, which may not be readily available in many applications. In this paper, we establish a novel connection between unsupervised object-centric learning and mitigation of spurious correlations. Instead of directly inferring subgroups with varying correlations with labels, our approach focuses on discovering concepts: discrete ideas that are shared across input samples. Leveraging existing object-centric representation learning, we introduce CoBalT: a concept balancing technique that effectively mitigates spurious correlations without requiring human labeling of subgroups. Evaluation across the benchmark datasets for sub-population shifts demonstrate superior or competitive performance compared state-of-the-art baselines, without the need for group annotation. Code is available at https://github.com/rarefin/CoBalT}, author = {Arefin, Rifat and Zhang, Yan and Baratin, Aristide and Locatello, Francesco and Rish, Irina and Liu, Dianbo and Kawaguchi, Kenji}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, issn = {2640-3498}, location = {Vienna, Austria}, pages = {1672--1688}, publisher = {ML Research Press}, title = {{Unsupervised concept discovery mitigates spurious correlations}}, volume = {235}, year = {2024}, } @inproceedings{18972, abstract = {Deep learning models are known to overfit and memorize spurious features in the training dataset. While numerous empirical studies have aimed at understanding this phenomenon, a rigorous theoretical framework to quantify it is still missing. In this paper, we consider spurious features that are uncorrelated with the learning task, and we provide a precise characterization of how they are memorized via two separate terms: (i) the stability of the model with respect to individual training samples, and (ii) the feature alignment between the spurious pattern and the full sample. While the first term is well established in learning theory and it is connected to the generalization error in classical work, the second one is, to the best of our knowledge, novel. Our key technical result gives a precise characterization of the feature alignment for the two prototypical settings of random features (RF) and neural tangent kernel (NTK) regression. We prove that the memorization of spurious features weakens as the generalization capability increases and, through the analysis of the feature alignment, we unveil the role of the model and of its activation function. Numerical experiments show the predictive power of our theory on standard datasets (MNIST, CIFAR-10).}, author = {Bombari, Simone and Mondelli, Marco}, booktitle = {41st International Conference on Machine Learning}, issn = {2640-3498}, location = {Vienna, Austria}, pages = {4267--4299}, publisher = {ML Research Press}, title = {{How spurious features are memorized: Precise analysis for random and NTK features}}, volume = {235}, year = {2024}, } @inproceedings{18973, abstract = {Understanding the reasons behind the exceptional success of transformers requires a better analysis of why attention layers are suitable for NLP tasks. In particular, such tasks require predictive models to capture contextual meaning which often depends on one or few words, even if the sentence is long. Our work studies this key property, dubbed word sensitivity (WS), in the prototypical setting of random features. We show that attention layers enjoy high WS, namely, there exists a vector in the space of embeddings that largely perturbs the random attention features map. The argument critically exploits the role of the softmax in the attention layer, highlighting its benefit compared to other activations (e.g., ReLU). In contrast, the WS of standard random features is of order 1/n−−√, n being the number of words in the textual sample, and thus it decays with the length of the context. We then translate these results on the word sensitivity into generalization bounds: due to their low WS, random features provably cannot learn to distinguish between two sentences that differ only in a single word; in contrast, due to their high WS, random attention features have higher generalization capabilities. We validate our theoretical results with experimental evidence over the BERT-Base word embeddings of the imdb review dataset.}, author = {Bombari, Simone and Mondelli, Marco}, booktitle = {41st International Conference on Machine Learning}, issn = {2640-3498}, location = {Vienna, Austria}, pages = {4300--4328}, publisher = {ML Research Press}, title = {{Towards understanding the word sensitivity of attention layers: A study via random features}}, volume = {235}, year = {2024}, } @inproceedings{18974, abstract = {Reinforcement Learning (RL) from temporal logical specifications is a fundamental problem in sequential decision making. One of the basic and core such specification is the reachability specification that requires a target set to be eventually visited. Despite strong empirical results for RL from such specifications, the theoretical guarantees are bleak, including the impossibility of Probably Approximately Correct (PAC) guarantee for reachability specifications. Given the impossibility result, in this work we consider the problem of RL from reachability specifications along with the information of expected conditional distance (ECD). We present (a) lower bound results which establish the necessity of ECD information for PAC guarantees and (b) an algorithm that establishes PAC-guarantees given the ECD information. To the best of our knowledge, this is the first RL from reachability specifications that does not make any assumptions on the underlying environment to learn policies.}, author = {Svoboda, Jakub and Bansal, Suguman and Chatterjee, Krishnendu}, booktitle = {41st International Conference on Machine Learning}, location = {Vienna, Austria}, pages = {47331--47344}, publisher = {ML Research Press}, title = {{Reinforcement learning from reachability specifications: PAC guarantees with expected conditional distance}}, volume = {235}, year = {2024}, } @inproceedings{18975, abstract = {Leveraging second-order information about the loss at the scale of deep networks is one of the main lines of approach for improving the performance of current optimizers for deep learning. Yet, existing approaches for accurate full-matrix preconditioning, such as Full-Matrix Adagrad (GGT) or Matrix-Free Approximate Curvature (M-FAC) suffer from massive storage costs when applied even to small-scale models, as they must store a sliding window of gradients, whose memory requirements are multiplicative in the model dimension. In this paper, we address this issue via a novel and efficient error-feedback technique that can be applied to compress preconditioners by up to two orders of magnitude in practice, without loss of convergence. Specifically, our approach compresses the gradient information via sparsification or low-rank compression before it is fed into the preconditioner, feeding the compression error back into future iterations. Extensive experiments on deep neural networks show that this approach can compress full-matrix preconditioners to up to 99% sparsity without accuracy loss, effectively removing the memory overhead of fullmatrix preconditioners such as GGT and M-FAC.}, author = {Modoranu, Ionut-Vlad and Kalinov, Aleksei and Kurtic, Eldar and Frantar, Elias and Alistarh, Dan-Adrian}, booktitle = {41st International Conference on Machine Learning}, issn = {2640-3498}, location = {Vienna, Austria}, pages = {35910--35933}, publisher = {ML Research Press}, title = {{Error feedback can accurately compress preconditioners}}, volume = {235}, year = {2024}, } @inproceedings{18976, abstract = {We analyze asynchronous-type algorithms for distributed SGD in the heterogeneous setting, where each worker has its own computation and communication speeds, as well as data distribution. In these algorithms, workers compute possibly stale and stochastic gradients associated with their local data at some iteration back in history and then return those gradients to the server without synchronizing with other workers. We present a unified convergence theory for non-convex smooth functions in the heterogeneous regime. The proposed analysis provides convergence for pure asynchronous SGD and its various modifications. Moreover, our theory explains what affects the convergence rate and what can be done to improve the performance of asynchronous algorithms. In particular, we introduce a novel asynchronous method based on worker shuffling. As a by-product of our analysis, we also demonstrate convergence guarantees for gradient-type algorithms such as SGD with random reshuffling and shuffle-once mini-batch SGD. The derived rates match the best-known results for those algorithms, highlighting the tightness of our approach. Finally, our numerical evaluations support theoretical findings and show the good practical performance of our method.}, author = {Islamov, Rustem and Safaryan, Mher and Alistarh, Dan-Adrian}, booktitle = {Proceedings of The 27th International Conference on Artificial Intelligence and Statistics}, issn = {2640-3498}, location = {Valencia, Spain}, pages = {649--657}, publisher = {ML Research Press}, title = {{AsGrad: A sharp unified analysis of asynchronous-SGD algorithms}}, volume = {238}, year = {2024}, } @inproceedings{18977, abstract = {Recent advances in large language model (LLM) pretraining have led to high-quality LLMs with impressive abilities. By compressing such LLMs via quantization to 3-4 bits per parameter, they can fit into memory-limited devices such as laptops and mobile phones, enabling personalized use. Quantizing models to 3-4 bits per parameter can lead to moderate to high accuracy losses, especially for smaller models (1-10B parameters), which are suitable for edge deployment. To address this accuracy issue, we introduce the Sparse-Quantized Representation (SpQR), a new compressed format and quantization technique that enables for the first time \emph{near-lossless} compression of LLMs across model scales while reaching similar compression levels to previous methods. SpQR works by identifying and isolating \emph{outlier weights}, which cause particularly large quantization errors, and storing them in higher precision while compressing all other weights to 3-4 bits, and achieves relative accuracy losses of less than in perplexity for highly-accurate LLaMA and Falcon LLMs. This makes it possible to run a 33B parameter LLM on a single 24 GB consumer GPU without performance degradation at 15% speedup, thus making powerful LLMs available to consumers without any downsides. SpQR comes with efficient algorithms for both encoding weights into its format, as well as decoding them efficiently at runtime. Specifically, we provide an efficient GPU inference algorithm for SpQR, which yields faster inference than 16-bit baselines at similar accuracy while enabling memory compression gains of more than 4x.}, author = {Dettmers, Tim and Svirschevski, Ruslan A. and Egiazarian, Vage and Kuznedelev, Denis and Frantar, Elias and Ashkboos, Saleh and Borzunov, Alexander and Hoefler, Torsten and Alistarh, Dan-Adrian}, booktitle = {12th International Conference on Learning Representations}, location = {Vienna, Austria}, publisher = {OpenReview}, title = {{SpQR: A sparse-quantized representation for near-lossless LLM weight compression}}, year = {2024}, } @unpublished{18981, abstract = {We establish several results combining discrete Morse theory and microlocal sheaf theory in the setting of finite posets and simplicial complexes. Our primary tool is a computationally tractable description of the bounded derived category of sheaves on a poset with the Alexandrov topology. We prove that each bounded complex of sheaves on a finite poset admits a unique (up to isomorphism of complexes) minimal injective resolution, and we provide algorithms for computing minimal injective resolution of an injective complex, as well as several useful functors between derived categories of sheaves. For the constant sheaf on a simplicial complex, we give asymptotically tight bounds on the complexity of computing the minimal injective resolution using those algorithms. Our main result is a novel definition of the discrete microsupport of a bounded complex of sheaves on a finite poset. We detail several foundational properties of the discrete microsupport, as well as a microlocal generalization of the discrete homological Morse theorem and Morse inequalities.}, author = {Brown, Adam and Draganov, Ondrej}, booktitle = {arXiv}, title = {{Discrete microlocal Morse theory}}, doi = {10.48550/arXiv.2209.14993}, year = {2024}, } @inproceedings{18996, abstract = {We consider the linear causal representation learning setting where we observe a linear mixing of d unknown latent factors, which follow a linear structural causal model. Recent work has shown that it is possible to recover the latent factors as well as the underlying structural causal model over them, up to permutation and scaling, provided that we have at least d environments, each of which corresponds to perfect interventions on a single latent node (factor). After this powerful result, a key open problem faced by the community has been to relax these conditions: allow for coarser than perfect single-node interventions, and allow for fewer than d of them, since the number of latent factors d could be very large. In this work, we consider precisely such a setting, where we allow a smaller than d number of environments, and also allow for very coarse interventions that can very coarsely \textit{change the entire causal graph over the latent factors}. On the flip side, we relax what we wish to extract to simply the \textit{list of nodes that have shifted between one or more environments}. We provide a surprising identifiability result that it is indeed possible, under some very mild standard assumptions, to identify the set of shifted nodes. Our identifiability proof moreover is a constructive one: we explicitly provide necessary and sufficient conditions for a node to be a shifted node, and show that we can check these conditions given observed data. Our algorithm lends itself very naturally to the sample setting where instead of just interventional distributions, we are provided datasets of samples from each of these distributions. We corroborate our results on both synthetic experiments as well as an interesting psychometric dataset. The code can be found at https://github.com/TianyuCodings/iLCS.}, author = {Chen, Tianyu and Bello, Kevin and Locatello, Francesco and Aragam, Bryon and Ravikumar, Pradeep Kumar}, booktitle = {38th Conference on Neural Information Processing Systems}, issn = {1049-5258}, location = {Vancouver, Canada}, publisher = {Neural Information Processing Systems Foundation}, title = {{Identifying general mechanism shifts in linear causal representations}}, volume = {37}, year = {2024}, } @inproceedings{18998, abstract = {Word embeddings represent language vocabularies as clouds of d-dimensional points. We investigate how information is conveyed by the general shape of these clouds, instead of representing the semantic meaning of each token. Specifically, we use the notion of persistent homology from topological data analysis (TDA) to measure the distances between language pairs from the shape of their unlabeled embeddings. These distances quantify the degree of non-isometry of the embeddings. To distinguish whether these differences are random training errors or capture real information about the languages, we use the computed distance matrices to construct language phylogenetic trees over 81 Indo-European languages. Careful evaluation shows that our reconstructed trees exhibit strong and statistically-significant similarities to the reference.}, author = {Draganov, Ondrej and Skiena, Steven}, booktitle = {Findings of the Association for Computational Linguistics: EMNLP 2024}, location = {Miami, FL, United States}, pages = {12080--12099}, publisher = {Association for Computational Linguistics}, title = {{The shape of word embeddings: Quantifying non-isometry with topological data analysis}}, doi = {10.18653/v1/2024.findings-emnlp.705}, year = {2024}, } @unpublished{18999, abstract = {Exploring the shape of point configurations has been a key driver in the evolution of TDA (short for topological data analysis) since its infancy. This survey illustrates the recent efforts to broaden these ideas to model spatial interactions among multiple configurations, each distinguished by a color. It describes advances in this area and prepares the ground for further exploration by mentioning unresolved questions and promising research avenues while focusing on the overlap with discrete geometry.}, author = {Cultrera di Montesano, Sebastiano and Draganov, Ondrej and Edelsbrunner, Herbert and Saghafian, Morteza}, booktitle = {arXiv}, title = {{Chromatic topological data analysis}}, doi = {10.48550/ARXIV.2406.04102}, year = {2024}, }