Author name cluster

Kevin Ren

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.

5 papers

2 author rows

STOC Conference 2025 Conference Paper

Optimal Rounding for Sparsest Cut

Alan Chang
Assaf Naor
Kevin Ren

We prove that the integrality gap of the Goemans–Linial semidefinite program for the Sparsest Cut problem (with general capacities and demands) on inputs of size n ≥ 2 is Θ(√log n ). We achieve this by establishing the following geometric/structural result. If ( M , d ) is an n -point metric space of negative type, then for every τ>0 there is a random subset Z of M such that for any pair of points x , y ∈ M with d ( x , y )≥ τ, the probability that both x ∈ Z and d ( y , Z )≥ βτ/√1+log(| B ( y ,κ β τ)|/| B ( y ,β τ)|) is Ω(1), where 0<β<1<κ are universal constants. The proof relies on a refinement of the Arora–Rao–Vazirani rounding technique.

Details

ICRA Conference 2025 Conference Paper

Work Smarter Not Harder: Simple Imitation Learning with CS-PIBT Outperforms Large-Scale Imitation Learning for MAPF

Rishi Veerapaneni
Arthur Jakobsson
Kevin Ren
Samuel Kim
Jiaoyang Li 0001
Maxim Likhachev

Multi-Agent Path Finding (MAPF) is the problem of effectively finding efficient collision-free paths for a group of agents in a shared workspace. The MAPF community has largely focused on developing high-performance heuristic search methods. Recently, several works have applied various machine learning (ML) techniques to solve MAPF, usually involving sophisticated architectures, reinforcement learning techniques, and set-ups, but none using large amounts of high-quality supervised data. Our initial objective in this work was to show how simple large-scale imitation learning of high-quality heuristic search methods can lead to state-of-the-art ML MAPF performance. However, we find that, at least with our model architecture, simple large-scale (700k examples with hundreds of agents per example) imitation learning does not produce impressive results. Instead, we find that by using prior work that post-processes MAPF model predictions to resolve 1-step collisions (CS-PIBT), we can train a simple ML MAPF policy in minutes that dramatically outperforms existing ML MAPF policies. This has serious implications for all future ML MAPF policies (with local communication) which currently struggle to scale. In particular, this finding implies that future learnt policies should always (1) use smart 1-step collision shields (e. g, CS-PIBT) and (2) include the collision shield with greedy actions as a baseline (e. g. PIBT), as well as (3) motivates future models to focus on longer horizon / more complex planning as 1-step collisions can be efficiently resolved.

Details

UAI Conference 2024 Conference Paper

Decision-Focused Evaluation of Worst-Case Distribution Shift

Kevin Ren
Yewon Byun
Bryan Wilder

Recent studies have shown that performance on downstream optimization tasks often diverges from standard accuracy-based losses, highlighting that the loss function of a predictive model should align with the decision task of the downstream optimizer. Despite this observation, no work{—} to our knowledge{—}has yet examined the impact of this divergence for distribution shift. In this paper, we demonstrate that worst-case distribution shifts identified by traditional average accuracy-based metrics fundamentally differ from those for the downstream decision task at hand. We introduce a novel framework that employs a hierarchical model structure to identify worst-case distribution shifts in predictive resource allocation settings. This task is more difficult than in standard distribution shift settings because of combinatorial interactions, where decisions depend on the joint presence of individuals in the allocation task. We show that the problem can be reformulated as a submodular optimization problem, enabling efficient approximations, to capture shifts both within and across instances of the optimization problem.

Details

ICAPS Conference 2024 Conference Paper

Improving Learnt Local MAPF Policies with Heuristic Search

Rishi Veerapaneni
Qian Wang
Kevin Ren
Arthur Jakobsson
Jiaoyang Li 0001
Maxim Likhachev

Multi-agent path finding (MAPF) is the problem of finding collision-free paths for a team of agents to reach their goal locations. State-of-the-art classical MAPF solvers typically employ heuristic search to find solutions for hundreds of agents but are typically centralized and can struggle to scale when run with short timeouts. Machine learning (ML) approaches that learn policies for each agent are appealing as these could enable decentralized systems and scale well while maintaining good solution quality. Current ML approaches to MAPF have proposed methods that have started to scratch the surface of this potential. However, state-of-the-art ML approaches produce ``local" policies that only plan for a single timestep and have poor success rates and scalability. Our main idea is that we can improve a ML local policy by using heuristic search methods on the output probability distribution to resolve deadlocks and enable full horizon planning. We show several model-agnostic ways to use heuristic search with learnt policies that significantly improve the policies

Details

JBHI Journal 2022 Journal Article

SC2Net: A Novel Segmentation-Based Classification Network for Detection of COVID-19 in Chest X-Ray Images

Huimin Zhao
Zhenyu Fang
Jinchang Ren
Calum MacLellan
Yong Xia
Shuo Li
Meijun Sun
Kevin Ren

The pandemic of COVID-19 has become a global crisis in public health, which has led to a massive number of deaths and severe economic degradation. To suppress the spread of COVID-19, accurate diagnosis at an early stage is crucial. As the popularly used real-time reverse transcriptase polymerase chain reaction (RT-PCR) swab test can be lengthy and inaccurate, chest screening with radiography imaging is still preferred. However, due to limited image data and the difficulty of the early-stage diagnosis, existing models suffer from ineffective feature extraction and poor network convergence and optimisation. To tackle these issues, a segmentation-based COVID-19 classification network, namely SC2Net, is proposed for effective detection of the COVID-19 from chest x-ray (CXR) images. The SC2Net consists of two subnets: a COVID-19 lung segmentation network (CLSeg), and a spatial attention network (SANet). In order to supress the interference from the background, the CLSeg is first applied to segment the lung region from the CXR. The segmented lung region is then fed to the SANet for classification and diagnosis of the COVID-19. As a shallow yet effective classifier, SANet takes the ResNet-18 as the feature extractor and enhances high-level feature via the proposed spatial attention module. For performance evaluation, the COVIDGR 1. 0 dataset is used, which is a high-quality dataset with various severity levels of the COVID-19. Experimental results have shown that, our SC2Net has an average accuracy of 84. 23% and an average F1 score of 81. 31% in detection of COVID-19, outperforming several state-of-the-art approaches.

Details DOI