Publications | Hancheng Min

Journal and Preprints

A Frequency Domain Analysis of Slow Coherency in Networked Systems

Hancheng Min, Richard Pates, and Enrique Mallada

Automatica, 2023

submitted, under revision

Abs arXiv PDF

Network coherence generally refers to the emergence of simple aggregated dynamical behaviours, despite heterogeneity in the dynamics of the subsystems that constitute the network. In this paper, we develop a general frequency domain framework to analyze and quantify the level of network coherence that a system exhibits by relating coherence with a low-rank property of the system’s input-output response. More precisely, for a networked system with linear dynamics and coupling, we show that, as the network’s \empheffective algebraic connectivity grows, the system transfer matrix converges to a rank-one transfer matrix representing the coherent behavior. Interestingly, the non-zero eigenvalue of such a rank-one matrix is given by the harmonic mean of individual nodal dynamics, and we refer to it as the coherent dynamics. Our analysis unveils the frequency-dependent nature of coherence and a non-trivial interplay between dynamics and network topology. We further show that many networked systems can exhibit similar coherent behavior by establishing a concentration result in a setting with randomly chosen individual nodal dynamics.
Learning to Act Safely with Limited Exposure and Almost Sure Certainty

Agustin Castellano, Hancheng Min, Juan Bazerque, and Enrique Mallada

IEEE Transaction on Automatic Control, May 2023

Abs PDF

This paper aims to put forward the concept that learning to take safe actions in unknown environments, even with probability one guarantees, can be achieved without the need for an unbounded number of exploratory trials, provided that one is willing to navigate trade-offs between optimality, level of exposure to unsafe events, and the maximum detection time of unsafe actions. We illustrate this concept in two complementary settings. We first focus on the canonical multi-armed bandit problem and seek to study the intrinsic trade-offs of learning safety in the presence of uncertainty. Under mild assumptions on sufficient exploration, we provide an algorithm that provably detects all unsafe machines in an (expected) finite number of rounds. The analysis also unveils a trade-off between the number of rounds needed to secure the environment and the probability of discarding safe machines. We then consider the problem of finding optimal policies for a Markov Decision Process (MDP) with almost sure constraints. We show that the (action) value function satisfies a barrier-based decomposition which allows for the identification of feasible policies independently of the reward process. Using this decomposition, we develop a Barrier-learning algorithm, that identifies such unsafe state-action pairs in a finite expected number of steps. Our analysis further highlights a trade-off between the time lag for the underlying MDP necessary to detect unsafe actions, and the level of exposure to unsafe events. Simulations corroborate our theoretical findings, further illustrating the aforementioned trade-offs, and suggesting that safety constraints can further speed up the learning process.
Convergence and Implicit Bias of Gradient Flow on Overparametrized Linear Networks

Hancheng Min, Salma Tarmoun, René Vidal, and Enrique Mallada

Journal of Machine Learning Research, May 2023

in preparation

arXiv PDF
Accurate Reduced Order Models for Coherent Heterogeneous Generators

Hancheng Min, Fernando Paganini, and Enrique Mallada

IEEE Control Systems Letters (L-CSS), Nov 2021

also in ACC 2021

Abs arXiv PDF

We introduce a novel framework to approximate the aggregate frequency dynamics of coherent synchronous generators. By leveraging recent results on dynamics concentration of tightly connected networks, we develop a hierarchy of reduced order models –based on frequency weighted balanced truncation– that accurately approximate the aggregate system response. Our results outperform existing aggregation techniques and can be shown to monotonically improve the approximation as the hierarchy order increases.

Conference

Can Implicit Bias Imply Adversarial Robustness?

Hancheng Min, and Rene Vidal

In Proceedings of the 41th International Conference on Machine Learning (ICML), Jul 2024

to appear

Abs

The implicit bias of gradient-based training algorithms has been considered mostly beneficial as it leads to trained networks that often generalize well. However, \citetfrei2023the show that such implicit bias can harm adversarial robustness. Specifically, when the data consists of clusters with small inter-cluster correlation, a shallow (two-layer) ReLU network trained by gradient flow generalizes well, but it is not robust to adversarial attacks of small radius, despite the existence of a much more robust classifier that can be explicitly constructed from a shallow network. In this paper, we extend recent analyses of neuron alignment to show that a shallow network with a polynomial ReLU activation (pReLU) trained by gradient flow not only generalizes well but is also robust to adversarial attacks. Our results highlight the importance of the interplay between data structure and architecture design in the implicit bias and robustness of trained networks.
Oscillations-Aware Frequency Security Assessment via Efficient Worst-Case Frequency Nadir Computation

Yan Jiang, Hancheng Min, and Baosen Zhang

In Power Systems Computation Conference, Jun 2024

to appear

Abs PDF

Frequency security assessment following major disturbances has long been one of the central tasks in power system operations. The standard approach is to study the center of inertia frequency, an aggregate signal for an entire system, to avoid analyzing the frequency signal at individual buses. However, as the amount of low-inertia renewable resources in a grid increases, the center of inertia frequency is becoming too coarse to provide reliable frequency security assessment. In this paper, we propose an efficient algorithm to determine the worst-case frequency nadir across all buses for bounded power disturbances, as well as identify the power disturbances leading to that severest scenario. The proposed algorithm allows oscillation-aware frequency security assessment without conducting exhaustive simulations and intractable analysis.
Early Neuron Alignment in Two-layer ReLU Networks with Small Initialization

Hancheng Min, Enrique Mallada, and René Vidal

In International Conference on Learning Representations (ICLR), May 2024

to appear

Abs arXiv PDF

This paper studies the problem of training a two-layer ReLU network for binary classification using gradient flow with small initialization. We consider a training dataset with well-separated input vectors: Any pair of input data with the same label are positively correlated, and any pair with different labels are negatively correlated. Our analysis shows that, during the early phase of training, neurons in the first layer try to align with either the positive data or the negative data, depending on its corresponding weight on the second layer. A careful analysis of the neurons’ directional dynamics allows us to provide an \mathcalO(\frac\log n\sqrtμ) upper bound on the time it takes for all neurons to achieve good alignment with the input data, where n is the number of data points and μmeasures how well the data are separated. After the early alignment phase, the loss converges to zero at a \mathcalO(\frac1t) rate, and the weight matrix on the first layer is approximately low-rank. Numerical experiments on the MNIST dataset illustrate our theoretical findings.
On the Convergence of Gradient Flow on Multi-layer Linear Models

Hancheng Min, René Vidal, and Enrique Mallada

In The 40th International Conference on Machine Learning (ICML), Jul 2023

Abs PDF

In this paper, we analyze the convergence of gradient flow on a multi-layer linear model with a loss function of the form f(W_1W_2⋯W_L). We show that when f satisfies the gradient dominance property, proper weight initialization leads to exponential convergence of the gradient flow to a global minimum of the loss. Moreover, the convergence rate depends on two trajectory-specific quantities that are controlled by the weight initialization: the imbalance matrices, which measure the difference between the weights of adjacent layers, and the least singular value of the weight product W=W_1W_2⋯W_L. Our analysis exploits the fact that the gradient of the overparameterized loss can be written as the composition of the non-overparametrized gradient with a time-varying (weight-dependent) linear operator whose smallest eigenvalue controls the convergence rate. The key challenge we address is to derive a uniform lower bound for this time-varying eigenvalue that lead to improved rates for several multi-layer network models studied in the literature.
Linear Convergence of Gradient Descent For Finite Width Over-parametrized Linear Networks With General Initialization

Ziqing Xu, Hancheng Min, Salma Tarmoun, Enrique Mallada, and Rene Vidal

In Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, Apr 2023

Abs PDF

Recent theoretical analyses of the convergence of gradient descent (GD) to a global minimum for over-parametrized neural networks make strong assumptions on the step size (infinitesimal), the hidden-layer width (infinite), or the initialization (spectral, balanced). In this work, we relax these assumptions and derive a linear convergence rate for two-layer linear networks trained using GD on the squared loss in the case of finite step size, finite width and general initialization. Despite the generality of our analysis, our rate estimates are significantly tighter than those of prior work. Moreover, we provide a time-varying step size rule that monotonically improves the convergence rate as the loss function decreases to zero. Numerical experiments validate our findings.
Learning Coherent Clusters in Weakly-Connected Network Systems

Hancheng Min, and Enrique Mallada

In Proceedings of The 5th Annual Learning for Dynamics and Control Conference, Jun 2023

Abs arXiv PDF

We propose a structure-preserving model-reduction methodology for large-scale dynamic networks with tightly-connected components. First, the coherent groups are identified by a spectral clustering algorithm on the graph Laplacian matrix that models the network feedback. Then, a reduced network is built, where each node represents the aggregate dynamics of each coherent group, and the reduced network captures the dynamic coupling between the groups. We provide an upper bound on the approximation error when the network graph is randomly generated from a weight stochastic block model. Finally, numerical experiments align with and validate our theoretical findings.
Spectral clustering and model reduction for weakly-connected coherent network systems

Hancheng Min, and Enrique Mallada

In 2023 American Control Conference (ACC), Jun 2023

Abs arXiv PDF

We propose a novel model-reduction methodology for large-scale dynamic networks with tightly-connected components. First, the coherent groups are identified by a spectral clustering algorithm on the graph Laplacian matrix that models the network feedback. Then, a reduced network is built, where each node represents the aggregate dynamics of each coherent group, and the reduced network captures the dynamic coupling between the groups. Our approach is theoretically justified under a random graph setting. Finally, numerical experiments align with and validate our theoretical findings.
Reinforcement Learning with Almost Sure Constraints

Agustin Castellano, Hancheng Min, Juan Andrés Bazerque, and Enrique Mallada

In The 4th Annual Learning for Dynamics and Control Conference, Jun 2022

Abs PDF

In this work we address the problem of finding feasible policies for Constrained Markov Decision Processes under probability one constraints. We argue that stationary policies are not sufficient for solving this problem, and that a rich class of policies can be found by endowing the controller with a scalar quantity, so called budget, that tracks how close the agent is to violating the constraint. We show that the minimal budget required to act safely can be obtained as the smallest fixed point of a Bellman-like operator, for which we analyze its convergence properties. We also show how to learn this quantity when the true kernel of the Markov decision process is not known, while providing sample-complexity bounds. The utility of knowing this minimal budget relies in that it can aid in the search of optimal or near-optimal policies by shrinking down the region of the state space the agent must navigate. Simulations illustrate the different nature of probability one constraints against the typically used constraints in expectation.
On the Explicit Role of Initialization on the Convergence and Implicit Bias of Overparametrized Linear Networks

Hancheng Min, Salma Tarmoun, René Vidal, and Enrique Mallada

In The 38th International Conference on Machine Learning (ICML), Jul 2021

Abs PDF

Neural networks trained via gradient descent with random initialization and without any regularization enjoy good generalization performance in practice despite being highly overparametrized. A promising direction to explain this phenomenon is to study how initialization and overparametrization affect convergence and implicit bias of training algorithms. In this paper, we present a novel analysis of single-hidden-layer linear networks trained under gradient flow, which connects initialization, optimization, and overparametrization. Firstly, we show that the squared loss converges exponentially to its optimum at a rate that depends on the level of imbalance of the initialization. Secondly, we show that proper initialization constrains the dynamics of the network parameters to lie within an invariant set. In turn, minimizing the loss over this set leads to the min-norm solution. Finally, we show that large hidden layer width, together with (properly scaled) random initialization, ensures proximity to such an invariant set during training, allowing us to derive a novel non-asymptotic upper-bound on the distance between the trained network and the min-norm solution.
Dynamics Concentration of Tightly-Connected Large-Scale Networks

Hancheng Min, and Enrique Mallada

In 58th IEEE Conference on Decision and Control (CDC), Dec 2019

Abs arXiv PDF

The ability to achieve coordinated behavior –engineered or emergent– on networked systems has attracted widespread interest over several fields. This has led to remarkable advances on the development of a theoretical understanding of the conditions under which agents within a network can reach agreement (consensus) or develop coordinated behaviors such as synchronization. However, fewer advances have been made toward explaining another commonly observed phenomena in tightly-connected networks systems: output responses of nodes in the networks are almost identical to each other despite heterogeneity in their individual dynamics. In this paper, we leverage tools from high-dimensional probability to provide an initial answer to this phenomena. More precisely, we show that for linear networks of nodal random transfer functions, as the networks size and connectivity grows, every node in the network follows the same response to an input or disturbance – irrespectively of the source of this input. We term this behavior as dynamics concentration as it stems from the fact that the network transfer matrix uniformly converges in probability to a unique dynamic response –i.e., it concentrates– determined by the distribution of the random transfer function of each node. We further discuss the implications of our analysis in the context of model reduction and robustness, and provide numerical evidence that similar phenomena occur in small deterministic networks over a properly defined frequency band.
Voronoi-Based Coverage Control of Pan/Tilt/Zoom Camera Networks

O. Arslan, H. Min, and D. E. Koditschek

In 2018 IEEE International Conference on Robotics and Automation (ICRA), May 2018

PDF