Xiangyu Guo
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Xiangyu Guo has a total of 29 co-authors. Here are the top co-authors by number of shared publications:
- Shi Li
Nanjing University, Nanjing, China
10 shared publications - Jiayi Xian
Department of Computer Science and Engineering University at Buffalo
4 shared publications - Di Wang
Nanyang technological university, Singapore, Singapore
3 shared publications - Jinhui Xu
Department of Computer Science and Engineering, State University of New York at Buffalo, NY, USA
3 shared publications - Kelin Luo
University at Buffalo
3 shared publications - Bundit Laekhanukit
Shanghai University of Finance and Economics
2 shared publications
Latest Publications
- 31 October 2023
- Published by Springer Nature in Algorithmica
- Vol. 86 (4) , 907-943
Minimizing the Maximum Flow Time in the Online Food Delivery Problem
- 31 October 2023
- Published by Springer Nature in Algorithmica
- Vol. 86 (4) , 907-943
Minimizing the Maximum Flow Time in the Online Food Delivery Problem
- Open Access
- 1 January 2023
- Published by Association for Computing Machinery (ACM) in Proceedings of the VLDB Endowment
- Vol. 16 (5) , 1195-1207
A Hierarchical Grouping Algorithm for the Multi-Vehicle Dial-a-Ride Problem
Ride-sharing is an essential aspect of modern urban mobility. In this paper, we consider a classical problem in ride-sharing - the Multi-Vehicle Dial-a-Ride Problem (Multi-Vehicle DaRP). Given a fleet of vehicles with a fixed capacity stationed at various locations and a set of ride requests specified by origins and destinations, the goal is to serve all requests such that no vehicle is assigned more passengers than its capacity at any point in its trip. We give an algorithm HGR, which is the first non-trivial approximation algorithm for the Multi-Vehicle DaRP. The main technical contribution is to reduce Multi-Vehicle DaRP to a certain capacitated partitioning problem, which we solve using a novel hierarchical grouping algorithm. Experimental results show that the vehicle routes produced by our algorithm not only exhibit less total travel distance compared to state-of-the-art baselines, but also enjoy a small in-transit latency, which crucially relates to each individual rider's traveling time. This suggests that HGR enhances rider experience while being energy-efficient.
- 1 January 2023
- Published by Association for Computing Machinery (ACM) in Proceedings of the VLDB Endowment
- Vol. 16 (5) , 1195-1207
Open AccessA Hierarchical Grouping Algorithm for the Multi-Vehicle Dial-a-Ride Problem
Ride-sharing is an essential aspect of modern urban mobility. In this paper, we consider a classical problem in ride-sharing - the Multi-Vehicle Dial-a-Ride Problem (Multi-Vehicle DaRP). Given a fleet of vehicles with a fixed capacity stationed at various locations and a set of ride requests specified by origins and destinations, the goal is to serve all requests such that no vehicle is assigned more passengers than its capacity at any point in its trip. We give an algorithm HGR, which is the first non-trivial approximation algorithm for the Multi-Vehicle DaRP. The main technical contribution is to reduce Multi-Vehicle DaRP to a certain capacitated partitioning problem, which we solve using a novel hierarchical grouping algorithm. Experimental results show that the vehicle routes produced by our algorithm not only exhibit less total travel distance compared to state-of-the-art baselines, but also enjoy a small in-transit latency, which crucially relates to each individual rider's traveling time. This suggests that HGR enhances rider experience while being energy-efficient.
- Open Access
- 8 June 2022
- Published by Elsevier in Theoretical Computer Science
- Vol. 928, 13-26
The online food delivery problem on stars
- 8 June 2022
- Published by Elsevier in Theoretical Computer Science
- Vol. 928, 13-26
Open AccessThe online food delivery problem on stars
- Open Access
Finding Optimal Tangent Points for Reducing Distortions of Hard-label Attacks
One major problem in black-box adversarial attacks is the high query complexity in the hard-label attack setting, where only the top-1 predicted label is available. In this paper, we propose a novel geometric-based approach called Tangent Attack (TA), which identifies an optimal tangent point of a virtual hemisphere located on the decision boundary to reduce the distortion of the attack. Assuming the decision boundary is locally flat, we theoretically prove that the minimum $\ell_2$ distortion can be obtained by reaching the decision boundary along the tangent line passing through such tangent point in each iteration. To improve the robustness of our method, we further propose a generalized method which replaces the hemisphere with a semi-ellipsoid to adapt to curved decision boundaries. Our approach is free of pre-training. Extensive experiments conducted on the ImageNet and CIFAR-10 datasets demonstrate that our approach can consume only a small number of queries to achieve the low-magnitude distortion. The implementation source code is released online at https://github.com/machanic/TangentAttack.Open AccessFinding Optimal Tangent Points for Reducing Distortions of Hard-label Attacks
One major problem in black-box adversarial attacks is the high query complexity in the hard-label attack setting, where only the top-1 predicted label is available. In this paper, we propose a novel geometric-based approach called Tangent Attack (TA), which identifies an optimal tangent point of a virtual hemisphere located on the decision boundary to reduce the distortion of the attack. Assuming the decision boundary is locally flat, we theoretically prove that the minimum $\ell_2$ distortion can be obtained by reaching the decision boundary along the tangent line passing through such tangent point in each iteration. To improve the robustness of our method, we further propose a generalized method which replaces the hemisphere with a semi-ellipsoid to adapt to curved decision boundaries. Our approach is free of pre-training. Extensive experiments conducted on the ImageNet and CIFAR-10 datasets demonstrate that our approach can consume only a small number of queries to achieve the low-magnitude distortion. The implementation source code is released online at https://github.com/machanic/TangentAttack. - 24 January 2022
- Published by Springer Nature in Algorithmica
- Vol. 84 (5) , 1252-1278
On Approximating Degree-Bounded Network Design Problems
- 24 January 2022
- Published by Springer Nature in Algorithmica
- Vol. 84 (5) , 1252-1278
On Approximating Degree-Bounded Network Design Problems
- Open Access
Online Food Delivery to Minimize Maximum Flow Time
We study a common delivery problem encountered in nowadays online food-ordering platforms: Customers order dishes online, and the restaurant delivers the food after receiving the order. Specifically, we study a problem where $k$ vehicles of capacity $c$ are serving a set of requests ordering food from one restaurant. After a request arrives, it can be served by a vehicle moving from the restaurant to its delivery location. We are interested in serving all requests while minimizing the maximum flow-time, i.e., the maximum time length a customer waits to receive his/her food after submitting the order. We show that the problem is hard in both offline and online settings: There is a hardness of approximation of $\Omega(n)$ for the offline problem, and a lower bound of $\Omega(n)$ on the competitive ratio of any online algorithm, where $n$ is number of points in the metric. Our main result is an $O(1)$-competitive online algorithm for the uncapaciated (i.e, $c = \infty$) food delivery problem on tree metrics. Then we consider the speed-augmentation model. We develop an exponential time $(1+\epsilon)$-speeding $O(1/\epsilon)$-competitive algorithm for any $\epsilon > 0$. A polynomial time algorithm can be obtained with a speeding factor of $\alpha_{TSP}+ \epsilon$ or $\alpha_{CVRP}+ \epsilon$, depending on whether the problem is uncapacitated. Here $\alpha_{TSP}$ and $\alpha_{CVRP}$ are the best approximation factors for the traveling salesman (TSP) and capacitated vehicle routing (CVRP) problems respectively. We complement the results with some negative ones.Open AccessOnline Food Delivery to Minimize Maximum Flow Time
We study a common delivery problem encountered in nowadays online food-ordering platforms: Customers order dishes online, and the restaurant delivers the food after receiving the order. Specifically, we study a problem where $k$ vehicles of capacity $c$ are serving a set of requests ordering food from one restaurant. After a request arrives, it can be served by a vehicle moving from the restaurant to its delivery location. We are interested in serving all requests while minimizing the maximum flow-time, i.e., the maximum time length a customer waits to receive his/her food after submitting the order. We show that the problem is hard in both offline and online settings: There is a hardness of approximation of $\Omega(n)$ for the offline problem, and a lower bound of $\Omega(n)$ on the competitive ratio of any online algorithm, where $n$ is number of points in the metric. Our main result is an $O(1)$-competitive online algorithm for the uncapaciated (i.e, $c = \infty$) food delivery problem on tree metrics. Then we consider the speed-augmentation model. We develop an exponential time $(1+\epsilon)$-speeding $O(1/\epsilon)$-competitive algorithm for any $\epsilon > 0$. A polynomial time algorithm can be obtained with a speeding factor of $\alpha_{TSP}+ \epsilon$ or $\alpha_{CVRP}+ \epsilon$, depending on whether the problem is uncapacitated. Here $\alpha_{TSP}$ and $\alpha_{CVRP}$ are the best approximation factors for the traveling salesman (TSP) and capacitated vehicle routing (CVRP) problems respectively. We complement the results with some negative ones. - 28 June 2021
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 825-831
A harmony search algorithm to operation sequencing optimization in process planning
Aiming at the problem that the sequence of operation in the processing of complex parts directly affects the processing cost, an improved harmony search algorithm with the lowest processing cost as the optimization goal is proposed. The constraint relationship between the operation is represented by a process priority diagram. Then use the topological sorting method on the graph to generate the initial sequence as the initial harmony of the harmony memory. The crossover operator is introduced to ensure the feasibility of the new generation of harmony, and the local search method is used to change the machine and tool resources available for the operation to avoid falling into the local optimum. Experimental results show that the improved harmony search method can effectively solve the cost optimization problem of step sequencing.
- 28 June 2021
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 825-831
A harmony search algorithm to operation sequencing optimization in process planning
Aiming at the problem that the sequence of operation in the processing of complex parts directly affects the processing cost, an improved harmony search algorithm with the lowest processing cost as the optimization goal is proposed. The constraint relationship between the operation is represented by a process priority diagram. Then use the topological sorting method on the graph to generate the initial sequence as the initial harmony of the harmony memory. The crossover operator is introduced to ensure the feasibility of the new generation of harmony, and the local search method is used to change the machine and tool resources available for the operation to avoid falling into the local optimum. Experimental results show that the improved harmony search method can effectively solve the cost optimization problem of step sequencing.
- Open Access
- 2 November 2020
- Published by Springer Nature in Machine Learning
- Vol. 109 (12) , 2283-2311
Robust high dimensional expectation maximization algorithm via trimmed hard thresholding
- 2 November 2020
- Published by Springer Nature in Machine Learning
- Vol. 109 (12) , 2283-2311
Open AccessRobust high dimensional expectation maximization algorithm via trimmed hard thresholding
- Open Access
Robust High Dimensional Expectation Maximization Algorithm via Trimmed Hard Thresholding
In this paper, we study the problem of estimating latent variable models with arbitrarily corrupted samples in high dimensional space ({\em i.e.,} $d\gg n$) where the underlying parameter is assumed to be sparse. Specifically, we propose a method called Trimmed (Gradient) Expectation Maximization which adds a trimming gradients step and a hard thresholding step to the Expectation step (E-step) and the Maximization step (M-step), respectively. We show that under some mild assumptions and with an appropriate initialization, the algorithm is corruption-proofing and converges to the (near) optimal statistical rate geometrically when the fraction of the corrupted samples $\epsilon$ is bounded by $ \tilde{O}(\frac{1}{\sqrt{n}})$. Moreover, we apply our general framework to three canonical models: mixture of Gaussians, mixture of regressions and linear regression with missing covariates. Our theory is supported by thorough numerical results.Open AccessRobust High Dimensional Expectation Maximization Algorithm via Trimmed Hard Thresholding
In this paper, we study the problem of estimating latent variable models with arbitrarily corrupted samples in high dimensional space ({\em i.e.,} $d\gg n$) where the underlying parameter is assumed to be sparse. Specifically, we propose a method called Trimmed (Gradient) Expectation Maximization which adds a trimming gradients step and a hard thresholding step to the Expectation step (E-step) and the Maximization step (M-step), respectively. We show that under some mild assumptions and with an appropriate initialization, the algorithm is corruption-proofing and converges to the (near) optimal statistical rate geometrically when the fraction of the corrupted samples $\epsilon$ is bounded by $ \tilde{O}(\frac{1}{\sqrt{n}})$. Moreover, we apply our general framework to three canonical models: mixture of Gaussians, mixture of regressions and linear regression with missing covariates. Our theory is supported by thorough numerical results. - Open Access
Estimating Stochastic Linear Combination of Non-linear Regressions Efficiently and Scalably
Recently, many machine learning and statistical models such as non-linear regressions, the Single Index, Multi-index, Varying Coefficient Index Models and Two-layer Neural Networks can be reduced to or be seen as a special case of a new model which is called the \textit{Stochastic Linear Combination of Non-linear Regressions} model. However, due to the high non-convexity of the problem, there is no previous work study how to estimate the model. In this paper, we provide the first study on how to estimate the model efficiently and scalably. Specifically, we first show that with some mild assumptions, if the variate vector $x$ is multivariate Gaussian, then there is an algorithm whose output vectors have $\ell_2$-norm estimation errors of $O(\sqrt{\frac{p}{n}})$ with high probability, where $p$ is the dimension of $x$ and $n$ is the number of samples. The key idea of the proof is based on an observation motived by the Stein's lemma. Then we extend our result to the case where $x$ is bounded and sub-Gaussian using the zero-bias transformation, which could be seen as a generalization of the classic Stein's lemma. We also show that with some additional assumptions there is an algorithm whose output vectors have $\ell_\infty$-norm estimation errors of $O(\frac{1}{\sqrt{p}}+\sqrt{\frac{p}{n}})$ with high probability. We also provide a concrete example to show that there exists some link function which satisfies the previous assumptions. Finally, for both Gaussian and sub-Gaussian cases we propose a faster sub-sampling based algorithm and show that when the sub-sample sizes are large enough then the estimation errors will not be sacrificed by too much. Experiments for both cases support our theoretical results. To the best of our knowledge, this is the first work that studies and provides theoretical guarantees for the stochastic linear combination of non-linear regressions model.Open AccessEstimating Stochastic Linear Combination of Non-linear Regressions Efficiently and Scalably
Recently, many machine learning and statistical models such as non-linear regressions, the Single Index, Multi-index, Varying Coefficient Index Models and Two-layer Neural Networks can be reduced to or be seen as a special case of a new model which is called the \textit{Stochastic Linear Combination of Non-linear Regressions} model. However, due to the high non-convexity of the problem, there is no previous work study how to estimate the model. In this paper, we provide the first study on how to estimate the model efficiently and scalably. Specifically, we first show that with some mild assumptions, if the variate vector $x$ is multivariate Gaussian, then there is an algorithm whose output vectors have $\ell_2$-norm estimation errors of $O(\sqrt{\frac{p}{n}})$ with high probability, where $p$ is the dimension of $x$ and $n$ is the number of samples. The key idea of the proof is based on an observation motived by the Stein's lemma. Then we extend our result to the case where $x$ is bounded and sub-Gaussian using the zero-bias transformation, which could be seen as a generalization of the classic Stein's lemma. We also show that with some additional assumptions there is an algorithm whose output vectors have $\ell_\infty$-norm estimation errors of $O(\frac{1}{\sqrt{p}}+\sqrt{\frac{p}{n}})$ with high probability. We also provide a concrete example to show that there exists some link function which satisfies the previous assumptions. Finally, for both Gaussian and sub-Gaussian cases we propose a faster sub-sampling based algorithm and show that when the sub-sample sizes are large enough then the estimation errors will not be sacrificed by too much. Experiments for both cases support our theoretical results. To the best of our knowledge, this is the first work that studies and provides theoretical guarantees for the stochastic linear combination of non-linear regressions model.