NeurIPS 2026 Papers

Conference on Neural Information Processing Systems

Decision breakdown

6,437papers

Counted from the official paper list; may differ slightly from the number the conference announced.

  • Oral
    991.5%
  • Spotlight
    2403.7%
  • Poster
    6,09894.7%

Browse all papers

Topic: Simulation for Driving · 940 papers · Reset filters

NuMuon: Nuclear-Norm-Constrained Muon for Compressible LLM Training

Hadi Mohaghegh Dolatabadi, Thalaiyasingam Ajanthan, Sameera Ramasinghe, Chamin Hewa Koneputugodage, Shamane Siriwardhana, Violetta Shevchenko, Karol Pajak, James Snewin, Gil Avraham, Alexander Long

Expand abstract

The rapid progress of large language models (LLMs) is increasingly constrained by memory and deployment costs, motivating compression methods for practical deployment. Many state-of-the-art compression pipelines leverage the low-rank structure of trained weight matrices, a phenomenon often associated with the properties of popular optimizers such as Adam. In this context, Muon is a recently proposed optimizer that improves LLM pretraining via full-rank update steps, but its induced weight-space structure has not been characterized yet. In this work, we report a surprising empirical finding: despite imposing full-rank updates, Muon-trained models exhibit pronounced low-rank structure in their weight matrices and are readily compressible under standard pipelines. Motivated by this insight, we propose *NuMuon*, which augments Muon with a nuclear-norm constraint on the update direction, further constraining the learned weights toward low-rank structure. Across billion-parameter-scale models, we show that NuMuon increases weight compressibility and improves post-compression model quality under state-of-the-art LLM compression pipelines while retaining Muon's convergence behavior.

Poster
Not All Routing Drift Is Harmful: Trust-Region Projection for Class-Incremental Learning

Tae-Hwan Kim, Sung-Bae Cho

Expand abstract

Class-incremental learning (CIL) with pre-trained models has increasingly adopted Mixture-of-Experts (MoE) adapters, which freeze the backbone and selectively route inputs to sparse adapter subsets, achieving competitive performance through efficient parameter reuse. However, as new tasks are learned sequentially, the router's output distribution gradually shifts away from previous states, undermining consistent adapter reuse and accelerating forgetting. Through a controlled instance-level analysis, we show that this effect is highly asymmetric, where instances with large routing drift account for most of the performance degradation, while those with small drift remain stable or can even benefit from it. This finding suggests that only excessive drift requires correction, while small drift may be better preserved than suppressed, and motivates us to propose Trust-Region Projected Routing (TRPR) that adapts the trust-region principle from constrained optimization to routing stabilization. It constrains each input's routing distribution within a KL-bounded trust region around a class-level anchor, correcting only excessive deviations while leaving small drift intact. To complement class-level anchoring with per-sample adaptability, TRPR additionally introduces an Instance-Adaptive (IA) path for fine-grained per-sample specialization, fused with the projected path via a learned gate. Extensive experiments on four CIL benchmarks show that TRPR consistently outperforms nine representative PEFT-based baselines, with accuracy gains of up to 3.06% in average and final accuracy and forgetting reduced by up to 2.48%.

Poster
Not All Instances Should Contribute Equally: Sparse Support Grounding via Unbalanced Transport for Heterogeneous MIL

Hojoon Kim, Beomgu Kang, Hyunseok Seo

Expand abstract

Multiple instance learning (MIL) learns from bag-level labels, but a bag’s label is often supported by only a few hidden instances. In heterogeneous bags, these useful instances are rare, diverse, and surrounded by many weak or noisy observations. We propose Sparse Support Grounding, a MIL framework that learns instance influence directly. The key idea is simple: an instance should not matter just because it can be matched somewhere; it should matter when the match provides reliable label evidence. Our method forms a compact, bag-specific evidence support, compares instances with label-consistent supports, and uses unbalanced transport to estimate how much source mass each instance should retain. This retained mass becomes the strength of its grounding signal, so reliable evidence shapes training more than nuisance content, while the bag classifier still uses the full bag. Thus, transport is turned from a matching rule into a way of learning which instances should drive supervision. Experiments on synthetic MIL, whole-slide images, and clinical endomicroscopy show consistent gains, with the largest improvements when sparse diagnostic evidence is embedded in heterogeneous nuisance content.

Poster
Nonlinear Direct Feedback Alignment for Scalable Backpropagation-Free Training

Wu Lin, Yan Fan, Chenxiang Ma, Yinglan Feng, Jia Wang, Ka-Chun Wong, Qiuzhen Lin

Expand abstract

Backpropagation (BP) remains the predominant algorithm for training deep neural networks, but it is biologically implausible and suffers from the backward locking problem, constraining parallelization across layers. Direct Feedback Alignment (DFA), which propagates the global output error directly to each hidden layer via fixed feedback matrices, has emerged as a promising alternative for addressing these limitations. However, a significant performance gap persists between DFA and BP, which we attribute to the limited ability of fixed feedback matrices to capture the nonlinear transformation from hidden representations to the network output. To address this limitation, we propose Nonlinear Direct Feedback Alignment (NDFA), which constructs each hidden-layer feedback using a lightweight nonlinear surrogate subnetwork. To enhance the effectiveness of the feedback throughout training, we further propose a learning strategy to update the surrogate subnetwork, thereby better approximating the underlying nonlinear transformation. Extensive experiments across residual networks and vision transformers on CIFAR-10, CIFAR-100, SVHN, and ImageNet datasets demonstrate that NDFA consistently outperforms existing DFA-based methods and substantially narrows the performance gap to BP, while maintaining efficient parallel training. Code will be publicly available after the review process.

Poster
Non-Linear Pricing Restores Tractability for a Data Seller

Bhaskar Ray Chaudhury, Jugal Garg, Eklavya Sharma, Jiaxin Song

Expand abstract

We consider a data seller who designs pricing mechanisms over multiple datasets to maximize revenue from budget-constrained buyers. The seller offers multiple datasets and assigns each a pricing function that maps the quantity purchased to a total payment. The goal is to design these pricing functions to maximize revenue, anticipating that buyers—who trade off accuracy gains against cost—choose bundles optimally subject to their budget constraints. Prior work [Chaudhury et al., 2026] studies such optimal pricing under the restriction that each dataset is assigned a linear price, and shows that computing optimal linear prices is computationally intractable. In contrast, we allow each dataset to be priced via a general function and show that this additional flexibility can not only increase the revenue but also restore tractability, yielding a surprising simultaneous improvement in economic performance and computational efficiency. Even when pricing functions are only required to be monotone and lower-continuous, optimal pricing admits a highly structured and simple form: each pricing function is piecewise linear and convex (PLC), and the optimal solution can be computed in polynomial time. Moreover, the total number of kinks across all pricing functions is bounded by the number of buyers. Consequently, when datasets significantly outnumber buyers, most pricing functions are effectively linear. We further empirically study the structure of optimal pricing by analyzing the number of kinks and the revenue gap between optimal nonlinear pricing and optimal linear pricing on simulations generated from a real dataset.

Poster
Non-Expanding Gated Continued Fraction Architecture for Feedforward Layers in Language Models

Amit Dhurandhar, Vijil Chenthamarakshan, Karthikeyan Natesan Ramamurthy, Dennis Wei, Rahul Nair

Expand abstract

Recent work has shown that continued fraction inspired neural architectures (CoFrGeNets) can be highly parameter efficient yet performant for language modeling. In this work, we revisit continued fraction-based channel mixing with the goal of improving its performance and simplifying integration into standard pre-training protocols for language models. We achieve this by two simple yet critical contributions: i) we propose a novel non-expanding gated continued fraction inspired architectural component to replace feedforward layers in established language model architectures that may use vanilla multilayer perceptrons or gated linear units or (vanilla/gated) experts in mixture-of-experts (MoE) type architectures. ii) We propose a way to re-implement divisions -- the non-linearity in these architectures -- in terms of logarithms and exponentials. By experimenting on different language modeling architectures such as GPT-2, Llama-3, Mamba-2 and (nano) Llama-MoE we find that our proposed architecture performs similarly or significantly better than the continued fraction architecture proposed in prior work along with having higher throughput. In addition, our re-implementation of divisions makes training of deeper CoFrGeNets stable without the need for incremental training which was proposed in prior work as a means to stabilize training, but added notable complexity to existing large language model training implementations.

Poster
No Free Alignment: Observability-Aware Alignment for Multimodal Heterogeneous Learning

Canran Xiao, Puning Zhao, Enneng Yang, Xiaochun Cao, Haobo Fu, Li Shen

Expand abstract

Multimodal heterogeneous learning aims to train reliable multimodal models when data sources differ in modality availability, semantic coverage, domain distribution, and missingness patterns. Although cross-modal alignment is widely used to mitigate such heterogeneity, we argue that alignment is not free: enforcing relations that are weakly supported by the observed data can amplify noise, over-transfer missing-modality information, and induce negative transfer. This paper studies when a modality--modality--semantic relation is sufficiently observable to be safely aligned and shared across heterogeneous sources. We propose **ObsAlign**, an observability-aware framework that summarizes visible modality--semantic evidence through compact source-level sketches and estimates relation-level support from bridge evidence, side support, cross-modal consistency, and prototype uncertainty. The resulting observability score gates co-observed alignment, calibrates weak missing-modality transfer, and guides evidence-aware source consolidation so that reliable relations are shared while unsupported variation remains local. Across image--text, audio--visual--text, action-recognition, sensor, and healthcare benchmarks under source-partitioned multimodal heterogeneity, ObsAlign achieves the best overall performance in both encoder-based and VLM-compatible regimes, while sharply reducing negative transfer on low-observability relations. These results suggest that relation-level observability provides a practical principle for deciding when cross-modal alignment should be strengthened, weakened, or avoided.

Poster
NitroBox: Lightning-Fast Sandbox for Large-Scale RL Training

Yuzhou Nie, Ruilin Zhou, Zhaorun Chen, Jingyang Zhang, Yan Shao, Hongwei Li, Bo Li, Dawn Song, Wenbo Guo

Expand abstract

Recent work on agentic training efficiency has mainly focused on improving learning algorithms, rollout strategies, or model-hardware co-design. However, these approaches overlook an important source of training latency: the sandbox that runs the environments. Recent studies show that creating, executing, and resetting containers accounts for an important portion of the rollout process in RL training, substantially slowing down overall training. This overhead largely stems from the centralized management mechanisms (e.g., DAEMON) of existing sandboxes, along with additional features (e.g., multi-tenancy) that are unnecessary for reinforcement learning (RL). Moreover, existing sandboxes are designed for general-purpose isolated execution, making them a poor fit for the requirements of RL rollout and training. We propose NitroBox, a novel sandbox system purpose-built for agentic RL that significantly accelerates the rollout and training process. Technically speaking, we first comprehensively redesign NitroBox's lifecycle to eliminate the dependency on DAEMON, so that every sandbox instance is fully independent during creation, startup, and reset (e.g., via rootless full-namespace isolation). Furthermore, we introduce a copy-on-write mechanism to enable fast startup across multiple instances. Second, we knock off features that are time-consuming but unnecessary for RL — such as multi-tenancy — while preserving the core functionality and security guarantees needed for RL training. Finally, we introduce some RL-nature features to further improve efficiency, such as optional CRIU-based process checkpoint saving and restoring for mid-trajectory branching. Our experiments show that NitroBox is faster than Docker across the entire lifecycle: 10.6× faster in sandbox creation, 24.6× in reset, and 19.1× in deletion. When training Qwen2.5-Coder-32B-Instruct with GRPO at c=32 concurrency, end-to-end wall-clock training time drops from 40.6 hours to 28.4 hours when replacing Docker with NitroBox, while preserving the same task pass rate.

Poster
New Coresets for Fair Clustering

Xuan Wu, Chansophea Wathanak In, Yi Li

Expand abstract

We construct the first coreset of size near-linear in $k$ for fair \kMedian in general metric spaces. Combined with the standard merge-and-reduce framework, our construction also gives the first streaming algorithm for fair \kMedian with space complexity near-linear in $k$. The main technical innovation is a distributional reinterpretation of capacitated clustering that the cost of assigning a dataset to a capacitated center set can be expressed as the earth mover's distance between two discrete distributions. This viewpoint enables us to use tools from optimal transport to analyse uniform sampling. A key ingredient in this analysis is a new family of problem-specific $\eps$-nets for the earth mover's distance.

Poster
Never Go Full Batch: Stochastic TMLE for Large-Scale Debiased Inference

Diyang Li, Fei Wang, Kyra Gan

Expand abstract

Targeted Minimum Loss-based Estimation (TMLE) is a classical plug-in debiasing methodology that delivers doubly robust estimation and asymptotically efficient inference. Despite its statistical guarantees, each iteration of standard TMLE requires solving a minimization subproblem over the entire dataset, resulting in prohibitive computational and memory costs that render the method impractical for large-scale or real-time settings. To ease the bottlenecks, we introduce stochastic TMLE, a randomized targeting procedure that replaces each expensive full-batch fluctuation fit with mini-batch alternatives. Our theoretical analysis establishes that the stochastic iterates converge to a neighborhood (noise ball) centered around the target solution, and crucially, only a small number of subsequent full-sample TMLE iterations suffice to reach an empirical efficient influence function root. Consequently, our stochastic variant inherits the same guarantees and attractive properties as classical TMLE while substantially reducing per-iteration complexity. We further propose two computational variants with provable guarantees that broaden the algorithmic design space, offering flexibility for future developments in scalable targeted learning. Extensive experiments across diverse regimes demonstrate substantial acceleration over standard TMLE without sacrificing inferential quality.

Poster
Neutral-atom quantum features as complementary structural encodings for graph learning

Igor Sokolov, Mathieu Garrigues, Matthias Hecker, Lorenzo Moro, Shaheen Acheche

Expand abstract

Structural descriptors provide graph neural networks (GNNs) with positional and topological inductive biases. However, widely used classical encodings based on random walks or Laplacian spectra emphasize specific structural statistics of a graph, leaving room for alternative descriptors. Neutral-atom quantum processing units (QPUs) can realize graph-dependent Rydberg Hamiltonians, allowing graph topology to be probed through dynamical correlation measurements. In this work, we use these measurements as quantum graph features (QGFs), providing a complementary, hardware-derived family of structural encoding that --- as we demonstrate empirically --- is not accurately described by classical features derived from Laplacian or adjacency matrix. By appropriately selecting the quench parameters of the Hamiltonian, we access two characteristic correlation regimes with distinct structural signatures: antiferromagnetic-like and ferromagnetic-like. On an intrinsic information benchmark of 15 topological and spectral probing tasks, quantum and hybrid quantum-classical features match or surpass classical descriptors on local topological properties. When supplied to message-passing, attention, and graph-transformer backbones, hybrid quantum-classical features yield small improvements that are within cross-fold noise on most cells but sign-consistent across architectures. When comparing noiseless emulation-derived quantum features with an end-to-end neutral-atom QPU implementation, the downstream hybrid gain over the classical baseline persists on five out of six backbones.

Poster
Neurosymbolic Learning for Inference-Time Argumentation

Gabriel Freedman, Adam Dejl, Adam Gould, Mansi -, Lihu Chen, Junqi Jiang, Francesca Toni

Expand abstract

Claim verification is an important problem in high-stakes settings, including health and finance. When information underpinning claims is incomplete or conflicting, uncertain answers may be more appropriate than binary true or false classifications. In all cases, faithful explanations of the considerations determining the final verdict are crucial. We introduce inference-time argumentation (ITA), a trainable neurosymbolic framework for ternary claim verification in which a formal argumentation semantics giving the strength of claims is used both (i) to guide LLM training as models learn to generate arguments and assign them base scores (representing intrinsic strengths) and (ii) to compute ternary (true/false/uncertain) predictions from generated, scored arguments. As a result, at training time, argument generation and scoring can be optimised according to the quality of the induced argumentative predictions. Moreover, at inference time, the final prediction is faithful, by construction, to the arguments and scores determining the verdict, rather than being justified by a potentially unfaithful post-hoc reasoning trace as in conventional reasoning models. We finally show that, on two datasets for ternary claim verification, ITA improves upon argumentative baselines and can perform competitively against non-argumentative direct-prediction baselines, while providing verdicts that are computed deterministically from explicit, inspectable argumentative structures.

Poster
Neuronal Identity as an Organizational Basis for Analyzing Neural Population Dynamics

Seungjae Han, Joshua Y You, Soi Kim, Minho Eom, Jinho Park, Seunghee Park, Byeongwook Lee, Young-Gyu Yoon

Expand abstract

Individual neurons exhibit diverse molecular, morphological, and electrophysiological properties that shape their distinct roles in neural circuits. While these multimodal features are largely shared across individuals, they remain an underutilized source of information in analyzing neural population dynamics. We posit that these shared biological profiles provide a common reference for relating neural dynamics across subjects and recording sessions. Our framework leverages this structure by routing neurons into latent groups based on their biological profiles and analyzing population dynamics through group-level representations. Because these assignments are anchored in biological properties that are consistent across subjects, the learned organization supports transfer to unseen animals without retraining or neuron-wise correspondence. We evaluate our framework on whole-brain calcium imaging in larval zebrafish and large-scale electrophysiology in the mouse visual cortex. Across both species and recording modalities, the framework delivers state-of-the-art performance in both neural decoding and manifold analysis: it achieves superior decoding of behavior and stimulus labels while better preserving the temporal consistency and local geometric structure of latent trajectories on unseen data. Our experiments demonstrate that not only does providing biological features improve baseline performance, but our proposed framework achieves even stronger results by using these properties to explicitly structure the population rather than treating them as auxiliary inputs. Together, these results suggest that organizing neural populations by their multimodal biological features offers a promising framework for generalizing population dynamics across subjects and recording sessions.

Poster
Neuromodulated Constrained Autoencoders for Context-Dependent Manifold Learning

Jérôme Adriaens, Gustave Bainier, Guillaume Drion, Pierre Sacré

Expand abstract

Many physical systems exhibit a low-dimensional structure that varies with external parameters: link lengths in a robot, forcing constants in a fluid, or Reynolds numbers in a flow shift the underlying manifold while preserving its intrinsic dimension. Constrained AutoEncoders (cAEs) learn such manifolds through an *idempotent* encoder-decoder projection, a property that unconstrained autoencoders cannot match and that is essential whenever the model is applied iteratively. However, the standard strategies for making a cAE context-dependent, namely concatenating the context to the input or affinely modulating hidden activations, break the encoder-decoder idempotency, sacrificing the projection guarantee precisely in the setting where it would be most valuable. To restore this guarantee under context variation, we developed the Neuromodulated Constrained Autoencoder (NcAE), which modulates the activation slope and bias of a cAE through a context-driven hyper-network. This paper presents the NcAE, its theoretical foundation, and its empirical validation. We prove that for every context, including contexts unseen at training time, the reconstruction map remains an idempotent projection, the topology of the learned manifold is invariant, and context perturbations induce smooth changes in the manifold. We evaluated our approach on a 16-DoF pendulum with context dependent coupling and the Lorenz96 system across a bifurcation. The NcAE matched or exceeded the best of six baselines on reconstruction, idempotency, and latent-geometry metrics, while being the only architecture that preserves geometric consistency by construction. The NcAE thereby provides a stable, geometry-preserving coordinate system across families of physical regimes.

Poster
NeuralBES: A Differentiable, Control-Aware Emulator for Scalable Building Energy Modeling

Ting-Yu Dai, Takuya Kurihana, Wing Yee Au, YUNG WONG

Expand abstract

Demand-side flexibility, i.e., forecasting, shifting, and curtailing residential energy loads, depends on thermal models trusted across millions of heterogeneous buildings. Existing tools force a hard tradeoff: high-fidelity physics simulators such as EnergyPlus are accurate but sequential and require per-building calibration, while purely data-driven sequence models scale but abandon the physical structure that makes their predictions trustworthy. We introduce NeuralBES (Building Energy Simulation), a differentiable emulator that resolves this tradeoff by parameterizing a resistance--capacitance (RC) based thermal model with a shared neural encoder: static building metadata such as floor area, vintage, and HVAC type is mapped to physically bounded capacitances, conductances, and equipment coefficients, which become the coefficients of a scalar linear recurrence solved via a log-space parallel scan, and a predictor--corrector loop closes the thermostat--temperature nonlinearity while preserving full-horizon gradient flow. Trained on the ResStock dataset across three climate zones, NeuralBES handles heterogeneous building archetypes, vintages, and climate zones within a single trained encoder, while black-box baselines produce statistically plausible but physically inconsistent trajectories. On the annual full-year rollout, NeuralBES is the only data-conditioned model that is simultaneously physics-valid and accurate to within 4 MAPE points of the strongest raw-error baseline, while operating at roughly an order of magnitude fewer parameters than the transformer and recurrent baselines; among physics-valid baselines at parameter parity it more than halves the MAPE of the grey-box RC alternative.

Poster
Neural Operator-based Curriculum Learning for Physics-Informed Neural Networks

Lingshi MENG, Haosen Shi, Sinno Pan

Expand abstract

In this paper, we tackle the critical failure modes of Physics-Informed Neural Networks (PINNs), such as spectral bias, which lead to poor convergence on complex PDEs. We identify two key shortcomings in existing curriculum learning methods for PINNs: unreliable knowledge transfer between stages and a reliance on manual, ad-hoc curriculum design. To overcome these limitations, we present Neural Operator-based Curriculum Learning (NOCL), a unified framework that leverages Neural Tangent Kernel (NTK) theory to automate curriculum generation and employs neural operators to enable robust, dynamic knowledge transfer across curriculum stages. By dynamically training neural operators and filtering data for PINN initialization, our approach ensures scalable and effective learning across progressively difficult tasks. Experiments verify that NOCL leads to marked gains in convergence and generalization relative to prior methods, resulting in substantially better performance on test suite.

Poster
Neural Circuit Architectural Priors for Rat Locomotion

Nikhil Bhattasali, Jaron Cui, Lerrel Pinto, Grace Lindsay

Expand abstract

Animals generate behavior through continuous interactions between their neural circuits, bodies, and environment. Embodied simulations provide a means to study these interactions by testing neural circuit models in biologically realistic settings. Recent efforts have developed embodied simulations of diverse animals, and emerging work on biologically grounded neural architectures has begun to integrate circuit connectivity and single-unit dynamics from experimental data into artificial neural networks, introducing stronger inductive biases and closer mechanistic alignment with biology. How can we develop embodied simulations that enable the study of increasingly complex bodies and neural circuits? In this work, we address the challenge through coordinated advances in the simulated body, neural architecture, and training algorithm. We introduce *Rat v2*, a biomechanical model that provides an efficient and flexible tool for simulating rat behavior. To control this body, we develop *Rat NCAP*, a biologically grounded neural architecture for locomotion based on mammalian spinal circuits that incorporates cell-type-specific connectivity and a novel flexor-extensor neuromechanical interface. To optimize circuit parameters, we refine an evolutionary algorithm to support reliable and efficient training. The integrated system learns to locomote at different speeds without imitation learning, producing locomotion statistics and gaits that match experimental data. Systematic analyses reveal that neuromechanical interface choice substantially affects trainability and gait quality, and that specific neural populations play distinct roles in gait generation. Together, these findings support the view that embodied simulations at an intermediate level of abstraction can simultaneously reproduce complex behavior and yield mechanistic insights into the neural circuits that generate it.

Poster
Necessary but Not Sufficient: Spectral Tests for Value-Linear Attention Surrogates

Blaž Škrlj, Ivan Can Arisoy, Solal Vernier

Expand abstract

We give computable necessary conditions for replacing a fixed attention head by a value-linear recurrent surrogate. The semiseparable spectrum of the causal attention matrix lower-bounds the operator-norm error of any finite-state value-linear recurrence, and retrieval-style blocks yield sharp K and Kd_v state-scaling laws. Empirically, these lower bounds are tight on retrieval-shaped targets but can be loose on smooth or clustered targets, where rank feasibility does not imply trainability or downstream quality. Large pretrained-head surveys suggest that this rank obstruction is often small, including in modern 1B, 7B, and 8B checkpoints. The resulting diagnostic is best used as a rejection test for under-sized recurrent state, not as a certificate that a recurrent replacement will train or improve downstream performance.

Poster
Nearly-Optimal Algorithm for Adversarial Kernelized Bandits

Shogo Iwazaki

Expand abstract

This paper studies kernelized bandits (also known as Gaussian process bandits) in an adversarial environment, where the reward functions in a known reproducing kernel Hilbert space (RKHS) may be adversarially chosen at each round. We show that the exponential-weight algorithm achieves $\tilde{O}(\sqrt{T \gamma_T})$ adversarial regret, where $T$ and $\gamma_T$ denote the number of total rounds and the maximum information gain, respectively. For $\nu$-Mat\'ern kernels, we also show algorithm-independent lower bounds that guarantee the optimality of our algorithm up to polylogarithmic factors. Furthermore, we present a computationally efficient variant of our algorithm using Nystr\"om approximation while maintaining nearly optimal regret guarantees.

Poster
Nearly Optimal Bounds for Orthogonal Trace-Sum Maximization

Yiheng Xiao, Huikang Liu

Expand abstract

Orthogonal trace-sum maximization (OTSM) problems arise in a wide range of data processing applications, including canonical correlation analysis and cryogenic electron microscopy. Despite their practical importance, the existing theoretical understanding of these problems remains incomplete. In this paper, we show that the generalized power method (GPM) converges linearly to the global optimal solution with high probability under an additive Gaussian noise model, provided that the noise level satisfies the nearly optimal bound $(O(\sqrt{n/\log n}))$. In addition, we prove that the semidefinite programming (SDP) relaxation of OTSM is tight and admits a unique optimal solution under the same noise regime, improving upon the best known theoretical guarantee of $(O(n^{1/4}))$. Extensive numerical experiments further demonstrate that our theoretical predictions closely match empirical observations.

Poster