1 paper accepted to CDC 21

Our paper on tight inner approximation of the positive-semidefinite cone [1] have been accepted to IEEE Conference on Decision and Control!

[1] T. Zheng, J. Guthrie, and E. Mallada, “Tight Inner Approximations of the Positive-Semidefinite Cone via Grassmannian Packings,” in 60th IEEE Conference on Decision and Control (CDC), 2021.
[Bibtex] [Abstract] [Download PDF]

We investigate the problem of finding tight innerapproximations of large dimensional positive semidefinite (PSD)cones. To solve this problem, we develop a novel decompositionframework of the PSD cone by means of conical combinationsof smaller dimensional sub-cones. We show that many innerapproximation techniques could be summarized within thisframework, including the set of (scaled) diagonally dominantmatrices, Factor-widthkmatrices, and Chordal Sparse ma-trices. Furthermore, we provide a more flexible family ofinner approximations of the PSD cone, where we aim toarrange the sub-cones so that they are maximally separatedfrom each other. In doing so, these approximations tend tooccupy large fractions of the volume of the PSD cone. Theproposed approach is connected to a classical packing problemin Riemannian Geometry. Precisely, we show that the problemof finding maximally distant sub-cones in an ambient PSD coneis equivalent to the problem of packing sub-spaces in a Grass-mannian Manifold. We further leverage existing computationalmethod for constructing packings in Grassmannian manifoldsto build tighter approximations of the PSD cone. Numericalexperiments show how the proposed framework can balancebetween accuracy and computational complexity, to efficientlysolve positive-semidefinite programs.

@inproceedings{zgm2021cdc,
  abstract = {We investigate the problem of finding tight innerapproximations of large dimensional positive semidefinite (PSD)cones. To solve this problem, we develop a novel decompositionframework of the PSD cone by means of conical combinationsof smaller dimensional sub-cones. We show that many innerapproximation techniques could be summarized within thisframework, including the set of (scaled) diagonally dominantmatrices, Factor-widthkmatrices, and Chordal Sparse ma-trices. Furthermore, we provide a more flexible family ofinner approximations of the PSD cone, where we aim toarrange the sub-cones so that they are maximally separatedfrom each other. In doing so, these approximations tend tooccupy large fractions of the volume of the PSD cone. Theproposed approach is connected to a classical packing problemin Riemannian Geometry. Precisely, we show that the problemof finding maximally distant sub-cones in an ambient PSD coneis equivalent to the problem of packing sub-spaces in a Grass-mannian Manifold. We further leverage existing computationalmethod for constructing packings in Grassmannian manifoldsto build tighter approximations of the PSD cone. Numericalexperiments show how the proposed framework can balancebetween accuracy and computational complexity, to efficientlysolve positive-semidefinite programs.},
  author = {Zheng, Tianqi and Guthrie, James and Mallada, Enrique},
  booktitle = {60th IEEE Conference on Decision and Control (CDC)},
  grants = {EPCN-1711188, CAREER-1752362, AMPS-1736448, TRIPODS-1934979},
  month = {7},
  pubstate = {accepted, submitted Mar. 2021},
  title = {Tight Inner Approximations of the Positive-Semidefinite Cone via Grassmannian Packings},
  url = {https://mallada.ece.jhu.edu/pubs/2021-Preprint-ZGM.pdf},
  year = {2021}
}

Yan and Charalampos defended their dissertations

Yan has defended her dissertation entitled “Leveraging Inverter-Interfaced Energy Storage for Frequency Control in Low-Inertia Power Systems” on Tuesday, June 29th!

Charalampos has defended his dissertation entitled “Designing resilient interdependent infrastructures across spatial and temporal scales” on Wednesday, June 30th!

Congratulations, Yan and Charalampos!

2 papers accepted to ICML’21

Our papers on nullspace property for subspace-preserving recovery[1], and on convergence and implicit bias of overparametrized linear networks [2] have been accepted to the International Conference of Machine Learning (ICML), 2021.

[1] M. D. Kaba, C. You, D. R. Robinson, E. Mallada, and R. Vidal, “A Nullspace Property for Subspace-Preserving Recovery,” in International Conference of Machine Learning (ICML), 2021, pp. 1-9.
[Bibtex] [Abstract] [Download PDF]

Much of the theory for classical sparse recovery is based on conditions on the dictionary that are both necessary and sufficient (e.g., nullspace property) or only sufficient (e.g., incoherence and restricted isometry). In contrast, much of the theory for subspace-preserving recovery, the theoretical underpinnings for sparse subspace classification and clustering methods, is based on conditions on the subspaces and the data that are only sufficient (e.g., subspace incoherence and data inner-radius). This paper derives a necessary and sufficient condition for subspace-preserving recovery that is inspired by the classical nullspace property. Based on this novel condition, called here subspace nullspace property, we derive equivalent characterizations that either admit a clear geometric interpretation, relating data distribution and subspace separation to the recovery success, or can be verified using a finite set of extreme points of a properly defined set. We further exploit these characterizations to derive new sufficient conditions, based on inner-radius and outer-radius measures and dual bounds, that generalize existing conditions, while preserving the geometric interpretations. These results fill an important gap in the subspace-preserving recovery literature

@inproceedings{kcrmv2021icml,
  abstract = {Much of the theory for classical sparse recovery is based on conditions on the dictionary that are both necessary and sufficient (e.g., nullspace property) or only sufficient (e.g., incoherence and restricted isometry). In contrast, much of the theory for subspace-preserving recovery, the theoretical underpinnings for sparse subspace classification and clustering methods, is based on conditions on the subspaces and the data that are only sufficient (e.g., subspace incoherence and data inner-radius). This paper derives a necessary and sufficient condition for subspace-preserving recovery that is inspired by the classical nullspace property.
Based on this novel condition, called here subspace nullspace property, we derive equivalent characterizations that either admit a clear geometric interpretation, relating data distribution and subspace separation to the recovery success, or can be verified using a finite set of extreme points of a properly defined set. We further exploit these characterizations to derive new sufficient conditions, based on inner-radius and outer-radius measures and dual bounds, that generalize existing conditions, while preserving the geometric interpretations. These results fill an important gap in the subspace-preserving recovery literature},
  author = {Kaba, Mustafa Devrim and You, Chong and Robinson, Daniel R. and Mallada, Enrique and Vidal, Rene},
  booktitle = {International Conference of Machine Learning (ICML)},
  month = {5},
  note = {(21.5$%$ acceptance)},
  pages = {1-9},
  pubstate = {accepted},
  title = {A Nullspace Property for Subspace-Preserving Recovery},
  url = {https://mallada.ece.jhu.edu/pubs/2021-ICML-KCRMV.pdf},
  year = {2021}
}
[2] H. Min, S. Tarmoun, R. Vidal, and E. Mallada, “On the Explicit Role of Initialization on the Convergence and Implicit Bias of Overparametrized Linear Networks,” in International Conference of Machine Learning (ICML), 2021, pp. 1-9.
[Bibtex] [Abstract] [Download 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.

@inproceedings{mtvm2021icml,
  abstract = {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.        },
  author = {Min, Hancheng and Tarmoun, Salma and Vidal, Rene and Mallada, Enrique},
  booktitle = {International Conference of Machine Learning (ICML)},
  month = {5},
  note = {(21.5$%$ acceptance)},
  pages = {1-9},
  pubstate = {accepted},
  title = {On the Explicit Role of Initialization on the Convergence and Implicit Bias of Overparametrized Linear Networks},
  url = {https://mallada.ece.jhu.edu/pubs/2021-ICML-MTVM.pdf},
  year = {2021}
}