Masked diffusion models (MDM) exhibit superior generalization when learned using a Partial masking scheme (Prime). This approach converts tokens into sub-tokens and models the diffusion process at the sub-token level. We identify two limitations of the MDM-Prime framework. First, we find that the functional form of the subtokenizer significantly increases the cross-entropy loss in the objective when paired with commonly used Byte-Pair-Encoding (BPE) tokenizers. Second, we lack tools to guide the hyperparameter choice of the token granularity in the subtokenizer. To address these limitations, we analyze the optimal design of the subtokenizer that minimizes MDM-Prime training objective and develop MDM-Prime-v2, a masked diffusion language model which incorporates Binary Encoding and Index Shuffling. Our analysis characterizes how token granularity and sub-token entropy influence the training objective and downstream performance, providing principled criteria for subtokenizer design. When extending the model size to 1.1B parameters, MDM-Prime-v2 demonstrates superior average zero-shot accuracy across eight commonsense reasoning benchmarks, outperforming similar-sized baselines including GPT-Neo, OPT, Pythia, Bloom, SMDM, and TinyLLaMA.
Chen-Hao Chao, Wei-Fang Sun, Junwei Quan et al.· 0 citations
We introduce Canary, a risk-averse method designed to optimize Value-at-Risk (VaR) constrained reinforcement learning (RL) problems. We employ Cantelli's inequality to obtain a tractable, conservative and smooth bound on the VaR constraint based on the first two moments of the cost return. This yields a constraint estimator that remains stable with tight violation thresholds in dense cost regimes. Extending the trust-region framework of the Constrained Policy Optimization (CPO) method, we further provide worst-case bounds for both policy improvement and constraint violation during the training process. Empirically during training, Canary is the only method that reliably satisfies the VaR constraint in every environment tested.
Datasets may contain observations with multiple labels. If the labels are not mutually exclusive, and if the labels vary greatly in frequency, obtaining a sample that includes sufficient observations with scarcer labels to make inferences about those labels, and which deviates from the population frequencies in a known manner, creates challenges. In this paper, we consider a multivariate Bernoulli distribution as our underlying distribution of a multi-label problem. We present a novel sampling algorithm that takes label dependencies into account. It uses observed label frequencies to estimate multivariate Bernoulli distribution parameters and calculates weights for each label combination. This approach ensures the weighted sampling acquires target distribution characteristics while accounting for label dependencies. We applied this approach to a variety of datasets, including a sample of research articles from Web of Science labeled with 64 biomedical topic categories. We aimed to preserve category frequency order, reduce frequency differences between most and least common categories, and account for category dependencies. This approach produced a more balanced sub-sample, enhancing the representation of minority categories.
Simon Chung, Colby J. Vorland, Donna L. Maney et al.· 0 citations
We study whether otherwise-idle inference resources could reduce the scarce-GPU cost of training. Our analysis uses a simulated compute ledger in which fleet work is billed at a fraction of a scarce-GPU forward; all experiments run on a regular GPU. Our algorithm predicts gradients with a reduced-precision, inference-style reverse-mode program and combines many predictions with a few exact gradients through a control variate, so approximation error becomes variance rather than bias. On a 124M-parameter language model and selected short training windows, the method can lower simulated ledger cost relative to the tested baselines when fleet work is sufficiently cheap. Experiments spanning 10M-774M parameters show both transfers and failures. We do not test inference-only hardware, end-to-end distributed latency, or a full optimizer-by-batch-size baseline sweep.
Kamil Ciosek, Nicol\`o Felicioni, Juan Elenter et al.· 0 citations
Reach audiences
Advertise in front of researchers, engineers, and readers.
Safe reinforcement learning (RL) aims to optimize long-term performance while adhering to safety requirements. However, many practical applications involve an infinite number of constraints, forming semi-infinite safe RL (SI-safe RL). Such scenarios typically appear when safety conditions must be enforced across an entire continuous parameter space, such as ensuring adequate resource distribution at every spatial location. Existing approaches typically tackle these continuous constraints through naive spatial discretization or stochastic sampling. Such methods inherently suffer from residual violations or provide only probabilistic safety guarantees. Therefore, no current framework can handle infinitely many constraints to provide reliable safety certificates. In this paper, we propose exchange policy optimization (EPO), an algorithmic framework that achieves optimal policy performance with provably bounded safety guarantees. EPO operates by iteratively solving safe RL subproblems restricted to a finite constraint set, adaptively adjusting the active set through constraint expansion and deletion. Specifically, at each iteration, constraints violating a predefined tolerance are added to refine the policy, while those with zero Lagrange multipliers are removed after the policy update. This exchange rule limits the subproblem complexity to ensure computational tractability while driving policy convergence. Theoretically, we establish that, under mild assumptions, EPO achieves finite convergence to a policy that both ensures the optimal reward performance and keeps the global constraint violation within the prescribed tolerance. Furthermore, we derive an upper bound on the required number of iterations and quantify the gap between the obtained policy and the true optimum.
Jiaming Zhang, Yujie Yang, Haoning Wang et al.· 0 citations
Predict-Then-Optimize combines machine learning predictions with downstream optimization to support decision-making when problem parameters are unknown at the time of solving. However, better predictive performance does not necessarily lead to better decisions, making it useful to assess this relationship before investing in the development of a prediction model. Existing simulation-based approaches enable such ex-ante evaluation, but are limited to binary classification and may require solving the downstream optimization problem many times. We generalize this methodology to optimization problems with categorical uncertain parameters by introducing a method for simulating multiclass predictions at prescribed performance levels and using it to construct a prediction-error-to-decision-regret mapping. To reduce the computational effort required to obtain this mapping, we also propose a first-order approximation based on the regret caused by individual misclassifications. Computational experiments confirm that the proposed prediction simulation algorithm reproduces the target classification performance and that the first-order approximation closely matches the simulation-based error-to-regret mapping for some problems. Its accuracy decreases when interactions between simultaneous misclassifications become more important. These results demonstrate the potential of the proposed approach and identify new questions about when simple approximations of the error-to-regret relationship are sufficiently accurate.
Min cut is an important graph partitioning method. However, current solutions to the min cut problem suffer from slow speeds, difficulty in solving, and often converge to simple solutions. To address these issues, we relax the min cut problem into a double-bounded constraint and, for the first time, treat the min cut problem as a double-bounded nonlinear optimal transport problem. Additionally, we develop a method for solving double bounded nonlinear optimal transport based on the Frank-Wolfe method (abbreviated as DNF). We prove that for convex problems satisfying Lipschitz smoothness, the DNF method can achieve a convergence rate of \(\mathcal{O}(\frac{1}{t})\). We apply DNF to size-constrained min-cut clustering and evaluate it on eight benchmark datasets. DNF achieves competitive clustering performance and matches or outperforms the compared baselines on several datasets and metrics.
Fangyuan Xie, Jinghui Yuan, Feiping Nie et al.· 0 citations
Semi-supervised anomaly detection is based on the principle that any record that looks different from normal training data is a potential anomaly. However, in some cases we are specifically interested in anomalies that correspond to high attribute values (or low, but not both). For distance-based methods, we propose an asymmetrical distance measure that takes this monotonicity into account by incorporating the ramp function. For the Isolation Forest algorithm, we propose a modified path length algorithm. Through experiments on synthetic and real-life datasets, we show that these proposals increase anomaly detection performance on datasets with monotonic attributes.
Oliver Urs Lenz, Matthijs van Leeuwen· 0 citations
Ensemble learning is a method that leverages weak learners to produce a strong learner. However, obtaining a large number of base learners requires substantial time and computational resources. Therefore, it is meaningful to study how to achieve the performance typically obtained with many base learners using only a few. We argue that to achieve this, it is essential to enhance both classification performance and generalization ability during the ensemble process. To increase model accuracy, each weak base learner needs to be more efficiently integrated. It is observed that different base learners exhibit varying levels of accuracy in predicting different classes. To capitalize on this, we introduce confidence tensors $\tilde{\mathbf{\Theta}}$, where $\tilde{\mathbf{\Theta}}_{rst}$ signifies the degree of confidence that the $t$-th base classifier assigns the sample to class $r$ while it actually belongs to class $s$. To the best of our knowledge, this is the first time an evaluation of the performance of base classifiers across different classes has been proposed. The proposed confidence tensor compensates for the strengths and weaknesses of each base classifier in different classes, enabling the method to achieve superior results with a smaller number of base learners. To enhance generalization performance, we design a smooth and partially convex objective function that leverages the concept of margin, making the strong learner more discriminative. Furthermore, it is proved that in the gradient matrix of the loss function, the sum of each column's elements is zero, allowing us to solve a constrained optimization problem using gradient-based methods.
Jinghui Yuan, Weijin Jiang, Zhe Cao et al.· 0 citations
Large language models (LLMs) are widely used in decision-making across diverse domains. Ensuring the generation of safe and reliable responses is critical for the effective deployment of LLM-based applications, particularly in high-stakes domains such as healthcare and finance. Most of these applications typically use carefully crafted prompts to guide response generation; however, the relationship between prompts and the reliability of LLM-generated responses is not yet fully understood. To address this gap, we propose a novel prompt-response concept model that explains the relationship between the amount of task-relevant information (informativeness) provided in the prompt and the LLM-generated response uncertainty by identifying four sources of response uncertainty: prompt underspecification, model quality, task variability, and semantic redundancy. We prove that response uncertainty decreases as prompt informativeness or model quality increases, mirroring the behavior of epistemic uncertainty in probabilistic models. Our experimental results on real-world datasets further validate our proposed model and corroborate the theoretical results.
Ze Yu Zhang, Arun Verma, Finale Doshi-Velez et al.· 0 citations
In traditional models of supervised learning, the goal of a learner-- given examples from an arbitrary joint distribution on $\mathbb{R}^d \times \{\pm 1\}$-- is to output a hypothesis that is competitive (to within $\epsilon$) of the best fitting concept from some class. In order to escape strong hardness results for learning even simple concept classes, we introduce a smoothed-analysis framework that requires a learner to compete only with the best classifier that is robust to small random Gaussian perturbation.
This subtle change allows us to give a wide array of learning results for any concept that (1) depends on a low-dimensional subspace (aka multi-index model) and (2) has a bounded Gaussian surface area. This class includes functions of halfspaces and (low-dimensional) convex sets, cases that are only known to be learnable in non-smoothed settings with respect to highly structured distributions such as Gaussians.
Our definition of smoothed agnostic learning is an interpolation between the case where the instance distribution $D$ and the optimal classifier can be arbitrarily coupled (which corresponds to agnostic learning and $\sigma = 0$) and completely decoupled (when $\sigma = \infty$). This decoupling allows us to avoid worst-case concepts that can encode complexity-theoretic primitives.
Surprisingly, our analysis also yields new results for traditional non-smoothed frameworks such as learning with margin. In particular, we obtain the first algorithm for agnostically learning intersections of $k$-halfspaces in time $k^{\mathrm{poly}(\frac{\log k}{\epsilon \gamma}) }$ where $\gamma$ is the margin parameter. Before our work, the best-known runtime was exponential in $k$ (Arriaga and Vempala, FOCS' 99).
Gautam Chandrasekaran, Adam Klivans, Vasilis Kontonis et al.· 0 citations
We study gradient descent (GD) dynamics on logistic regression problems with large, constant step sizes. For linearly-separable data, it is known that GD converges to the minimizer with arbitrarily large step sizes, a property which no longer holds when the problem is not separable. In fact, the behaviour can be much more complex -- a sequence of period-doubling bifurcations begins at the critical step size $2/\lambda$, where $\lambda$ is the largest eigenvalue of the Hessian at the solution. Using a smaller-than-critical step size guarantees convergence if initialized nearby the solution: but does this suffice globally? In one dimension, we show that a step size less than $1/\lambda$ suffices for global convergence. However, for all step sizes between $1/\lambda$ and the critical step size $2/\lambda$, one can construct a dataset such that GD converges to a stable cycle. In higher dimensions, this is actually possible even for step sizes less than $1/\lambda$. Our results show that although local convergence is guaranteed for all step sizes less than the critical step size, global convergence is not, and GD may instead converge to a cycle depending on the initialization.
Si Yi Meng, Antonio Orvieto, Daniel Yiming Cao et al.· 0 citations
A weeklong summer workshop brought higher education faculty to campus to explore how AI and machine learning materials can be adapted for their classrooms.
A new machine-learning framework aims to improve the success rate of computational protein design while moving away from results that reproduce sequences found in nature.
MIT News · Artificial Intelligence· news.mit.eduAug 24, 2026
