Paris Giampouras

selected publications

1. ICLR

   Implicit Bias of Projected Subgradient Method Gives Provable Robust Recovery of Subspaces of Unknown Codimension

   Paris Giampouras, Benjamin Haeffele, and Rene Vidal

   International Conference on Learning Representations 2022

   Abs Bib

   Robust subspace recovery (RSR) is the problem of learning a subspace from sample data points corrupted by outliers. Dual Principal Component Pursuit (DPCP) is a robust subspace recovery method that aims to find a basis for the orthogonal complement of the subspace by minimizing the sum of the distances of the points to the subspaces subject to orthogonality constraints on the basis. Prior work has shown that DPCP can provably recover the correct subspace in the presence of outliers as long as the true dimension of the subspace is known. In this paper, we show that if the orthogonality constraints –adopted in previous DPCP formulations– are relaxed and random initialization is used instead of spectral one, DPCP can provably recover a subspace of \emphunknown dimension. Specifically, we propose a very simple algorithm based on running multiple instances of a projected sub-gradient descent method (PSGM), with each problem instance seeking to find one vector in the null space of the subspace. We theoretically prove that under mild conditions this approach succeeds with high probability. In particular, we show that 1) all of the problem instances will converge to a vector in the nullspace of the subspace and 2) the ensemble of problem instance solutions will be sufficiently diverse to fully span the nullspace of the subspace thus also revealing its true unknown codimension. We provide empirical results that corroborate our theoretical results and showcase the remarkable implicit rank regularization behavior of the PSGM algorithm that allows us to perform RSR without knowing the subspace dimension

   @article{giampouras2022implicit,
     title = {Implicit Bias of Projected Subgradient Method Gives Provable Robust Recovery of Subspaces of Unknown Codimension},
     author = {Giampouras, Paris and Haeffele, Benjamin and Vidal, Rene},
     journal = {International Conference on Learning Representations},
     year = {2022},
     url = {https://openreview.net/forum?id=vA7doMdgi75},
   }

2. IEEE TSP

   Block-Term Tensor Decomposition Model Selection and Computation: The Bayesian Way

   Paris Giampouras, Athanasios A. Rontogiannis, and Eleftherios Kofidis

   IEEE Transactions on Signal Processing 2022

   Abs Bib

   The so-called block-term decomposition (BTD) tensor model, especially in its rank- (Lr,Lr,1) version, has been recently receiving increasing attention due to its enhanced ability of representing systems and signals that are composed of blocks of rank higher than one, a scenario encountered in numerous and diverse applications. Uniqueness conditions and fitting methods have thus been thoroughly studied. Nevertheless, the challenging problem of estimating the BTD model structure, namely the number of block terms, R , and their individual ranks, Lr , has only recently started to attract significant attention, mainly through regularization-based approaches which entail the need to tune the regularization parameter(s). In this work, we build on ideas of sparse Bayesian learning (SBL) and put forward a fully automated Bayesian approach. Through a suitably crafted multi-level hierarchical probabilistic model, which gives rise to heavy-tailed prior distributions for the BTD factors, structured sparsity is jointly imposed. Ranks are then estimated from the numbers of blocks ( R ) and columns ( Lr ) of non-negligible energy. Approximate posterior inference is implemented, within the variational inference framework. The resulting iterative algorithm completely avoids hyperparameter tuning, which is a significant defect of regularization-based methods. Alternative probabilistic models are also explored and the connections with their regularization-based counterparts are brought to light with the aid of the associated maximum a-posteriori (MAP) estimators. We report simulation results with both synthetic and real-word data, which demonstrate the merits of the proposed method in terms of both rank estimation and model fitting as compared to state-of-the-art relevant methods.

   @article{9735405,
     author = {Giampouras, Paris and Rontogiannis, Athanasios A. and Kofidis, Eleftherios},
     journal = {IEEE Transactions on Signal Processing},
     title = {Block-Term Tensor Decomposition Model Selection and Computation: The Bayesian Way},
     year = {2022},
     volume = {70},
     number = {},
     pages = {1704-1717},
     doi = {10.1109/TSP.2022.3159029}
   }

3. ICML

   Reverse Engineering \ell_p attacks: A block-sparse optimization approach with recovery guarantees

   Darshan Thaker *, Paris Giampouras *, and Rene Vidal

   (* equal contribution) 39th International Conference on Machine Learning 2022

   Abs Bib PDF

   Deep neural network-based classifiers have been shown to be vulnerable to imperceptible perturbations to their input, such as \ell_p-bounded norm adversarial attacks. This has motivated the development of many defense methods, which are then broken by new attacks, and so on. This paper focuses on a different but related problem of reverse engineering adversarial attacks. Specifically, given an attacked signal, we study conditions under which one can determine the type of attack (\ell_1, \ell_2 or \ell_∞) and recover the clean signal. We pose this problem as a block-sparse recovery problem, where both the signal and the attack are assumed to lie in a union of subspaces that includes one subspace per class and one subspace per attack type. We derive geometric conditions on the subspaces under which any attacked signal can be decomposed as the sum of a clean signal plus an attack. In addition, by determining the subspaces that contain the signal and the attack, we can also classify the signal and determine the attack type. Experiments on digit and face classification demonstrate the effectiveness of the proposed approach.

   @article{pmlr-v162-thaker22a,
     title = {Reverse Engineering $\ell_p$ attacks: A block-sparse optimization approach with recovery guarantees},
     author = {Thaker *, Darshan and Giampouras *, Paris and Vidal, Rene},
     journal = {(* equal contribution) 39th International Conference on Machine Learning},
     pages = {21253--21271},
     year = {2022},
     editor = {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan},
     volume = {162},
     series = {Proceedings of Machine Learning Research},
     publisher = {PMLR},
   }