Year: 2024

@inproceedings{zlym2024cdc,
  abstract = {Gradient Descent Ascent (GDA) methods for min-max optimization problems typically produce oscillatory behavior that can lead to instability, e.g., in bilinear settings.
To address this problem, we introduce a dissipation term into the GDA updates to dampen these oscillations. The proposed Dissipative GDA (DGDA) method can be seen as performing standard GDA on a state-augmented and regularized saddle function that does not strictly introduce additional convexity/concavity. We theoretically show the linear convergence of DGDA in the bilinear and strongly convex-strongly concave settings and assess its performance by comparing DGDA with other methods such as GDA, Extra-Gradient (EG), and Optimistic GDA.
Our findings demonstrate that DGDA surpasses these methods, achieving superior convergence rates. We support our claims with two numerical examples that showcase DGDA's effectiveness in solving saddle point problems.},
  author = {Zheng, Tianqi and Loizou, Nicolas and You, Pengcheng and Mallada, Enrique},
  booktitle = {63rd IEEE Conference on Decision and Control (CDC)},
  grants = {CPS-2136324, Global-Centers-2330450},
  month = {12},
  note = {also in L-CSS},
  pubstate = {presented},
  record = {accepted Jul 2024, submitted Mar 2024},
  title = {Dissipative Gradient Descent Ascent Method: A Control Theory Inspired Algorithm for Min-max Optimization},
  url = {https://mallada.ece.jhu.edu/pubs/2024-CDC-ZLYM.pdf},
  year = {2024}
}

@inproceedings{lmly2024cdc,
  abstract = {Minimax problems have attracted much attention due to various applications in constrained optimization problems and zero-sum games. Identifying saddle points within these problems is crucial, and saddle flow dynamics offer a straightforward yet useful approach. This study focuses on a class of bilinearly coupled minimax problems and designs an accelerated algorithm based on saddle flow dynamics that achieves a convergence rate beyond stereotype limits.  The algorithm is derived based on a sequential two-step transformation of the objective function. First, a change of variable is aimed at a better-conditioned saddle function. Second, a proximal regularization, when staggered with the first step, guarantees strong convexity-strong concavity of the objective function that can be tuned for accelerated exponential convergence.
Besides, such an approach can be extended to a class of weakly convex-weakly concave functions and still achieve exponential convergence to one stationary point. The theory is verified by a numerical test on an affine equality-constrained convex optimization problem.},
  author = {Liu, Yingzhu and Mallada, Enrique and Li, Zhongkui and You, Pengcheng},
  booktitle = {63rd IEEE Conference on Decision and Control (CDC)},
  grants = {CPS-2136324, Global-Centers-2330450},
  month = {07},
  pubstate = {accepted, submitted Mar 2024},
  title = {Accelerated Saddle Flow Dynamics for Bilinearly Coupled Minimax Problems},
  url = {https://mallada.ece.jhu.edu/pubs/2024-Preprint-LMLY.pdf},
  year = {2024}
}

@inproceedings{pmv2024cdc,
  abstract = {One of the fundamental problems of interest for discrete-time linear systems is whether its input sequence may be recovered given its output sequence, a.k.a. the left inversion problem. Many conditions on the state space geometry, dynamics, and spectral structure of a system have been used to characterize the well-posedness of this problem, without assumptions on the inputs. However, certain structural assumptions, such as input sparsity, have been shown to translate to practical gains in the performance of inversion algorithms, surpassing classical guarantees. Establishing necessary and sufficient conditions for left invertibility of systems with sparse inputs is therefore a crucial step toward understanding the performance limits of system inversion under structured input assumptions. In this work, we provide the first necessary and sufficient characterizations of left invertibility for linear systems with sparse inputs,  echoing classic characterizations for standard linear systems. The key insight in deriving these results is in establishing the existence of two novel geometric invariants unique to the sparse-input setting, the weakly unobservable and strongly reachable subspace arrangements. By means of a concrete example, we demonstrate the utility of these characterizations. We conclude by discussing extensions and applications of this framework to several related problems in sparse control.},
  author = {Poe, Kyle and Mallada, Enrique and Vidal, Rene},
  booktitle = {63rd IEEE Conference on Decision and Control (CDC)},
  grants = {CPS-2136324, Global-Centers-2330450},
  month = {12},
  pubstate = {presented},
  record = {accepted Jul 2024, submitted Mar 2024},
  title = {Invertibility of Discrete-Time Linear Systems with Sparse Inputs},
  url = {https://mallada.ece.jhu.edu/pubs/2024-CDC-PMV.pdf},
  year = {2024}
}

@article{zlym2024lcss,
  abstract = {Gradient Descent Ascent (GDA) methods for min-max optimization problems typically produce oscillatory behavior that can lead to instability, e.g., in bilinear settings.
To address this problem, we introduce a dissipation term into the GDA updates to dampen these oscillations. The proposed Dissipative GDA (DGDA) method can be seen as performing standard GDA on a state-augmented and regularized saddle function that does not strictly introduce additional convexity/concavity. We theoretically show the linear convergence of DGDA in the bilinear and strongly convex-strongly concave settings and assess its performance by comparing DGDA with other methods such as GDA, Extra-Gradient (EG), and Optimistic GDA.
Our findings demonstrate that DGDA surpasses these methods, achieving superior convergence rates. We support our claims with two numerical examples that showcase DGDA's effectiveness in solving saddle point problems.},
  author = {Zheng, Tianqi and Loizou, Nicolas and You, Pengcheng and Mallada, Enrique},
  doi = {10.1109/LCSYS.2024.3413004},
  grants = {CPS-2136324, Global-Centers-2330450},
  journal = {IEEE Control Systems Letters (L-CSS)},
  month = {06},
  pages = {2009-2014},
  record = {published, accepted May 2024, submitted Mar 2024},
  title = {Dissipative Gradient Descent Ascent Method: A Control Theory Inspired Algorithm for Min-max Optimization},
  url = {https://mallada.ece.jhu.edu/pubs/2024-LCSS-ZLYM.pdf},
  volume = {8},
  year = {2024}
}

@inproceedings{mvm2024iclr,
  abstract = {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łog 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.},
  author = {Min, Hancheng and Vidal, Rene and Mallada, Enrique},
  booktitle = {International Conference on Representation Learning (ICLR)},
  grants = {CAREER-1752362},
  month = {05},
  record = {published, accepted Jan 2024, submitted Sep 2023},
  title = {Early Neuron Alignment in Two-layer ReLU Networks with Small Initialization},
  url = {https://mallada.ece.jhu.edu/pubs/2024-ICLR-MVM.pdf},
  year = {2024}
}