Showing 1–49 of 49 results for author: Gai, Y

Comprehensive Evaluation of Large Language Model Responses: A Multi-Factor Scoring System

Authors: Yiming Gai, Junde Lu, Xuefei Huang

Abstract: The remarkable performance of large language models (LLMs) in linguistic tasks underscores an urgent need for comprehensive evaluation of their response quality. Prevailing methods, often confined to singular dimensions, fall short of capturing the full spectrum of model capabilities. This study introduces a multifactor scoring paradigm, integrating accuracy, conciseness, factual consistency, read… ▽ More The remarkable performance of large language models (LLMs) in linguistic tasks underscores an urgent need for comprehensive evaluation of their response quality. Prevailing methods, often confined to singular dimensions, fall short of capturing the full spectrum of model capabilities. This study introduces a multifactor scoring paradigm, integrating accuracy, conciseness, factual consistency, readability, and coherence, complemented by a graphical user interface (GUI) for visualizing outcomes. Evaluations on the TruthfulQA dataset unveil mainstream LLMs' strengths in reasoning tasks (peaking at a composite score of 0.6104) alongside pervasive limitations in navigating complex facts and ambiguities. Transcending the narrow lens of traditional metrics, this framework offers a transparent, adaptable avenue to illuminate model potential and deficiencies. Though presently focused on English tasks, its horizons beckon toward multilingual domains. This work carves a novel path for knowledge engineering and model refinement. △ Less

Submitted 7 July, 2026; originally announced July 2026.

Modality Relevance is not Modality Utility: Post-hoc Selective Modality Escalation for Cost-Aware Multimodal RAG

Authors: Xue Li, Yiming Gai

Abstract: Multimodal retrieval-augmented generation (RAG) grounds a generator in evidence drawn from heterogeneous modalities -- text, tables, and images. The dominant deployment choice is binary and made before the model has tried to answer: either run a cheap text(+table) pipeline, or pay for an expensive vision-language model (VLM) over every image. Recent adaptive systems improve on this by selecting th… ▽ More Multimodal retrieval-augmented generation (RAG) grounds a generator in evidence drawn from heterogeneous modalities -- text, tables, and images. The dominant deployment choice is binary and made before the model has tried to answer: either run a cheap text(+table) pipeline, or pay for an expensive vision-language model (VLM) over every image. Recent adaptive systems improve on this by selecting the modality or fidelity pre-retrieval, from a question-conditioned predictor of which modality will be needed. We show that this is the wrong decision point. Through an oracle headroom analysis on MultiModalQA, we find that the relevance of a modality to a question is a weak predictor of whether that modality is actually needed to answer correctly: a large fraction of questions whose gold support includes an image are nonetheless answerable from text and tables alone, and a pre-retrieval router that escalates on apparent visual relevance over-escalates substantially relative to an oracle. We propose \textbf{post-hoc selective modality escalation}: answer cheaply from text and tables, run a verifier on the (query, draft answer, evidence) tuple that localizes which modality is missing, and pay for VLM evidence only there. A calibrated value-of-escalation router then decides whether the expected accuracy gain justifies the visual cost. On MultiModalQA, our router recovers the accuracy of an always-on VLM pipeline while issuing far fewer visual calls, and closes most of the gap to the oracle escalation rate. The result extends a routing-signal hierarchy established for retrieval depth and reasoning hops to a third axis -- modality -- under a single cost-aware selective-escalation view. △ Less

Submitted 3 July, 2026; originally announced July 2026.

Twin Algebras: Condensable Algebras beyond Anyons

Authors: Yuhan Gai, Sakura Schafer-Nameki, Alison Warman

Abstract: Condensable algebras in 2+1d non-chiral topological orders characterize gapped boundary conditions and interfaces. Applied to the Symmetry Topological Field Theory, they allow classification of symmetric gapped phases and impose sharp constraints on possible phase transitions. A condensable algebra is specified not only by its underlying set of anyons, which end on the boundary or interface, but a… ▽ More Condensable algebras in 2+1d non-chiral topological orders characterize gapped boundary conditions and interfaces. Applied to the Symmetry Topological Field Theory, they allow classification of symmetric gapped phases and impose sharp constraints on possible phase transitions. A condensable algebra is specified not only by its underlying set of anyons, which end on the boundary or interface, but also by its algebra structure. We introduce the concept of twin condensable algebras, which have the same anyon decomposition, but inequivalent algebra structure. We revisit the classification of condensable algebras in $\mathcal{Z}(\text{Vec}_G^ω)$, i.e. in group-theoretical topological orders for finite groups $G$ with anomaly $ω$. In this context we are able to identify twin algebras that arise from different mechanisms, such as subgroup data, SPT cocycles, and symmetry actions. In particular, we construct infinite families of examples of twins from so-called Gassmann triples, and exhibit cases in which the reduced topological orders are inequivalent despite having identical anyon content. Physically, twin algebras describe distinct symmetric phases that have isomorphic spaces of ground states, but inequivalent order parameters. Such twin phases never exhibit relative spontaneous symmetry breaking, and can be used to construct phase transitions without hidden symmetry breaking, which are intrinsically beyond Landau transitions. △ Less

Submitted 29 May, 2026; originally announced May 2026.

Comments: 37 pages, 3 ancillary files

Twin Phases: Intrinsic Deconfined Quantum Criticality

Authors: Alison Warman, Yuhan Gai, Sakura Schafer-Nameki

Abstract: We introduce the concept of twin phases for a symmetry $\mathcal{S}$, defined as inequivalent phases, whose order parameters are part of the same generalized charge under $\mathcal{S}$. Stable, direct transitions between such twin phases are never spontaneous-symmetry-breaking transitions, even after (partially) gauging the initial symmetry $\mathcal{S}$: they are phase transitions without hidden… ▽ More We introduce the concept of twin phases for a symmetry $\mathcal{S}$, defined as inequivalent phases, whose order parameters are part of the same generalized charge under $\mathcal{S}$. Stable, direct transitions between such twin phases are never spontaneous-symmetry-breaking transitions, even after (partially) gauging the initial symmetry $\mathcal{S}$: they are phase transitions without hidden symmetry breaking. We illustrate this with an (anomalous) finite group symmetry in 1+1d, which exhibits such intrinsically beyond Landau transition, i.e. an intrinsically Deconfined Quantum Critical Point (DQCP). △ Less

Submitted 3 July, 2026; v1 submitted 29 May, 2026; originally announced May 2026.

Comments: 5 pages + appendices and ancillary data file; v2: added numerical simulations for phase transition

Ascend-RaBitQ: Heterogeneous NPU-CPU Acceleration of Billion-Scale Similarity Search with 1-bit Quantization

Authors: Fujun He, Chuyue Ye, Huaxiang Cai, Zetao Lv, Baolong Cui, Wenru Yan, Chao Zhan, Zigang Zhang, Hao Yi, Jie Xiang, Xiabing Li, Yuhang Gai, Ziyang Zhang, Pengfei Zheng, Yunfei Du

Abstract: Vector similarity search is a critical component of modern AI systems, but traditional CPU-based implementations face fundamental scalability bottlenecks for billion-scale corpora due to prohibitive computational overhead and memory bandwidth limitations. While Neural Processing Units (NPUs) offer orders-of-magnitude higher compute density, existing CPU/GPU-optimized 1-bit RaBitQ quantization impl… ▽ More Vector similarity search is a critical component of modern AI systems, but traditional CPU-based implementations face fundamental scalability bottlenecks for billion-scale corpora due to prohibitive computational overhead and memory bandwidth limitations. While Neural Processing Units (NPUs) offer orders-of-magnitude higher compute density, existing CPU/GPU-optimized 1-bit RaBitQ quantization implementations cannot be directly ported to NPU architectures due to fundamental hardware mismatches, and homogeneous design paradigms struggle to simultaneously balance accuracy, memory footprint, and performance. This paper presents Ascend-RaBitQ, the first heterogeneous NPU-CPU optimized IVF-RaBitQ system for billion-scale vector search, built on the core insight that decoupling coarse ranking (NPU) from fine ranking (CPU) allows each stage to leverage its optimal hardware, breaking the long-standing accuracy-memory-performance trade-off. We propose a three-stage heterogeneous execution path comprising AI Core-accelerated coarse ranking on 1-bit quantized vectors, on-device AI CPU Top-k processing, and host CPU fine re-ranking on full-precision vectors. We introduce four NPU architecture-native optimizations: fused AIC-AIV operators for parallel distance computation, computation flow restructuring to exploit rotation orthogonality, fine-grained index block-level load balancing that breaks query boundaries, and intra-NPU pipeline parallelism between AI Core and AI CPU to mask Top-k latency. Evaluation on standard datasets shows that Ascend-RaBitQ achieves 3.0X to 62.8X faster index construction than the CPU baseline, up to 11.7X throughput improvement over the fastest CPU IVF-RaBitQ implementation, and over two orders of magnitude over the mathematically equivalent CPU baseline, while demonstrating encouraging scalability on distributed multi-NPU systems. △ Less

Submitted 14 June, 2026; v1 submitted 15 May, 2026; originally announced May 2026.

FashionStylist: An Expert Knowledge-enhanced Multimodal Dataset for Fashion Understanding

Authors: Kaidong Feng, Zhuoxuan Huang, Huizhong Guo, Yuting Jin, Xinyu Chen, Yue Liang, Yifei Gai, Li Zhou, Yunshan Ma, Zhu Sun

Abstract: Fashion understanding requires both visual perception and expert-level reasoning about style, occasion, compatibility, and outfit rationale. However, existing fashion datasets remain fragmented and task-specific, often focusing on item attributes, outfit co-occurrence, or weak textual supervision, and thus provide limited support for holistic outfit understanding. In this paper, we introduce Fashi… ▽ More Fashion understanding requires both visual perception and expert-level reasoning about style, occasion, compatibility, and outfit rationale. However, existing fashion datasets remain fragmented and task-specific, often focusing on item attributes, outfit co-occurrence, or weak textual supervision, and thus provide limited support for holistic outfit understanding. In this paper, we introduce FashionStylist, an expert-annotated benchmark for holistic and expert-level fashion understanding. Constructed through a dedicated fashion-expert annotation pipeline, FashionStylist provides professionally grounded annotations at both the item and outfit levels. It supports three representative tasks: outfit-to-item grounding, outfit completion, and outfit evaluation. These tasks cover realistic item recovery from complex outfits with layering and accessories, compatibility-aware composition beyond co-occurrence matching, and expert-level assessment of style, season, occasion, and overall coherence. Experimental results show that FashionStylist serves not only as a unified benchmark for multiple fashion tasks, but also as an effective training resource for improving grounding, completion, and outfit-level semantic evaluation in MLLM-based fashion systems. △ Less

Submitted 13 April, 2026; v1 submitted 10 April, 2026; originally announced April 2026.

Rationale Matters: Learning Transferable Rubrics via Proxy-Guided Critique for VLM Reward Models

Authors: Weijie Qiu, Dai Guan, Junxin Wang, Zhihang Li, Yongbo Gai, Mengyu Zhou, Erchao Zhao, Xiaoxi Jiang, Guanjun Jiang

Abstract: Generative reward models (GRMs) for vision-language models (VLMs) often evaluate outputs via a three-stage pipeline: rubric generation, criterion-based scoring, and a final verdict. However, the intermediate rubric is rarely optimized directly. Prior work typically either treats rubrics as incidental or relies on expensive LLM-as-judge checks that provide no differentiable signal and limited train… ▽ More Generative reward models (GRMs) for vision-language models (VLMs) often evaluate outputs via a three-stage pipeline: rubric generation, criterion-based scoring, and a final verdict. However, the intermediate rubric is rarely optimized directly. Prior work typically either treats rubrics as incidental or relies on expensive LLM-as-judge checks that provide no differentiable signal and limited training-time guidance. We propose Proxy-GRM, which introduces proxy-guided rubric verification into Reinforcement Learning (RL) to explicitly enhance rubric quality. Concretely, we train lightweight proxy agents (Proxy-SFT and Proxy-RL) that take a candidate rubric together with the original query and preference pair, and then predict the preference ordering using only the rubric as evidence. The proxy's prediction accuracy serves as a rubric-quality reward, incentivizing the model to produce rubrics that are internally consistent and transferable. With ~50k data samples, Proxy-GRM reaches state-of-the-art results on the VL-Reward Bench, Multimodal Reward Bench, and MM-RLHF-Reward Bench, outperforming the methods trained on four times the data. Ablations show Proxy-SFT is a stronger verifier than Proxy-RL, and implicit reward aggregation performs best. Crucially, the learned rubrics transfer to unseen evaluators, improving reward accuracy at test time without additional training. Our code is available at https://github.com/Qwen-Applications/Proxy-GRM. △ Less

Submitted 17 March, 2026; v1 submitted 17 March, 2026; originally announced March 2026.

Comments: 25 pages, 10 figures,

Grounding the Score: Explicit Visual Premise Verification for Reliable Vision-Language Process Reward Models

Authors: Junxin Wang, Dai Guan, Weijie Qiu, Zhihang Li, Yongbo Gai, Zhengyi Yang, Mengyu Zhou, Erchao Zhao, Xiaoxi Jiang, Guanjun Jiang

Abstract: Vision-language process reward models (VL-PRMs) are increasingly used to score intermediate reasoning steps and rerank candidates under test-time scaling. However, they often function as black-box judges: a low step score may reflect a genuine reasoning mistake or simply the verifier's misperception of the image. This entanglement between perception and reasoning leads to systematic false positive… ▽ More Vision-language process reward models (VL-PRMs) are increasingly used to score intermediate reasoning steps and rerank candidates under test-time scaling. However, they often function as black-box judges: a low step score may reflect a genuine reasoning mistake or simply the verifier's misperception of the image. This entanglement between perception and reasoning leads to systematic false positives (rewarding hallucinated visual premises) and false negatives (penalizing correct grounded statements), undermining both reranking and error localization. We introduce Explicit Visual Premise Verification (EVPV), a lightweight verification interface that conditions step scoring on the reliability of the visual premises a step depends on. The policy is prompted to produce a step-wise visual checklist that makes required visual facts explicit, while a constraint extractor independently derives structured visual constraints from the input image. EVPV matches checklist claims against these constraints to compute a scalar visual reliability signal, and calibrates PRM step rewards via reliability gating: rewards for visually dependent steps are attenuated when reliability is low and preserved when reliability is high. This decouples perceptual uncertainty from logical evaluation without per-step tool calls. Experiments on VisualProcessBench and six multimodal reasoning benchmarks show that EVPV improves step-level verification and consistently boosts Best-of-N reranking accuracy over strong baselines. Furthermore, injecting controlled corruption into the extracted constraints produces monotonic performance degradation, providing causal evidence that the gains arise from constraint fidelity and explicit premise verification rather than incidental prompt effects. Code is available at: https://github.com/Qwen-Applications/EVPV-PRM △ Less

Submitted 9 May, 2026; v1 submitted 17 March, 2026; originally announced March 2026.

Comments: 27 pages, 4 figures, 10 tables. Evaluated on VisualProcessBench and six multimodal reasoning benchmarks (LogicVista, MMMU, MathVerse-VO, MathVision, MathVista, WeMath). Includes ablations and causal analysis via controlled constraint corruption. Code: https://github.com/Qwen-Applications/EVPV-PRM

ACM Class: I.2.7; I.4.8; H.3.3

CLIPO: Contrastive Learning in Policy Optimization Generalizes RLVR

Authors: Sijia Cui, Pengyu Cheng, Jiajun Song, Yongbo Gai, Guojun Zhang, Zhechao Yu, Jianhe Lin, Xiaoxi Jiang, Guanjun Jiang

Abstract: Reinforcement Learning with Verifiable Rewards (RLVR) has significantly advanced the reasoning capacity of Large Language Models (LLMs). However, RLVR solely relies on final answers as outcome rewards, neglecting the correctness of intermediate reasoning steps. Training on these process-wrong but outcome-correct rollouts can lead to hallucination and answer-copying, severely undermining the model'… ▽ More Reinforcement Learning with Verifiable Rewards (RLVR) has significantly advanced the reasoning capacity of Large Language Models (LLMs). However, RLVR solely relies on final answers as outcome rewards, neglecting the correctness of intermediate reasoning steps. Training on these process-wrong but outcome-correct rollouts can lead to hallucination and answer-copying, severely undermining the model's generalization and robustness. To address this, we incorporate a Contrastive Learning mechanism into the Policy Optimization (CLIPO) to generalize the RLVR process. By optimizing a contrastive loss over successful rollouts, CLIPO steers the LLM to capture the invariant structure shared across correct reasoning paths. This provides a more robust cross-trajectory regularization than the original single-path supervision in RLVR, effectively mitigating step-level reasoning inconsistencies and suppressing hallucinatory artifacts. In experiments, CLIPO consistently improves multiple RLVR baselines across diverse reasoning benchmarks, demonstrating uniform improvements in generalization and robustness for policy optimization of LLMs. Our code and training recipes are available at https://github.com/Qwen-Applications/CLIPO. △ Less

Submitted 10 March, 2026; originally announced March 2026.

Open Rubric System: Scaling Reinforcement Learning with Pairwise Adaptive Rubric

Authors: Ruipeng Jia, Yunyi Yang, Yuxin Wu, Yongbo Gai, Siyuan Tao, Mengyu Zhou, Jianhe Lin, Xiaoxi Jiang, Guanjun Jiang

Abstract: Scalar reward models compress multi-dimensional human preferences into a single opaque score, creating an information bottleneck that often leads to brittleness and reward hacking in open-ended alignment. We argue that robust alignment for non-verifiable tasks is fundamentally a principle generalization problem: reward should not be a learned function internalized into a judge, but an explicit rea… ▽ More Scalar reward models compress multi-dimensional human preferences into a single opaque score, creating an information bottleneck that often leads to brittleness and reward hacking in open-ended alignment. We argue that robust alignment for non-verifiable tasks is fundamentally a principle generalization problem: reward should not be a learned function internalized into a judge, but an explicit reasoning process executed under inspectable principles. To operationalize this view, we present the Open Rubric System (OpenRS), a plug-and-play, rubrics-based LLM-as-a-Judge framework built around Pairwise Adaptive Meta-Rubrics (PAMR) and lightweight Pointwise Verifiable Rubrics (PVRs), which provide both hard-constraint guardrails and verifiable reward components when ground-truth or programmatic checks are available. OpenRS uses an explicit meta-rubric -- a constitution-like specification that governs how rubrics are instantiated, weighted, and enforced -- and instantiates adaptive rubrics on the fly by conditioning on the semantic differences between two candidate responses. It then performs criterion-wise pairwise comparisons and aggregates criterion-level preferences externally, avoiding pointwise weighted scalarization while improving discriminability in open-ended settings. To keep principles consistent yet editable across various domains, we introduce a two-level meta-rubric refinement pipeline (automated evolutionary refinement for general principles and a reproducible human-in-the-loop procedure for domain principles), complemented with pointwise verifiable rubrics that act as both guardrails against degenerate behaviors and a source of verifiable reward for objective sub-tasks. Finally, we instantiate OpenRS as reward supervision in pairwise RL training. △ Less

Submitted 26 February, 2026; v1 submitted 15 February, 2026; originally announced February 2026.

Beyond Wigner: Non-Invertible Symmetries Preserve Probabilities

Authors: Thomas Bartsch, Yuhan Gai, Sakura Schafer-Nameki

Abstract: In recent years, the traditional notion of symmetry in quantum theory was expanded to so-called generalised or categorical symmetries, which, unlike ordinary group symmetries, may be non-invertible. This appears to be at odds with Wigner's theorem, which requires quantum symmetries to be implemented by (anti)unitary -- and hence invertible -- operators in order to preserve probabilities. We resolv… ▽ More In recent years, the traditional notion of symmetry in quantum theory was expanded to so-called generalised or categorical symmetries, which, unlike ordinary group symmetries, may be non-invertible. This appears to be at odds with Wigner's theorem, which requires quantum symmetries to be implemented by (anti)unitary -- and hence invertible -- operators in order to preserve probabilities. We resolve this puzzle for (higher) fusion category symmetries $\mathcal{C}$ by proposing that, instead of acting by unitary operators on a fixed Hilbert space, symmetry defects in $\mathcal{C}$ act as isometries between distinct Hilbert spaces constructed from twisted sectors. As a result, we find that non-invertible symmetries naturally act as trace-preserving quantum channels. Crucially, our construction relies on the symmetry category $\mathcal{C}$ being unitary. We illustrate our proposal through several examples that include Tambara-Yamagami, Fibonacci, and Yang-Lee as well as higher categorical symmetries. △ Less

Submitted 17 February, 2026; v1 submitted 6 February, 2026; originally announced February 2026.

Comments: 4 pages + Supplementary Material, v2: references added

Categorical Anomaly Matching

Authors: Andrea Antinucci, Christian Copetti, Yuhan Gai, Sakura Schafer-Nameki

Abstract: Matching 't Hooft anomalies is a powerful tool for constraining the low-energy dynamics of quantum systems and their allowed renormalization group (RG) flows. For non-invertible (or categorical) symmetries, however, a key challenge has been the lack of a precise framework to characterize and quantify anomalies. We address this by identifying tensor functors between UV and IR symmetry categories as… ▽ More Matching 't Hooft anomalies is a powerful tool for constraining the low-energy dynamics of quantum systems and their allowed renormalization group (RG) flows. For non-invertible (or categorical) symmetries, however, a key challenge has been the lack of a precise framework to characterize and quantify anomalies. We address this by identifying tensor functors between UV and IR symmetry categories as central to capturing these constraints. To this end, we introduce Anomalous Simple Categories (ASCies) as fundamental building blocks of categorical anomalies. A given symmetry category may support multiple ASCies, each encoding distinct anomalous features. These structures naturally arise in the context of the Symmetry Topological Field Theory (SymTFT), where tensor functors correspond to RG-interfaces between UV and IR SymTFTs, and ASCies are realized as particular such interfaces satisfying simple, universal criteria. We demonstrate the utility of this framework through examples involving anomalous 0-form, higher-form, and crucially, non-invertible symmetries in various spacetime dimensions. △ Less

Submitted 1 August, 2025; originally announced August 2025.

Comments: 37 pages + appendix

Writing-Zero: Bridge the Gap Between Non-verifiable Tasks and Verifiable Rewards

Authors: Ruipeng Jia, Yunyi Yang, Yongbo Gai, Kai Luo, Shihao Huang, Jianhe Lin, Xiaoxi Jiang, Guanjun Jiang

Abstract: Reinforcement learning with verifiable rewards (RLVR) has enabled large language models (LLMs) to achieve remarkable breakthroughs in reasoning tasks with objective ground-truth answers, such as mathematics and code generation. However, a significant gap remains for non-verifiable tasks, like creative writing and open-ended dialogue, where quality assessment is inherently subjective and lacks defi… ▽ More Reinforcement learning with verifiable rewards (RLVR) has enabled large language models (LLMs) to achieve remarkable breakthroughs in reasoning tasks with objective ground-truth answers, such as mathematics and code generation. However, a significant gap remains for non-verifiable tasks, like creative writing and open-ended dialogue, where quality assessment is inherently subjective and lacks definitive references. Existing approaches for these domains often rely on scalar reward models trained with human preferences, which suffer from limited generalization and are prone to reward hacking, such as over-explanation and length bias. In this work, we propose a unified RLVR-based training paradigm that bridges the gap between non-verifiable tasks and verifiable rewards. We introduce a writing-principle-based pairwise Generative Reward Model (GenRM) and a novel Bootstrapped Relative Policy Optimization (BRPO) algorithm. The pairwise writing GenRM leverages self-principled critique to transform subjective assessments into reliable, verifiable rewards, while BRPO enables dynamic, reference-free pairwise comparison by leveraging a bootstrapped response as temporary reference from within group rollouts during RL training. Our approach empowers LLMs to develop robust writing capabilities without supervised fine-tuning, as demonstrated by Writing-Zero, which shows consistent improvement and strong resistance to reward hacking compared to scalar reward baselines. Furthermore, our method achieves competitive results on both in-house and open-source writing benchmarks. Our findings suggest the potential to unify rule-based, reference-based, and reference-free reward modeling under the RLVR framework, thus paving the way for a comprehensive and scalable RL training paradigm applicable across all language tasks. △ Less

Submitted 11 June, 2025; v1 submitted 30 May, 2025; originally announced June 2025.

Pangu Ultra MoE: How to Train Your Big MoE on Ascend NPUs

Authors: Yehui Tang, Yichun Yin, Yaoyuan Wang, Hang Zhou, Yu Pan, Wei Guo, Ziyang Zhang, Miao Rang, Fangcheng Liu, Naifu Zhang, Binghan Li, Yonghan Dong, Xiaojun Meng, Yasheng Wang, Dong Li, Yin Li, Dandan Tu, Can Chen, Youliang Yan, Fisher Yu, Ruiming Tang, Yunhe Wang, Botian Huang, Bo Wang, Boxiao Liu , et al. (49 additional authors not shown)

Abstract: Sparse large language models (LLMs) with Mixture of Experts (MoE) and close to a trillion parameters are dominating the realm of most capable language models. However, the massive model scale poses significant challenges for the underlying software and hardware systems. In this paper, we aim to uncover a recipe to harness such scale on Ascend NPUs. The key goals are better usage of the computing r… ▽ More Sparse large language models (LLMs) with Mixture of Experts (MoE) and close to a trillion parameters are dominating the realm of most capable language models. However, the massive model scale poses significant challenges for the underlying software and hardware systems. In this paper, we aim to uncover a recipe to harness such scale on Ascend NPUs. The key goals are better usage of the computing resources under the dynamic sparse model structures and materializing the expected performance gain on the actual hardware. To select model configurations suitable for Ascend NPUs without repeatedly running the expensive experiments, we leverage simulation to compare the trade-off of various model hyperparameters. This study led to Pangu Ultra MoE, a sparse LLM with 718 billion parameters, and we conducted experiments on the model to verify the simulation results. On the system side, we dig into Expert Parallelism to optimize the communication between NPU devices to reduce the synchronization overhead. We also optimize the memory efficiency within the devices to further reduce the parameter and activation management overhead. In the end, we achieve an MFU of 30.0% when training Pangu Ultra MoE, with performance comparable to that of DeepSeek R1, on 6K Ascend NPUs, and demonstrate that the Ascend system is capable of harnessing all the training stages of the state-of-the-art language models. Extensive experiments indicate that our recipe can lead to efficient training of large-scale sparse language models with MoE. We also study the behaviors of such models for future reference. △ Less

Submitted 7 May, 2025; originally announced May 2025.

Why and How LLMs Hallucinate: Connecting the Dots with Subsequence Associations

Authors: Yiyou Sun, Yu Gai, Lijie Chen, Abhilasha Ravichander, Yejin Choi, Dawn Song

Abstract: Large language models (LLMs) frequently generate hallucinations-content that deviates from factual accuracy or provided context-posing challenges for diagnosis due to the complex interplay of underlying causes. This paper introduces a subsequence association framework to systematically trace and understand hallucinations. Our key insight is that hallucinations arise when dominant hallucinatory ass… ▽ More Large language models (LLMs) frequently generate hallucinations-content that deviates from factual accuracy or provided context-posing challenges for diagnosis due to the complex interplay of underlying causes. This paper introduces a subsequence association framework to systematically trace and understand hallucinations. Our key insight is that hallucinations arise when dominant hallucinatory associations outweigh faithful ones. Through theoretical and empirical analyses, we demonstrate that decoder-only transformers effectively function as subsequence embedding models, with linear layers encoding input-output associations. We propose a tracing algorithm that identifies causal subsequences by analyzing hallucination probabilities across randomized input contexts. Experiments show our method outperforms standard attribution techniques in identifying hallucination causes and aligns with evidence from the model's training corpus. This work provides a unified perspective on hallucinations and a robust framework for their tracing and analysis. △ Less

Submitted 17 April, 2025; originally announced April 2025.

The Alon-Tarsi Number of Cartesian product and Corona product of Hypercube Graph and Special Graphs

Authors: Zhiguo Li, Yujia Gai, Zeling Shao

Abstract: The \emph{Alon-Tarsi number} of a graph $G$ is the smallest $k$ so that there exists an orientation $D$ of $G$ with max outdegree $k-1$ satisfying the number of even Eulerian subgraphs different from the number of odd Eulerian subgraphs. In this paper, the Alon-Tarsi number of the $n$-cube is obtained according to its special properties, we obtain the Alon-Tarsi number of Cartesian product of some… ▽ More The \emph{Alon-Tarsi number} of a graph $G$ is the smallest $k$ so that there exists an orientation $D$ of $G$ with max outdegree $k-1$ satisfying the number of even Eulerian subgraphs different from the number of odd Eulerian subgraphs. In this paper, the Alon-Tarsi number of the $n$-cube is obtained according to its special properties, we obtain the Alon-Tarsi number of Cartesian product of some special bipartite graphs, and get the Alon-Tarsi number of Corona product of graphs. As corollaries, we get the Alon-Tarsi number of Cartesian product and Corona product of hypercube graph and special graphs. △ Less

Submitted 4 April, 2025; originally announced April 2025.

MSC Class: 05C15

UB-Mesh: a Hierarchically Localized nD-FullMesh Datacenter Network Architecture

Authors: Heng Liao, Bingyang Liu, Xianping Chen, Zhigang Guo, Chuanning Cheng, Jianbing Wang, Xiangyu Chen, Peng Dong, Rui Meng, Wenjie Liu, Zhe Zhou, Ziyang Zhang, Yuhang Gai, Cunle Qian, Yi Xiong, Zhongwu Cheng, Jing Xia, Yuli Ma, Xi Chen, Wenhua Du, Shizhong Xiao, Chungang Li, Yong Qin, Liudong Xiong, Zhou Yu , et al. (9 additional authors not shown)

Abstract: As the Large-scale Language Models (LLMs) continue to scale, the requisite computational power and bandwidth escalate. To address this, we introduce UB-Mesh, a novel AI datacenter network architecture designed to enhance scalability, performance, cost-efficiency and availability. Unlike traditional datacenters that provide symmetrical node-to-node bandwidth, UB-Mesh employs a hierarchically locali… ▽ More As the Large-scale Language Models (LLMs) continue to scale, the requisite computational power and bandwidth escalate. To address this, we introduce UB-Mesh, a novel AI datacenter network architecture designed to enhance scalability, performance, cost-efficiency and availability. Unlike traditional datacenters that provide symmetrical node-to-node bandwidth, UB-Mesh employs a hierarchically localized nD-FullMesh network topology. This design fully leverages the data locality of LLM training, prioritizing short-range, direct interconnects to minimize data movement distance and reduce switch usage. Although UB-Mesh's nD-FullMesh topology offers several theoretical advantages, its concrete architecture design, physical implementation and networking system optimization present new challenges. For the actual construction of UB-Mesh, we first design the UB-Mesh-Pod architecture, which is based on a 4D-FullMesh topology. UB-Mesh-Pod is implemented via a suite of hardware components that serve as the foundational building blocks, including specifically-designed NPU, CPU, Low-Radix-Switch (LRS), High-Radix-Switch (HRS), NICs and others. These components are interconnected via a novel Unified Bus (UB) technique, which enables flexible IO bandwidth allocation and hardware resource pooling. For networking system optimization, we propose advanced routing mechanism named All-Path-Routing (APR) to efficiently manage data traffic. These optimizations, combined with topology-aware performance enhancements and robust reliability measures like 64+1 backup design, result in 2.04x higher cost-efficiency, 7.2% higher network availability compared to traditional Clos architecture and 95%+ linearity in various LLM training tasks. △ Less

Submitted 17 May, 2025; v1 submitted 26 March, 2025; originally announced March 2025.

MMDT: Decoding the Trustworthiness and Safety of Multimodal Foundation Models

Authors: Chejian Xu, Jiawei Zhang, Zhaorun Chen, Chulin Xie, Mintong Kang, Yujin Potter, Zhun Wang, Zhuowen Yuan, Alexander Xiong, Zidi Xiong, Chenhui Zhang, Lingzhi Yuan, Yi Zeng, Peiyang Xu, Chengquan Guo, Andy Zhou, Jeffrey Ziwei Tan, Xuandong Zhao, Francesco Pinto, Zhen Xiang, Yu Gai, Zinan Lin, Dan Hendrycks, Bo Li, Dawn Song

Abstract: Multimodal foundation models (MMFMs) play a crucial role in various applications, including autonomous driving, healthcare, and virtual assistants. However, several studies have revealed vulnerabilities in these models, such as generating unsafe content by text-to-image models. Existing benchmarks on multimodal models either predominantly assess the helpfulness of these models, or only focus on li… ▽ More Multimodal foundation models (MMFMs) play a crucial role in various applications, including autonomous driving, healthcare, and virtual assistants. However, several studies have revealed vulnerabilities in these models, such as generating unsafe content by text-to-image models. Existing benchmarks on multimodal models either predominantly assess the helpfulness of these models, or only focus on limited perspectives such as fairness and privacy. In this paper, we present the first unified platform, MMDT (Multimodal DecodingTrust), designed to provide a comprehensive safety and trustworthiness evaluation for MMFMs. Our platform assesses models from multiple perspectives, including safety, hallucination, fairness/bias, privacy, adversarial robustness, and out-of-distribution (OOD) generalization. We have designed various evaluation scenarios and red teaming algorithms under different tasks for each perspective to generate challenging data, forming a high-quality benchmark. We evaluate a range of multimodal models using MMDT, and our findings reveal a series of vulnerabilities and areas for improvement across these perspectives. This work introduces the first comprehensive and unique safety and trustworthiness evaluation platform for MMFMs, paving the way for developing safer and more reliable MMFMs and systems. Our platform and benchmark are available at https://mmdecodingtrust.github.io/. △ Less

Submitted 18 March, 2025; originally announced March 2025.

Comments: ICLR 2025

Gapless Phases in (2+1)d with Non-Invertible Symmetries

Authors: Lakshya Bhardwaj, Yuhan Gai, Sheng-Jie Huang, Kansei Inamura, Sakura Schafer-Nameki, Apoorv Tiwari, Alison Warman

Abstract: The study of gapless phases with categorical (or so-called non-invertible) symmetries is a formidable task, in particular in higher than two space-time dimensions. In this paper we build on previous works arXiv:2408.05266 and arXiv:2502.20440 on gapped phases in (2+1)d and provide a systematic framework to study phase transitions with categorical symmetries. The Symmetry Topological Field Theory (… ▽ More The study of gapless phases with categorical (or so-called non-invertible) symmetries is a formidable task, in particular in higher than two space-time dimensions. In this paper we build on previous works arXiv:2408.05266 and arXiv:2502.20440 on gapped phases in (2+1)d and provide a systematic framework to study phase transitions with categorical symmetries. The Symmetry Topological Field Theory (SymTFT) is, as often in these matters, the central tool. Applied to gapless theories, we need to consider the extension of the SymTFT to interfaces between topological orders, so-called ``club sandwiches", which realize generalizations of so-called Kennedy-Tasaki (KT) transformations. This requires an input phase transition for a smaller symmetry, such as the Ising transition for $\mathbb{Z}_2$, and the SymTFT constructs a transformation to a gapless phase with a larger categorical symmetry. We carry this out for categorical symmetries whose SymTFT is a (3+1)d Dijkgraaf-Witten (DW) theory for a finite group $G$ with twist -- so-called all bosonic fusion 2-categories. We classify such interfaces using a physically motivated picture of generalized gauging, as well as with a complementary analysis using (bi-)module 2-categories.This is exemplified in numerous abelian and non-abelian DW theories, giving rise to interesting gapless phases such as intrinsically gapless symmetry protected phases (igSPTs) and spontaneous symmetry breaking phases (igSSBs) from abelian, $S_3$, and $D_8$ DW theories. △ Less

Submitted 26 May, 2026; v1 submitted 16 March, 2025; originally announced March 2025.

Comments: 114 pages + appendices

Journal ref: SciPost Phys. 21, 019 (2026)

A general design method for ultra-long optical path length multipass matrix cells

Authors: Yiyun Gai, Wenjin Li, Kaihao Yi, Xue Ou, Peng Liu, Xin Zhou

Abstract: For the first time, we propose a general design method for ultra-long optical path length (OPL) multipass matrix cells (MMCs) based on multi-cycle mode of two-sided field mirrors. The design idea of the dual circulation mode with two-sided field mirrors is elaborated in detail with the example of MMC based on dual Pickett Bradley White cell (PBWC), and the simple design methods of the other three… ▽ More For the first time, we propose a general design method for ultra-long optical path length (OPL) multipass matrix cells (MMCs) based on multi-cycle mode of two-sided field mirrors. The design idea of the dual circulation mode with two-sided field mirrors is elaborated in detail with the example of MMC based on dual Pickett Bradley White cell (PBWC), and the simple design methods of the other three MMCs based on the dual circulation mode of PBWC and Bernstein Herzberg White cell (BHWC) are given. Further, we propose a general design method for ultra-long OPL MMCs with multi-cycle mode by adding cyclic elements. The OPL of the MMCs designed by this method can reach the order of kilometers or even tens of kilometers. The novel MMCs have the advantages of simple structure, strong spot formation regularity, easy expansion, high mirror utilization ratio, high reuse times of spot spatial position, good stability and extremely high ratio of the optical path length to the volume (RLV). In order to evaluate the performance of the new MMCs, an open-path methane gas sensor with the MMC based on triple PBWC was constructed, which was used to continuously measure the methane in the laboratory, and the feasibility, effectiveness and practicability of the new design method were verified. The design method proposed in this paper provides a new idea for the design of multipass cell (MPC), and the new MMCs designed have great potential application value in the field of high-precision trace gas monitoring. △ Less

Submitted 17 January, 2025; v1 submitted 4 June, 2024; originally announced June 2024.

Journal ref: Optics Express 33, 2728-2744 (2025)

KnowHalu: Hallucination Detection via Multi-Form Knowledge Based Factual Checking

Authors: Jiawei Zhang, Chejian Xu, Yu Gai, Freddy Lecue, Dawn Song, Bo Li

Abstract: This paper introduces KnowHalu, a novel approach for detecting hallucinations in text generated by large language models (LLMs), utilizing step-wise reasoning, multi-formulation query, multi-form knowledge for factual checking, and fusion-based detection mechanism. As LLMs are increasingly applied across various domains, ensuring that their outputs are not hallucinated is critical. Recognizing the… ▽ More This paper introduces KnowHalu, a novel approach for detecting hallucinations in text generated by large language models (LLMs), utilizing step-wise reasoning, multi-formulation query, multi-form knowledge for factual checking, and fusion-based detection mechanism. As LLMs are increasingly applied across various domains, ensuring that their outputs are not hallucinated is critical. Recognizing the limitations of existing approaches that either rely on the self-consistency check of LLMs or perform post-hoc fact-checking without considering the complexity of queries or the form of knowledge, KnowHalu proposes a two-phase process for hallucination detection. In the first phase, it identifies non-fabrication hallucinations--responses that, while factually correct, are irrelevant or non-specific to the query. The second phase, multi-form based factual checking, contains five key steps: reasoning and query decomposition, knowledge retrieval, knowledge optimization, judgment generation, and judgment aggregation. Our extensive evaluations demonstrate that KnowHalu significantly outperforms SOTA baselines in detecting hallucinations across diverse tasks, e.g., improving by 15.65% in QA tasks and 5.50% in summarization tasks, highlighting its effectiveness and versatility in detecting hallucinations in LLM-generated content. △ Less

Submitted 2 April, 2024; originally announced April 2024.

Blockchain Large Language Models

Authors: Yu Gai, Liyi Zhou, Kaihua Qin, Dawn Song, Arthur Gervais

Abstract: This paper presents a dynamic, real-time approach to detecting anomalous blockchain transactions. The proposed tool, BlockGPT, generates tracing representations of blockchain activity and trains from scratch a large language model to act as a real-time Intrusion Detection System. Unlike traditional methods, BlockGPT is designed to offer an unrestricted search space and does not rely on predefined… ▽ More This paper presents a dynamic, real-time approach to detecting anomalous blockchain transactions. The proposed tool, BlockGPT, generates tracing representations of blockchain activity and trains from scratch a large language model to act as a real-time Intrusion Detection System. Unlike traditional methods, BlockGPT is designed to offer an unrestricted search space and does not rely on predefined rules or patterns, enabling it to detect a broader range of anomalies. We demonstrate the effectiveness of BlockGPT through its use as an anomaly detection tool for Ethereum transactions. In our experiments, it effectively identifies abnormal transactions among a dataset of 68M transactions and has a batched throughput of 2284 transactions per second on average. Our results show that, BlockGPT identifies abnormal transactions by ranking 49 out of 124 attacks among the top-3 most abnormal transactions interacting with their victim contracts. This work makes contributions to the field of blockchain transaction analysis by introducing a custom data encoding compatible with the transformer architecture, a domain-specific tokenization technique, and a tree encoding method specifically crafted for the Ethereum Virtual Machine (EVM) trace representation. △ Less

Submitted 29 April, 2023; v1 submitted 25 April, 2023; originally announced April 2023.

Robotic Assembly Control Reconfiguration Based on Transfer Reinforcement Learning for Objects with Different Geometric Features

Authors: Yuhang Gai, Bing Wang, Jiwen Zhang, Dan Wu, Ken Chen

Abstract: Robotic force-based compliance control is a preferred approach to achieve high-precision assembly tasks. When the geometric features of assembly objects are asymmetric or irregular, reinforcement learning (RL) agents are gradually incorporated into the compliance controller to adapt to complex force-pose mapping which is hard to model analytically. Since force-pose mapping is strongly dependent on… ▽ More Robotic force-based compliance control is a preferred approach to achieve high-precision assembly tasks. When the geometric features of assembly objects are asymmetric or irregular, reinforcement learning (RL) agents are gradually incorporated into the compliance controller to adapt to complex force-pose mapping which is hard to model analytically. Since force-pose mapping is strongly dependent on geometric features, a compliance controller is only optimal for current geometric features. To reduce the learning cost of assembly objects with different geometric features, this paper is devoted to answering how to reconfigure existing controllers for new assembly objects with different geometric features. In this paper, model-based parameters are first reconfigured based on the proposed Equivalent Theory of Compliance Law (ETCL). Then the RL agent is transferred based on the proposed Weighted Dimensional Policy Distillation (WDPD) method. The experiment results demonstrate that the control reconfiguration method costs less time and achieves better control performance, which confirms the validity of proposed methods. △ Less

Submitted 4 November, 2022; originally announced November 2022.

Local Connection Reinforcement Learning Method for Efficient Control of Robotic Peg-in-Hole Assembly

Authors: Yuhang Gai, Jiwen Zhang, Dan Wu, Ken Chen

Abstract: Traditional control methods of robotic peg-in-hole assembly rely on complex contact state analysis. Reinforcement learning (RL) is gradually becoming a preferred method of controlling robotic peg-in-hole assembly tasks. However, the training process of RL is quite time-consuming because RL methods are always globally connected, which means all state components are assumed to be the input of polici… ▽ More Traditional control methods of robotic peg-in-hole assembly rely on complex contact state analysis. Reinforcement learning (RL) is gradually becoming a preferred method of controlling robotic peg-in-hole assembly tasks. However, the training process of RL is quite time-consuming because RL methods are always globally connected, which means all state components are assumed to be the input of policies for all action components, thus increasing action space and state space to be explored. In this paper, we first define continuous space serialized Shapley value (CS3) and construct a connection graph to clarify the correlativity of action components on state components. Then we propose a local connection reinforcement learning (LCRL) method based on the connection graph, which eliminates the influence of irrelevant state components on the selection of action components. The simulation and experiment results demonstrate that the control strategy obtained through LCRL method improves the stability and rapidity of the control process. LCRL method will enhance the data-efficiency and increase the final reward of the training process. △ Less

Submitted 24 October, 2022; originally announced October 2022.

iEmoTTS: Toward Robust Cross-Speaker Emotion Transfer and Control for Speech Synthesis based on Disentanglement between Prosody and Timbre

Authors: Guangyan Zhang, Ying Qin, Wenjie Zhang, Jialun Wu, Mei Li, Yutao Gai, Feijun Jiang, Tan Lee

Abstract: The capability of generating speech with specific type of emotion is desired for many applications of human-computer interaction. Cross-speaker emotion transfer is a common approach to generating emotional speech when speech with emotion labels from target speakers is not available for model training. This paper presents a novel cross-speaker emotion transfer system, named iEmoTTS. The system is c… ▽ More The capability of generating speech with specific type of emotion is desired for many applications of human-computer interaction. Cross-speaker emotion transfer is a common approach to generating emotional speech when speech with emotion labels from target speakers is not available for model training. This paper presents a novel cross-speaker emotion transfer system, named iEmoTTS. The system is composed of an emotion encoder, a prosody predictor, and a timbre encoder. The emotion encoder extracts the identity of emotion type as well as the respective emotion intensity from the mel-spectrogram of input speech. The emotion intensity is measured by the posterior probability that the input utterance carries that emotion. The prosody predictor is used to provide prosodic features for emotion transfer. The timber encoder provides timbre-related information for the system. Unlike many other studies which focus on disentangling speaker and style factors of speech, the iEmoTTS is designed to achieve cross-speaker emotion transfer via disentanglement between prosody and timbre. Prosody is considered as the main carrier of emotion-related speech characteristics and timbre accounts for the essential characteristics for speaker identification. Zero-shot emotion transfer, meaning that speech of target speakers are not seen in model training, is also realized with iEmoTTS. Extensive experiments of subjective evaluation have been carried out. The results demonstrate the effectiveness of iEmoTTS as compared with other recently proposed systems of cross-speaker emotion transfer. It is shown that iEmoTTS can produce speech with designated emotion type and controllable emotion intensity. With appropriate information bottleneck capacity, iEmoTTS is able to effectively transfer emotion information to a new speaker. Audio samples are publicly available https://patrick-g-zhang.github.io/iemotts/ △ Less

Submitted 4 January, 2023; v1 submitted 29 June, 2022; originally announced June 2022.

Comments: Submitted to IEEE Transactions on Audio, Speech, and Language Processing

Collective Behavior of Crowded Drops in Microfluidic Systems

Authors: Ya Gai, Andrea Montessori, Sauro Succi, Sindy K. Y. Tang

Abstract: Droplet microfluidics, in which micro-droplets serve as individual reactors, has enabled a wide range of high-throughput biochemical processes. Unlike solid wells typically used in current biochemical assays, droplets are subject to instability and can undergo breakup, especially under fast flow conditions. Although the physics of single drops has been studied extensively, the flow of crowded drop… ▽ More Droplet microfluidics, in which micro-droplets serve as individual reactors, has enabled a wide range of high-throughput biochemical processes. Unlike solid wells typically used in current biochemical assays, droplets are subject to instability and can undergo breakup, especially under fast flow conditions. Although the physics of single drops has been studied extensively, the flow of crowded drops or concentrated emulsions, where droplet volume fraction exceeds 80 percent, is relatively unexplored in microfluidics. In this article and the related invited lecture from the 74th Annual Meeting of the American Physical Society's Division of Fluid Dynamics, we describe the collective behavior of drops in a concentrated emulsion by tracking the dynamics and the fate of individual drops within the emulsion. At the slow flow limit of the concentrated emulsion, we observe an unexpected order, where the velocity of individual drops in the emulsion exhibits spatiotemporal periodicity. As the flow rate increases, the emulsion transitions from a solid-like to a liquid-like material, and the spatiotemporal order in the flow is lost. At the fast flow limit, droplet breakup starts to occur. We show that droplet breakup within the emulsion follows a probability distribution, in stark contrast to the deterministic behavior in classical single-drop studies. In addition to capillary number and viscosity ratio, break-up probability is governed by a confinement factor that measures drop size relative to a characteristic channel length. The breakup probability arises from the time-varying packing configuration of the drops. Finally, we discuss recent progress in computation methods for recapitulating the flow of concentrated emulsions. △ Less

Submitted 1 June, 2022; originally announced June 2022.

Comments: 58 pages, 14 figures

Grounded Graph Decoding Improves Compositional Generalization in Question Answering

Authors: Yu Gai, Paras Jain, Wendi Zhang, Joseph E. Gonzalez, Dawn Song, Ion Stoica

Abstract: Question answering models struggle to generalize to novel compositions of training patterns, such to longer sequences or more complex test structures. Current end-to-end models learn a flat input embedding which can lose input syntax context. Prior approaches improve generalization by learning permutation invariant models, but these methods do not scale to more complex train-test splits. We propos… ▽ More Question answering models struggle to generalize to novel compositions of training patterns, such to longer sequences or more complex test structures. Current end-to-end models learn a flat input embedding which can lose input syntax context. Prior approaches improve generalization by learning permutation invariant models, but these methods do not scale to more complex train-test splits. We propose Grounded Graph Decoding, a method to improve compositional generalization of language representations by grounding structured predictions with an attention mechanism. Grounding enables the model to retain syntax information from the input in thereby significantly improving generalization over complex inputs. By predicting a structured graph containing conjunctions of query clauses, we learn a group invariant representation without making assumptions on the target domain. Our model significantly outperforms state-of-the-art baselines on the Compositional Freebase Questions (CFQ) dataset, a challenging benchmark for compositional generalization in question answering. Moreover, we effectively solve the MCD1 split with 98% accuracy. △ Less

Submitted 5 November, 2021; originally announced November 2021.

Comments: To be published in Findings of EMNLP 2021. Code available at https://github.com/gaiyu0/cfq

Practical Convex Formulation of Robust One-hidden-layer Neural Network Training

Authors: Yatong Bai, Tanmay Gautam, Yu Gai, Somayeh Sojoudi

Abstract: Recent work has shown that the training of a one-hidden-layer, scalar-output fully-connected ReLU neural network can be reformulated as a finite-dimensional convex program. Unfortunately, the scale of such a convex program grows exponentially in data size. In this work, we prove that a stochastic procedure with a linear complexity well approximates the exact formulation. Moreover, we derive a conv… ▽ More Recent work has shown that the training of a one-hidden-layer, scalar-output fully-connected ReLU neural network can be reformulated as a finite-dimensional convex program. Unfortunately, the scale of such a convex program grows exponentially in data size. In this work, we prove that a stochastic procedure with a linear complexity well approximates the exact formulation. Moreover, we derive a convex optimization approach to efficiently solve the "adversarial training" problem, which trains neural networks that are robust to adversarial input perturbations. Our method can be applied to binary classification and regression, and provides an alternative to the current adversarial training methods, such as Fast Gradient Sign Method (FGSM) and Projected Gradient Descent (PGD). We demonstrate in experiments that the proposed method achieves a noticeably better adversarial robustness and performance than the existing methods. △ Less

Submitted 25 May, 2021; originally announced May 2021.

Progressive extension of reinforcement learning action dimension for asymmetric assembly tasks

Authors: Yuhang Gai, Jiuming Guo, Dan Wu, Ken Chen

Abstract: Reinforcement learning (RL) is always the preferred embodiment to construct the control strategy of complex tasks, like asymmetric assembly tasks. However, the convergence speed of reinforcement learning severely restricts its practical application. In this paper, the convergence is first accelerated by combining RL and compliance control. Then a completely innovative progressive extension of acti… ▽ More Reinforcement learning (RL) is always the preferred embodiment to construct the control strategy of complex tasks, like asymmetric assembly tasks. However, the convergence speed of reinforcement learning severely restricts its practical application. In this paper, the convergence is first accelerated by combining RL and compliance control. Then a completely innovative progressive extension of action dimension (PEAD) mechanism is proposed to optimize the convergence of RL algorithms. The PEAD method is verified in DDPG and PPO. The results demonstrate the PEAD method will enhance the data-efficiency and time-efficiency of RL algorithms as well as increase the stable reward, which provides more potential for the application of RL. △ Less

Submitted 6 April, 2021; originally announced April 2021.

Feature-Based Compliance Control for Peg-in-Hole Assembly with Clearance or Interference Fit

Authors: Yuhang Gai, Jiuming Guo, Dan Wu, Ken Chen

Abstract: This paper aims at solving mass precise peg-in-hole assembly. First, a feature space and a response space are constructed according to the relative pose and equivalent forces and moments. Then the contact states are segmented in the feature space and the segmentation boundaries are mapped into the response space. Further, a feature-based compliance control (FBCC) algorithm is proposed based on bou… ▽ More This paper aims at solving mass precise peg-in-hole assembly. First, a feature space and a response space are constructed according to the relative pose and equivalent forces and moments. Then the contact states are segmented in the feature space and the segmentation boundaries are mapped into the response space. Further, a feature-based compliance control (FBCC) algorithm is proposed based on boundary mapping. In the FBCC algorithm, a direction matrix is designed to execute accurate adjustment and an integrator is applied to eliminate the residual responses. Finally, the simulations and experiments demonstrate the superiority, robustness, and generalization ability of the FBCC. △ Less

Submitted 29 March, 2021; originally announced March 2021.

Comments: 10 pages, 14 figures

A General Framework of Online Updating Variable Selection for Generalized Linear Models with Streaming Datasets

Authors: Xiaoyu Ma, Lu Lin, Yujie Gai

Abstract: In the research field of big data, one of important issues is how to recover the sequentially changing sets of true features when the data sets arrive sequentially. The paper presents a general framework for online updating variable selection and parameter estimation in generalized linear models with streaming datasets. This is a type of online updating penalty likelihoods with differentiable or n… ▽ More In the research field of big data, one of important issues is how to recover the sequentially changing sets of true features when the data sets arrive sequentially. The paper presents a general framework for online updating variable selection and parameter estimation in generalized linear models with streaming datasets. This is a type of online updating penalty likelihoods with differentiable or non-differentiable penalty function. The online updating coordinate descent algorithm is proposed to solve the online updating optimization problem. Moreover, a tuning parameter selection is suggested in an online updating way. The selection and estimation consistencies, and the oracle property are established, theoretically. Our methods are further examined and illustrated by various numerical examples from both simulation experiments and a real data analysis. △ Less

Submitted 21 January, 2021; originally announced January 2021.

Comments: 35 pages, 2 figures, 13 tables

A Statistical Framework for Low-bitwidth Training of Deep Neural Networks

Authors: Jianfei Chen, Yu Gai, Zhewei Yao, Michael W. Mahoney, Joseph E. Gonzalez

Abstract: Fully quantized training (FQT), which uses low-bitwidth hardware by quantizing the activations, weights, and gradients of a neural network model, is a promising approach to accelerate the training of deep neural networks. One major challenge with FQT is the lack of theoretical understanding, in particular of how gradient quantization impacts convergence properties. In this paper, we address this p… ▽ More Fully quantized training (FQT), which uses low-bitwidth hardware by quantizing the activations, weights, and gradients of a neural network model, is a promising approach to accelerate the training of deep neural networks. One major challenge with FQT is the lack of theoretical understanding, in particular of how gradient quantization impacts convergence properties. In this paper, we address this problem by presenting a statistical framework for analyzing FQT algorithms. We view the quantized gradient of FQT as a stochastic estimator of its full precision counterpart, a procedure known as quantization-aware training (QAT). We show that the FQT gradient is an unbiased estimator of the QAT gradient, and we discuss the impact of gradient quantization on its variance. Inspired by these theoretical results, we develop two novel gradient quantizers, and we show that these have smaller variance than the existing per-tensor quantizer. For training ResNet-50 on ImageNet, our 5-bit block Householder quantizer achieves only 0.5% validation accuracy loss relative to QAT, comparable to the existing INT8 baseline. △ Less

Submitted 27 October, 2020; originally announced October 2020.

Comments: 24 pages

Neutron Star Extreme Matter Observatory: A kilohertz-band gravitational-wave detector in the global network

Authors: K. Ackley, V. B. Adya, P. Agrawal, P. Altin, G. Ashton, M. Bailes, E. Baltinas, A. Barbuio, D. Beniwal, C. Blair, D. Blair, G. N. Bolingbroke, V. Bossilkov, S. Shachar Boublil, D. D. Brown, B. J. Burridge, J. Calderon Bustillo, J. Cameron, H. Tuong Cao, J. B. Carlin, S. Chang, P. Charlton, C. Chatterjee, D. Chattopadhyay, X. Chen , et al. (139 additional authors not shown)

Abstract: Gravitational waves from coalescing neutron stars encode information about nuclear matter at extreme densities, inaccessible by laboratory experiments. The late inspiral is influenced by the presence of tides, which depend on the neutron star equation of state. Neutron star mergers are expected to often produce rapidly-rotating remnant neutron stars that emit gravitational waves. These will provid… ▽ More Gravitational waves from coalescing neutron stars encode information about nuclear matter at extreme densities, inaccessible by laboratory experiments. The late inspiral is influenced by the presence of tides, which depend on the neutron star equation of state. Neutron star mergers are expected to often produce rapidly-rotating remnant neutron stars that emit gravitational waves. These will provide clues to the extremely hot post-merger environment. This signature of nuclear matter in gravitational waves contains most information in the 2-4 kHz frequency band, which is outside of the most sensitive band of current detectors. We present the design concept and science case for a neutron star extreme matter observatory (NEMO): a gravitational-wave interferometer optimized to study nuclear physics with merging neutron stars. The concept uses high circulating laser power, quantum squeezing and a detector topology specifically designed to achieve the high-frequency sensitivity necessary to probe nuclear matter using gravitational waves. Above one kHz, the proposed strain sensitivity is comparable to full third-generation detectors at a fraction of the cost. Such sensitivity changes expected event rates for detection of post-merger remnants from approximately one per few decades with two A+ detectors to a few per year, and potentially allows for the first gravitational-wave observations of supernovae, isolated neutron stars, and other exotica. △ Less

Submitted 5 November, 2020; v1 submitted 6 July, 2020; originally announced July 2020.

Comments: Accepted for publication in PASA

Journal ref: PASA (2020) 37, e047

Deep Graph Library: A Graph-Centric, Highly-Performant Package for Graph Neural Networks

Authors: Minjie Wang, Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, Tianjun Xiao, Tong He, George Karypis, Jinyang Li, Zheng Zhang

Abstract: Advancing research in the emerging field of deep graph learning requires new tools to support tensor computation over graphs. In this paper, we present the design principles and implementation of Deep Graph Library (DGL). DGL distills the computational patterns of GNNs into a few generalized sparse tensor operations suitable for extensive parallelization. By advocating graph as the central program… ▽ More Advancing research in the emerging field of deep graph learning requires new tools to support tensor computation over graphs. In this paper, we present the design principles and implementation of Deep Graph Library (DGL). DGL distills the computational patterns of GNNs into a few generalized sparse tensor operations suitable for extensive parallelization. By advocating graph as the central programming abstraction, DGL can perform optimizations transparently. By cautiously adopting a framework-neutral design, DGL allows users to easily port and leverage the existing components across multiple deep learning frameworks. Our evaluation shows that DGL significantly outperforms other popular GNN-oriented frameworks in both speed and memory consumption over a variety of benchmarks and has little overhead for small scale workloads. △ Less

Submitted 25 August, 2020; v1 submitted 3 September, 2019; originally announced September 2019.

Comments: Major update with significantly more results

Loss Functions for Multiset Prediction

Authors: Sean Welleck, Zixin Yao, Yu Gai, Jialin Mao, Zheng Zhang, Kyunghyun Cho

Abstract: We study the problem of multiset prediction. The goal of multiset prediction is to train a predictor that maps an input to a multiset consisting of multiple items. Unlike existing problems in supervised learning, such as classification, ranking and sequence generation, there is no known order among items in a target multiset, and each item in the multiset may appear more than once, making this pro… ▽ More We study the problem of multiset prediction. The goal of multiset prediction is to train a predictor that maps an input to a multiset consisting of multiple items. Unlike existing problems in supervised learning, such as classification, ranking and sequence generation, there is no known order among items in a target multiset, and each item in the multiset may appear more than once, making this problem extremely challenging. In this paper, we propose a novel multiset loss function by viewing this problem from the perspective of sequential decision making. The proposed multiset loss function is empirically evaluated on two families of datasets, one synthetic and the other real, with varying levels of difficulty, against various baseline loss functions including reinforcement learning, sequence, and aggregated distribution matching loss functions. The experiments reveal the effectiveness of the proposed loss function over the others. △ Less

Submitted 25 October, 2018; v1 submitted 14 November, 2017; originally announced November 2017.

Comments: NIPS 2018

On Equivalence of Likelihood Maximization of Stochastic Block Model and Constrained Nonnegative Matrix Factorization

Authors: Zhong-Yuan Zhang, Yujie Gai, Yu-Fei Wang, Hui-Min Cheng, Xin Liu

Abstract: Community structures detection in complex network is important for understanding not only the topological structures of the network, but also the functions of it. Stochastic block model and nonnegative matrix factorization are two widely used methods for community detection, which are proposed from different perspectives. In this paper, the relations between them are studied. The logarithm of like… ▽ More Community structures detection in complex network is important for understanding not only the topological structures of the network, but also the functions of it. Stochastic block model and nonnegative matrix factorization are two widely used methods for community detection, which are proposed from different perspectives. In this paper, the relations between them are studied. The logarithm of likelihood function for stochastic block model can be reformulated under the framework of nonnegative matrix factorization. Besides the model equivalence, the algorithms employed by the two methods are different. Preliminary numerical experiments are carried out to compare the behaviors of the algorithms. △ Less

Submitted 10 July, 2017; v1 submitted 5 April, 2016; originally announced April 2016.

Inference for biased models: a quasi-instrumental variable approach

Authors: Lu Lin, Lixing Zhu, Yujie Gai

Abstract: For linear regression models who are not exactly sparse in the sense that the coefficients of the insignificant variables are not exactly zero, the working models obtained by a variable selection are often biased. Even in sparse cases, after a variable selection, when some significant variables are missing, the working models are biased as well. Thus, under such situations, root-n consistent estim… ▽ More For linear regression models who are not exactly sparse in the sense that the coefficients of the insignificant variables are not exactly zero, the working models obtained by a variable selection are often biased. Even in sparse cases, after a variable selection, when some significant variables are missing, the working models are biased as well. Thus, under such situations, root-n consistent estimation and accurate prediction could not be expected. In this paper, a novel remodelling method is proposed to produce an unbiased model when quasi-instrumental variables are introduced. The root-n estimation consistency and the asymptotic normality can be achieved, and the prediction accuracy can be promoted as well. The performance of the new method is examined through simulation studies. △ Less

Submitted 15 July, 2014; originally announced July 2014.

Comments: 33 pages. arXiv admin note: substantial text overlap with arXiv:1112.0712, arXiv:1008.1345

Estimation and inference for high-dimensional non-sparse models

Authors: Lu Lin, Lixing Zhu, Yujie Gai

Abstract: To successfully work on variable selection, sparse model structure has become a basic assumption for all existing methods. However, this assumption is questionable as it is hard to hold in most of cases and none of existing methods may provide consistent estimation and accurate model prediction in nons-parse scenarios. In this paper, we propose semiparametric re-modeling and inference when the lin… ▽ More To successfully work on variable selection, sparse model structure has become a basic assumption for all existing methods. However, this assumption is questionable as it is hard to hold in most of cases and none of existing methods may provide consistent estimation and accurate model prediction in nons-parse scenarios. In this paper, we propose semiparametric re-modeling and inference when the linear regression model under study is possibly non-sparse. After an initial working model is selected by a method such as the Dantzig selector adopted in this paper, we re-construct a globally unbiased semiparametric model by use of suitable instrumental variables and nonparametric adjustment. The newly defined model is identifiable, and the estimator of parameter vector is asymptotically normal. The consistency, together with the re-built model, promotes model prediction. This method naturally works when the model is indeed sparse and thus is of robustness against non-sparseness in certain sense. Simulation studies show that the new approach has, particularly when $p$ is much larger than $n$, significant improvement of estimation and prediction accuracies over the Gaussian Dantzig selector and other classical methods. Even when the model under study is sparse, our method is also comparable to the existing methods designed for sparse models. △ Less

Submitted 3 December, 2011; originally announced December 2011.

Comments: This is a substantial revision of the manuscript Adaptive post-Dantzig estimation and prediction for non-sparse "large $p$ and small $n$" models [arXiv:1008.1345]

Online Learning Algorithms for Stochastic Water-Filling

Authors: Yi Gai, Bhaskar Krishnamachari

Abstract: Water-filling is the term for the classic solution to the problem of allocating constrained power to a set of parallel channels to maximize the total data-rate. It is used widely in practice, for example, for power allocation to sub-carriers in multi-user OFDM systems such as WiMax. The classic water-filling algorithm is deterministic and requires perfect knowledge of the channel gain to noise rat… ▽ More Water-filling is the term for the classic solution to the problem of allocating constrained power to a set of parallel channels to maximize the total data-rate. It is used widely in practice, for example, for power allocation to sub-carriers in multi-user OFDM systems such as WiMax. The classic water-filling algorithm is deterministic and requires perfect knowledge of the channel gain to noise ratios. In this paper we consider how to do power allocation over stochastically time-varying (i.i.d.) channels with unknown gain to noise ratio distributions. We adopt an online learning framework based on stochastic multi-armed bandits. We consider two variations of the problem, one in which the goal is to find a power allocation to maximize $\sum\limits_i \mathbb{E}[\log(1 + SNR_i)]$, and another in which the goal is to find a power allocation to maximize $\sum\limits_i \log(1 + \mathbb{E}[SNR_i])$. For the first problem, we propose a \emph{cognitive water-filling} algorithm that we call CWF1. We show that CWF1 obtains a regret (defined as the cumulative gap over time between the sum-rate obtained by a distribution-aware genie and this policy) that grows polynomially in the number of channels and logarithmically in time, implying that it asymptotically achieves the optimal time-averaged rate that can be obtained when the gain distributions are known. For the second problem, we present an algorithm called CWF2, which is, to our knowledge, the first algorithm in the literature on stochastic multi-armed bandits to exploit non-linear dependencies between the arms. We prove that the number of times CWF2 picks the incorrect power allocation is bounded by a function that is polynomial in the number of channels and logarithmic in time, implying that its frequency of incorrect allocation tends to zero. △ Less

Submitted 9 September, 2011; originally announced September 2011.

Online Learning for Combinatorial Network Optimization with Restless Markovian Rewards

Authors: Yi Gai, Bhaskar Krishnamachari, Mingyan Liu

Abstract: Combinatorial network optimization algorithms that compute optimal structures taking into account edge weights form the foundation for many network protocols. Examples include shortest path routing, minimal spanning tree computation, maximum weighted matching on bipartite graphs, etc. We present CLRMR, the first online learning algorithm that efficiently solves the stochastic version of these prob… ▽ More Combinatorial network optimization algorithms that compute optimal structures taking into account edge weights form the foundation for many network protocols. Examples include shortest path routing, minimal spanning tree computation, maximum weighted matching on bipartite graphs, etc. We present CLRMR, the first online learning algorithm that efficiently solves the stochastic version of these problems where the underlying edge weights vary as independent Markov chains with unknown dynamics. The performance of an online learning algorithm is characterized in terms of regret, defined as the cumulative difference in rewards between a suitably-defined genie, and that obtained by the given algorithm. We prove that, compared to a genie that knows the Markov transition matrices and uses the single-best structure at all times, CLRMR yields regret that is polynomial in the number of edges and nearly-logarithmic in time. △ Less

Submitted 7 September, 2011; originally announced September 2011.

Efficient Online Learning for Opportunistic Spectrum Access

Authors: Wenhan Dai, Yi Gai, Bhaskar Krishnamachari

Abstract: The problem of opportunistic spectrum access in cognitive radio networks has been recently formulated as a non-Bayesian restless multi-armed bandit problem. In this problem, there are N arms (corresponding to channels) and one player (corresponding to a secondary user). The state of each arm evolves as a finite-state Markov chain with unknown parameters. At each time slot, the player can select K… ▽ More The problem of opportunistic spectrum access in cognitive radio networks has been recently formulated as a non-Bayesian restless multi-armed bandit problem. In this problem, there are N arms (corresponding to channels) and one player (corresponding to a secondary user). The state of each arm evolves as a finite-state Markov chain with unknown parameters. At each time slot, the player can select K < N arms to play and receives state-dependent rewards (corresponding to the throughput obtained given the activity of primary users). The objective is to maximize the expected total rewards (i.e., total throughput) obtained over multiple plays. The performance of an algorithm for such a multi-armed bandit problem is measured in terms of regret, defined as the difference in expected reward compared to a model-aware genie who always plays the best K arms. In this paper, we propose a new continuous exploration and exploitation (CEE) algorithm for this problem. When no information is available about the dynamics of the arms, CEE is the first algorithm to guarantee near-logarithmic regret uniformly over time. When some bounds corresponding to the stationary state distributions and the state-dependent rewards are known, we show that CEE can be easily modified to achieve logarithmic regret over time. In contrast, prior algorithms require additional information concerning bounds on the second eigenvalues of the transition matrices in order to guarantee logarithmic regret. Finally, we show through numerical simulations that CEE is more efficient than prior algorithms. △ Less

Submitted 7 September, 2011; originally announced September 2011.

The Non-Bayesian Restless Multi-Armed Bandit: A Case of Near-Logarithmic Strict Regret

Authors: Wenhan Dai, Yi Gai, Bhaskar Krishnamachari, Qing Zhao

Abstract: In the classic Bayesian restless multi-armed bandit (RMAB) problem, there are $N$ arms, with rewards on all arms evolving at each time as Markov chains with known parameters. A player seeks to activate $K \geq 1$ arms at each time in order to maximize the expected total reward obtained over multiple plays. RMAB is a challenging problem that is known to be PSPACE-hard in general. We consider in thi… ▽ More In the classic Bayesian restless multi-armed bandit (RMAB) problem, there are $N$ arms, with rewards on all arms evolving at each time as Markov chains with known parameters. A player seeks to activate $K \geq 1$ arms at each time in order to maximize the expected total reward obtained over multiple plays. RMAB is a challenging problem that is known to be PSPACE-hard in general. We consider in this work the even harder non-Bayesian RMAB, in which the parameters of the Markov chain are assumed to be unknown \emph{a priori}. We develop an original approach to this problem that is applicable when the corresponding Bayesian problem has the structure that, depending on the known parameter values, the optimal solution is one of a prescribed finite set of policies. In such settings, we propose to learn the optimal policy for the non-Bayesian RMAB by employing a suitable meta-policy which treats each policy from this finite set as an arm in a different non-Bayesian multi-armed bandit problem for which a single-arm selection policy is optimal. We demonstrate this approach by developing a novel sensing policy for opportunistic spectrum access over unknown dynamic channels. We prove that our policy achieves near-logarithmic regret (the difference in expected reward compared to a model-aware genie), which leads to the same average reward that can be achieved by the optimal policy under a known model. This is the first such result in the literature for a non-Bayesian RMAB. For our proof, we also develop a novel generalization of the Chernoff-Hoeffding bound. △ Less

Submitted 7 September, 2011; originally announced September 2011.

Comments: arXiv admin note: significant text overlap with arXiv:1011.4752

Funding Games: the Truth but not the Whole Truth

Authors: Amotz Bar-Noy, Yi Gai, Matthew P. Johnson, Bhaskar Krishnamachari, George Rabanca

Abstract: We introduce the Funding Game, in which $m$ identical resources are to be allocated among $n$ selfish agents. Each agent requests a number of resources $x_i$ and reports a valuation $\tilde{v}_i(x_i)$, which verifiably {\em lower}-bounds $i$'s true value for receiving $x_i$ items. The pairs $(x_i, \tilde{v}_i(x_i))$ can be thought of as size-value pairs defining a knapsack problem with capacity… ▽ More We introduce the Funding Game, in which $m$ identical resources are to be allocated among $n$ selfish agents. Each agent requests a number of resources $x_i$ and reports a valuation $\tilde{v}_i(x_i)$, which verifiably {\em lower}-bounds $i$'s true value for receiving $x_i$ items. The pairs $(x_i, \tilde{v}_i(x_i))$ can be thought of as size-value pairs defining a knapsack problem with capacity $m$. A publicly-known algorithm is used to solve this knapsack problem, deciding which requests to satisfy in order to maximize the social welfare. We show that a simple mechanism based on the knapsack {\it highest ratio greedy} algorithm provides a Bayesian Price of Anarchy of 2, and for the complete information version of the game we give an algorithm that computes a Nash equilibrium strategy profile in $O(n^2 \log^2 m)$ time. Our primary algorithmic result shows that an extension of the mechanism to $k$ rounds has a Price of Anarchy of $1 + \frac{1}{k}$, yielding a graceful tradeoff between communication complexity and the social welfare. △ Less

Submitted 15 November, 2012; v1 submitted 12 July, 2011; originally announced July 2011.

A Packet Dropping Mechanism for Efficient Operation of M/M/1 Queues with Selfish Users

Authors: Yi Gai, Hua Liu, Bhaskar Krishnamachari

Abstract: We consider a fundamental game theoretic problem concerning selfish users contributing packets to an M/M/1 queue. In this game, each user controls its own input rate so as to optimize a desired tradeoff between throughput and delay. We first show that the original game has an inefficient Nash Equilibrium (NE), with a Price of Anarchy (PoA) that scales linearly or worse in the number of users. In o… ▽ More We consider a fundamental game theoretic problem concerning selfish users contributing packets to an M/M/1 queue. In this game, each user controls its own input rate so as to optimize a desired tradeoff between throughput and delay. We first show that the original game has an inefficient Nash Equilibrium (NE), with a Price of Anarchy (PoA) that scales linearly or worse in the number of users. In order to improve the outcome efficiency, we propose an easily implementable mechanism design whereby the server randomly drops packets with a probability that is a function of the total arrival rate. We show that this results in a modified M/M/1 queueing game that is an ordinal potential game with at least one NE. In particular, for a linear packet dropping function, which is similar to the Random Early Detection (RED) algorithm used in Internet Congestion Control, we prove that there is a unique NE. We also show that the simple best response dynamic converges to this unique equilibrium. Finally, for this scheme, we prove that the social welfare (expressed either as the summation of utilities of all players, or as the summation of the logarithm of utilities of all players) at the equilibrium point can be arbitrarily close to the social welfare at the global optimal point, i.e. the PoA can be made arbitrarily close to 1. We also study the impact of arrival rate estimation error on the PoA through simulations. △ Less

Submitted 20 June, 2011; originally announced June 2011.

Comments: This work is an extended version of the conference paper: Y. Gai, H. Liu and B. Krishnamachari, "A packet dropping-based incentive mechanism for M/M/1 queues with selfish users", the 30th IEEE International Conference on Computer Communications (IEEE INFOCOM 2011), China, April, 2011

Decentralized Online Learning Algorithms for Opportunistic Spectrum Access

Authors: Yi Gai, Bhaskar Krishnamachari

Abstract: The fundamental problem of multiple secondary users contending for opportunistic spectrum access over multiple channels in cognitive radio networks has been formulated recently as a decentralized multi-armed bandit (D-MAB) problem. In a D-MAB problem there are $M$ users and $N$ arms (channels) that each offer i.i.d. stochastic rewards with unknown means so long as they are accessed without collisi… ▽ More The fundamental problem of multiple secondary users contending for opportunistic spectrum access over multiple channels in cognitive radio networks has been formulated recently as a decentralized multi-armed bandit (D-MAB) problem. In a D-MAB problem there are $M$ users and $N$ arms (channels) that each offer i.i.d. stochastic rewards with unknown means so long as they are accessed without collision. The goal is to design a decentralized online learning policy that incurs minimal regret, defined as the difference between the total expected rewards accumulated by a model-aware genie, and that obtained by all users applying the policy. We make two contributions in this paper. First, we consider the setting where the users have a prioritized ranking, such that it is desired for the $K$-th-ranked user to learn to access the arm offering the $K$-th highest mean reward. For this problem, we present the first distributed policy that yields regret that is uniformly logarithmic over time without requiring any prior assumption about the mean rewards. Second, we consider the case when a fair access policy is required, i.e., it is desired for all users to experience the same mean reward. For this problem, we present a distributed policy that yields order-optimal regret scaling with respect to the number of users and arms, better than previously proposed policies in the literature. Both of our distributed policies make use of an innovative modification of the well known UCB1 policy for the classic multi-armed bandit problem that allows a single user to learn how to play the arm that yields the $K$-th largest mean reward. △ Less

Submitted 1 April, 2011; originally announced April 2011.

On the Combinatorial Multi-Armed Bandit Problem with Markovian Rewards

Authors: Yi Gai, Bhaskar Krishnamachari, Mingyan Liu

Abstract: We consider a combinatorial generalization of the classical multi-armed bandit problem that is defined as follows. There is a given bipartite graph of $M$ users and $N \geq M$ resources. For each user-resource pair $(i,j)$, there is an associated state that evolves as an aperiodic irreducible finite-state Markov chain with unknown parameters, with transitions occurring each time the particular use… ▽ More We consider a combinatorial generalization of the classical multi-armed bandit problem that is defined as follows. There is a given bipartite graph of $M$ users and $N \geq M$ resources. For each user-resource pair $(i,j)$, there is an associated state that evolves as an aperiodic irreducible finite-state Markov chain with unknown parameters, with transitions occurring each time the particular user $i$ is allocated resource $j$. The user $i$ receives a reward that depends on the corresponding state each time it is allocated the resource $j$. The system objective is to learn the best matching of users to resources so that the long-term sum of the rewards received by all users is maximized. This corresponds to minimizing regret, defined here as the gap between the expected total reward that can be obtained by the best-possible static matching and the expected total reward that can be achieved by a given algorithm. We present a polynomial-storage and polynomial-complexity-per-step matching-learning algorithm for this problem. We show that this algorithm can achieve a regret that is uniformly arbitrarily close to logarithmic in time and polynomial in the number of users and resources. This formulation is broadly applicable to scheduling and switching problems in networks and significantly extends prior results in the area. △ Less

Submitted 19 March, 2011; v1 submitted 14 December, 2010; originally announced December 2010.

The Non-Bayesian Restless Multi-Armed Bandit: a Case of Near-Logarithmic Regret

Authors: Wenhan Dai, Yi Gai, Bhaskar Krishnamachari, Qing Zhao

Abstract: In the classic Bayesian restless multi-armed bandit (RMAB) problem, there are $N$ arms, with rewards on all arms evolving at each time as Markov chains with known parameters. A player seeks to activate $K \geq 1$ arms at each time in order to maximize the expected total reward obtained over multiple plays. RMAB is a challenging problem that is known to be PSPACE-hard in general. We consider in thi… ▽ More In the classic Bayesian restless multi-armed bandit (RMAB) problem, there are $N$ arms, with rewards on all arms evolving at each time as Markov chains with known parameters. A player seeks to activate $K \geq 1$ arms at each time in order to maximize the expected total reward obtained over multiple plays. RMAB is a challenging problem that is known to be PSPACE-hard in general. We consider in this work the even harder non-Bayesian RMAB, in which the parameters of the Markov chain are assumed to be unknown \emph{a priori}. We develop an original approach to this problem that is applicable when the corresponding Bayesian problem has the structure that, depending on the known parameter values, the optimal solution is one of a prescribed finite set of policies. In such settings, we propose to learn the optimal policy for the non-Bayesian RMAB by employing a suitable meta-policy which treats each policy from this finite set as an arm in a different non-Bayesian multi-armed bandit problem for which a single-arm selection policy is optimal. We demonstrate this approach by developing a novel sensing policy for opportunistic spectrum access over unknown dynamic channels. We prove that our policy achieves near-logarithmic regret (the difference in expected reward compared to a model-aware genie), which leads to the same average reward that can be achieved by the optimal policy under a known model. This is the first such result in the literature for a non-Bayesian RMAB. △ Less

Submitted 22 November, 2010; originally announced November 2010.

Combinatorial Network Optimization with Unknown Variables: Multi-Armed Bandits with Linear Rewards

Authors: Yi Gai, Bhaskar Krishnamachari, Rahul Jain

Abstract: In the classic multi-armed bandits problem, the goal is to have a policy for dynamically operating arms that each yield stochastic rewards with unknown means. The key metric of interest is regret, defined as the gap between the expected total reward accumulated by an omniscient player that knows the reward means for each arm, and the expected total reward accumulated by the given policy. The polic… ▽ More In the classic multi-armed bandits problem, the goal is to have a policy for dynamically operating arms that each yield stochastic rewards with unknown means. The key metric of interest is regret, defined as the gap between the expected total reward accumulated by an omniscient player that knows the reward means for each arm, and the expected total reward accumulated by the given policy. The policies presented in prior work have storage, computation and regret all growing linearly with the number of arms, which is not scalable when the number of arms is large. We consider in this work a broad class of multi-armed bandits with dependent arms that yield rewards as a linear combination of a set of unknown parameters. For this general framework, we present efficient policies that are shown to achieve regret that grows logarithmically with time, and polynomially in the number of unknown parameters (even though the number of dependent arms may grow exponentially). Furthermore, these policies only require storage that grows linearly in the number of unknown parameters. We show that this generalization is broadly applicable and useful for many interesting tasks in networks that can be formulated as tractable combinatorial optimization problems with linear objective functions, such as maximum weight matching, shortest path, and minimum spanning tree computations. △ Less

Submitted 22 November, 2010; originally announced November 2010.

Adaptive post-Dantzig estimation and prediction for non-sparse "large $p$ and small $n$" models

Authors: Lu Lin, Lixing Zhu, Yujie Gai

Abstract: For consistency (even oracle properties) of estimation and model prediction, almost all existing methods of variable/feature selection critically depend on sparsity of models. However, for ``large $p$ and small $n$" models sparsity assumption is hard to check and particularly, when this assumption is violated, the consistency of all existing estimations is usually impossible because working models… ▽ More For consistency (even oracle properties) of estimation and model prediction, almost all existing methods of variable/feature selection critically depend on sparsity of models. However, for ``large $p$ and small $n$" models sparsity assumption is hard to check and particularly, when this assumption is violated, the consistency of all existing estimations is usually impossible because working models selected by existing methods such as the LASSO and the Dantzig selector are usually biased. To attack this problem, we in this paper propose adaptive post-Dantzig estimation and model prediction. Here the adaptability means that the consistency based on the newly proposed method is adaptive to non-sparsity of model, choice of shrinkage tuning parameter and dimension of predictor vector. The idea is that after a sub-model as a working model is determined by the Dantzig selector, we construct a globally unbiased sub-model by choosing suitable instrumental variables and nonparametric adjustment. The new estimation of the parameters in the sub-model can be of the asymptotic normality. The consistent estimator, together with the selected sub-model and adjusted model, improves model predictions. Simulation studies show that the new approach has the significant improvement of estimation and prediction accuracies over the Gaussian Dantzig selector and other classical methods have. △ Less

Submitted 7 August, 2010; originally announced August 2010.

Comments: 37

MSC Class: 62C05; 62F10; 62F12; 62G05