We introduce the Probabilistic Coin Change Problem (PCCP), a novel variant of the classical Combination Coin Change Problem (CCCP), motivated by a real-world scientific inverse task. The goal of CCCP is to enumerate all unordered combinations of coin denominations that sum to a given target. In PCCP, each coin type’s value follows a discrete probability distribution, and the aggregate value of a combination of coins is thus stochastic. Given a set of such coin types and noisy observations of total sums, the task is to infer the most likely latent coin combination. To address the combinatorial and probabilistic complexity of PCCP, we propose DeepProReasoner (Deep Combinatorial Probabilistic Reasoning with Embedded Representations), an unsupervised, end-to-end, deep-learning framework that integrates combinatorial reasoning, latent-space modeling, and differentiable probabilistic reasoning. The model is trained using a reconstruction loss between the observed empirical distribution and a decoded probability mass function (PMF), enabling efficient gradient-based search over a continuous relaxation of the combinatorial space. We evaluate DeepProReasoner on two instances of PCCP: (1) a synthetic Candy Mix problem for ablation studies, and (2) a real-world task of molecular formula inference from ultrahigh resolution mass spectrometry (MS) data. Besides the two given instances, PCCP captures a wide range of inverse settings in biology, chemistry, environmental sciences, and medicine, where latent combinatorial structures give rise to noisy aggregate observations through stochastic processes. Our results show that DeepProReasoner achieves high accuracy and robustness, outperforming state-of-the-art methods.

Addressing global sustainability challenges as outlined by the United Nations (UN) Sustainable Development Goals (SDGs) often requires navigating many potentially conflicting societal objectives simultaneously. For instance, increasing hydropower production enhances renewable energy supply but may adversely impact people and nature. Understanding these trade-offs is crucial, and the Pareto frontier - the set of solutions that cannot be improved with respect to one objective without negatively affecting another - is a valuable framework. Strategic hydropower planning concerns finding energy portfolios that achieve decarbonization targets, while balancing energy production with socioeconomic and environmental impacts. Previous work has considered exact and approximate algorithms for Pareto optimization for tree-structured networks, such as rivers, for hydropower planning. However, such approaches do not account for bounding constraints, such as realistic energy production targets, critical in real-world applications. Herein, we propose a novel approach for constraint-aware Pareto optimization for tree-structured networks, incorporating objective bounds to ensure more realistic and robust solution outcomes. We apply our constraint-aware Pareto approach to the strategic planning of hydropower expansion, considering energy bounds to adhere to the UN's net zero by 2050 decarbonization targets, in the Magdalena River basin, home to more than 80% of Colombia’s population. Our analysis demonstrates how lower and upper bounds can significantly modify the unconstrained Pareto frontier, revealing that feasible Pareto solutions can be dominated by infeasible solutions, and thus may be ignored by constraint-agnostic solvers. Our results highlight the importance of considering real-world constraints in multi-objective problems such as optimizing hydropower expansion to meet both energy and sustainability goals.

Climate change and biodiversity loss are among humanity’s most pressing challenges. In 2022, under the auspices of the United Nations, over 190 countries reached a historic agreement to address the alarming loss of biodiversity and restore natural ecosystems. Target 3, often referred to as ``30x30'', seeks to effectively protect and manage 30% of the world’s terrestrial, inland water, coastal, and marine areas by 2030. In this work, we address the UN 30x30 target in the context of global freshwater fish conservation. Freshwater ecosystems are disproportionately unprotected, and their biota are declining at an alarming rate. Our goal is to select new protected areas that protect freshwater fish species as much as possible without exceeding total coverage of 30% of land area. To support this goal, we introduce the Expansion of Connected Components from Alternative Terminals Problem, a graph-based optimization problem that captures ecological priorities and connectivity constraints. We analyze its computational complexity, propose novel integer programming formulations, and develop scalable solution methods. We further evaluate its typical-case complexity under diverse settings and demonstrate that our approach scales to a global real-world scope, encompassing approximately 200,000 freshwater basins and 13,000 species, paving the way for implementing the 30x30 target on a worldwide scale.

Very recently, the first mathematical runtime analyses for the NSGA-II, the most common multi-objective evolutionary algorithm, have been conducted. Continuing this research direction, we prove that the NSGA-II optimizes the OneJumpZeroJump benchmark asymptotically faster when crossover is employed. Together with a parallel independent work by Dang, Opris, Salehi, and Sudholt, this is the first time such an advantage of crossover is proven for the NSGA-II. Our arguments can be transferred to single-objective optimization. They then prove that crossover can speed up the (mu+1) genetic algorithm in a different way and more pronounced than known before. Our experiments confirm the added value of crossover and show that the observed advantages are even larger than what our proofs can guarantee.

Due to the more complicated population dynamics of the NSGA-II, none of the existing runtime guarantees for this algorithm is accompanied by a non-trivial lower bound. Via a first mathematical understanding of the population dynamics of the NSGA-II, that is, by estimating the expected number of individuals having a certain objective value, we prove that the NSGA-II with suitable population size needs Omega(Nn log n) function evaluations to find the Pareto front of the OneMinMax problem and Omega(Nn^k) evaluations on the OneJumpZeroJump problem with jump size k. These bounds are asymptotically tight (that is, they match previously shown upper bounds) and show that the NSGA-II here does not even in terms of the parallel runtime (number of iterations) profit from larger population sizes. For the OneJumpZeroJump problem and when the same sorting is used for the computation of the crowding distance contributions of the two objectives, we even obtain a runtime estimate that is tight including the leading constant.

Very recently, the first mathematical runtime analyses of the multiobjective evolutionary optimizer nondominated sorting genetic algorithm II (NSGA-II) have been conducted. We continue this line of research with a first runtime analysis of this algorithm on a benchmark problem consisting of multimodal objectives. We prove that if the population size$N$is at least four times the size of the Pareto front, then the NSGA-II with four standard ways to select parents, bitwise mutation, and crossover with rate less than one, optimizes the OneJumpZeroJump benchmark with jump size$2 \le k \le n/4$in time$O(N n^{k})$. When using fast mutation instead of bitwise mutation this guarantee improves by a factor of$k^{\Omega (k)}$. Overall, this work shows that the NSGA-II copes with the local optima of the OneJumpZeroJump problem at least as well as the global SEMO algorithm.

Recent advances in end-to-end speech recognition have made it possible to build multilingual models, capable of recognizing speech in multiple languages. Multilingual models can outperform their monolingual counterparts, depending on the amount of training data and the relatedness of languages. However, in some cases, these models rely on having perfect knowledge of the language being spoken; that is, they expect to be provided with an external language ID that augments the input features or modulates internal layers of the network. In this paper, we introduce a novel technique for inferring the language ID in a streaming fashion using RNN-T, and a novel loss function that pressures the model to identify the language after as few frames as possible. The output of this streaming language-ID model is used in training and inference of a multilingual recognition model. We show the effectiveness of our approach through experiments on two sets of languages, one consisting of different dialects of Arabic, and the other consisting of Nordic languages, Finnish and Dutch.

Conventional spoken language understanding systems consist of two main components: an automatic speech recognition module that converts audio to a transcript, and a natural language understanding module that transforms the resulting text (or top N hypotheses) into a set of domains, intents, and arguments. These modules are typically optimized independently. In this paper, we formulate audio to semantic understanding as a sequence-to-sequence problem [1]. We propose and compare various encoder-decoder based approaches that optimize both modules jointly, in an end-to-end manner. Evaluations on a real-world task show that 1) having an intermediate text representation is crucial for the quality of the predicted semantics, especially the intent arguments and 2) jointly optimizing the full system improves overall accuracy of prediction. Compared to independently trained models, our best jointly trained model achieves similar domain and intent prediction F1 scores, but improves argument word error rate by 18% relative.

We explore the feasibility of training long short-term memory (LSTM) recurrent neural networks (RNNs) with syllables, rather than phonemes, as outputs. Syllables are a natural choice of linguistic unit for modeling the acoustics of languages such as Mandarin Chinese, due to the inherent nature of the syllable as an elemental pronunciation construct and the limited size of the syllable set for such languages (around 1400 syllables for Mandarin). Our models are trained with Connectionist Temporal Classification (CTC) and state-level minimum Bayes risk (sMBR) loss using asynchronous stochastic gradient descent (ASGD) utilizing a parallel computation infrastructure for large-scale training. Our acoustic models operate on feature frames computed every 30ms, which makes them well suited for modeling syllables rather than phonemes, which can have a shorter duration. Additionally, when compared to wordlevel modeling, syllables have the advantage of avoiding out-of-vocabulary (OOV) model outputs. Our experiments on a Mandarin voice search task show that syllable-output models can perform better than context-independent (CI) phone-output models, and can give similar performance as our state-of-the-art context-dependent (CD) models. Additionally, decoding with syllable-output models is substantially faster than with CI models or with CD models. We demonstrate that these improvements are maintained when the model is trained to recognize both Mandarin syllables and English phonemes.