Publications
List of my publications and preprints
Journal and Preprints
- On the Convergence, Implicit Bias and Edge of Stability of Gradient Descent in Deep LearningH. Min, L. MacDonald, and R. VidalIEEE Signal Processing Magazine (IEEE SPM), 2026 Abs Bib PDF
Deep neural networks (DNNs) trained via gradient descent (GD) with random initialization and without any regularization enjoy good generalization performance in practice despite being highly overparametrized. To theoretically understand this puzzling phenomenon, many works on convergence analysis for GD algorithms on NNs have been developed over the last half-decade. In this article, we review these research efforts and discuss how they address three specific questions related to this puzzle. The first question is why GD finds a global minimum efficiently, which the literature has addressed by studying what level of overparametrization (width, depth, etc.) and what type of initialization lead to a benign optimization landscape along the training trajectory, facilitating a linear convergence rate of GD. The next question is why the global minimum found by GD generalizes well, which has been addressed by showing that overparametrization induces an implicit simplicity bias along the GD trajectory. More recently, it has been observed that in practice, training DNNs with far larger learning rates than theoretically permissible results in faster convergence and better generalization. This leads to the third question of why faster convergence and better generalization can be achieved with a large learning rate, which has been recently addressed by identifying a self-stabilization mechanism and implicit bias toward flat minima.
@article{mmv26spm, title = {On the Convergence, Implicit Bias and Edge of Stability of Gradient Descent in Deep Learning}, author = {Min, Hancheng and MacDonald, Lachlan E. and Vidal, Ren\'e}, journal = {IEEE Signal Processing Magazine (IEEE SPM)}, year = {2026}, volume = {43}, number = {3}, pages = {37-51}, recent = {true} } - A Local Polyak-łOjasiewicz and Descent Lemma of Gradient Descent for Overparameterized Linear ModelsZ. Xu, H. Min, S. Tarmoun, E. Mallada, and R. VidalTransactions on Machine Learning Research (TMLR), 2025 Abs arXiv PDF
Most prior work on the convergence of gradient descent (GD) for overparameterized neural networks relies on strong assumptions on the step size (infinitesimal), the hidden-layer width (infinite), or the initialization (large, spectral, balanced). Recent efforts to relax these assumptions focus on two-layer linear networks trained with the squared loss. In this work, we derive a linear convergence rate for training two-layer linear neural networks with GD for general losses and under relaxed assumptions on the step size, width, and initialization. A key challenge in deriving this result is that classical ingredients for deriving convergence rates for nonconvex problems, such as the Polyak-Łojasiewicz (PL) condition and Descent Lemma, do not hold globally for overparameterized neural networks. Here, we prove that these two conditions hold locally with local constants that depend on the weights. Then, we provide bounds on these local constants, which depend on the initialization of the weights, the current loss, and the global PL and smoothness constants of the non-overparameterized model. Based on these bounds, we derive a linear convergence rate for GD. Our convergence analysis not only improves upon prior results but also suggests a better choice for the step size, as verified through our numerical experiments.
- A Frequency Domain Analysis of Slow Coherency in Networked SystemsH. Min, R. Pates, and E. MalladaAutomatica, 2025 Abs arXiv Bib 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.
@article{mpm2025aut, title = {A Frequency Domain Analysis of Slow Coherency in Networked Systems}, author = {Min, Hancheng and Pates, Richard and Mallada, Enrique}, journal = {Automatica}, volume = {174}, pages = {112184}, year = {2025}, } - Oscillations-aware Frequency Security Assessment via Efficient Worst-case Frequency Nadir ComputationElectric Power Systems Research (EPSR), 2024 Abs arXiv Bib 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 oscillations-aware frequency security assessment without conducting exhaustive simulations and intractable analysis.
@article{jmz2024pscc, title = {Oscillations-aware Frequency Security Assessment via Efficient Worst-case Frequency Nadir Computation}, author = {Jiang, Yan and Min, Hancheng and Zhang, Baosen}, journal = {Electric Power Systems Research ({EPSR})}, volume = {234}, pages = {110656}, year = {2024}, } - Learning to Act Safely with Limited Exposure and Almost Sure CertaintyIEEE Transactions on Automatic Control (TAC), 2023 Abs Bib 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.
@article{cmbm2021tac, title = {Learning to Act Safely with Limited Exposure and Almost Sure Certainty}, author = {Castellano, Agustin and Min, Hancheng and Bazerque, Juan and Mallada, Enrique}, journal = {IEEE Transactions on Automatic Control ({TAC})}, volume = {68}, pages = {2979-2994}, year = {2023}, doi = {10.1109/TAC.2023.3240925} } - Convergence and Implicit Bias of Gradient Flow on Overparametrized Linear NetworksH. Min, S. Tarmoun, R. Vidal, and E. Mallada
- Accurate Reduced Order Models for Coherent Heterogeneous GeneratorsH. Min, F. Paganini, and E. MalladaIEEE Control Systems Letters (L-CSS), 2021 Abs arXiv Bib PDF Slides
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.
@article{mpm2021lcss, title = {Accurate Reduced Order Models for Coherent Heterogeneous Generators}, author = {Min, Hancheng and Paganini, Fernando and Mallada, Enrique}, journal = {IEEE Control Systems Letters ({L-CSS})}, volume = {5}, pages = {1741-1746}, year = {2021}, doi = {10.1109/LCSYS.2020.3043733} }
Conference
- Transformers Learn the Optimal DDPM Denoiser for Multi-Token GMMsH. Li, H. Min, and R. VidalInternational Conference on Machine Learning (ICML), Jul 2026 Abs arXiv Bib PDF
Transformer-based diffusion models have demonstrated remarkable performance at generating high-quality samples. However, our theoretical understanding of the reasons for this success remains limited. For instance, existing models are typically trained by minimizing a denoising objective, which is equivalent to fitting the score function of the training data. However, we do not know why transformer-based models can match the score function for denoising, or why gradient-based methods converge to the optimal denoising model despite the non-convex loss landscape. To the best of our knowledge, this paper provides the first convergence analysis for training transformer-based diffusion models. More specifically, we consider the population Denoising Diffusion Probabilistic Model (DDPM) objective for denoising data that follow a multi-token Gaussian mixture distribution. We theoretically quantify the required number of tokens per data point and training iterations for the global convergence towards the Bayes optimal risk of the denoising objective, thereby achieving a desired score matching error. A deeper investigation reveals that the self-attention module of the trained transformer implements a mean denoising mechanism that enables the trained model to approximate the oracle Minimum Mean Squared Error (MMSE) estimator of the injected noise in the diffusion steps. Numerical experiments validate these findings.
@inproceedings{lmv26icml, title = {Transformers Learn the Optimal {DDPM} Denoiser for Multi-Token {GMM}s}, author = {Li, Hongkang and Min, Hancheng and Vidal, Ren\'e}, booktitle = {International Conference on Machine Learning ({ICML})}, year = {2026}, month = jul, recent = {true}, } - Neural Collapse under Gradient Flow on Shallow ReLU Networks for Orthogonally Separable DataConference on Neural Information Processing Systems (NeurIPS), Jul 2025 Abs arXiv Bib PDF Poster
Among many mysteries behind the success of deep networks lies the exceptional discriminative power of their learned representations as manifested by the intriguing Neural Collapse (NC) phenomenon, where simple feature structures emerge in the last layer of a trained neural network. Prior work on understanding NC theoretically has focused on analyzing the optimization landscape of matrix-factorization-like problems by considering the last-layer features as unconstrained free optimization variables and showing that their global minima exhibit NC. In this paper, we show that gradient flow on a two-layer ReLU network for classifying orthogonally separable data provably exhibits NC, thereby advancing prior results in two ways: First, we relax the assumption of unconstrained features, showing the effect of data structure and nonlinear activations on NC characterizations. Second, we reveal the role of the implicit bias of the training dynamics in facilitating the emergence of NC.
@inproceedings{mzv2025neurips, title = {Neural Collapse under Gradient Flow on Shallow ReLU Networks for Orthogonally Separable Data}, author = {Min, Hancheng and Zhu, Zhihui and Vidal, Ren\'e}, booktitle = {Conference on Neural Information Processing Systems (NeurIPS)}, year = {2025}, recent = {true}, } - Convergence Rates for Gradient Descent on the Edge of Stability for Overparametrised Least SquaresL. MacDonald, L. Palma, Z. Xu, H. Min, S. Tarmoun, and R. VidalConference on Neural Information Processing Systems (NeurIPS), Jul 2025 Abs arXiv Bib
Classical optimisation theory guarantees monotonic objective decrease for gradient descent (GD) when employed in a small step size, or "stable", regime. In contrast, gradient descent on neural networks is frequently performed in a large step size regime called the "edge of stability", in which the objective decreases non-monotonically with an observed implicit bias towards flat minima. In this paper, we take a step toward quantifying this phenomenon by providing convergence rates for gradient descent with large learning rates in an overparametrised least squares setting. The key insight behind our analysis is that, as a consequence of overparametrisation, the set of global minimisers forms a Riemannian manifold M, which enables the decomposition of the GD dynamics into components parallel and orthogonal to M. The parallel component corresponds to Riemannian gradient descent on the objective sharpness, while the orthogonal component corresponds to a quadratic dynamical system. This insight allows us to derive rates in three regimes characterised by the learning rate size: the subcritical regime, in which transient instability is overcome in finite time before linear convergence to a suboptimally flat global minimum; the critical regime, in which instability persists for all time with a power-law convergence toward the optimally flat global minimum; the supercritical regime, in which instability persists for all time with linear convergence to an oscillation of period two centred on the optimally flat global minimum.
@inproceedings{mpxmtv2025neurips, title = {Convergence Rates for Gradient Descent on the Edge of Stability for Overparametrised Least Squares}, author = {MacDonald, Lachlan E. and Palma, Leandro and Xu, Ziqing and Min, Hancheng and Tarmoun, Salma and Vidal, Ren\'e}, booktitle = {Conference on Neural Information Processing Systems (NeurIPS)}, year = {2025}, } - Understanding Incremental Learning with Closed-form Solution to Gradient Flow on Overparamerterized Matrix FactorizationH. Min, and R. VidalIEEE Conference on Decision and Control (CDC), Jul 2025 Abs arXiv Bib PDF Slides
Many theoretical studies on neural networks attribute their excellent empirical performance to the implicit bias or regularization induced by first-order optimization algorithms when training networks under certain initialization assumptions. One example is the incremental learning phenomenon in gradient flow (GF) on an overparamerterized matrix factorization problem with small initialization: GF learns a target matrix by sequentially learning its singular values in decreasing order of magnitude over time. In this paper, we develop a quantitative understanding of this incremental learning behavior for GF on the symmetric matrix factorization problem, using its closed-form solution obtained by solving a Riccati-like matrix differential equation. We show that incremental learning emerges from some time-scale separation among dynamics corresponding to learning different components in the target matrix. By decreasing the initialization scale, these time-scale separations become more prominent, allowing one to find low-rank approximations of the target matrix. Lastly, we discuss the possible avenues for extending this analysis to asymmetric matrix factorization problems.
@inproceedings{mv2025cdc, title = {Understanding Incremental Learning with Closed-form Solution to Gradient Flow on Overparamerterized Matrix Factorization}, author = {Min, Hancheng and Vidal, Ren\'e}, booktitle = {IEEE Conference on Decision and Control ({CDC})}, year = {2025}, } - Voyaging into Perpetual Dynamic Scenes from a Single ViewIEEE International Conference on Computer Vision (ICCV), Jul 2025 Abs arXiv Bib PDF Code Website
The problem of generating a perpetual dynamic scene from a single view is an important problem with widespread applications in augmented and virtual reality, and robotics. However, since dynamic scenes regularly change over time, a key challenge is to ensure that different generated views be consistent with the underlying 3D motions. Prior work learns such consistency by training on multiple views, but the generated scene regions often interpolate between training views and fail to generate perpetual views. To address this issue, we propose \ourframework, which reformulates dynamic scene generation as a scene outpainting problem with new dynamic content. As 2D outpainting models struggle at generating 3D consistent motions from a single 2D view, we enrich 2D pixels with information from their 3D rays that facilitates learning of 3D motion consistency. More specifically, we first map the single-view video input to a dynamic point cloud using the estimated video depths. We then render a partial video of the point cloud from a novel view and outpaint the missing regions using ray information (e.g., the distance from a ray to the point cloud) to generate 3D consistent motions. Next, we use the outpainted video to update the point cloud, which is used for outpainting the scene from future novel views. Moreover, we can control the generated content with the input text prompt. Experiments show that our model can generate perpetual scenes with consistent motions along fly-through cameras.
@inproceedings{tdlmv2025iccv, title = {Voyaging into Perpetual Dynamic Scenes from a Single View}, author = {Tian, Fengrui and Ding, Tianjiao and Luo, Jinqi and Min, Hancheng and Vidal, Ren\'e}, booktitle = {IEEE International Conference on Computer Vision ({ICCV})}, year = {2025}, } - Gradient Flow Provably Learns Robust Classifiers for Orthonormal GMMsH. Min, and R. VidalInternational Conference on Machine Learning (ICML), Jul 2025 Abs Bib PDF Poster
Deep learning-based classifiers are known to be vulnerable to adversarial attacks. Existing methods for defending against such attacks require adding a defense mechanism or modifying the learning procedure (e.g., by adding adversarial examples). This paper shows that for certain data distributions one can learn a provably robust classifier using standard learning methods and without adding a defense mechanism. More specifically, this paper addresses the problem of finding a robust classifier for a binary classification problem in which the data comes from an isotropic mixture of Gaussians with orthonormal cluster centers. First, we characterize the largest \ell_2-attack any classifier can defend against while maintaining high accuracy, and show the existence of optimal robust classifiers achieving this maximum \ell_2-robustness. Next, we show that given data sampled from the orthonormal Gaussian mixture model, gradient flow on a two-layer network with a polynomial ReLU activation and without adversarial examples provably finds an optimal robust classifier.
@inproceedings{mv2025icml, title = {Gradient Flow Provably Learns Robust Classifiers for Orthonormal GMMs}, author = {Min, Hancheng and Vidal, Ren\'e}, booktitle = {International Conference on Machine Learning ({ICML})}, pages = {1--8}, year = {2025}, recent = {true}, } - Concept Lancet: Image Editing with Compositional Representation TransplantIEEE\CVF Conference on Computer Vision and Pattern Recognition (CVPR), Jul 2025 Abs arXiv Bib PDF Code Website
Diffusion models are widely used for image editing tasks. Existing editing methods often design a representation manipulation procedure (e.g., Cat -> Dog, Sketch -> Painting) by curating an edit direction in the text embedding or score space. However, such a procedure faces a key challenge: overestimating the edit strength harms visual consistency while underestimating it fails the editing task. Notably, each source image may require a different editing strength, and it is costly to search for an appropriate strength via trial-and-error. To address this challenge, we propose ConceptLancent (CoLan), a zero-shot plug-and-play framework for principled representation manipulation in diffusion-based image editing. At inference time, we decompose the source input in the latent (text embedding or diffusion score) space as a sparse linear combination of the representations of the collected visual concepts and phrases. This allows us to accurately estimate the presence of concepts in each image, which informs the edit. Based on the editing task (replace, add, or remove), we perform a customized concept transplant process to impose the corresponding editing direction. To sufficiently model the concept space, we curate a conceptual representation dataset, CoLan 150k, which contains diverse descriptions and scenarios of visual concepts and phrases for the latent dictionary. Experiments on multiple diffusion-based image editing baselines show that methods equipped with CoLan achieve state-of-the-art performance in editing effectiveness and consistency preservation.
@inproceedings{ldcmcv2025cvpr, title = {Concept Lancet: Image Editing with Compositional Representation Transplant}, author = {Luo, Jinqi and Ding, Tianjiao and Chan, Kwan Ho Ryan and Min, Hancheng and Callison-Burch, Chris and Vidal, Ren\'e}, year = {2025}, booktitle = {IEEE\CVF Conference on Computer Vision and Pattern Recognition ({CVPR})}, } - Understanding the Learning Dynamics of LoRA: A Gradient Flow Perspective on Low-Rank Adaptation in Matrix FactorizationInternational Conference on Artificial Intelligence and Statistics (AISTATS), Jul 2025 Abs arXiv Bib PDF
Despite Low-Rank Adaptation’s (LoRA) empirical success in fine-tuning pretrained models, there is little theoretical understanding of how first-order methods with carefully crafted initialization adapt models to new tasks. In this work, we take the first step towards bridging this gap by theoretically analyzing the learning dynamics of LoRA for matrix factorization (MF) under gradient flow (GF), emphasizing the crucial role of initialization. For small initialization, we theoretically show that GF converges to a neighborhood of the optimal solution, with smaller initialization leading to lower final error. Our analysis shows that the final error is affected by the misalignment between the singular spaces of the model and the target matrix, and reducing the initialization scale improves alignment. To address this misalignment, we propose a spectral initialization for LoRA in MF and theoretically prove that GF with small spectral initialization can converge to the target matrix with arbitrary precision. Numerical experiments from MF and image classification validate our findings.
@inproceedings{xmlmtmv2025aistats, title = {Understanding the Learning Dynamics of LoRA: A Gradient Flow Perspective on Low-Rank Adaptation in Matrix Factorization}, author = {Xu, Ziqing and Min, Hancheng and Luo, Jinqi and MacDonald, Lachlan Ewen and Tarmoun, Salma and Mallada, Enrique and Vidal, Ren\'e}, booktitle = {International Conference on Artificial Intelligence and Statistics ({AISTATS})}, year = {2025}, } - Can Implicit Bias Imply Adversarial Robustness?H. Min, and R. VidalInternational Conference on Machine Learning (ICML), Jul 2024 Abs arXiv Bib PDF Poster
The implicit bias of gradient-based training algorithms has been considered mostly beneficial as it leads to trained networks that often generalize well. However, Frei et al. (2023) show that such implicit bias can harm adversarial robustness. Specifically, they show that if 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. Moreover, this phenomenon occurs 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.
@inproceedings{mv2024icml, title = {Can Implicit Bias Imply Adversarial Robustness?}, author = {Min, Hancheng and Vidal, Ren\'e}, booktitle = {International Conference on Machine Learning ({ICML})}, pages = {35687--35718}, year = {2024}, volume = {235}, } - Early Neuron Alignment in Two-layer ReLU Networks with Small InitializationH. Min, E. Mallada, and R. VidalInternational Conference on Learning Representations (ICLR), Jul 2024 Abs arXiv Bib PDF Poster Slides
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.
@inproceedings{mmv2024iclr, title = {Early Neuron Alignment in Two-layer ReLU Networks with Small Initialization}, author = {Min, Hancheng and Mallada, Enrique and Vidal, Ren\'e}, year = {2024}, booktitle = {International Conference on Learning Representations ({ICLR})}, pages = {1-8}, } - On the Convergence of Gradient Flow on Multi-layer Linear ModelsH. Min, R. Vidal, and E. MalladaInternational Conference on Machine Learning (ICML), Jul 2023 Abs Bib PDF Poster Slides
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.
@inproceedings{mvm2023icml, title = {On the Convergence of Gradient Flow on Multi-layer Linear Models}, author = {Min, Hancheng and Vidal, Ren\'e and Mallada, Enrique}, booktitle = {International Conference on Machine Learning ({ICML})}, pages = {24850--24887}, year = {2023}, volume = {202}, } - Linear Convergence of Gradient Descent For Finite Width Over-parametrized Linear Networks With General InitializationZ. Xu, H. Min, S. Tarmoun, E. Mallada, and R. VidalInternational Conference on Artificial Intelligence and Statistics (AISTATS), Jul 2023 Abs Bib PDF Slides
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.
@inproceedings{xu2023aistat, title = {Linear Convergence of Gradient Descent For Finite Width Over-parametrized Linear Networks With General Initialization}, author = {Xu, Ziqing and Min, Hancheng and Tarmoun, Salma and Mallada, Enrique and Vidal, Ren\'e}, booktitle = {International Conference on Artificial Intelligence and Statistics ({AISTATS})}, pages = {2262--2284}, year = {2023}, volume = {206}, } - Learning Coherent Clusters in Weakly-Connected Network SystemsH. Min, and E. MalladaLearning for Dynamics and Control Conference (L4DC), Jul 2023 Abs arXiv Bib PDF Poster
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.
@inproceedings{mm2023l4dc, title = {Learning Coherent Clusters in Weakly-Connected Network Systems}, author = {Min, Hancheng and Mallada, Enrique}, booktitle = {Learning for Dynamics and Control Conference ({L4DC})}, pages = {1167--1179}, year = {2023}, volume = {211}, } - Spectral Clustering and Model Reduction for Weakly-connected Coherent Network SystemsH. Min, and E. MalladaAmerican Control Conference (ACC), Jul 2023 Abs arXiv Bib PDF Slides
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.
@inproceedings{mm2023acc, title = {Spectral Clustering and Model Reduction for Weakly-connected Coherent Network Systems}, author = {Min, Hancheng and Mallada, Enrique}, booktitle = {American Control Conference ({ACC})}, pages = {2957-2962}, year = {2023}, doi = {10.23919/ACC55779.2023.10156212} } - Learning Safety Critics via a Non-Contractive Binary Bellman Operator2023 57th Asilomar Conference on Signals, Systems, and Computers (ACSSC), Jul 2023 Bib
@inproceedings{cmbm2023acssc, author = {Castellano, Agustin and Min, Hancheng and Bazerque, Juan Andrés and Mallada, Enrique}, booktitle = {2023 57th Asilomar Conference on Signals, Systems, and Computers ({ACSSC})}, title = {Learning Safety Critics via a Non-Contractive Binary Bellman Operator}, year = {2023}, pages = {814-821}, doi = {10.1109/IEEECONF59524.2023.10476995} } - Reinforcement Learning with Almost Sure ConstraintsLearning for Dynamics and Control Conference (L4DC), Jul 2022 Abs Bib 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.
@inproceedings{cmbm2022l4dc, title = {Reinforcement Learning with Almost Sure Constraints}, author = {Castellano, Agustin and Min, Hancheng and Bazerque, Juan Andr\'es and Mallada, Enrique}, booktitle = {Learning for Dynamics and Control Conference ({L4DC})}, pages = {559--570}, year = {2022}, volume = {168}, } - On the Explicit Role of Initialization on the Convergence and Implicit Bias of Overparametrized Linear NetworksH. Min, S. Tarmoun, R. Vidal, and E. MalladaInternational Conference on Machine Learning (ICML), Jul 2021 Abs Bib PDF Poster Slides
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.
@inproceedings{mtvm2021icml, title = {On the Explicit Role of Initialization on the Convergence and Implicit Bias of Overparametrized Linear Networks}, author = {Min, Hancheng and Tarmoun, Salma and Vidal, Ren\'e and Mallada, Enrique}, booktitle = {International Conference on Machine Learning ({ICML})}, pages = {7760--7768}, year = {2021}, volume = {139}, } - Dynamics Concentration of Tightly-Connected Large-Scale NetworksH. Min, and E. MalladaIEEE Conference on Decision and Control (CDC), Jul 2019 Abs arXiv Bib PDF Slides
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.
@inproceedings{mm2019cdc, title = {Dynamics Concentration of Tightly-Connected Large-Scale Networks}, author = {Min, Hancheng and Mallada, Enrique}, booktitle = {IEEE Conference on Decision and Control ({CDC})}, pages = {758-763}, year = {2019}, doi = {10.1109/CDC40024.2019.9029796} } - Voronoi-Based Coverage Control of Pan/Tilt/Zoom Camera NetworksO. Arslan, H. Min, and D. KoditschekIEEE International Conference on Robotics and Automation (ICRA), Jul 2018 Bib
@inproceedings{amk2018icra, title = {Voronoi-Based Coverage Control of Pan/Tilt/Zoom Camera Networks}, author = {Arslan, O. and Min, H. and Koditschek, D. E.}, booktitle = {IEEE International Conference on Robotics and Automation ({ICRA})}, pages = {5062-5069}, year = {2018}, }
Thesis
- Exploiting Structural Properties in the Analysis of High-dimensional Dynamical SystemsH. MinPh.D. Thesis, Johns Hopkins University, 2023
- On Balancing Event and Area Coverage in Mobile Sensor NetworksH. MinMaster’s Thesis, University of Pennsylvania, 2018