论文检索

Optimization · Large Scale, Parallel and Distributed

Pierre Aguié, Mathieu Even, Laurent Massoulié

We analyze the Accelerated Noisy Power Method, an algorithm for Principal Component Analysis in the setting where only inexact matrix-vector products are available, which can arise for instance in decentralized PCA. While previous works have established that acceleration can improve convergence rates compared to the standard Noisy Power Method, these guarantees require overly restrictive upper bounds on the magnitude of the perturbations, limiting their practical applicability. We provide an improved analysis of this algorithm, which preserves the accelerated convergence rate under much milder conditions on the perturbations. We show that our new analysis is worst-case optimal, in the sense that the convergence rate cannot be improved, and that the noise conditions we derive cannot be relaxed without sacrificing convergence guarantees. We demonstrate the practical relevance of our results by deriving an accelerated algorithm for decentralized PCA, which has similar communication costs to non-accelerated methods. To our knowledge, this is the first decentralized algorithm for PCA with provably accelerated convergence.

Optimization · Zero-order and Black-box Optimization

Mingqian Li, Sina Zadeh, Raymundo Arroyave, Xiaoning Qian

In batch multi-objective Bayesian optimization (MOBO), it is often desirable to identify the whole Pareto optimal set, especially when considering the complicated interplay between different design criteria and constraints. This poses unique challenges in acquiring batches of both high quality and diversity to cover the Pareto front. We propose a novel acquisition strategy, Probability of Matching (POM), which evaluates both batch candidate quality and diversity by explicitly capturing the likelihood that all batch points are Pareto optimal, and the probability that they collectively cover the full Pareto set. To estimate the coverage probability and promote diversity, we incorporate non-replacement sampling principles, resulting in our new POM-guided batch MOBO method. Across synthetic benchmarks and real-world tasks, our method consistently outperforms state-of-the-art baselines on standard MOBO metrics as well as a new design-space coverage metric, Expected Minimum Distance (EMD), with comparable computational efficiency.

Deep Learning · Theory

Tho Tran Huu, Huu-Tuan Nguyen, Thien-Hai Nguyen, Nhat-Tri Ho, Viet Hoang Tran, Tho Quan, Tan Nguyen

Sparse Mixture-of-Experts (SMoE) architectures are now widely deployed in state-of-the-art language and vision models, where conditional routing allows scaling to very large networks. However, this very Top-$k$ expert selection that enables conditional routing also renders the SMoE map inherently discontinuous. In the vicinity of these discontinuity surfaces, even inputs that are arbitrarily close may activate substantially different sets of experts resulting in significantly different outputs. In this work we give a rigorous geometric and stochastic analysis of these discontinuities. We first classify them by order, determined by the number of tied experts at a switching event. Using measure-theoretic slicing arguments, we establish asymptotic volume estimates for the thickened discontinuity surfaces, showing that lower-order discontinuity sets dominate, whereas higher-order ones occupy a vanishingly small relative volume. Next, modeling random perturbations in the input space via a diffusion process, we prove that the path eventually encounter a discontinuity, and moreover that the first hit almost surely occurs on an order-1 discontinuity with explicit finite-time probability bounds. We further derive occupation-time bounds that quantify the duration the random path spend in the neighborhoods of each discontinuity order. These theoretical results imply that inputs are more likely to lie near lower order discontinuities. Motivated by this insight, we propose a simple smoothing mechanism that can be directly applied to existing SMoEs, softly incorporating experts near discontinuities; our analysis guarantees that the added computational overhead remains small while providing localized smoothing near discontinuities, and experiments across language and vision tasks show that smoothing not only enforces continuity of the SMoE map but also enhances empirical performance.

General Machine Learning · Clustering

Sayan Bhattacharya, Martín Costa, Silvio Lattanzi, Jakub Łącki, Nikos Parotsidis

We study the problem of dynamic facility location with non-uniform costs. Facility location is a central problem in unsupervised learning and in recent years the dynamic version of the problem has been extensively studied. In this paper, we study the setting where clients are added and deleted in real-time and one is interested in maintaining efficiently a stable and high-quality solution. Interestingly, we are able to show that on High Dimensional Euclidean metrics it is possible to obtain efficient algorithms for this problem. More formally, we obtain a randomized algorithm for dynamic facility location in $d$-dimensional Euclidean spaces with $\gamma$ approximation ratio, $O(\log m)$ amortized recourse and $\text{poly}(d) \cdot (m+n)^{O(1/\gamma)}$ amortized update time, for every sufficiently large constant $\gamma \geq 1$. Our result is the first efficient dynamic algorithm for the \emph{non-uniform} dynamic facility location problem in high-dimensional Euclidean spaces. It also provides a stronger recourse bound than the existing solutions.

Deep Learning · Large Language Models

Jose Javier Gonzalez Ortiz, Abhay Gupta, Christopher Rinard, Davis Blalock

Standard mixed-precision training of neural networks requires many bytes of accelerator memory for each model parameter. These bytes reflect not just the parameter itself, but also its gradient and one or more optimizer state variables. With each of these values typically requiring 4 bytes, training even a 7 billion parameter model can be impractical for researchers with less than 100GB of accelerator memory. We introduce FlashOptim, a suite of optimizations that reduces per-parameter memory by over 50% while preserving model quality and API compatibility. Our approach introduces two key techniques. First, we improve master weight splitting by finding and exploiting a tight bound on its quantization error. Second, we design companding functions that greatly reduce the error in 8-bit optimizer state quantization. Together with 16-bit gradients, these techniques reduce AdamW memory from 16 bytes to 7 bytes per parameter, or 5 bytes with gradient release. They also cut model checkpoint sizes by more than half. Experiments with FlashOptim applied to SGD, AdamW, and Lion show no measurable quality degradation on any task from a collection of standard vision and language benchmarks, including Llama-3.1-8B finetuning.

Deep Learning · Large Language Models

Mostafa Elhoushi, Nolan Dey, Alexander Pretko, Bin Zhang, Gavia Gray, Gurpreet Gosal, Abdulrahman Mahmoud, Shane Bergsma, Joel Hestness

Layer dropout (a.k.a.\ stochastic depth) has been shown to enable faster training, higher accuracy, and robustness to zero-shot layer pruning in both language and vision transformers. However, as models and datasets have scaled, dropout---particularly layer dropout---has largely disappeared from LLM pre-training recipes. While some prior work has reported that dropout can degrade accuracy, no comprehensive study has quantified, let alone mitigated, this effect. In this study, we show that layer dropout **should** be used in state-of-the-art LLM training, establishing best practices and scaling analysis for both training and post-training benefits. Concretely, with optimal layer distribution, time schedule, and optimizer hyperparameters, a 3.9B-parameter LLM can achieve \textbf{lower validation loss} while saving 20\% of training FLOPs. Moreover, layer dropout enables significant post-training optimizations, such as early exit, intermediate-layer skipping, and self-speculative decoding, yielding up to 1.7x inference speedup with negligible accuracy loss. Across more than 2400 training experiments, spanning models from 271M to 3.9B parameters and datasets up to 116B tokens, we demonstrate that these findings extend reliably to large-scale training regimes.

Shitong Shao, zikai ZHOU, Haopeng Li, Yingwei Song, Wenliang Zhong, Lichen Bai, Zeke Xie

Video editing has evolved toward In-Context Learning (ICL) paradigms, yet the resulting quadratic attention costs create a critical computational bottleneck. In this work, we propose **I**n-context **S**parse **A**ttention (**ISA**), the first experimentally lossless sparse framework tailored for ICL video editing. Our design is grounded in two key insights: __**first**__, context tokens exhibit significantly lower saliency than source tokens; __**second**__, we theoretically prove and empirically validate that Query sharpness correlates with approximation error. Motivated by these findings, ISA implements an efficient pre-selection strategy to prune redundant context, followed by a dynamic query grouping mechanism that routes high-error queries to full attention and low-error ones to a computationally efficient 0-th order Taylor sparse attention. Furthermore, we construct a scalable pipeline to curate a 1M-sample dataset and train __**LIVEditor**__, a novel lightning video editing model via ISA. Extensive experiments demonstrate that LIVEditor achieves a ~60% reduction in latency while surpassing state-of-the-art methods across EditVerseBench, IVE-Bench, and VIE-Bench, delivering experimentally lossless acceleration without compromising visual fidelity.

Theory · Online Learning and Bandits

Seoungbin Bae, Dabeen Lee

We study the problem of neural logistic bandits, where the main task is to learn an unknown reward function within a logistic link function using a neural network. Existing approaches either exhibit unfavorable dependencies on $\kappa$, where $1/\kappa$ represents the minimum variance of reward distributions, or suffer from direct dependence on the feature dimension $d$, which can be huge in neural network–based settings. In this work, we introduce a novel Bernstein-type inequality for self-normalized vector-valued martingales that is designed to bypass a direct dependence on the ambient dimension. This lets us deduce a regret upper bound that grows with the effective dimension $\widetilde{d}$, not the feature dimension, while keeping a minimal dependence on $\kappa$. Based on the concentration inequality, we propose two algorithms, NeuralLog-UCB-1 and NeuralLog-UCB-2, that guarantee regret upper bounds of order $\widetilde{O}(\widetilde{d}\sqrt{\kappa T})$ and $\widetilde{O}(\widetilde{d}\sqrt{T/\kappa})$, respectively, improving on the existing results. Lastly, we report numerical results on both synthetic and real datasets to validate our theoretical findings.

Applications · Computer Vision

Kaimin Yu, Puyun Wang, Huayang He, Xianyu Wu

Recovering surface normals from single-view polarization images in complex media remains challenging. This paper focuses on ice as a representative complex medium, where intricate light–matter interactions lead to a nonlinear mapping between polarization observations and surface normals. To address this, a structure-aware polarization prior based on autocorrelation functions is proposed to capture the local spatial consistency of AoLP. Building on this, a dual-branch network (IceSfP) is designed to integrate raw polarization features with priors via cross-modal attention and multi-scale feature fusion, enabling accurate surface normal estimation under complex media conditions. To evaluate the method, the first real-world ice SfP dataset is constructed. Experimental results show that the method outperforms existing approaches across all metrics, achieving a MAE of 16.01$^\circ$, which is 2.74$^\circ$ lower than the second-best method. The framework provides a generalizable solution for high-precision geometric perception in complex media.

Deep Learning · Everything Else

Akash Amalan, Georgios Smaragdakis, Tom Viering

Malware detection remains largely reactive: machine learning models trained on known samples degrade as threats evolve. Understanding evolutionary relationships among malware families can inform proactive defense, but traditional reverse engineering can take months to years to uncover such lineage relationships. We propose MalTree, a framework that applies bioinformatics-inspired phylogenetic techniques (UPGMA and Neighbor-Joining) at scale to model malware evolution automatically using structural, behavioral, and image-based features. We introduce temporal validation using VirusTotal timestamps to assess whether inferred trees reflect actual evolutionary order. MalTree achieves 87% temporal consistency, indicating that inferred evolutionary relationships closely align with real-world emergence timelines. Our analysis shows that some families mutate over 10 times faster than others, suggesting that detection strategies should be tailored to family-specific evolutionary tempos. Case studies, including the Mirai botnet, confirm that inferred relationships from our phylogenetic tree align with documented threat intelligence. Our framework provides a foundation for shifting malware analysis from sample-by-sample classification toward lineage-aware evolutionary modeling.

General Machine Learning · Online Learning, Active Learning and Bandits

Youngmin Oh

We study linear dueling bandits in volatile environments characterized by the simultaneous presence of post-serving contexts, delayed feedback, and adversarial corruption. Feedback is subject to unknown stochastic or adversarial delays and a cumulative corruption budget $\mathcal{C}$. To address these challenges, we propose \term, which integrates a learned approximator that predicts post-serving contexts from pre-serving information. It further employs an adaptive weighting strategy that clips feature vectors to mitigate the impact of corrupted and delayed observations simultaneously. Under standard regularity conditions and a parametric post-serving mapping, we rigorously establish that our algorithm is delay-regime-agnostic, achieving a regret upper bound of $\widetilde{\mathcal{O}}(d(\sqrt{T} + \mathcal{C} + \mathcal{D}))$, where $d$ is the total feature dimension and $\mathcal{D}$ encapsulates the delay complexity. Crucially, our analysis reveals an additive cost structure between corruption and delay, avoiding the multiplicative degradation typical of prior works. We further establish lower bounds that nearly match our upper bounds up to a $\sqrt{d}$ factor for adversarial delays in the absence of post-serving contexts.

Deep Learning · Everything Else

Quang-Anh N.D., Kok-Seng Wong

WiFi-based human pose estimation offers privacy-preserving and occlusion-robust sensing, but current Transformer-based approaches suffer from quadratic complexity and lack explicit inductive biases for Channel State Information structure. We propose WiFi-Mamba, the first State Space Model architecture for WiFi-based 3D multi-person pose estimation. Our approach introduces three key contributions: (1) a Dual-Stream Selective State Space Model that processes amplitude and phase through parallel pathways with cross-stream state coupling to respect their distinct physical properties, (2) Selective State Attention for pose query decoding with SSM-derived sequential context, and (3) Persistent SSM Memory for temporal consistency across frames without recurrent memory explosion. Extensive experiments on the Person-in-WiFi 3D dataset, covering both single-person and multi-person scenarios, demonstrate 16-27% MPJPE reduction across varying numbers of persons while using only 4.4% of baseline parameters (2.14M vs. 48.2M), achieving superior efficiency-accuracy trade-offs particularly beneficial for edge deployment in privacy-sensitive continuous monitoring scenarios.

Applications · Language, Speech and Dialog

Talor Abramovich, Maor Ashkenazi, Izzy Putterman, Benjamin Chislett, Tiyasa Mitra, Bita Darvish Rouhani, Ran Zilberstein, Yonatan Geifman

Speculative Decoding (SD) has emerged as a critical technique for accelerating Large Language Model (LLM) inference. Unlike deterministic system optimizations, SD performance is inherently data-dependent, meaning that diverse and representative workloads are essential for accurately measuring its effectiveness. Existing benchmarks suffer from limited task diversity, inadequate support for throughput-oriented evaluation, and a reliance on high-level implementations that fail to reflect production environments. To address this, we introduce **SPEED-Bench**, a comprehensive suite designed to standardize SD evaluation across diverse semantic domains and realistic serving regimes. SPEED-Bench offers a carefully curated *Qualitative* data split, selected by prioritizing semantic diversity across the data samples. Additionally, it includes a *Throughput* data split, allowing speedup evaluation across a range of concurrencies, from latency-sensitive low-batch settings to throughput-oriented high-load scenarios. By integrating with production engines like vLLM and TensorRT-LLM, SPEED-Bench allows practitioners to analyze system behaviors often masked by other benchmarks. We highlight this by quantifying how synthetic inputs overestimate real-world throughput, identifying batch-size dependent optimal draft lengths and biases in low-diversity data, and analyzing the caveats of vocabulary pruning in state-of-the-art drafters. We release SPEED-Bench to establish a unified evaluation standard for practical comparisons of SD algorithms.

Deep Learning · Generative Models and Autoencoders

Adrian Rodriguez-Munoz, William Daspit, Adam Klivans, Antonio Torralba, Constantinos Daskalakis, Giannis Daras

We propose Ambient Dataloops, an iterative framework for refining datasets that makes it easier for diffusion models to learn the underlying data distribution. Modern datasets contain samples of highly varying quality, and training directly on such heterogeneous data often yields suboptimal models. We propose a dataset-model co-evolution process; at each iteration of our method, the dataset becomes progressively higher quality, and the model improves accordingly. To avoid destructive self-consuming loops, at each generation, we treat the synthetically improved samples as noisy, but at a slightly lower noisy level than the previous iteration, and we use Ambient Diffusion techniques for learning under corruption. Empirically, Ambient Dataloops achieve state-of-the-art performance in unconditional and text-conditional image generation and de novo protein design. We further provide a theoretical justification for the proposed framework that captures the benefits of the data looping procedure.

Theory · Everything Else

Daniel Cao, August Chen, Karthik Sridharan, Yuchen Wu

We consider the robustness of score-based generative modeling to errors in the estimate of the score function. In particular, we show that Langevin dynamics is not robust to the $L^2$ errors (more generally $L^p$ errors) in the estimate of the score function. It is well-established that with small $L^2$ errors in the estimate of the score function, diffusion models can sample faithfully from the target distribution under fairly mild regularity assumptions in a polynomial time horizon. In contrast, our work shows that even for simple distributions in high dimensions, Langevin dynamics run for any polynomial time horizon will produce a distribution far from the target distribution in Total Variation (TV) distance, even when the $L^2$ error (more generally $L^p$) of the estimate of the score function is arbitrarily small. Considering such an error in the estimate of the score function is unavoidable in practice when learning the score function from data, our results provide further justification for diffusion models over Langevin dynamics and serve to caution against the use of Langevin dynamics with estimated scores.

Applications · Chemistry, Physics, and Earth Sciences

Abdel-Rahim Mezidi, Jordan Patracone, Amaury Habrard

Operator splitting methods are at the foundation of many numerical solvers for partial differential equations. In parallel, unrolled and hybrid learning-based architectures have been introduced to enhance classical solvers, but their design is rarely linked to the underlying problem structure. In this work, we propose a unifying framework that explicitly links operator splitting algorithms from optimization with unrolled hybrid architectures. We show that each operator splitting scheme naturally defines an unrolled architecture, which recovers a wide range of existing plug-and-play and hybrid models as special cases. Using this framework, we design new unrolled hybrid architectures and validate them on benchmark fluid dynamics simulations, where they achieve improved accuracy and stability.

Social Aspects · Accountability, Transparency, and Interpretability

Yixin Wang, Yucheng Dong

Local post-hoc explanations are widely used to understand black-box models on tabular data, with Local Interpretable Model-agnostic Explanations (LIME) being a popular approach. LIME approximates a black-box model using a sparse linear surrogate in a local neighborhood, implicitly assuming feature-wise linear homogeneity. However, this assumption often fails when local feature effects exhibit heterogeneous or nonlinear behaviors, resulting in unfaithful and unstable explanations. Moreover, LIME relies on a decoupled feature selection procedure that is not aligned with the surrogate modeling objective, further exacerbating instability under local sampling. To address these limitations, we propose PL-LIME, a two-stage sparse local explanation framework that ensures objective consistency across stages. PL-LIME models feature-wise local effects using instance-anchored piecewise linear functions, providing a minimal yet principled extension beyond linear surrogates under a fixed explanation budget. Sparsity is enforced through a decoupled nonnegative shrinkage procedure that directly scales the estimated local effects, improving stability while preserving interpretability. Experiments on synthetic and real-world datasets demonstrate that PL-LIME achieves higher local fidelity and stability, and provides more reliable local explanations that capture finer-grained local effect structures than LIME.

Applications · Computer Vision

Shangwen Zhu, Qianyu Peng, Zhilei Shu, Yuting Hu, Han Zhang, Andy Zheng, Xinyu Cui, Jian Zhao, Ruili Feng, Fan Cheng

High-fidelity text-to-image and text-to-video generation typically relies on Classifier-Free Guidance (CFG), but achieving optimal results often demands computationally expensive sampling schedules. In this work, we propose MAMBO-G, a training-free acceleration framework that significantly reduces computational cost by dynamically optimizing guidance magnitudes. We observe that standard CFG schedules are inefficient, applying disproportionately large updates in early steps that hinder convergence speed. MAMBO-G mitigates this by modulating the guidance scale based on the update-to-prediction magnitude ratio, effectively stabilizing the trajectory and enabling rapid convergence. This efficiency is particularly vital for resource-intensive tasks like video generation. Our method serves as a universal plug-and-play accelerator, achieving up to 3$\times$ speedup on Stable Diffusion v3.5 (SD3.5) and 4$\times$ on Lumina. Most notably, MAMBO-G accelerates the 14B-parameter Wan2.1 video model by 2$\times$ while preserving visual fidelity, offering a practical solution for efficient large-scale video synthesis. Our implementation follows a mainstream open-source diffusion framework and is plug-and-play with existing pipelines.

Theory · Reinforcement Learning and Planning

Yivan Zhang, Ziyan Luo, Manuel Baltieri

State abstraction plays a central role in scaling reinforcement learning to complex but structured systems. In studying such systems, a wide range of behavioral structures have been proposed in reinforcement learning, including value functions, invariants, bisimulation relations, and behavioral metrics. However, a general principle for determining what structures are provably preserved under state abstraction is still lacking. In this paper, we present a unified framework for defining and analyzing behavioral structures in reinforcement learning. Our framework provides a compositional way to specify behavioral semantics and metrics based on local, one-step descriptions of system dynamics. Using this framework, we establish results showing how behavioral structures can be safely transferred between abstract and concrete systems. We further show how to construct quantitative metrics from logical behavioral semantics with soundness guarantees. Together, these results provide a principled foundation for reasoning about behaviors under state abstraction in reinforcement learning and offer reusable definition and proof principles for a broad class of behavioral structures in reinforcement learning.

Deep Learning · Robustness

Peiyu Yang, Paul MONTAGUE, Feng Liu, Andrew C. Cullen, Amar Kaur, Christopher Leckie, Sarah Erfani

Vision-language models (VLMs) are now widely used in downstream tasks. However, real-world applications often expose VLMs to distribution shifts induced by semantic variation (e.g., shape, size, and style). Robustness certification determines if a model’s prediction changes when transformations are applied to its input. While most certification frameworks study geometric or pixel-level transformations over inputs, this work proposes a novel framework that enables certifying VLM robustness under semantic-level transformations. Leveraging the open-vocabulary capability of VLMs, we use text prompts as semantic proxies to construct transformations parameterized by an extent that controls the degree of semantic variation. By characterizing the VLM decision boundary in closed form, our framework quantitatively certifies extent intervals for which the predicted class remains unchanged under the semantic transformation. Our framework is the first to certify VLM robustness under semantic-level variations without requiring additional data for each variation, making it practical to apply. Experiments on both synthetic and real-world data show that our framework enables certifying robustness under diverse semantic variations across scenarios.