Arrow Research search

Author name cluster

Xiaoming Sun

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

23 papers
1 author row

Possible papers

23

EAAI Journal 2025 Journal Article

A single-valued neutrosophic affinity propagation approach for engineering geological zoning of open-pit mine slopes

  • Jibo Qin
  • Xiaoming Sun
  • Shigui Du
  • Jun Ye

Engineering geological zoning is an important foundation for assessing the stability of open-pit mine (OPM) slopes. Because of the complexity and uncertainty of geological conditions, this work brings great challenges to mining engineers and researchers. This paper presents a single-valued neutrosophic affinity propagation (SVNS-AP) approach for engineering geological zoning of OPM slopes. The approach utilizes the concept of a single-valued neutrosophic set (SVNS) to express the inconsistent and indeterminate information present in the influencing factors of engineering geological conditions through truth, indeterminate and falsity membership functions. Then, the similarity measure of SVNS is integrated into the affinity propagation (AP) algorithm to calculate the degree of similarity between the data points. Finally, the modified silhouette index is used to evaluate the clustering results and decide the optimal number of clusters. The practical application results of the engineering geological zoning of Lanping lead-zinc OPM demonstrate that the SVNS-AP method is an effective way for engineering geological zoning of OPM slopes in the uncertain environment. Clustering results based on datasets in the literature and the UC Irvine Machine Learning Repository show that the proposed method can be used as a general clustering algorithm.

Details DOI

TCS Journal 2025 Journal Article

Efficient deterministic algorithms for maximizing symmetric submodular functions

  • Zongqi Wan
  • Jialin Zhang
  • Xiaoming Sun
  • Zhijie Zhang

Symmetric submodular maximization is an important class of combinatorial optimization problems, including MAX-CUT on graphs and hyper-graphs. The state-of-the-art algorithm for the problem over general constraints has an approximation ratio of 0. 432 [16]. The algorithm applies the canonical continuous greedy technique that involves a sampling process. It, therefore, suffers from high query complexity and is inherently randomized. In this paper, we present several efficient deterministic algorithms for maximizing a symmetric submodular function under various constraints. Specifically, for the cardinality constraint, we design a deterministic algorithm that attains a 0. 432 ratio and uses O ( k n ) queries. Previously, the best deterministic algorithm attains a 0. 385 − ϵ ratio and uses O ( k n ( 10 9 ϵ ) 20 9 ϵ − 1 ) queries [12]. For the matroid constraint, we design a deterministic algorithm that attains a 1 / 3 − ϵ ratio and uses O ( k n log ⁡ ϵ − 1 ) queries. Previously, the best deterministic algorithm can also attain 1 / 3 − ϵ ratio but it uses much larger O ( ϵ − 1 n 4 ) queries [24]. For the packing constraints with a large width, we design a deterministic algorithm that attains a 0. 432 − ϵ ratio and uses O ( n 2 ) queries. To the best of our knowledge, there is no deterministic algorithm for the constraint previously. The last algorithm can be adapted to attain a 0. 432 ratio for single knapsack constraint using O ( n 4 ) queries. Previously, the best deterministic algorithm attains a 0. 316 − ϵ ratio and uses O ˜ ( n 3 ) queries [2].

Details DOI

TCS Journal 2024 Journal Article

Improved deterministic algorithms for non-monotone submodular maximization

  • Xiaoming Sun
  • Jialin Zhang
  • Shuo Zhang
  • Zhijie Zhang

Submodular maximization is one of the central topics in combinatorial optimization. It has found numerous applications in the real world. In the past decades, a series of algorithms have been proposed for this problem. However, most of the state-of-the-art algorithms are randomized. There remain non-negligible gaps with respect to approximation ratios between deterministic and randomized algorithms in submodular maximization. In this paper, we propose deterministic algorithms with improved approximation ratios for non-monotone submodular maximization. Specifically, for the matroid constraint, we provide a deterministic 0. 283 − o ( 1 ) approximation algorithm, while the previous best deterministic algorithm only achieves a 1/4 approximation ratio. For the knapsack constraint, we provide a deterministic 1/4 approximation algorithm, while the previous best deterministic algorithm only achieves a 1/6 approximation ratio. For the linear packing constraints with large widths, we provide a deterministic 1 / 6 − ϵ approximation algorithm. To the best of our knowledge, there is currently no deterministic approximation algorithm for the constraints.

Details DOI

AAAI Conference 2023 Conference Paper

Quantum Multi-Armed Bandits and Stochastic Linear Bandits Enjoy Logarithmic Regrets

  • Zongqi Wan
  • Zhijie Zhang
  • Tongyang Li
  • Jialin Zhang
  • Xiaoming Sun

Multi-arm bandit (MAB) and stochastic linear bandit (SLB) are important models in reinforcement learning, and it is well-known that classical algorithms for bandits with time horizon T suffer from the regret of at least the square root of T. In this paper, we study MAB and SLB with quantum reward oracles and propose quantum algorithms for both models with the order of the polylog T regrets, exponentially improving the dependence in terms of T. To the best of our knowledge, this is the first provable quantum speedup for regrets of bandit problems and in general exploitation in reinforcement learning. Compared to previous literature on quantum exploration algorithms for MAB and reinforcement learning, our quantum input model is simpler and only assumes quantum oracles for each individual arm.

PDF Details DOI

IJCAI Conference 2022 Conference Paper

Bounded Memory Adversarial Bandits with Composite Anonymous Delayed Feedback

  • Zongqi Wan
  • Xiaoming Sun
  • Jialin Zhang

We study the adversarial bandit problem with composite anonymous delayed feedback. In this setting, losses of an action are split into d components, spreading over consecutive rounds after the action is chosen. And in each round, the algorithm observes the aggregation of losses that come from the latest d rounds. Previous works focus on oblivious adversarial setting, while we investigate the harder nonoblivious setting. We show nonoblivious setting incurs Omega(T) pseudo regret even when the loss sequence is bounded memory. However, we propose a wrapper algorithm which enjoys o(T) policy regret on many adversarial bandit problems with the assumption that the loss sequence is bounded memory. Especially, for K armed bandit and bandit convex optimization, our policy regret bound is in the order of T to the two third. We also prove a matching lower bound for K armed bandit. Our lower bound works even when the loss sequence is oblivious but the delay is nonoblivious. It answers the open problem proposed in [Wang, Wang, Huang 2021], showing that nonoblivious delay is enough to incur the regret in the order of T to the two third.

PDF Details DOI

AAAI Conference 2022 Conference Paper

Online Influence Maximization with Node-Level Feedback Using Standard Offline Oracles

  • Zhijie Zhang
  • Wei Chen
  • Xiaoming Sun
  • Jialin Zhang

We study the online influence maximization (OIM) problem in social networks, where in multiple rounds the learner repeatedly chooses seed nodes to generate cascades, observes the cascade feedback, and gradually learns the best seeds that generate the largest cascade. We focus on two major challenges in this paper. First, we work with node-level feedback instead of edge-level feedback. The edge-level feedback reveals all edges that pass through information in a cascade, whereas the node-level feedback only reveals the activated nodes with timestamps. The node-level feedback is arguably more realistic since in practice it is relatively easy to observe who is influenced but very difficult to observe from which relationship (edge) the influence comes. Second, we use standard offline oracles instead of offline pair-oracles. To compute a good seed set for the next round, an offline pair-oracle finds the best seed set and the best parameters within the confidence region simultaneously, and such an oracle is difficult to compute due to the combinatorial core of the OIM problem. So we focus on how to use the standard offline influence maximization oracle which finds the best seed set given the edge parameters as input. In this paper, we resolve these challenges for the famous independent cascade (IC) diffusion model. The past research only achieves edge-level feedback, while we present the first e O( √ T)-regret algorithm for the node-level feedback. For the first challenge above, we apply a novel adaptation of the maximum likelihood estimation (MLE) approach to learn the graph parameters and its confidence region (a confidence ellipsoid). For the second challenge, we adjust the update procedure to dissect the confidence ellipsoid into confidence intervals on each parameter, so that the standard offline influence maximization oracle is enough.

PDF Details

AAAI Conference 2020 Conference Paper

Revisiting Online Quantum State Learning

  • Feidiao Yang
  • Jiaqing Jiang
  • Jialin Zhang
  • Xiaoming Sun

In this paper, we study the online quantum state learning problem which is recently proposed by Aaronson et al. (2018). In this problem, the learning algorithm sequentially predicts quantum states based on observed measurements and losses and the goal is to minimize the regret. In the previous work, the existing algorithms may output mixed quantum states. However, in many scenarios, the prediction of a pure quantum state is required. In this paper, we first propose a Follow-the-Perturbed-Leader (FTPL) algorithm that can guarantee to predict pure quantum states. Theoretical analysis shows that our algorithm can achieve an O( √ T) expected regret under some reasonable settings. In the case that the pure state prediction is not mandatory, we propose another deterministic learning algorithm which is simpler and more efficient. The algorithm is based on the online gradient descent (OGD) method and can also achieve an O( √ T) regret bound. The main technical contribution of this result is an algorithm of projecting an arbitrary Hermitian matrix onto the set of density matrices with respect to the Frobenius norm. We think this subroutine is of independent interest and can be widely used in many other problems in the quantum computing area. In addition to the theoretical analysis, we evaluate the algorithms with a series of simulation experiments. The experimental results show that our FTPL method and OGD method outperform the existing RFTL approach proposed by Aaronson et al. (2018) in almost all settings. In the implementation of the RFTL approach, we give a closed-form solution to the algorithm. This provides an efficient, accurate, and completely executable solution to the RFTL method.

PDF Details

IJCAI Conference 2019 Conference Paper

A Quantum-inspired Classical Algorithm for Separable Non-negative Matrix Factorization

  • Zhihuai Chen
  • Yinan Li
  • Xiaoming Sun
  • Pei Yuan
  • Jialin Zhang

Non-negative Matrix Factorization (NMF) asks to decompose a (entry-wise) non-negative matrix into the product of two smaller-sized nonnegative matrices, which has been shown intractable in general. In order to overcome this issue, separability assumption is introduced which assumes all data points are in a conical hull. This assumption makes NMF tractable and widely used in text analysis and image processing, but still impractical for huge-scale datasets. In this paper, inspired by recent development on dequantizing techniques, we propose a new classical algorithm for separable NMF problem. Our new algorithm runs in polynomial time in the rank and logarithmic in the size of input matrices, which achieves an exponential speedup in the low-rank setting.

PDF Details

AAAI Conference 2017 Conference Paper

Efficient Delivery Policy to Minimize User Traffic Consumption in Guaranteed Advertising

  • Jia Zhang
  • Zheng Wang
  • Qian Li
  • Jialin Zhang
  • Yanyan Lan
  • Qiang Li
  • Xiaoming Sun

In this work, we study the guaranteed delivery model which is widely used in online advertising. In the guaranteed delivery scenario, ad exposures (which are also called impressions in some works) to users are guaranteed by contracts signed in advance between advertisers and publishers. A crucial problem for the advertising platform is how to fully utilize the valuable user traffic to generate as much as possible revenue. Different from previous works which usually minimize the penalty of unsatisfied contracts and some other cost (e. g. representativeness), we propose the novel consumption minimization model, in which the primary objective is to minimize the user traffic consumed to satisfy all contracts. Under this model, we develop a near optimal method to deliver ads for users. The main advantage of our method lies in that it consumes nearly as least as possible user traffic to satisfy all contracts, therefore more contracts can be accepted to produce more revenue. It also enables the publishers to estimate how much user traffic is redundant or short so that they can sell or buy this part of traffic in bulk in the exchange market. Furthermore, it is robust with regard to priori knowledge of user type distribution. Finally, the simulation shows that our method outperforms the traditional state-of-the-art methods.

PDF Details

AAAI Conference 2017 Conference Paper

Randomized Mechanisms for Selling Reserved Instances in Cloud

  • Jia Zhang
  • Weidong Ma
  • Tao Qin
  • Xiaoming Sun
  • Tie-Yan Liu

Selling reserved instances (or virtual machines) is a basic service in cloud computing. In this paper, we consider a more flexible pricing model for instance reservation, in which a customer can propose the time length and number of resources of her request, while in today’s industry, customers can only choose from several predefined reservation packages. Under this model, we design randomized mechanisms for customers coming online to optimize social welfare and providers’ revenue. We first consider a simple case, where the requests from the customers do not vary too much in terms of both length and value density. We design a randomized mechanism that achieves a competitive ratio 1 42 for both social welfare and revenue, which is a improvement as there is usually no revenue guarantee in previous works such as (Azar et al. 2015; Wang et al. 2015). This ratio can be improved up to 1 11 when we impose a realistic constraint on the maximum number of resources used by each request. On the hardness side, we show an upper bound 1 3 on competitive ratio for any randomized mechanism. We then extend our mechanism to the general case and achieve a competitive ratio 1 42 log k log T for both social welfare and revenue, where T is the ratio of the maximum request length to the minimum request length and k is the ratio of the maximum request value density to the minimum request value density. This result outperforms the previous upper bound 1 CkT for deterministic mechanisms (Wang et al. 2015). We also prove an upper bound 2 log 8kT for any randomized mechanism. All the mechanisms we provide are in a greedy style. They are truthful and easy to be integrated into practical cloud systems.

PDF Details

AAAI Conference 2016 Conference Paper

Learning Market Parameters Using Aggregate Demand Queries

  • Xiaohui Bei
  • Wei Chen
  • Jugal Garg
  • Martin Hoefer
  • Xiaoming Sun

We study efficient algorithms for a natural learning problem in markets. There is one seller with m divisible goods and n buyers with unknown individual utility functions and budgets of money. The seller can repeatedly announce prices and observe aggregate demand bundles requested by the buyers. The goal of the seller is to learn the utility functions and budgets of the buyers. Our scenario falls into the classic domain of “revealed preference” analysis. Problems with revealed preference have recently started to attract increased interest in computer science due to their fundamental nature in understanding customer behavior in electronic markets. The goal of revealed preference analysis is to observe rational agent behavior, to explain it using a suitable model for the utility functions, and to predict future agent behavior. Our results are the first polynomial-time algorithms to learn utility and budget parameters via revealed preference queries in classic Fisher markets with multiple buyers. Our analysis concentrates on linear, CES, and Leontief markets, which are the most prominent classes studied in the literature. Some of our results extend to general Arrow-Debreu exchange markets.

PDF Details

IJCAI Conference 2013 Conference Paper

Optimal Pricing for Improving Efficiency of Taxi Systems

  • Jiarui Gan
  • Bo An
  • Haizhong Wang
  • Xiaoming Sun
  • Zhongzhi Shi

In Beijing, most taxi drivers intentionally avoid working during peak hours despite of the huge customer demand within these peak periods. This dilemma is mainly due to the fact that taxi drivers’ congestion costs are not reflected in the current taxi fare structure. To resolve this problem, we propose a new pricing scheme to provide taxi drivers with extra incentives to work during peak hours. This differs from previous studies of taxi market by considering market variance over multiple periods, taxi drivers’ profit-driven decisions, and their scheduling constraints regarding the interdependence among different periods. The major challenge of this research is the computational intensiveness to identify optimal strategy due to the exponentially large size of a taxi driver’s strategy space and the scheduling constraints. We develop an atom schedule method to overcome these issues. It reduces the magnitude of the problem while satisfying the constraints to filter out infeasible pure strategies. Simulation results based on real data show the effectiveness of the proposed methods, which opens up a new door to improving the ef- ficiency of taxi market in megacities (e. g. , Beijing).

PDF Details DOI