Showing 1–42 of 42 results for author: Lyu, B

Pessimism Meets Risk: Risk-Sensitive Offline Reinforcement Learning

Authors: Dake Zhang, Boxiang Lyu, Shuang Qiu, Mladen Kolar, Tong Zhang

Abstract: We study risk-sensitive reinforcement learning (RL), a crucial field due to its ability to enhance decision-making in scenarios where it is essential to manage uncertainty and minimize potential adverse outcomes. Particularly, our work focuses on applying the entropic risk measure to RL problems. While existing literature primarily investigates the online setting, there remains a large gap in unde… ▽ More We study risk-sensitive reinforcement learning (RL), a crucial field due to its ability to enhance decision-making in scenarios where it is essential to manage uncertainty and minimize potential adverse outcomes. Particularly, our work focuses on applying the entropic risk measure to RL problems. While existing literature primarily investigates the online setting, there remains a large gap in understanding how to efficiently derive a near-optimal policy based on this risk measure using only a pre-collected dataset. We center on the linear Markov Decision Process (MDP) setting, a well-regarded theoretical framework that has yet to be examined from a risk-sensitive standpoint. In response, we introduce two provably sample-efficient algorithms. We begin by presenting a risk-sensitive pessimistic value iteration algorithm, offering a tight analysis by leveraging the structure of the risk-sensitive performance measure. To further improve the obtained bounds, we propose another pessimistic algorithm that utilizes variance information and reference-advantage decomposition, effectively improving both the dependence on the space dimension $d$ and the risk-sensitivity factor. To the best of our knowledge, we obtain the first provably efficient risk-sensitive offline RL algorithms. △ Less

Submitted 10 July, 2024; originally announced July 2024.

Comments: ICML 2024

Deep Mamba Multi-modal Learning

Authors: Jian Zhu, Xin Zou, Yu Cui, Zhangmin Huang, Chenshu Hu, Bo Lyu

Abstract: Inspired by the excellent performance of Mamba networks, we propose a novel Deep Mamba Multi-modal Learning (DMML). It can be used to achieve the fusion of multi-modal features. We apply DMML to the field of multimedia retrieval and propose an innovative Deep Mamba Multi-modal Hashing (DMMH) method. It combines the advantages of algorithm accuracy and inference speed. We validated the effectivenes… ▽ More Inspired by the excellent performance of Mamba networks, we propose a novel Deep Mamba Multi-modal Learning (DMML). It can be used to achieve the fusion of multi-modal features. We apply DMML to the field of multimedia retrieval and propose an innovative Deep Mamba Multi-modal Hashing (DMMH) method. It combines the advantages of algorithm accuracy and inference speed. We validated the effectiveness of DMMH on three public datasets and achieved state-of-the-art results. △ Less

Submitted 9 April, 2024; originally announced June 2024.

Comments: Deep Mamba Multi-modal Learning; Deep Mamba Multi-modal Hashing

VideoScore: Building Automatic Metrics to Simulate Fine-grained Human Feedback for Video Generation

Authors: Xuan He, Dongfu Jiang, Ge Zhang, Max Ku, Achint Soni, Sherman Siu, Haonan Chen, Abhranil Chandra, Ziyan Jiang, Aaran Arulraj, Kai Wang, Quy Duc Do, Yuansheng Ni, Bohan Lyu, Yaswanth Narsupalli, Rongqi Fan, Zhiheng Lyu, Yuchen Lin, Wenhu Chen

Abstract: The recent years have witnessed great advances in video generation. However, the development of automatic video metrics is lagging significantly behind. None of the existing metric is able to provide reliable scores over generated videos. The main barrier is the lack of large-scale human-annotated dataset. In this paper, we release VideoFeedback, the first large-scale dataset containing human-prov… ▽ More The recent years have witnessed great advances in video generation. However, the development of automatic video metrics is lagging significantly behind. None of the existing metric is able to provide reliable scores over generated videos. The main barrier is the lack of large-scale human-annotated dataset. In this paper, we release VideoFeedback, the first large-scale dataset containing human-provided multi-aspect score over 37.6K synthesized videos from 11 existing video generative models. We train VideoScore (initialized from Mantis) based on VideoFeedback to enable automatic video quality assessment. Experiments show that the Spearman correlation between VideoScore and humans can reach 77.1 on VideoFeedback-test, beating the prior best metrics by about 50 points. Further result on other held-out EvalCrafter, GenAI-Bench, and VBench show that VideoScore has consistently much higher correlation with human judges than other metrics. Due to these results, we believe VideoScore can serve as a great proxy for human raters to (1) rate different video models to track progress (2) simulate fine-grained human feedback in Reinforcement Learning with Human Feedback (RLHF) to improve current video generation models. △ Less

Submitted 24 June, 2024; v1 submitted 21 June, 2024; originally announced June 2024.

Unveiling the Power of Source: Source-based Minimum Bayes Risk Decoding for Neural Machine Translation

Authors: Boxuan Lyu, Hidetaka Kamigaito, Kotaro Funakoshi, Manabu Okumura

Abstract: Maximum a posteriori decoding, a commonly used method for neural machine translation (NMT), aims to maximize the estimated posterior probability. However, high estimated probability does not always lead to high translation quality. Minimum Bayes Risk (MBR) decoding offers an alternative by seeking hypotheses with the highest expected utility. In this work, we show that Quality Estimation (QE) re… ▽ More Maximum a posteriori decoding, a commonly used method for neural machine translation (NMT), aims to maximize the estimated posterior probability. However, high estimated probability does not always lead to high translation quality. Minimum Bayes Risk (MBR) decoding offers an alternative by seeking hypotheses with the highest expected utility. In this work, we show that Quality Estimation (QE) reranking, which uses a QE model as a reranker, can be viewed as a variant of MBR. Inspired by this, we propose source-based MBR (sMBR) decoding, a novel approach that utilizes synthetic sources generated by backward translation as ``support hypotheses'' and a reference-free quality estimation metric as the utility function, marking the first work to solely use sources in MBR decoding. Experiments show that sMBR significantly outperforms QE reranking and is competitive with standard MBR decoding. Furthermore, sMBR calls the utility function fewer times compared to MBR. Our findings suggest that sMBR is a promising approach for high-quality NMT decoding. △ Less

Submitted 17 June, 2024; originally announced June 2024.

Convex-area-wise Linear Regression and Algorithms for Data Analysis

Authors: Bohan Lyu, Jianzhong Li

Abstract: This paper introduces a new type of regression methodology named as Convex-Area-Wise Linear Regression(CALR), which separates given datasets by disjoint convex areas and fits different linear regression models for different areas. This regression model is highly interpretable, and it is able to interpolate any given datasets, even when the underlying relationship between explanatory and response v… ▽ More This paper introduces a new type of regression methodology named as Convex-Area-Wise Linear Regression(CALR), which separates given datasets by disjoint convex areas and fits different linear regression models for different areas. This regression model is highly interpretable, and it is able to interpolate any given datasets, even when the underlying relationship between explanatory and response variables are non-linear and discontinuous. In order to solve CALR problem, 3 accurate algorithms are proposed under different assumptions. The analysis of correctness and time complexity of the algorithms are given, indicating that the problem can be solved in $o(n^2)$ time accurately when the input datasets have some special features. Besides, this paper introduces an equivalent mixed integer programming problem of CALR which can be approximately solved using existing optimization solvers. △ Less

Submitted 9 June, 2024; originally announced June 2024.

Exploring Diffusion Models' Corruption Stage in Few-Shot Fine-tuning and Mitigating with Bayesian Neural Networks

Authors: Xiaoyu Wu, Jiaru Zhang, Yang Hua, Bohan Lyu, Hao Wang, Tao Song, Haibing Guan

Abstract: Few-shot fine-tuning of Diffusion Models (DMs) is a key advancement, significantly reducing training costs and enabling personalized AI applications. However, we explore the training dynamics of DMs and observe an unanticipated phenomenon: during the training process, image fidelity initially improves, then unexpectedly deteriorates with the emergence of noisy patterns, only to recover later with… ▽ More Few-shot fine-tuning of Diffusion Models (DMs) is a key advancement, significantly reducing training costs and enabling personalized AI applications. However, we explore the training dynamics of DMs and observe an unanticipated phenomenon: during the training process, image fidelity initially improves, then unexpectedly deteriorates with the emergence of noisy patterns, only to recover later with severe overfitting. We term the stage with generated noisy patterns as corruption stage. To understand this corruption stage, we begin by theoretically modeling the one-shot fine-tuning scenario, and then extend this modeling to more general cases. Through this modeling, we identify the primary cause of this corruption stage: a narrowed learning distribution inherent in the nature of few-shot fine-tuning. To tackle this, we apply Bayesian Neural Networks (BNNs) on DMs with variational inference to implicitly broaden the learned distribution, and present that the learning target of the BNNs can be naturally regarded as an expectation of the diffusion loss and a further regularization with the pretrained DMs. This approach is highly compatible with current few-shot fine-tuning methods in DMs and does not introduce any extra inference costs. Experimental results demonstrate that our method significantly mitigates corruption, and improves the fidelity, quality and diversity of the generated images in both object-driven and subject-driven generation tasks. △ Less

Submitted 30 May, 2024; originally announced May 2024.

Comments: Preprint. Under review

Movable Antenna-Enhanced Wireless Powered Mobile Edge Computing Systems

Authors: Pengcheng Chen, Yuxuan Yang, Bin Lyu, Zhen Yang, Abbas Jamalipour

Abstract: In this paper, we propose a movable antenna (MA) enhanced scheme for wireless powered mobile edge computing (WP-MEC) system, where the hybrid access point (HAP) equipped with multiple MAs first emits wireless energy to charge wireless devices (WDs), and then receives the offloaded tasks from the WDs for edge computing. The MAs deployed at the HAP enhance the spatial degrees of freedom (DoFs) by fl… ▽ More In this paper, we propose a movable antenna (MA) enhanced scheme for wireless powered mobile edge computing (WP-MEC) system, where the hybrid access point (HAP) equipped with multiple MAs first emits wireless energy to charge wireless devices (WDs), and then receives the offloaded tasks from the WDs for edge computing. The MAs deployed at the HAP enhance the spatial degrees of freedom (DoFs) by flexibly adjusting the positions of MAs within an available region, thereby improving the efficiency of both downlink wireless energy transfer (WPT) and uplink task offloading. To balance the performance enhancement against the implementation intricacy, we further propose three types of MA positioning configurations, i.e., dynamic MA positioning, semi-dynamic MA positioning, and static MA positioning. In addition, the non-linear power conversion of energy harvesting (EH) circuits at the WDs and the finite computing capability at the edge server are taken into account. Our objective is to maximize the sum computational rate (SCR) by jointly optimizing the time allocation, positions of MAs, energy beamforming matrix, receive combing vectors, and offloading strategies of WDs. To solve the non-convex problems, efficient alternating optimization (AO) frameworks are proposed. Moreover, we propose a hybrid algorithm of particle swarm optimization with variable local search (PSO-VLS) to solve the sub-problem of MA positioning. Numerical results validate the superiority of exploiting MAs over the fixed-position antennas (FPAs) for enhancing the SCR performance of WP-MEC systems. △ Less

Submitted 28 April, 2024; originally announced April 2024.

Comments: 13 pages, 10 figures. Submitted for possible publication

Primary Rate Maximization in Movable Antennas Empowered Symbiotic Radio Communications

Authors: Bin Lyu, Hao Liu, Wenqing Hong, Shimin Gong, Feng Tian

Abstract: In this paper, we propose a movable antenna (MA) empowered scheme for symbiotic radio (SR) communication systems. Specifically, multiple antennas at the primary transmitter (PT) can be flexibly moved to favorable locations to boost the channel conditions of the primary and secondary transmissions. The primary transmission is achieved by the active transmission from the PT to the primary user (PU),… ▽ More In this paper, we propose a movable antenna (MA) empowered scheme for symbiotic radio (SR) communication systems. Specifically, multiple antennas at the primary transmitter (PT) can be flexibly moved to favorable locations to boost the channel conditions of the primary and secondary transmissions. The primary transmission is achieved by the active transmission from the PT to the primary user (PU), while the backscatter device (BD) takes a ride over the incident signal from the PT to passively send the secondary signal to the PU. Under this setup, we consider a primary rate maximization problem by jointly optimizing the transmit beamforming and the positions of MAs at the PT under a practical bit error rate constraint on the secondary transmission. Then, an alternating optimization framework with the utilization of the successive convex approximation, semi-definite processing and simulated annealing (SA) modified particle swarm optimization (SA-PSO) methods is proposed to find the solution of the transmit beamforming and MAs' positions. Finally, numerical results are provided to demonstrate the performance improvement provided by the proposed MA empowered scheme and the proposed algorithm. △ Less

Submitted 22 March, 2024; originally announced March 2024.

Comments: To appear in IEEE VTC-Spring 2024. 6 Pages,5 figures

3D Kinematics Estimation from Video with a Biomechanical Model and Synthetic Training Data

Authors: Zhi-Yi Lin, Bofan Lyu, Judith Cueto Fernandez, Eline van der Kruk, Ajay Seth, Xucong Zhang

Abstract: Accurate 3D kinematics estimation of human body is crucial in various applications for human health and mobility, such as rehabilitation, injury prevention, and diagnosis, as it helps to understand the biomechanical loading experienced during movement. Conventional marker-based motion capture is expensive in terms of financial investment, time, and the expertise required. Moreover, due to the scar… ▽ More Accurate 3D kinematics estimation of human body is crucial in various applications for human health and mobility, such as rehabilitation, injury prevention, and diagnosis, as it helps to understand the biomechanical loading experienced during movement. Conventional marker-based motion capture is expensive in terms of financial investment, time, and the expertise required. Moreover, due to the scarcity of datasets with accurate annotations, existing markerless motion capture methods suffer from challenges including unreliable 2D keypoint detection, limited anatomic accuracy, and low generalization capability. In this work, we propose a novel biomechanics-aware network that directly outputs 3D kinematics from two input views with consideration of biomechanical prior and spatio-temporal information. To train the model, we create synthetic dataset ODAH with accurate kinematics annotations generated by aligning the body mesh from the SMPL-X model and a full-body OpenSim skeletal model. Our extensive experiments demonstrate that the proposed approach, only trained on synthetic data, outperforms previous state-of-the-art methods when evaluated across multiple datasets, revealing a promising direction for enhancing video-based human motion capture △ Less

Submitted 5 March, 2024; v1 submitted 20 February, 2024; originally announced February 2024.

A Graph-Native Query Optimization Framework

Authors: Bingqing Lyu, Xiaoli Zhou, Longbin Lai, Yufan Yang, Yunkai Lou, Wenyuan Yu, Jingren Zhou

Abstract: Graph queries that combine pattern matching with relational operations, referred as PatRelQuery, are widely used in many real-world applications. It allows users to identify arbitrary patterns in a graph and further perform in-depth relational analysis on the results. To effectively support PatRelQuery, two key challenges need to be addressed: (1) how to optimize PatRelQuery in a unified framework… ▽ More Graph queries that combine pattern matching with relational operations, referred as PatRelQuery, are widely used in many real-world applications. It allows users to identify arbitrary patterns in a graph and further perform in-depth relational analysis on the results. To effectively support PatRelQuery, two key challenges need to be addressed: (1) how to optimize PatRelQuery in a unified framework, and (2) how to handle the arbitrary type constraints in patterns in PatRelQuery. In this paper, we present a graph-native query optimization framework named GOpt, to tackle these issues. GOpt is built on top of a unified intermediate representation (IR) that is capable of capturing both graph and relational operations, thereby streamlining the optimization of PatRelQuery. To handle the arbitrary type constraints, GOpt employs an automatic type inference approach to identify implicit type constraints. Additionally, GOpt introduces a graph-native optimizer, which encompasses an extensive collection of optimization rules along with cost-based techniques tailored for arbitrary patterns, to optimize PatRelQuery. Through comprehensive experiments, we demonstrate that GOpt can achieve significant query performance improvements, in both crafted benchmarks and real-world applications. △ Less

Submitted 5 February, 2024; v1 submitted 31 January, 2024; originally announced January 2024.

GitAgent: Facilitating Autonomous Agent with GitHub by Tool Extension

Authors: Bohan Lyu, Xin Cong, Heyang Yu, Pan Yang, Yujia Qin, Yining Ye, Yaxi Lu, Zhong Zhang, Yukun Yan, Yankai Lin, Zhiyuan Liu, Maosong Sun

Abstract: While Large Language Models (LLMs) like ChatGPT and GPT-4 have demonstrated exceptional proficiency in natural language processing, their efficacy in addressing complex, multifaceted tasks remains limited. A growing area of research focuses on LLM-based agents equipped with external tools capable of performing diverse tasks. However, existing LLM-based agents only support a limited set of tools wh… ▽ More While Large Language Models (LLMs) like ChatGPT and GPT-4 have demonstrated exceptional proficiency in natural language processing, their efficacy in addressing complex, multifaceted tasks remains limited. A growing area of research focuses on LLM-based agents equipped with external tools capable of performing diverse tasks. However, existing LLM-based agents only support a limited set of tools which is unable to cover a diverse range of user queries, especially for those involving expertise domains. It remains a challenge for LLM-based agents to extend their tools autonomously when confronted with various user queries. As GitHub has hosted a multitude of repositories which can be seen as a good resource for tools, a promising solution is that LLM-based agents can autonomously integrate the repositories in GitHub according to the user queries to extend their tool set. In this paper, we introduce GitAgent, an agent capable of achieving the autonomous tool extension from GitHub. GitAgent follows a four-phase procedure to incorporate repositories and it can learn human experience by resorting to GitHub Issues/PRs to solve problems encountered during the procedure. Experimental evaluation involving 30 user queries demonstrates GitAgent's effectiveness, achieving a 69.4% success rate on average. △ Less

Submitted 28 December, 2023; originally announced December 2023.

GraphScope Flex: LEGO-like Graph Computing Stack

Authors: Tao He, Shuxian Hu, Longbin Lai, Dongze Li, Neng Li, Xue Li, Lexiao Liu, Xiaojian Luo, Binqing Lyu, Ke Meng, Sijie Shen, Li Su, Lei Wang, Jingbo Xu, Wenyuan Yu, Weibin Zeng, Lei Zhang, Siyuan Zhang, Jingren Zhou, Xiaoli Zhou, Diwen Zhu

Abstract: Graph computing has become increasingly crucial in processing large-scale graph data, with numerous systems developed for this purpose. Two years ago, we introduced GraphScope as a system addressing a wide array of graph computing needs, including graph traversal, analytics, and learning in one system. Since its inception, GraphScope has achieved significant technological advancements and gained w… ▽ More Graph computing has become increasingly crucial in processing large-scale graph data, with numerous systems developed for this purpose. Two years ago, we introduced GraphScope as a system addressing a wide array of graph computing needs, including graph traversal, analytics, and learning in one system. Since its inception, GraphScope has achieved significant technological advancements and gained widespread adoption across various industries. However, one key lesson from this journey has been understanding the limitations of a "one-size-fits-all" approach, especially when dealing with the diversity of programming interfaces, applications, and data storage formats in graph computing. In response to these challenges, we present GraphScope Flex, the next iteration of GraphScope. GraphScope Flex is designed to be both resource-efficient and cost-effective, while also providing flexibility and user-friendliness through its LEGO-like modularity. This paper explores the architectural innovations and fundamental design principles of GraphScope Flex, all of which are direct outcomes of the lessons learned during our ongoing development process. We validate the adaptability and efficiency of GraphScope Flex with extensive evaluations on synthetic and real-world datasets. The results show that GraphScope Flex achieves 2.4X throughput and up to 55.7X speedup over other systems on the LDBC Social Network and Graphalytics benchmarks, respectively. Furthermore, GraphScope Flex accomplishes up to a 2,400X performance gain in real-world applications, demonstrating its proficiency across a wide range of graph computing scenarios with increased effectiveness. △ Less

Submitted 19 December, 2023; originally announced December 2023.

Keyword spotting -- Detecting commands in speech using deep learning

Authors: Sumedha Rai, Tong Li, Bella Lyu

Abstract: Speech recognition has become an important task in the development of machine learning and artificial intelligence. In this study, we explore the important task of keyword spotting using speech recognition machine learning and deep learning techniques. We implement feature engineering by converting raw waveforms to Mel Frequency Cepstral Coefficients (MFCCs), which we use as inputs to our models.… ▽ More Speech recognition has become an important task in the development of machine learning and artificial intelligence. In this study, we explore the important task of keyword spotting using speech recognition machine learning and deep learning techniques. We implement feature engineering by converting raw waveforms to Mel Frequency Cepstral Coefficients (MFCCs), which we use as inputs to our models. We experiment with several different algorithms such as Hidden Markov Model with Gaussian Mixture, Convolutional Neural Networks and variants of Recurrent Neural Networks including Long Short-Term Memory and the Attention mechanism. In our experiments, RNN with BiLSTM and Attention achieves the best performance with an accuracy of 93.9 % △ Less

Submitted 9 December, 2023; originally announced December 2023.

An Efficient Data Analysis Method for Big Data using Multiple-Model Linear Regression

Authors: Bohan Lyu, Jianzhong Li

Abstract: This paper introduces a new data analysis method for big data using a newly defined regression model named multiple model linear regression(MMLR), which separates input datasets into subsets and construct local linear regression models of them. The proposed data analysis method is shown to be more efficient and flexible than other regression based methods. This paper also proposes an approximate a… ▽ More This paper introduces a new data analysis method for big data using a newly defined regression model named multiple model linear regression(MMLR), which separates input datasets into subsets and construct local linear regression models of them. The proposed data analysis method is shown to be more efficient and flexible than other regression based methods. This paper also proposes an approximate algorithm to construct MMLR models based on $(ε,δ)$-estimator, and gives mathematical proofs of the correctness and efficiency of MMLR algorithm, of which the time complexity is linear with respect to the size of input datasets. This paper also empirically implements the method on both synthetic and real-world datasets, the algorithm shows to have comparable performance to existing regression methods in many cases, while it takes almost the shortest time to provide a high prediction accuracy. △ Less

Submitted 24 August, 2023; originally announced August 2023.

Addressing Budget Allocation and Revenue Allocation in Data Market Environments Using an Adaptive Sampling Algorithm

Authors: Boxin Zhao, Boxiang Lyu, Raul Castro Fernandez, Mladen Kolar

Abstract: High-quality machine learning models are dependent on access to high-quality training data. When the data are not already available, it is tedious and costly to obtain them. Data markets help with identifying valuable training data: model consumers pay to train a model, the market uses that budget to identify data and train the model (the budget allocation problem), and finally the market compensa… ▽ More High-quality machine learning models are dependent on access to high-quality training data. When the data are not already available, it is tedious and costly to obtain them. Data markets help with identifying valuable training data: model consumers pay to train a model, the market uses that budget to identify data and train the model (the budget allocation problem), and finally the market compensates data providers according to their data contribution (revenue allocation problem). For example, a bank could pay the data market to access data from other financial institutions to train a fraud detection model. Compensating data contributors requires understanding data's contribution to the model; recent efforts to solve this revenue allocation problem based on the Shapley value are inefficient to lead to practical data markets. In this paper, we introduce a new algorithm to solve budget allocation and revenue allocation problems simultaneously in linear time. The new algorithm employs an adaptive sampling process that selects data from those providers who are contributing the most to the model. Better data means that the algorithm accesses those providers more often, and more frequent accesses corresponds to higher compensation. Furthermore, the algorithm can be deployed in both centralized and federated scenarios, boosting its applicability. We provide theoretical guarantees for the algorithm that show the budget is used efficiently and the properties of revenue allocation are similar to Shapley's. Finally, we conduct an empirical evaluation to show the performance of the algorithm in practical scenarios and when compared to other baselines. Overall, we believe that the new algorithm paves the way for the implementation of practical data markets. △ Less

Submitted 4 June, 2023; originally announced June 2023.

Comments: Published on International Conference on Machine Learning (ICML) 2023

Pairwise Ranking Losses of Click-Through Rates Prediction for Welfare Maximization in Ad Auctions

Authors: Boxiang Lyu, Zhe Feng, Zachary Robertson, Sanmi Koyejo

Abstract: We study the design of loss functions for click-through rates (CTR) to optimize (social) welfare in advertising auctions. Existing works either only focus on CTR predictions without consideration of business objectives (e.g., welfare) in auctions or assume that the distribution over the participants' expected cost-per-impression (eCPM) is known a priori, then use various additional assumptions on… ▽ More We study the design of loss functions for click-through rates (CTR) to optimize (social) welfare in advertising auctions. Existing works either only focus on CTR predictions without consideration of business objectives (e.g., welfare) in auctions or assume that the distribution over the participants' expected cost-per-impression (eCPM) is known a priori, then use various additional assumptions on the parametric form of the distribution to derive loss functions for predicting CTRs. In this work, we bring back the welfare objectives of ad auctions into CTR predictions and propose a novel weighted rankloss to train the CTR model. Compared to existing literature, our approach provides a provable guarantee on welfare but without assumptions on the eCPMs' distribution while also avoiding the intractability of naively applying existing learning-to-rank methods. Further, we propose a theoretically justifiable technique for calibrating the losses using labels generated from a teacher network, only assuming that the teacher network has bounded $\ell_2$ generalization error. Finally, we demonstrate the advantages of the proposed loss on synthetic and real-world data. △ Less

Submitted 1 June, 2023; originally announced June 2023.

Comments: 25 pages, 6 figures

Transmit Power Minimization for STAR-RIS Empowered Symbiotic Radio Communications

Authors: Chao Zhou, Bin Lyu, Youhong Feng, Dinh Thai Hoang

Abstract: In this paper, we propose a simultaneously transmitting and reflecting reconfigurable intelligent surface (STAR-RIS) empowered transmission scheme for symbiotic radio (SR) systems to make more flexibility for network deployment and enhance system performance. The STAR-RIS is utilized to not only beam the primary signals from the base station (BS) towards multiple primary users on the same side of… ▽ More In this paper, we propose a simultaneously transmitting and reflecting reconfigurable intelligent surface (STAR-RIS) empowered transmission scheme for symbiotic radio (SR) systems to make more flexibility for network deployment and enhance system performance. The STAR-RIS is utilized to not only beam the primary signals from the base station (BS) towards multiple primary users on the same side of the STAR-RIS, but also achieve the secondary transmission to the secondary users on another side. We consider both the broadcasting signal model and unicasting signal model at the BS. For each model, we aim for minimizing the transmit power of the BS by designing the active beamforming and simultaneous reflection and transmission coefficients under the practical phase correlation constraint. To address the challenge of solving the formulated problem, we propose a block coordinate descent based algorithm with the semidefinite relaxation, penalty dual decomposition and successive convex approximation methods, which decomposes the original problem into one sub-problem about active beamforming and the other sub-problem about simultaneous reflection and transmission coefficients, and iteratively solve them until the convergence is achieved. Numerical results indicate that the proposed scheme can reduce up to 150.6% transmit power compared to the backscattering device enabled scheme. △ Less

Submitted 20 April, 2023; originally announced April 2023.

Comments: 32 pages, 12 figures

Robust Secure Transmission for Active RIS Enabled Symbiotic Radio Multicast Communications

Authors: Bin Lyu, Chao Zhou, Shimin Gong, Dinh Thai Hoang, Ying-chang Liang

Abstract: In this paper, we propose a robust secure transmission scheme for an active reconfigurable intelligent surface (RIS) enabled symbiotic radio (SR) system in the presence of multiple eavesdroppers (Eves). In the considered system, the active RIS is adopted to enable the secure transmission of primary signals from the primary transmitter to multiple primary users in a multicasting manner, and simulta… ▽ More In this paper, we propose a robust secure transmission scheme for an active reconfigurable intelligent surface (RIS) enabled symbiotic radio (SR) system in the presence of multiple eavesdroppers (Eves). In the considered system, the active RIS is adopted to enable the secure transmission of primary signals from the primary transmitter to multiple primary users in a multicasting manner, and simultaneously achieve its own information delivery to the secondary user by riding over the primary signals. Taking into account the imperfect channel state information (CSI) related with Eves, we formulate the system power consumption minimization problem by optimizing the transmit beamforming and reflection beamforming for the bounded and statistical CSI error models, taking the worst-case SNR constraints and the SNR outage probability constraints at the Eves into considerations, respectively. Specifically, the S-Procedure and the Bernstein-Type Inequality are implemented to approximately transform the worst-case SNR and the SNR outage probability constraints into tractable forms, respectively. After that, the formulated problems can be solved by the proposed alternating optimization (AO) algorithm with the semi-definite relaxation and sequential rank-one constraint relaxation techniques. Numerical results show that the proposed active RIS scheme can reduce up to 27.0% system power consumption compared to the passive RIS. △ Less

Submitted 13 April, 2023; v1 submitted 5 April, 2023; originally announced April 2023.

Comments: 32 Pages, 12 figures, accepted to IEEE Transactions on Wireless Communications

A principled approach to model validation in domain generalization

Authors: Boyang Lyu, Thuan Nguyen, Matthias Scheutz, Prakash Ishwar, Shuchin Aeron

Abstract: Domain generalization aims to learn a model with good generalization ability, that is, the learned model should not only perform well on several seen domains but also on unseen domains with different data distributions. State-of-the-art domain generalization methods typically train a representation function followed by a classifier jointly to minimize both the classification risk and the domain di… ▽ More Domain generalization aims to learn a model with good generalization ability, that is, the learned model should not only perform well on several seen domains but also on unseen domains with different data distributions. State-of-the-art domain generalization methods typically train a representation function followed by a classifier jointly to minimize both the classification risk and the domain discrepancy. However, when it comes to model selection, most of these methods rely on traditional validation routines that select models solely based on the lowest classification risk on the validation set. In this paper, we theoretically demonstrate a trade-off between minimizing classification risk and mitigating domain discrepancy, i.e., it is impossible to achieve the minimum of these two objectives simultaneously. Motivated by this theoretical result, we propose a novel model selection method suggesting that the validation process should account for both the classification risk and the domain discrepancy. We validate the effectiveness of the proposed method by numerical results on several domain generalization datasets. △ Less

Submitted 2 April, 2023; originally announced April 2023.

Comments: Accepted to ICASSP 2023

Maximal Clique and Edge-Ranking Bounds of Biclique Cover Number

Authors: Bochuan Lyu, Illya V. Hicks

Abstract: The biclique cover number $(\text{bc})$ of a graph $G$ denotes the minimum number of complete bipartite (biclique) subgraphs to cover all the edges of the graph. In this paper, we show that $\text{bc}(G) \geq \lceil \log_2(\text{mc}(G^c)) \rceil \geq \lceil \log_2(χ(G)) \rceil$ for an arbitrary graph $G$, where $χ(G)$ is the chromatic number of $G$ and $\text{mc}(G^c)$ is the number of maximal cli… ▽ More The biclique cover number $(\text{bc})$ of a graph $G$ denotes the minimum number of complete bipartite (biclique) subgraphs to cover all the edges of the graph. In this paper, we show that $\text{bc}(G) \geq \lceil \log_2(\text{mc}(G^c)) \rceil \geq \lceil \log_2(χ(G)) \rceil$ for an arbitrary graph $G$, where $χ(G)$ is the chromatic number of $G$ and $\text{mc}(G^c)$ is the number of maximal cliques of the complementary graph $G^c$, i.e., the number of maximal independent sets of $G$. We also show that $\lceil \log_2(\text{mc}(G^c)) \rceil$ could be a strictly tighter lower bound of the biclique cover number than other existing lower bounds. We can also provide a bound of $\text{bc}(G)$ with respect to the biclique partition number ($\text{bp}$) of $G$: $\text{bc}(G) \geq \lceil \log_2(\text{bp}(G) + 1) \rceil$ or $\text{bp}(G) \leq 2^{\text{bc}(G)} - 1$ if $G$ is co-chordal. Furthermore, we show that $\text{bc}(G) \leq χ_r'(T_{{K}^c})$, where $G$ is a co-chordal graph such that each vertex is in at most two maximal independent sets and $χ_r'({T}_{{K}^c})$ is the optimal edge-ranking number of a clique tree of $G^c$. △ Less

Submitted 9 March, 2023; v1 submitted 24 February, 2023; originally announced February 2023.

MSC Class: 05C70

Sum-Rate Maximization in Active RIS-Assisted Multi-Antenna WPCN

Authors: Jie Jiang, Bin Lyu, Pengcheng Chen, Zhen Yang

Abstract: In this paper, we propose an active reconfigurable intelligent surface (RIS) enabled hybrid relaying scheme for a multi-antenna wireless powered communication network (WPCN), where the active RIS is employed to assist both wireless energy transfer (WET) from the power station (PS) to energy-constrained users and wireless information transmission (WIT) from users to the receiving station (RS). For… ▽ More In this paper, we propose an active reconfigurable intelligent surface (RIS) enabled hybrid relaying scheme for a multi-antenna wireless powered communication network (WPCN), where the active RIS is employed to assist both wireless energy transfer (WET) from the power station (PS) to energy-constrained users and wireless information transmission (WIT) from users to the receiving station (RS). For further performance enhancement, we propose to employ both transmit beamforming at the PS and receive beamforming at the RS. We formulate a sum-rate maximization problem by jointly optimizing the RIS phase shifts and amplitude reflection coefficients for both the WET and the WIT, transmit and receive beamforming vectors, and network resource allocation. To solve this non-convex problem, we propose an efficient alternating optimization algorithm with linear minimum mean squared error criterion, semi-definite relaxation (SDR) and successive convex approximation techniques. Specifically, the tightness of applying the SDR is proved. Simulation results demonstrate that our proposed scheme with 10 reflecting elements (REs) and 4 antennas can achieve 17.78% and 415.48% performance gains compared to the single-antenna scheme with 10 REs and passive RIS scheme with 100 REs, respectively. △ Less

Submitted 5 January, 2023; originally announced January 2023.

Comments: Accepted by China Communications

Hierarchical Deep Reinforcement Learning for Age-of-Information Minimization in IRS-aided and Wireless-powered Wireless Networks

Authors: Shimin Gong, Leiyang Cui, Bo Gu, Bin Lyu, Dinh Thai Hoang, Dusit Niyato

Abstract: In this paper, we focus on a wireless-powered sensor network coordinated by a multi-antenna access point (AP). Each node can generate sensing information and report the latest information to the AP using the energy harvested from the AP's signal beamforming. We aim to minimize the average age-of-information (AoI) by adapting the nodes' transmission scheduling and the transmission control strategie… ▽ More In this paper, we focus on a wireless-powered sensor network coordinated by a multi-antenna access point (AP). Each node can generate sensing information and report the latest information to the AP using the energy harvested from the AP's signal beamforming. We aim to minimize the average age-of-information (AoI) by adapting the nodes' transmission scheduling and the transmission control strategies jointly. To reduce the transmission delay, an intelligent reflecting surface (IRS) is used to enhance the channel conditions by controlling the AP's beamforming vector and the IRS's phase shifting matrix. Considering dynamic data arrivals at different sensing nodes, we propose a hierarchical deep reinforcement learning (DRL) framework to for AoI minimization in two steps. The users' transmission scheduling is firstly determined by the outer-loop DRL approach, e.g. the DQN or PPO algorithm, and then the inner-loop optimization is used to adapt either the uplink information transmission or downlink energy transfer to all nodes. A simple and efficient approximation is also proposed to reduce the inner-loop rum time overhead. Numerical results verify that the hierarchical learning framework outperforms typical baselines in terms of the average AoI and proportional fairness among different nodes. △ Less

Submitted 27 December, 2022; originally announced December 2022.

Comments: 31 pages, 6 figures, 2 tables, 3 algorithms

Trade-off between reconstruction loss and feature alignment for domain generalization

Authors: Thuan Nguyen, Boyang Lyu, Prakash Ishwar, Matthias Scheutz, Shuchin Aeron

Abstract: Domain generalization (DG) is a branch of transfer learning that aims to train the learning models on several seen domains and subsequently apply these pre-trained models to other unseen (unknown but related) domains. To deal with challenging settings in DG where both data and label of the unseen domain are not available at training time, the most common approach is to design the classifiers based… ▽ More Domain generalization (DG) is a branch of transfer learning that aims to train the learning models on several seen domains and subsequently apply these pre-trained models to other unseen (unknown but related) domains. To deal with challenging settings in DG where both data and label of the unseen domain are not available at training time, the most common approach is to design the classifiers based on the domain-invariant representation features, i.e., the latent representations that are unchanged and transferable between domains. Contrary to popular belief, we show that designing classifiers based on invariant representation features alone is necessary but insufficient in DG. Our analysis indicates the necessity of imposing a constraint on the reconstruction loss induced by representation functions to preserve most of the relevant information about the label in the latent space. More importantly, we point out the trade-off between minimizing the reconstruction loss and achieving domain alignment in DG. Our theoretical results motivate a new DG framework that jointly optimizes the reconstruction loss and the domain discrepancy. Both theoretical and numerical results are provided to justify our approach. △ Less

Submitted 26 October, 2022; originally announced October 2022.

Comments: 13 pages, 2 tables

Journal ref: International Conference on Machine Learning and Applications (ICMLA-2022)

A Reinforcement Learning Approach in Multi-Phase Second-Price Auction Design

Authors: Rui Ai, Boxiang Lyu, Zhaoran Wang, Zhuoran Yang, Michael I. Jordan

Abstract: We study reserve price optimization in multi-phase second price auctions, where seller's prior actions affect the bidders' later valuations through a Markov Decision Process (MDP). Compared to the bandit setting in existing works, the setting in ours involves three challenges. First, from the seller's perspective, we need to efficiently explore the environment in the presence of potentially nontru… ▽ More We study reserve price optimization in multi-phase second price auctions, where seller's prior actions affect the bidders' later valuations through a Markov Decision Process (MDP). Compared to the bandit setting in existing works, the setting in ours involves three challenges. First, from the seller's perspective, we need to efficiently explore the environment in the presence of potentially nontruthful bidders who aim to manipulates seller's policy. Second, we want to minimize the seller's revenue regret when the market noise distribution is unknown. Third, the seller's per-step revenue is unknown, nonlinear, and cannot even be directly observed from the environment. We propose a mechanism addressing all three challenges. To address the first challenge, we use a combination of a new technique named "buffer periods" and inspirations from Reinforcement Learning (RL) with low switching cost to limit bidders' surplus from untruthful bidding, thereby incentivizing approximately truthful bidding. The second one is tackled by a novel algorithm that removes the need for pure exploration when the market noise distribution is unknown. The third challenge is resolved by an extension of LSVI-UCB, where we use the auction's underlying structure to control the uncertainty of the revenue function. The three techniques culminate in the $\underline{\rm C}$ontextual-$\underline{\rm L}$SVI-$\underline{\rm U}$CB-$\underline{\rm B}$uffer (CLUB) algorithm which achieves $\tilde{ \mathcal{O}}(H^{5/2}\sqrt{K})$ revenue regret when the market noise is known and $\tilde{ \mathcal{O}}(H^{3}\sqrt{K})$ revenue regret when the noise is unknown with no assumptions on bidders' truthfulness. △ Less

Submitted 18 October, 2022; originally announced October 2022.

Joint Reconfigurable Intelligent Surface Location and Passive Beamforming Optimization for Maximizing the Secrecy-Rate

Authors: Haiyan Guo, Zhen Yang, Yulong Zou, Bin Lyu, Yuhan Jiang, Lajos Hanzo

Abstract: The physical layer security (PLS) is investigated for reconfigurable intelligent surface (RIS) assisted wireless networks, where a source transmits its confidential information to a legitimate destination with the aid of a single small RIS in the presence of a malicious eavesdropper. A new joint RIS location and passive beamforming (J-LPB) optimization scheme is proposed for the sake of maximizing… ▽ More The physical layer security (PLS) is investigated for reconfigurable intelligent surface (RIS) assisted wireless networks, where a source transmits its confidential information to a legitimate destination with the aid of a single small RIS in the presence of a malicious eavesdropper. A new joint RIS location and passive beamforming (J-LPB) optimization scheme is proposed for the sake of maximizing the secrecy rate under the RIS location constraint and the constraint that the modulus of the reflecting coefficient at each RIS's unit is not larger than 1. Specifically, we analyze the optimal location of the RIS, and conclude that the product involving the source-RIS distance and the RIS-destination distance should be minimized. Since the product minimization problem is nonconvex, we then propose a two-tier optimization algorithm for solving it. Based on the near-optimal RIS 3D location obtained, we further formulate the passive beamforming optimization problem, and then propose to apply the Charnes-Cooper transformation along with the sequential rank-one constraint relaxation (SROCR) algorithm to solve it. Our numerical results show that the secrecy rate of the proposed J-LPB optimization scheme is higher than that of the benchmarks. Explicitly, we use the following benchmarks: the near-source-based RIS location and passive beamforming (NSB-LPB) optimization scheme, the near-destination-based RIS location and passive beamforming (NDB-LPB) optimization scheme, and the random RIS location and passive beamforming (R-LPB) optimization scheme. Finally, the benefits of our J-LPB scheme are further increased with the number of RIS units. △ Less

Submitted 4 October, 2022; originally announced October 2022.

Joint covariate-alignment and concept-alignment: a framework for domain generalization

Authors: Thuan Nguyen, Boyang Lyu, Prakash Ishwar, Matthias Scheutz, Shuchin Aeron

Abstract: In this paper, we propose a novel domain generalization (DG) framework based on a new upper bound to the risk on the unseen domain. Particularly, our framework proposes to jointly minimize both the covariate-shift as well as the concept-shift between the seen domains for a better performance on the unseen domain. While the proposed approach can be implemented via an arbitrary combination of covari… ▽ More In this paper, we propose a novel domain generalization (DG) framework based on a new upper bound to the risk on the unseen domain. Particularly, our framework proposes to jointly minimize both the covariate-shift as well as the concept-shift between the seen domains for a better performance on the unseen domain. While the proposed approach can be implemented via an arbitrary combination of covariate-alignment and concept-alignment modules, in this work we use well-established approaches for distributional alignment namely, Maximum Mean Discrepancy (MMD) and covariance Alignment (CORAL), and use an Invariant Risk Minimization (IRM)-based approach for concept alignment. Our numerical results show that the proposed methods perform as well as or better than the state-of-the-art for domain generalization on several data sets. △ Less

Submitted 1 August, 2022; originally announced August 2022.

Comments: 8 pages, 2 figures, and 1 table. This paper is accepted at 32nd IEEE International Workshop on Machine Learning for Signal Processing (MLSP 2022)

One Policy is Enough: Parallel Exploration with a Single Policy is Near-Optimal for Reward-Free Reinforcement Learning

Authors: Pedro Cisneros-Velarde, Boxiang Lyu, Sanmi Koyejo, Mladen Kolar

Abstract: Although parallelism has been extensively used in reinforcement learning (RL), the quantitative effects of parallel exploration are not well understood theoretically. We study the benefits of simple parallel exploration for reward-free RL in linear Markov decision processes (MDPs) and two-player zero-sum Markov games (MGs). In contrast to the existing literature, which focuses on approaches that e… ▽ More Although parallelism has been extensively used in reinforcement learning (RL), the quantitative effects of parallel exploration are not well understood theoretically. We study the benefits of simple parallel exploration for reward-free RL in linear Markov decision processes (MDPs) and two-player zero-sum Markov games (MGs). In contrast to the existing literature, which focuses on approaches that encourage agents to explore a diverse set of policies, we show that using a single policy to guide exploration across all agents is sufficient to obtain an almost-linear speedup in all cases compared to their fully sequential counterpart. Furthermore, we demonstrate that this simple procedure is near-minimax optimal in the reward-free setting for linear MDPs. From a practical perspective, our paper shows that a single policy is sufficient and provably near-optimal for incorporating parallelism during the exploration phase. △ Less

Submitted 1 March, 2023; v1 submitted 31 May, 2022; originally announced May 2022.

Comments: 50 pages

Pessimism meets VCG: Learning Dynamic Mechanism Design via Offline Reinforcement Learning

Authors: Boxiang Lyu, Zhaoran Wang, Mladen Kolar, Zhuoran Yang

Abstract: Dynamic mechanism design has garnered significant attention from both computer scientists and economists in recent years. By allowing agents to interact with the seller over multiple rounds, where agents' reward functions may change with time and are state-dependent, the framework is able to model a rich class of real-world problems. In these works, the interaction between agents and sellers is of… ▽ More Dynamic mechanism design has garnered significant attention from both computer scientists and economists in recent years. By allowing agents to interact with the seller over multiple rounds, where agents' reward functions may change with time and are state-dependent, the framework is able to model a rich class of real-world problems. In these works, the interaction between agents and sellers is often assumed to follow a Markov Decision Process (MDP). We focus on the setting where the reward and transition functions of such an MDP are not known a priori, and we are attempting to recover the optimal mechanism using an a priori collected data set. In the setting where the function approximation is employed to handle large state spaces, with only mild assumptions on the expressiveness of the function class, we are able to design a dynamic mechanism using offline reinforcement learning algorithms. Moreover, learned mechanisms approximately have three key desiderata: efficiency, individual rationality, and truthfulness. Our algorithm is based on the pessimism principle and only requires a mild assumption on the coverage of the offline data set. To the best of our knowledge, our work provides the first offline RL algorithm for dynamic mechanism design without assuming uniform coverage. △ Less

Submitted 21 June, 2022; v1 submitted 5 May, 2022; originally announced May 2022.

Comments: 52 pages

Personalized Federated Learning with Multiple Known Clusters

Authors: Boxiang Lyu, Filip Hanzely, Mladen Kolar

Abstract: We consider the problem of personalized federated learning when there are known cluster structures within users. An intuitive approach would be to regularize the parameters so that users in the same cluster share similar model weights. The distances between the clusters can then be regularized to reflect the similarity between different clusters of users. We develop an algorithm that allows each c… ▽ More We consider the problem of personalized federated learning when there are known cluster structures within users. An intuitive approach would be to regularize the parameters so that users in the same cluster share similar model weights. The distances between the clusters can then be regularized to reflect the similarity between different clusters of users. We develop an algorithm that allows each cluster to communicate independently and derive the convergence results. We study a hierarchical linear model to theoretically demonstrate that our approach outperforms agents learning independently and agents learning a single shared weight. Finally, we demonstrate the advantages of our approach using both simulated and real-world data. △ Less

Submitted 28 April, 2022; originally announced April 2022.

Toward RIS-Enhanced Integrated Terrestrial/Non-Terrestrial Connectivity in 6G

Authors: Parisa Ramezani, Bin Lyu, Abbas Jamalipour

Abstract: The next generation of wireless systems will take the concept of communications and networking to another level through the seamless integration of terrestrial, aerial, satellite, maritime and underwater communication systems. Reconfigurable intelligent surface (RIS) is an innovative technology which, with its singular features and functionalities, can expedite the realization of this everywhere c… ▽ More The next generation of wireless systems will take the concept of communications and networking to another level through the seamless integration of terrestrial, aerial, satellite, maritime and underwater communication systems. Reconfigurable intelligent surface (RIS) is an innovative technology which, with its singular features and functionalities, can expedite the realization of this everywhere connectivity. Motivated by the unparalleled properties of this innovatory technology, this article provides a comprehensive discussion on how RIS can contribute to the actualization and proper functioning of future integrated terrestrial/non-terrestrial (INTENT) networks. As a case study, we explore the integration of RIS into non-orthogonal multiple access (NOMA)-based satellite communication networks and demonstrate the performance enhancement achieved by the inclusion of RIS via numerical simulations. Promising directions for future research in this area are set forth at the end of this article. △ Less

Submitted 29 July, 2022; v1 submitted 7 February, 2022; originally announced March 2022.

Comments: This work has been accepted for publication in IEEE Network

Finding Biclique Partitions of Co-Chordal Graphs

Authors: Bochuan Lyu, Illya V. Hicks

Abstract: The biclique partition number $(\text{bp})$ of a graph $G$ is referred to as the least number of complete bipartite (biclique) subgraphs that are required to cover the edges of the graph exactly once. In this paper, we show that the biclique partition number ($\text{bp}$) of a co-chordal (complementary graph of chordal) graph $G = (V, E)$ is less than the number of maximal cliques ($\text{mc}$) of… ▽ More The biclique partition number $(\text{bp})$ of a graph $G$ is referred to as the least number of complete bipartite (biclique) subgraphs that are required to cover the edges of the graph exactly once. In this paper, we show that the biclique partition number ($\text{bp}$) of a co-chordal (complementary graph of chordal) graph $G = (V, E)$ is less than the number of maximal cliques ($\text{mc}$) of its complementary graph: a chordal graph $G^c = (V, E^c)$. We first provide a general framework of the ``divide and conquer" heuristic of finding minimum biclique partitions of co-chordal graphs based on clique trees. Furthermore, a heuristic of complexity $O[|V|(|V|+|E^c|)]$ is proposed by applying lexicographic breadth-first search to find structures called moplexes. Either heuristic gives us a biclique partition of $G$ with size $\text{mc}(G^c)-1$. In addition, we prove that both of our heuristics can solve the minimum biclique partition problem on $G$ exactly if its complement $G^c$ is chordal and clique vertex irreducible. We also show that $\text{mc}(G^c) - 2 \leq \text{bp}(G) \leq \text{mc}(G^c) - 1$ if $G$ is a split graph. △ Less

Submitted 16 February, 2023; v1 submitted 5 March, 2022; originally announced March 2022.

Learning Dynamic Mechanisms in Unknown Environments: A Reinforcement Learning Approach

Authors: Shuang Qiu, Boxiang Lyu, Qinglin Meng, Zhaoran Wang, Zhuoran Yang, Michael I. Jordan

Abstract: Dynamic mechanism design studies how mechanism designers should allocate resources among agents in a time-varying environment. We consider the problem where the agents interact with the mechanism designer according to an unknown Markov Decision Process (MDP), where agent rewards and the mechanism designer's state evolve according to an episodic MDP with unknown reward functions and transition kern… ▽ More Dynamic mechanism design studies how mechanism designers should allocate resources among agents in a time-varying environment. We consider the problem where the agents interact with the mechanism designer according to an unknown Markov Decision Process (MDP), where agent rewards and the mechanism designer's state evolve according to an episodic MDP with unknown reward functions and transition kernels. We focus on the online setting with linear function approximation and propose novel learning algorithms to recover the dynamic Vickrey-Clarke-Grove (VCG) mechanism over multiple rounds of interaction. A key contribution of our approach is incorporating reward-free online Reinforcement Learning (RL) to aid exploration over a rich policy space to estimate prices in the dynamic VCG mechanism. We show that the regret of our proposed method is upper bounded by $\tilde{\mathcal{O}}(T^{2/3})$ and further devise a lower bound to show that our algorithm is efficient, incurring the same $\tilde{\mathcal{O}}(T^{2 / 3})$ regret as the lower bound, where $T$ is the total number of rounds. Our work establishes the regret guarantee for online RL in solving dynamic mechanism design problems without prior knowledge of the underlying model. △ Less

Submitted 25 February, 2024; v1 submitted 25 February, 2022; originally announced February 2022.

Comments: Minor Revision for JMLR. The first three authors contribute equally

L-SVRG and L-Katyusha with Adaptive Sampling

Authors: Boxin Zhao, Boxiang Lyu, Mladen Kolar

Abstract: Stochastic gradient-based optimization methods, such as L-SVRG and its accelerated variant L-Katyusha (Kovalev et al., 2020), are widely used to train machine learning models.The theoretical and empirical performance of L-SVRG and L-Katyusha can be improved by sampling observations from a non-uniform distribution (Qian et al., 2021). However,designing a desired sampling distribution requires prior… ▽ More Stochastic gradient-based optimization methods, such as L-SVRG and its accelerated variant L-Katyusha (Kovalev et al., 2020), are widely used to train machine learning models.The theoretical and empirical performance of L-SVRG and L-Katyusha can be improved by sampling observations from a non-uniform distribution (Qian et al., 2021). However,designing a desired sampling distribution requires prior knowledge of smoothness constants, which can be computationally intractable to obtain in practice when the dimension of the model parameter is high. To address this issue, we propose an adaptive sampling strategy for L-SVRG and L-Katyusha that can learn the sampling distribution with little computational overhead, while allowing it to change with iterates, and at the same time does not require any prior knowledge of the problem parameters. We prove convergence guarantees for L-SVRG and L-Katyusha for convex objectives when the sampling distribution changes with iterates. Our results show that even without prior information, the proposed adaptive sampling strategy matches, and in some cases even surpasses, the performance of the sampling scheme in Qian et al. (2021). Extensive simulations support our theory and the practical utility of the proposed sampling scheme on real data. △ Less

Submitted 5 June, 2023; v1 submitted 31 January, 2022; originally announced January 2022.

Comments: Published in Transactions on Machine Learning Research (03/2023)

Conditional entropy minimization principle for learning domain invariant representation features

Authors: Thuan Nguyen, Boyang Lyu, Prakash Ishwar, Matthias Scheutz, Shuchin Aeron

Abstract: Invariance-principle-based methods such as Invariant Risk Minimization (IRM), have recently emerged as promising approaches for Domain Generalization (DG). Despite promising theory, such approaches fail in common classification tasks due to the mixing of true invariant features and spurious invariant features. To address this, we propose a framework based on the conditional entropy minimization (C… ▽ More Invariance-principle-based methods such as Invariant Risk Minimization (IRM), have recently emerged as promising approaches for Domain Generalization (DG). Despite promising theory, such approaches fail in common classification tasks due to the mixing of true invariant features and spurious invariant features. To address this, we propose a framework based on the conditional entropy minimization (CEM) principle to filter-out the spurious invariant features leading to a new algorithm with a better generalization capability. We show that our proposed approach is closely related to the well-known Information Bottleneck (IB) framework and prove that under certain assumptions, entropy minimization can exactly recover the true invariant features. Our approach provides competitive classification accuracy compared to recent theoretically-principled state-of-the-art alternatives across several DG datasets. △ Less

Submitted 9 July, 2022; v1 submitted 25 January, 2022; originally announced January 2022.

Comments: 10 pages, this paper was accepted at 26th International Conference on Pattern Recognition (ICPR-2022)

AutoGMap: Learning to Map Large-scale Sparse Graphs on Memristive Crossbars

Authors: Bo Lyu, Shengbo Wang, Shiping Wen, Kaibo Shi, Yin Yang, Lingfang Zeng, Tingwen Huang

Abstract: The sparse representation of graphs has shown great potential for accelerating the computation of graph applications (e.g., Social Networks, Knowledge Graphs) on traditional computing architectures (CPU, GPU, or TPU). But the exploration of large-scale sparse graph computing on processing-in-memory (PIM) platforms (typically with memristive crossbars) is still in its infancy. To implement the comp… ▽ More The sparse representation of graphs has shown great potential for accelerating the computation of graph applications (e.g., Social Networks, Knowledge Graphs) on traditional computing architectures (CPU, GPU, or TPU). But the exploration of large-scale sparse graph computing on processing-in-memory (PIM) platforms (typically with memristive crossbars) is still in its infancy. To implement the computation or storage of large-scale or batch graphs on memristive crossbars, a natural assumption is that a large-scale crossbar is demanded, but with low utilization. Some recent works question this assumption, to avoid the waste of storage and computational resource, the fixed-size or progressively scheduled ''block partition'' schemes are proposed. However, these methods are coarse-grained or static, and are not effectively sparsity-aware. This work proposes the dynamic sparsity-aware mapping scheme generating method that models the problem with a sequential decision-making model, and optimizes it by reinforcement learning (RL) algorithm (REINFORCE). Our generating model (LSTM, combined with the dynamic-fill scheme) generates remarkable mapping performance on a small-scale graph/matrix data (complete mapping costs 43% area of the original matrix) and two large-scale matrix data (costing 22.5% area on qh882 and 17.1% area on qh1484). Our method may be extended to sparse graph computing on other PIM architectures, not limited to the memristive device-based platforms. △ Less

Submitted 2 March, 2023; v1 submitted 15 November, 2021; originally announced November 2021.

Comments: This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible

TND-NAS: Towards Non-differentiable Objectives in Progressive Differentiable NAS Framework

Authors: Bo Lyu, Shiping Wen

Abstract: Differentiable architecture search has gradually become the mainstream research topic in the field of Neural Architecture Search (NAS) for its high efficiency compared with the early NAS methods. Recent differentiable NAS also aims at further improving the search performance and reducing the GPU-memory consumption. However, these methods are no longer naturally capable of tackling the non-differen… ▽ More Differentiable architecture search has gradually become the mainstream research topic in the field of Neural Architecture Search (NAS) for its high efficiency compared with the early NAS methods. Recent differentiable NAS also aims at further improving the search performance and reducing the GPU-memory consumption. However, these methods are no longer naturally capable of tackling the non-differentiable objectives, e.g., energy, resource-constrained efficiency, and other metrics, let alone the multi-objective search demands. Researches in the multi-objective NAS field target this but requires vast computational resources cause of the sole optimization of each candidate architecture. In light of this discrepancy, we propose the TND-NAS, which is with the merits of the high efficiency in differentiable NAS framework and the compatibility among non-differentiable metrics in Multi-objective NAS. Under the differentiable NAS framework, with the continuous relaxation of the search space, TND-NAS has the architecture parameters been optimized in discrete space, while resorting to the progressive search space shrinking by architecture parameters. Our representative experiment takes two objectives (Parameters, Accuracy) as an example, we achieve a series of high-performance compact architectures on CIFAR10 (1.09M/3.3%, 2.4M/2.95%, 9.57M/2.54%) and CIFAR100 (2.46M/18.3%, 5.46/16.73%, 12.88/15.20%) datasets. Favorably, compared with other multi-objective NAS methods, TND-NAS is less time-consuming (1.3 GPU-days on NVIDIA 1080Ti, 1/6 of that in NSGA-Net), and can be conveniently adapted to real-world NAS scenarios (resource-constrained, platform-specialized). △ Less

Submitted 1 July, 2023; v1 submitted 6 November, 2021; originally announced November 2021.

Barycentric-alignment and reconstruction loss minimization for domain generalization

Authors: Boyang Lyu, Thuan Nguyen, Prakash Ishwar, Matthias Scheutz, Shuchin Aeron

Abstract: This paper advances the theory and practice of Domain Generalization (DG) in machine learning. We consider the typical DG setting where the hypothesis is composed of a representation mapping followed by a labeling function. Within this setting, the majority of popular DG methods aim to jointly learn the representation and the labeling functions by minimizing a well-known upper bound for the classi… ▽ More This paper advances the theory and practice of Domain Generalization (DG) in machine learning. We consider the typical DG setting where the hypothesis is composed of a representation mapping followed by a labeling function. Within this setting, the majority of popular DG methods aim to jointly learn the representation and the labeling functions by minimizing a well-known upper bound for the classification risk in the unseen domain. In practice, however, methods based on this theoretical upper bound ignore a term that cannot be directly optimized due to its dual dependence on both the representation mapping and the unknown optimal labeling function in the unseen domain. To bridge this gap between theory and practice, we introduce a new upper bound that is free of terms having such dual dependence, resulting in a fully optimizable risk upper bound for the unseen domain. Our derivation leverages classical and recent transport inequalities that link optimal transport metrics with information-theoretic measures. Compared to previous bounds, our bound introduces two new terms: (i) the Wasserstein-2 barycenter term that aligns distributions between domains, and (ii) the reconstruction loss term that assesses the quality of representation in reconstructing the original data. Based on this new upper bound, we propose a novel DG algorithm named Wasserstein Barycenter Auto-Encoder (WBAE) that simultaneously minimizes the classification loss, the barycenter loss, and the reconstruction loss. Numerical results demonstrate that the proposed method outperforms current state-of-the-art DG algorithms on several datasets. △ Less

Submitted 21 May, 2023; v1 submitted 4 September, 2021; originally announced September 2021.

Comments: This article has been accepted for publication in IEEE Access

Soft and subspace robust multivariate rank tests based on entropy regularized optimal transport

Authors: Shoaib Bin Masud, Boyang Lyu, Shuchin Aeron

Abstract: In this paper, we extend the recently proposed multivariate rank energy distance, based on the theory of optimal transport, for statistical testing of distributional similarity, to soft rank energy distance. Being differentiable, this in turn allows us to extend the rank energy to a subspace robust rank energy distance, dubbed Projected soft-Rank Energy distance, which can be computed via optimiza… ▽ More In this paper, we extend the recently proposed multivariate rank energy distance, based on the theory of optimal transport, for statistical testing of distributional similarity, to soft rank energy distance. Being differentiable, this in turn allows us to extend the rank energy to a subspace robust rank energy distance, dubbed Projected soft-Rank Energy distance, which can be computed via optimization over the Stiefel manifold. We show via experiments that using projected soft rank energy one can trade-off the detection power vs the false alarm via projections onto an appropriately selected low dimensional subspace. We also show the utility of the proposed tests on unsupervised change point detection in multivariate time series data. All codes are publicly available at the link provided in the experiment section. △ Less

Submitted 17 April, 2021; v1 submitted 15 March, 2021; originally announced March 2021.

Comments: 14 pages, 5 figures

LET: Linguistic Knowledge Enhanced Graph Transformer for Chinese Short Text Matching

Authors: Boer Lyu, Lu Chen, Su Zhu, Kai Yu

Abstract: Chinese short text matching is a fundamental task in natural language processing. Existing approaches usually take Chinese characters or words as input tokens. They have two limitations: 1) Some Chinese words are polysemous, and semantic information is not fully utilized. 2) Some models suffer potential issues caused by word segmentation. Here we introduce HowNet as an external knowledge base and… ▽ More Chinese short text matching is a fundamental task in natural language processing. Existing approaches usually take Chinese characters or words as input tokens. They have two limitations: 1) Some Chinese words are polysemous, and semantic information is not fully utilized. 2) Some models suffer potential issues caused by word segmentation. Here we introduce HowNet as an external knowledge base and propose a Linguistic knowledge Enhanced graph Transformer (LET) to deal with word ambiguity. Additionally, we adopt the word lattice graph as input to maintain multi-granularity information. Our model is also complementary to pre-trained language models. Experimental results on two Chinese datasets show that our models outperform various typical text matching approaches. Ablation study also indicates that both semantic information and multi-granularity information are important for text matching modeling. △ Less

Submitted 24 February, 2021; originally announced February 2021.

Comments: Accepted by AAAI 2021; 9 pages, 5 figures

Domain Adaptation for Robust Workload Level Alignment Between Sessions and Subjects using fNIRS

Authors: Boyang Lyu, Thao Pham, Giles Blaney, Zachary Haga, Angelo Sassaroli, Sergio Fantini, Shuchin Aeron

Abstract: Significance: We demonstrated the potential of using domain adaptation on functional Near-Infrared Spectroscopy (fNIRS) data to classify different levels of n-back tasks that involve working memory. Aim: Domain shift in fNIRS data is a challenge in the workload level alignment across different experiment sessions and subjects. In order to address this problem, two domain adaptation approaches -- G… ▽ More Significance: We demonstrated the potential of using domain adaptation on functional Near-Infrared Spectroscopy (fNIRS) data to classify different levels of n-back tasks that involve working memory. Aim: Domain shift in fNIRS data is a challenge in the workload level alignment across different experiment sessions and subjects. In order to address this problem, two domain adaptation approaches -- Gromov-Wasserstein (G-W) and Fused Gromov-Wasserstein (FG-W) were used. Approach: Specifically, we used labeled data from one session or one subject to classify trials in another session (within the same subject) or another subject. We applied G-W for session-by-session alignment and FG-W for subject-by-subject alignment to fNIRS data acquired during different n-back task levels. We compared these approaches with three supervised methods: multi-class Support Vector Machine (SVM), Convolutional Neural Network (CNN), and Recurrent Neural Network (RNN). Results: In a sample of six subjects, G-W resulted in an alignment accuracy of 68 $\pm$ 4 % (weighted mean $\pm$ standard error) for session-by-session alignment, FG-W resulted in an alignment accuracy of 55 $\pm$ 2 % for subject-by-subject alignment. In each of these cases, 25 % accuracy represents chance. Alignment accuracy results from both G-W and FG-W are significantly greater than those from SVM, CNN and RNN. We also showed that removal of motion artifacts from the fNIRS data plays an important role in improving alignment performance. Conclusions: Domain adaptation has potential for session-by-session and subject-by-subject alignment of mental workload by using fNIRS data. △ Less

Submitted 29 November, 2020; v1 submitted 2 July, 2020; originally announced July 2020.

Optimized Energy and Information Relaying in Self-Sustainable IRS-Empowered WPCN

Authors: Bin Lyu, Parisa Ramezani, Dinh Thai Hoang, Shimin Gong, Zhen Yang, Abbas Jamalipour

Abstract: This paper proposes a hybrid-relaying scheme empowered by a self-sustainable intelligent reflecting surface (IRS) in a wireless powered communication network (WPCN), to simultaneously improve the performance of downlink energy transfer (ET) from a hybrid access point (HAP) to multiple users and uplink information transmission (IT) from users to the HAP. We propose time-switching (TS) and power-spl… ▽ More This paper proposes a hybrid-relaying scheme empowered by a self-sustainable intelligent reflecting surface (IRS) in a wireless powered communication network (WPCN), to simultaneously improve the performance of downlink energy transfer (ET) from a hybrid access point (HAP) to multiple users and uplink information transmission (IT) from users to the HAP. We propose time-switching (TS) and power-splitting (PS) schemes for the IRS, where the IRS can harvest energy from the HAP's signals by switching between energy harvesting and signal reflection in the TS scheme or adjusting its reflection amplitude in the PS scheme. For both the TS and PS schemes, we formulate the sum-rate maximization problems by jointly optimizing the IRS's phase shifts for both ET and IT and network resource allocation. To address each problem's non-convexity, we propose a two-step algorithm to obtain the near-optimal solution with high accuracy. To show the structure of resource allocation, we also investigate the optimal solutions for the schemes with random phase shifts. Through numerical results, we show that our proposed schemes can achieve significant system sum-rate gain compared to the baseline scheme without IRS. △ Less

Submitted 30 September, 2020; v1 submitted 6 April, 2020; originally announced April 2020.

Comments: To appear in IEEE Transactions on Communications

IRS-based Wireless Jamming Attacks: When Jammers can Attack without Power

Authors: Bin Lyu, Dinh Thai Hoang, Shimin Gong, Dusit Niyato, Dong In Kim

Abstract: This paper proposes to use Intelligent Reflecting Surface (IRS) as a green jammer to attack a legitimate communication without using any internal energy to generate jamming signals. In particular, the IRS is used to intelligently reflect the signals from the legitimate transmitter to the legitimate receiver (LR) to guarantee that the received signals from direct and reflecting links can be added d… ▽ More This paper proposes to use Intelligent Reflecting Surface (IRS) as a green jammer to attack a legitimate communication without using any internal energy to generate jamming signals. In particular, the IRS is used to intelligently reflect the signals from the legitimate transmitter to the legitimate receiver (LR) to guarantee that the received signals from direct and reflecting links can be added destructively, which thus diminishes the Signal-to-Interference-plus-Noise Ratio (SINR) at the LR. To minimize the received signal power at the LR, we consider the joint optimization of magnitudes of reflection coefficients and discrete phase shifts at the IRS. Based on the block coordinate descent, semidefinite relaxation, and Gaussian randomization techniques, the solution can be obtained efficiently. Through simulation results, we show that by using the IRS-based jammer, we can reduce the signal power received at the LR by up to 99\%. Interestingly, the performance of the proposed IRS-based jammer is even better than that of the conventional active jamming attacks in some scenarios. △ Less

Submitted 29 May, 2020; v1 submitted 6 January, 2020; originally announced January 2020.

Comments: 12 pages, 5 figures