Author name cluster

Kangjie Zhou

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

Discrepancy Algorithms for the Binary Perceptron

Shuangping Li
Tselil Schramm
Kangjie Zhou

The binary perceptron problem asks us to find a sign vector in the intersection of independently chosen random halfspaces with intercept −κ. We analyze the performance of the canonical discrepancy minimization algorithms of Lovett-Meka and Rothvoss/Eldan-Singh for the asymmetric binary perceptron problem. We obtain new algorithmic results in the κ = 0 case and in the large-|κ| case. In the κ → −∞ case, we additionally characterize the storage capacity and complement our algorithmic results with an almost-matching overlap-gap lower bound.

Details

ICML Conference 2025 Conference Paper

Implicit Bias of Gradient Descent for Non-Homogeneous Deep Networks

Yuhang Cai
Kangjie Zhou
Jingfeng Wu
Song Mei
Michael Lindsey
Peter L. Bartlett

We establish the asymptotic implicit bias of gradient descent (GD) for generic non-homogeneous deep networks under exponential loss. Specifically, we characterize three key properties of GD iterates starting from a sufficiently small empirical risk, where the threshold is determined by a measure of the network’s non-homogeneity. First, we show that a normalized margin induced by the GD iterates increases nearly monotonically. Second, we prove that while the norm of the GD iterates diverges to infinity, the iterates themselves converge in direction. Finally, we establish that this directional limit satisfies the Karush–Kuhn–Tucker (KKT) conditions of a margin maximization problem. Prior works on implicit bias have focused exclusively on homogeneous networks; in contrast, our results apply to a broad class of non-homogeneous networks satisfying a mild near-homogeneity condition. In particular, our results apply to networks with residual connections and non-homogeneous activation functions, thereby resolving an open problem posed byJi & Telgarsky (2020).

Details

ICRA Conference 2024 Conference Paper

ASPIRe: An Informative Trajectory Planner with Mutual Information Approximation for Target Search and Tracking

Kangjie Zhou
Pengying Wu
Yao Su 0001
Han Gao
Ji Ma 0007
Hangxin Liu
Chang Liu 0002

This paper proposes an informative trajectory planning approach, namely, adaptive particle filter tree with sigma point-based mutual information reward approximation (ASPIRe), for mobile target search and tracking (SAT) in cluttered environments with limited sensing field of view. We develop a novel sigma point-based approximation to accurately estimate mutual information (MI) for general, non-Gaussian distributions utilizing particle representation of the belief state, while simultaneously maintaining high computational efficiency. Building upon the MI approximation, we develop the Adaptive Particle Filter Tree (APFT) approach with MI as the reward, which features belief state tree nodes for informative trajectory planning in continuous state and measurement spaces. An adaptive criterion is proposed in APFT to adjust the planning horizon based on the expected information gain. Simulations and physical experiments demonstrate that ASPIRe achieves real-time computation and outperforms benchmark methods in terms of both search efficiency and estimation accuracy.

Details

JMLR Journal 2024 Journal Article

Sharp analysis of power iteration for tensor PCA

Yuchen Wu
Kangjie Zhou

We investigate the power iteration algorithm for the tensor PCA model introduced in Richard and Montanari (2014). Previous work studying the properties of tensor power iteration is either limited to a constant number of iterations, or requires a non-trivial data-independent initialization. In this paper, we move beyond these limitations and analyze the dynamics of randomly initialized tensor power iteration up to polynomially many steps. Our contributions are threefold: First, we establish sharp bounds on the number of iterations required for power method to converge to the planted signal, for a broad range of the signal-to-noise ratios. Second, our analysis reveals that the actual algorithmic threshold for power iteration is smaller than the one conjectured in the literature by a $\mathrm{polylog}(n)$ factor, where $n$ is the ambient dimension. Finally, we propose a simple and effective stopping criterion for power iteration, which provably outputs a solution that is highly correlated with the true signal. Extensive numerical experiments verify our theoretical results. [abs] [ pdf ][ bib ] &copy JMLR 2024. ( edit, beta )

PDF Details

IROS Conference 2024 Conference Paper

SwarmPRM: Probabilistic Roadmap Motion Planning for Large-Scale Swarm Robotic Systems

Yunze Hu
Xuru Yang
Kangjie Zhou
Qinghang Liu
Kang Ding
Han Gao
Pingping Zhu
Chang Liu

Large-scale swarm robotic systems consisting of numerous cooperative agents show considerable promise for performing autonomous tasks across various sectors. Nonetheless, traditional motion planning approaches often face a trade-off between scalability and solution quality due to the exponential growth of the joint state space of robots. In response, this work proposes SwarmPRM, a hierarchical, scalable, computationally efficient, and risk-aware sampling-based motion planning approach for large-scale swarm robots. SwarmPRM utilizes a Gaussian Mixture Model (GMM) to represent the swarm’s macroscopic state and constructs a Probabilistic Roadmap in Gaussian space, referred to as the Gaussian roadmap, to generate a transport trajectory of GMM. This trajectory is then followed by each robot at the microscopic stage. To enhance trajectory safety, SwarmPRM incorporates the conditional value-at-risk (CVaR) in the collision checking process to impart the property of risk awareness to the constructed Gaussian roadmap. SwarmPRM then crafts a linear programming formulation to compute the optimal GMM transport trajectory within this roadmap. Extensive simulations demonstrate that SwarmPRM outperforms state-of-the-art methods in computational efficiency, scalability, and trajectory quality while offering the capability to adjust the risk tolerance of generated trajectories.

Details