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

One Loss to Rule Them All: Marked Time-to-Event for Structured EHR Foundation Models

Zilin Jing, Vincent Jeanselme, Yuta Kobayashi, Simon Lee, Chao Pang, Aparajita Kashyap, Yanwei Li, Xinzhuo Jiang, Shalmali Joshi

Expand abstract

Clinical events captured in Electronic Health Records (EHR) are irregularly sampled and may consist of a mixture of discrete events and numerical measurements, such as laboratory values or treatment dosages. The sequential nature of EHR, analogous to natural language, has motivated the use of next-token prediction to train prior EHR Foundation Models (FMs) over events. However, this training fails to capture the full structure of EHR. When a given event occurs must be captured, but the event value (abnormal lab) also modulates the likelihood of other clinical events. Most existing EHR FMs do not jointly model this likelihood and are unable to capture the full observation process, impacting downstream capabilities. We propose ORA, a marked time-to-event pretraining objective that jointly models event timing and associated measurements. Across multiple datasets, downstream tasks, and model architectures, this objective consistently yields more generalizable representations than next-token prediction and pretraining losses that ignore continuous measurements. Importantly, the proposed objective yields improvements beyond traditional classification evaluation, including better regression and time-to-event prediction. Beyond introducing a new family of FMs, our ablations suggest a broader takeaway: pretraining objectives that account for EHR structure are critical for expanding downstream capabilities and generalizability.

Poster
One Language-Free Foundation Model Is Enough for Universal Vision Anomaly Detection

Bin-Bin Gao

Expand abstract

Universal visual anomaly detection (AD) aims to identify anomalous images and segment anomalous regions towards open and dynamic scenarios, typically adhering to zero- and few-shot paradigms without dataset-specific fine-tuning. Recently, the field has seen significant progress driven by the integration of vision-language foundation models. However, we observe that current methods often struggle with laborious prompt engineering, elaborate adaptation modules, and complex training strategies that ultimately constrain their flexibility and generalizability. In this paper, we rethink the fundamental mechanism of vision-language models for AD and present UniADet, an embarrassingly simple, effective and general framework for Universal vision Anomaly Detection. Our approach is built on two key insights: First, we reveal that the primary function of the language encoder is merely to derive decision weights and we demonstrate that it is unnecessary, as these weights can be learned more directly and efficiently. Second, to resolve learning conflicts arising from disparate feature manifolds, we introduce a systematic decoupling strategy that learns independent weights across both distinct tasks (classification vs. segmentation) and hierarchical features. UniADet is highly simple and efficient, learning only decoupled weights and requiring 0.02M learnable parameters. It is inherently versatile, adapting seamlessly to various foundation models (\eg, CLIP, DINOv2, and DINOv3). Extensive evaluations of 14 real-world benchmarks in the industrial and medical domains demonstrate that UniADet not only exceeds state-of-the-art zero/few-shot methods by a substantial margin, but also outperforms full-shot AD methods for the first time. This empirical evidence reveals the profound potential of language-free frameworks to redefine the boundaries of visual anomaly detection. The code and models will be made publicly available.

Poster
One Avatar, Any Budget: Robust LoD for Dynamic Gaussian Avatars

Haoyu Zhao, Wenjuan Gong, Junang Qi, Haiyu Zhang, Wenjian Zhao, Zimu YOU

Expand abstract

Cross-device deployment of a single reconstructed avatar often requires adaptation to varying Gaussian budgets with minimal degradation in visual quality. Motivated by the need for a robust budget-adaptive 3D representation, we propose RobustAvatar, a train-once Level-of-Detail (LoD) adaptation framework for dynamic Gaussian avatars based on sequential selection and compensation. RobustAvatar supports flexible compression-ratio control within a single trained avatar, without requiring fine-tuning at each compression ratio. The framework consists of two coordinated modules: Semantic Distribution-Regularized Selection (SDS) and Canonical Budget-Conditioned Compensation (CBC). SDS performs budget-aware Gaussian selection guided by semantic distribution regularization, preserving the coverage of perceptually salient facial regions relative to the full avatar under constrained budgets. CBC refines the selected primitives in a canonical, expression- and pose-neutral space by predicting ratio-conditioned attribute residuals, reducing detail loss from Gaussian removal and improving robustness to decreasing Gaussian budgets. Experiments on the NeRSemble dataset show that RobustAvatar achieves more robust budget adaptation than state-of-the-art methods, with slower quality degradation as Gaussian budgets decrease. The code will be made publicly available.

Poster
One Algorithm, Two Goals: Dual Scoring for Parameter and Data Selection in LLM Fine-Tuning

Xinrui Chen, Liu Yang, Ou Wu

Expand abstract

In Large Language Model (LLM) fine-tuning, parameter and data selection are common strategies for reducing fine-tuning cost, yet they are typically driven by separate scoring mechanisms. When a parameter mask and data subset jointly determine restricted fine-tuning, this separation incurs redundant overhead and makes coordinated selection difficult. We cast parameter and data selection as two bilevel selection problems under a common validation objective and derive a shared local response-surrogate scoring rule. Under first- and second-order validation-improvement approximations, parameter importance and data utility emerge as column-wise and row-wise aggregations of a single gradient interaction matrix, yielding a closed-form row--column correspondence for co-extracting both signals. Building on this structure, we propose $\textbf{DualSFT}$ ($\textbf{Dual}$-$\textbf{S}$election $\textbf{F}$ine-$\textbf{T}$uning), a one-shot dual-scoring algorithm that produces a parameter mask and data subset from shared gradient statistics. On 3B$-$9B LLMs, single-axis DualSFT variants strengthen target-task performance and stability--plasticity trade-offs within their comparison groups, while full DualSFT yields a more favorable joint-constrained trade-off than sequential hybrid baselines under matched budgets.

Poster
One Adapter For All: Towards Generalizable Many-To-One Domain Adaptation In Heterogeneous Collaborative Perception

Lu Bin, Zhewei Fu, Shaohong Wang, Zhiyu Xiang, Hangguan Shan, Eryun Liu

Expand abstract

In autonomous driving, multi-agent collaboration enhances individual perception capabilities through information sharing. However, in real-world applications, differences in models and training data among heterogeneous agents inevitably lead to domain gaps between shared features, bringing challenges to collaboration. To address this, existing methods typically rely on a one-to-one adaptation paradigm, necessitating specific training or fine-tuning for every new agent. This results in a large accumulation of adapters on the vehicle, which is unsustainable for resource-constrained edge devices. To overcome these limitations, we propose UniMTO, a Unified adaptation framework that enables Many-To-One adaptation across heterogeneous agents using a single, fixed adapter. Specifically, it treats domain adaptation as a pattern transformation task, disentangling domain-invariant content and domain-specific pattern from features, and achieving source-to-target pattern transformation through recombination based on a Mixture-of-Experts (MoE) mechanism. Extensive experiments on V2V4Real and V2X-Real demonstrate that UniMTO achieves superior generalization, and exhibits strong zero-shot adaptation capabilities, outperforming all state-of-the-art methods, enabling many-to-one domain adaptation with a single, fixed adapter.

Poster
On-Policy Distillation with Open Property-Equivalence Reward for LLM-Based NL-to-SVA Generation

Qingyun Zou, Yingze Li, Tianen Liu, Bingsheng He, Weng-Fai Wong

Expand abstract

LLM-based generation of SystemVerilog Assertions (SVA) is often reported as nearing saturation, with the strongest specialized model reaching ${\sim}76\%$ accuracy on NL2SVA-Human. We show that this aggregate hides a temporal gap: models that appear strong overall still collapse to a few implication templates on bounded-delay and liveness specifications. The core issue is that the dominant recipe, supervised fine-tuning on NL/SVA pairs, optimizes token-level mimicry rather than the property equivalence that defines SVA correctness. We introduce Reward-Weighted On-Policy Distillation (RWOPD), an on-policy distillation method that samples student rollouts, scores them with an open SymbiYosys+Z3 Property-Equivalence Checker (PEC), and applies a verifier-reward-weighted forward-KL gradient from a frozen 14B teacher on verifier-passable rollouts. This keeps the supervision dense at every response token while grounding both selection and loss weight in property-equivalent behavior. RWOPD distills CodeV-SVA-14B into a Qwen2.5-Coder-7B-Instruct student that sets a new state of the art on NL2SVA-Human and NL2SVA-Machine across pass@1, pass@5, and pass@10, surpassing both specialized prior SOTA models and 671B general-purpose baselines.

Poster
On-Policy Counterfactual Influence

Rhys Gould, Yaowen Ye, Stuart J. Russell, Jacob Steinhardt

Expand abstract

On-policy training plays an important role in modern machine learning, especially in reinforcement learning (RL) for language models. However, quantifying how training data influences the policy's behavior is difficult in on-policy settings: one must account for the cascading effect by which a training event affects its immediate policy update, which in turn affects future action samples, which further affects future policy updates, and so on. Attribution methods developed for off-policy and supervised learning (e.g. influence functions) do not account for such \emph{policy-data interaction}, and can therefore fail in on-policy settings. In this work, we formalize the problem of attributing behaviors to individual training events in the on-policy setting. We derive an influence measure that accounts for policy-data interaction while also being tractable to compute in practical training setups (e.g. LM finetuning) and for realistic optimizers (e.g. AdamW) at a cost that scales linearly in the total number of training events. Empirically, our influence measure accurately predicts the true effect of ablating specific events during RL, while traditional methods fail to do so. Further, we show that this influence accurately identifies helpful and harmful RL training events, allowing us to improve performance via influence-weighted retraining. Overall, we show that accounting for policy-data interaction is both necessary and tractable, allowing for principled training intervention in modern RL pipelines.

Poster
On-Policy Consistency Training Improves LLM Safety with Minimal Capability Degradation

Andy Q Han, Kristina Fujimoto, Avidan Shah, Kiet Nguyen, Kai Xu, Yueh-Han Chen, Ilia Sucholutsky, Rico Angell

Expand abstract

Aligned models can misbehave in several ways: they are often sycophantic, fall victim to jailbreaks, or fail to include appropriate safety warnings. Consistency training is a promising new alignment paradigm to mitigate such failures by training invariants into the model using contrastive input pairs. Existing consistency training procedures generate the supervision signal once, offline, and use supervised fine-tuning (SFT) to update the model. Unfortunately, the resulting models tend to merely memorize the surface forms of the training distribution and thus generalize poorly and regress in their capabilities. We introduce On-Policy Consistency Training (OPCT), a new consistency training approach where the objective is computed over the model's own responses to prompts, supervised by itself conditioned on corresponding contrastive prompts. We evaluate OPCT on three safety axes: sycophancy, jailbreaking, and safety awareness. Across three model families, OPCT outperforms its SFT counterpart on all safety desiderata. It nearly halves the sycophancy rate relative to baseline (8.1\% vs. 15.4\%, compared to 11.2\% for SFT). Under an adaptive per-target attacker, OPCT holds jailbreak defense success near 99\% on held-out jailbreak behaviors, whereas SFT achieves 87\% on average. On safety awareness, OPCT outperforms SFT in two out of three models, and matches it on the other. OPCT also largely avoids the capability regressions that SFT induces, such as a 28-point drop on MATH-500. Our results suggest that consistency training is best implemented as OPCT rather than as SFT, especially when generalization beyond the training distribution is desired.

Poster
On the Token Value Inequality in Efficient Reasoning

Runjia Zeng, Hang Hua, Yiyang Liu, Zhiqiang Tao, Ruixiang Tang, Qifan Wang, Cheng Han, Dongfang Liu

Expand abstract

Chain-of-Thought reasoning has enabled large language models to achieve substantial performance gains on complex tasks. However, these gains come at the cost of dramatically increased token consumption. This raises a fundamental question: is every token in the reasoning trace equally valuable? We present a diagnostic and optimization framework grounded in a key empirical finding: the value of tokens within a CoT reasoning sequence is highly non-uniform, and this non-uniformity can be effectively characterized by token-level log probability signals. We show that normalized log probability helps distinguish core tokens, which carry structural and decisive reasoning content, from redundant tokens, which are exploratory, low-confidence filler that contributes less directly to the final answer. Building on these findings, we formulate the TokenProbe framework around two empirical findings and one claim: findings identify token value inequality first and then establish TokenProbe as a core-token proxy, and the claim introduces an efficient GRPO objective positing that selectively compressing redundant tokens can yield Pareto improvements in the accuracy–token efficiency space. Empirically, our method preserves reasoning quality while reducing the token usage by 76% of the baseline. Under matched reasoning-length budgets, we show that it can even outperform strong flagship baselines like Gemini-3.1-Pro.

Poster
On the Tightness and Computational Tractability of Higher-Dimensional Confidence Sequences

Fabian Denoodt, Sibylle Hess, Joaquin Vanschoren, Christian Andersson Naesseth

Expand abstract

Modern sequential monitoring problems often involve multiple metrics, where we monitor several data streams simultaneously and may act once the evidence is strong enough. Confidence sequences (CSs) are a natural tool for such continuous monitoring. However, for bounded vector means, existing multivariate CSs are either tight but computationally intractable, or fast to compute but conservative. To address this, we study three lifts of one-dimensional betting-based CSs to higher dimensions: a weighted Bonferroni region, an equivalent max-wealth form, and a portfolio region. The portfolio is typically much tighter, especially in higher dimensions, but its boundary and properties such as volume are not available in closed form. To make this tighter construction usable, we propose tractable outer approximations of the portfolio region that preserve statistical validity: a bounding box, an $\ell_p$-ellipsoid, and their intersection. We prove set relations among all constructions and show empirically that these approximations (i) achieve regions close to the intractable portfolio, (ii) substantially outperform existing tractable multivariate CSs, and (iii) enable practical use cases such as multi-metric A/B testing and model comparison.

Spotlight
On the Sparsity-Storage-Accuracy Tradeoff in Parsimoniously Activated Dictionary Learning

Zihui Zhao, Yang Li

Expand abstract

Dictionary learning has long been studied from both optimization and probabilistic perspectives. While formulations with element-wise sparsity regularization (e.g., L1-based sparse coding) admit well-established probabilistic interpretations, many structured variants that impose global constraints lack a clear and tractable generative view. In this paper, we revisit a class of practically effective yet theoretically under-explored dictionary learning methods that impose a simple global regularization on the number of activated dictionary atoms, which we term parsimoniously activated dictionary learning (PADL). We show that PADL admits an equivalent formulation as maximum a posteriori estimation under a structured generative model, with auxiliary latent variables that govern global activation patterns. This formulation allows us to derive generalization guarantees that are difficult to obtain under the original formulation. More importantly, it yields an analytical characterization of the tradeoff between sparsity, storage cost, and reconstruction accuracy, enabling data-driven estimation of optimal hyperparameters. Based on this connection, we develop an efficient and interpretable PADL algorithm that eliminates manual hyperparameter tuning, achieving improved reconstruction performance under comparable sparsity levels on visual benchmarks. We further demonstrate its practical utility in accelerating inference for vision-language models.

Poster
On the Sparsity of Direct Preference Optimization: Weight Disentanglement in the NTK Regime

Kensuke Sasaki, Issei Sato

Expand abstract

Direct Preference Optimization (DPO) has been widely adopted for aligning language models with human preferences. Recent empirical work has revealed that DPO induces remarkably sparse parameter updates, yet no theoretical explanation for this phenomenon has been offered. We analyze DPO's optimization dynamics under a neural tangent kernel linearization and show that the logistic structure of the DPO loss gives rise to an implicit maximum-margin bias. Building on this observation, we introduce the concept of dual sparsity: the DPO update direction is a sparse linear combination (data-level sparsity, driven by support vectors) of sparse gradient feature vectors (parameter-level sparsity, arising from gradient cancellation between preferred and dispreferred responses). We formalize this structure in our main theorem and present a framework relating it to weight disentanglement---a condition favorable for model merging. Experiments on GPT-2 Small and Medium with the Anthropic HH-RLHF and UltraFeedback datasets confirm both sources of sparsity and show that DPO reduces cross-task interference by up to $35 \times$ compared to supervised fine-tuning.

Poster
On the Selectivity of Generative Models in Structure-Based Drug Design

Ella Miray Rajaonson, Jungyoon Lee, William Chau, Alan Aspuru-Guzik, Benjamin Sanchez-Lengeling, Dominique Beaini, Kirill Neklyudov, Marta Skreta

Expand abstract

Designing small-molecule drugs that selectively bind to a target protein while avoiding unintended interactions with other proteins is essential for reducing side effects that contribute substantially to clinical attrition. Although structure-based drug design (SBDD) has advanced rapidly with deep learning, most generative models still optimize binding to a single target and disregard selectivity due to limited training data and unknown off-target interactions. Motivated by this gap, we introduce SelectBench, a comprehensive benchmark assessing the selectivity of generative SBDD models. SelectBench provides three curated evaluation tasks reflecting different real-world drug discovery scenarios: literature-based case studies, safety screening panels used in pharmaceutical development, and large-scale structure-based evaluation sets. We further introduce a suite of metrics to quantify selectivity and conduct a systematic evaluation of nine representative SBDD models, including methods explicitly trained for selectivity and widely-used inference-time guidance techniques. Our results show that even selectivity-trained models achieve only modest off-target discrimination and inference-time guidance provides limited improvements, underscoring the need for method improvement. SelectBench provides both a characterization of where current generative SBDD stands on selectivity and an open, extensible platform to accelerate progress.

Poster
On the Runway Cascade of Transformers for Language Modeling

Hunjae Lee, Corey Clark

Expand abstract

In decoder-only (causal) transformers, the computation graph created by causal masking routes information through both direct-path attention and indirect paths formed by intermediate tokens. We denote these indirect paths between token pairs as their \textit{runways}. We argue that certain failure modes of causal transformers as observed by a growing body of recent works are likely exacerbated by a misalignment between these two information propagation modes. We formalize \textit{runway cascade} as a phenomenon whereby this misalignment results in redundancies and irrelevant information cascading to token representations despite adequately learned attention patterns. As a solution, we propose \textit{runway-aware rewiring} as a more explicit way of incorporating runway context directly into each token's direct-path attention. This mechanism re-wires the attention pattern for each token based on a summary of its runway landscape, enabling awareness of accumulating representational influences and allowing for more balanced information propagation. Our proposed methodology introduces no additional parameters and can seamlessly be integrated into standard attention mechanism. Empirically, our rewired transformer results in steady improvements in general language modeling as well as noticeably stronger information retrieval and extrapolation abilities compared to standard transformers.

Poster
On the Relaxation of Conditional Independence Assumption for Image Segmentation

Zixun Wang, Ben Dai

Expand abstract

In semantic segmentation, a recent line of RankSEG methods directly optimizes Dice/IoU scores at inference time, improving alignment with evaluation metrics without modifying model training. Despite its theoretical and empirical success, RankSEG relies on the restrictive Conditional Independence Assumption (CIA), which ignores crucial label correlations and therefore degrades performance in ambiguous or low-contrast scenarios. However, accounting for full label dependence is computationally prohibitive, requiring $\mathcal{O}(d^3)$ time. To address this, we replace the CIA with a Spatially Localized Dependence (SLD) structure that captures local label correlations while keeping the dependence model tractable. We further overcome the remaining computational bottleneck via a Reciprocal Moment Approximation coupled with a novel fixed-point optimization strategy that eliminates exhaustive search. The proposed algorithm achieves a highly practical $\mathcal{O}(d \log d)$ complexity and consistently outperforms conventional argmax and CIA-based RankSEG across diverse segmentation benchmarks. Improvements are significant in low-contrast or small-object scenarios, where label dependence offers valuable signals complementary to image information for accurate segmentation.

Spotlight
On the Recall Scaling Laws in Mamba: A Theoretical and Mechanistic Study via Hashing

Yuval Koren, Assaf Ben-Kish, Raja Giryes, Lior Wolf, Itamar Zimerman

Expand abstract

Associative Recall (AR) is the cognitive ability to learn and retrieve links between items in memory. In NLP, AR is used as a benchmark for evaluating the in-context memory capacity of architectures such as Mamba, and has been found to strongly correlate with language modeling performance. This paper explores AR from the perspective of mechanistic interpretability, aiming to reverse-engineer the exact internal algorithm used by Mamba to perform recall. Our key insight is that Mamba performs recall by implicitly learning linear hash functions, and we identify the low-level circuit that enables this behavior. Building on these findings and inspired by theoretical tools in similarity-preserving hashing, such as the Johnson–Lindenstrauss (JL) lemma, we develop a theoretical framework for analyzing AR, which we term recall scaling laws. For example, given a model’s state, context length, and embedding dimensions, our theory predicts a lower bound on the largest vocabulary size that can be perfectly recalled in the AR task. Empirical results show that this bound is tight and predictive, offering insights into how AR capacity scales with vocabulary size, state size, embedding size, and model architecture.

Poster
On the Provable Emergence of Hierarchical Concept Structure in CLIP Embeddings

Nghia Nguyen, Tianjiao Ding, Lachlan MacDonald, Rene Vidal

Expand abstract

Contrastive vision-language models such as CLIP are trained to align images and text, not to represent taxonomies. Yet empirical studies show that CLIP embeddings exhibit a hierarchical geometry aligned with the semantic hierarchy of concepts. A theoretical characterization of why such hierarchy emerges from a non-hierarchical objective remains open. In this paper, we formalize this phenomenon as Hierarchical Angular Separation (HAS), a geometric property whereby each non-leaf concept embedding is more similar to its descendants than to off-branch concepts. Empirically, we show that HAS already holds weakly in randomly initialized CLIP image embeddings, suggesting that hierarchical structure may be induced by the raw image geometry, while in text embeddings it emerges only after contrastive training. To explain this asymmetry between text and image embeddings, we analyze an unconstrained features model in which the image embeddings are fixed and only the text embeddings are trained. We show that when the image embeddings satisfy HAS with a positive margin, the global minimizer of the contrastive objective induces HAS in the text embeddings, thereby transferring hierarchical structure across modalities. The key mechanism is the hierarchical co-occurrence structure of image-text pairs, which biases text embeddings toward root-centered image prototypes. For a linear contrastive loss, we derive a closed-form solution that makes this mechanism explicit. We extend the analysis to the InfoNCE loss and establish analogous guarantees under sufficient regularization. Synthetic experiments validate the theory and show that HAS emerges even beyond the regimes covered by our analysis.

Poster
On the Primacy Bias in RLVR Training

Nguyen Phuc, Ngoc-Hieu Nguyen, Parshin Shojaee, Chinh D La, Duy M. H. Nguyen, Rui Zhang, Khoa D Doan, Ting Hua, Nitesh Chawla

Expand abstract

Verifiable Reward (RLVR) has emerged as a promising approach for enhancing the reasoning capabilities of large language models. However, it still remains unclear whether RLVR can extend reasoning capabilities beyond what is already encoded in the base model. In this paper, we study this question through the lens of *primacy bias* — the tendency of models to over-rely on already-learned representations, disproportionately improving performance on problems they already handle well while underexploring harder ones that require departing from those representations. Through our controlled experiments and large-scale analysis, we show that RLVR training on mixed data tends to further sharpen performance on easier problems while yielding only marginal gains on harder ones. We find that although hard problems lead to modest gains overall, they are actually the ones that help most in expanding the model’s reasoning capabilities and pushing the representations. However, prolonged training on these hard problems may also hurt and lead to forgetting on easy problems. These findings help to better understand some of the prior conflicting observations about RLVR, specifically, why on (OOD) domains where the base model performs poorly, improvements on hard problems can expand reasoning; while on well-trained domains, forgetting can reduce performance and mask genuine gains obtained from hard problems. Data and code for reproducing our experiments are available at: https://anonymous.4open.science/r/neurips26_sub-0DE8.

Poster
On the Price of Privacy for Language Identification and Generation

Xiaoyu Li, Andi Han, Jiaojiao Jiang, Junbin Gao

Expand abstract

As large language models (LLMs) are increasingly trained on sensitive user data, understanding the fundamental cost of privacy in language learning becomes essential. We initiate the study of differentially private (DP) language identification and generation in the agnostic statistical setting, establishing algorithms and matching lower bounds that precisely quantify the cost of privacy. For both tasks, approximate $(\varepsilon, \delta)$-DP with constant $\varepsilon > 0$ recovers the non-private error rates: $\exp(-r(n))$ for identification (for any $r(n) = o(n)$) and $\exp(-\Omega(n))$ for generation. Under pure $\varepsilon$-DP, the exponents degrade by a multiplicative factor of $\min\\{1, \varepsilon\\}$, which we show is tight up to constants. Notably, for generation under pure DP with mild assumptions, the upper bound $\exp(-\min\\{1,\varepsilon\\} \cdot \Omega(n))$ matches the lower bound up to some constants, establishing an optimal rate. Our results show that the cost of privacy in language learning is surprisingly mild: absent entirely under approximate DP, and exactly a $\min\\{1,\varepsilon\\}$ factor in the exponent under pure DP.

Poster
On the Parallel Optimality of Exponentiated Gradient Descent

Xin Jennifer Chen, Andrei Graur, Aaron Sidford

Expand abstract

A classic result in learning and optimization theory is that exponentiated gradient descent (EG) or the multiplicative weight update method computes an $\\epsilon$-approximate minimizer of an $\\ell_1$-Lipschitz function over the $d$-dimensional probability simplex $\\Delta_d :=\\{x \in \\mathbb{R}^d_{\\geq0}:\\sum_{i\in[d]}x_i=1\\}$ with $\\tilde{O}(\epsilon^{-2})$ queries to a first-order oracle. We investigate whether there are improved parallel algorithms for this fundamental problem. We show that, up to logarithmic factors, the answer is negative for $\\epsilon=\\tilde \\Omega(d^{-1/6})$ - any randomized algorithm that makes $O(\\mathrm{poly}(d))$ subgradient queries per round requires $\\tilde{\\Omega}(1/\\epsilon^2)$ rounds to output an $\epsilon$-optimal point with constant success probability. Moreover, to obtain this result we provide an analogous characterization of the parallel complexity of minimizing a $\ell_1$-Lipschitz convex function over the unit $\\ell_1$ ball. Previous lower bounds for non-constant $\\epsilon$ for this $\\ell_1$-Lipschitz convex optimization problem either made additional assumptions on the domain, or instead attained a bound of $\\Omega(\\epsilon^{-2/3})$ [DG19].

Poster