René Vidal

ICML Conference 2025 Conference Paper

Gradient Flow Provably Learns Robust Classifiers for Orthonormal GMMs

• Hancheng Min
• René Vidal

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 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.

ICML Conference 2025 Conference Paper

Guarantees of a Preconditioned Subgradient Algorithm for Overparameterized Asymmetric Low-rank Matrix Recovery

• Paris Giampouras
• HanQin Cai
• René Vidal

In this paper, we focus on a matrix factorization-based approach for robust recovery of low-rank asymmetric matrices from corrupted measurements. We propose an Overparameterized Preconditioned Subgradient Algorithm (OPSA) and provide, for the first time in the literature, linear convergence rates independent of the rank of the sought asymmetric matrix in the presence of gross corruptions. Our work goes beyond existing results in preconditioned-type approaches addressing their current limitation, i. e. , the lack of convergence guarantees in the case of asymmetric matrices of unknown rank. By applying our approach to (robust) matrix sensing, we highlight its merits when the measurement operator satisfies a mixed-norm restricted isometry property. Lastly, we present extensive numerical experiments that validate our theoretical results and demonstrate the effectiveness of our approach for different levels of overparameterization and corruption from outliers.

ICLR Conference 2025 Conference Paper

InCoDe: Interpretable Compressed Descriptions For Image Generation

• Armand Comas Massague
• Aditya Chattopadhyay
• Feliu Formosa
• Changyu Liu
• Octavia I. Camps
• René Vidal

Generative models have been successfully applied in diverse domains, from natural language processing to image synthesis. However, despite this success, a key challenge that remains is the ability to control the semantic content of the scene being generated. We argue that adequate control of the generation process requires a data representation that allows users to access and efficiently manipulate the semantic factors shaping the data distribution. This work advocates for the adoption of succinct, informative, and interpretable representations, quantified using information-theoretic principles. Through extensive experiments, we demonstrate the efficacy of our proposed framework both qualitatively and quantitatively. Our work contributes to the ongoing quest to enhance both controllability and interpretability in the generation process. Code available at github.com/ArmandCom/InCoDe.

ICLR Conference 2025 Conference Paper

LoRanPAC: Low-rank Random Features and Pre-trained Models for Bridging Theory and Practice in Continual Learning

• Liangzu Peng
• Juan Elenter
• Joshua Agterberg
• Alejandro Ribeiro
• René Vidal

The goal of continual learning (CL) is to train a model that can solve multiple tasks presented sequentially. Recent CL approaches have achieved strong performance by leveraging large pre-trained models that generalize well to downstream tasks. However, such methods lack theoretical guarantees, making them prone to unexpected failures. Conversely, principled CL approaches often fail to achieve competitive performance. In this work, we aim to bridge this gap between theory and practice by designing a simple CL method that is theoretically sound and highly performant. Specifically, we lift pre-trained features into a higher dimensional space and formulate an over-parametrized minimum-norm least-squares problem. We find that the lifted features are highly ill-conditioned, potentially leading to large training errors (numerical instability) and increased generalization errors. We address these challenges by continually truncating the singular value decomposition of the lifted features. Our approach, termed LoRanPAC, is stable with respect to the choice of hyperparameters, can handle hundreds of tasks, and outperforms state-of-the-art CL methods on multiple datasets. Importantly, our method satisfies a recurrence relation throughout its continual learning process, which allows us to prove it maintains small training and test errors by appropriately truncating a fraction of SVD factors. This results in a stable continual learning method with strong empirical performance and theoretical guarantees. Code available: \url{https://github.com/liangzu/loranpac}.

ICLR Conference 2024 Conference Paper

Bootstrapping Variational Information Pursuit with Large Language and Vision Models for Interpretable Image Classification

• Aditya Chattopadhyay
• Kwan Ho Ryan Chan
• René Vidal

Variational Information Pursuit (V-IP) is an interpretable-by-design framework that makes predictions by sequentially selecting a short chain of user-defined, interpretable queries about the data that are most informative for the task. The prediction is based solely on the obtained query answers, which also serve as a faithful explanation for the prediction. Applying the framework to any task requires (i) specification of a query set, and (ii) densely annotated data with query answers to train classifiers to answer queries at test time. This limits V-IP's application to small-scale tasks where manual data annotation is feasible. In this work, we focus on image classification tasks and propose to relieve this bottleneck by leveraging pretrained language and vision models. Specifically, following recent work, we propose to use GPT, a Large Language Model, to propose semantic concepts as queries for a given classification task. To answer these queries, we propose a light-weight Concept Question-Answering network (Concept-QA) which learns to answer binary queries about semantic concepts in images. We design pseudo-labels to train our Concept-QA model using GPT and CLIP (a Vision-Language Model). Empirically, we find our Concept-QA model to be competitive with state-of-the-art VQA models in terms of answering accuracy but with an order of magnitude fewer parameters. This allows for seamless integration of Concept-QA into the V-IP framework as a fast-answering mechanism. We name this method Concept-QA+V-IP. Finally, we show on several datasets that Concept-QA+V-IP produces shorter, interpretable query chains which are more accurate than V-IP trained with CLIP-based answering systems. Code available at https://github.com/adityac94/conceptqa_vip.

ICML Conference 2024 Conference Paper

Can Implicit Bias Imply Adversarial Robustness?

• Hancheng Min
• René Vidal

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.

ICLR Conference 2024 Conference Paper

Early Neuron Alignment in Two-layer ReLU Networks with Small Initialization

• Hancheng Min
• Enrique Mallada
• René Vidal

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 $\mathcal{O}(\frac{\log n}{\sqrt{\mu}})$ 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 $\mu$ measures how well the data are separated. After the early alignment phase, the loss converges to zero at a $\mathcal{O}(\frac{1}{t})$ rate, and the weight matrix on the first layer is approximately low-rank. Numerical experiments on the MNIST dataset illustrate our theoretical findings.

NeurIPS Conference 2024 Conference Paper

Geometric Analysis of Nonlinear Manifold Clustering

• Nimita Shinde
• Tianjiao Ding
• Daniel P. Robinson
• René Vidal

Manifold clustering is an important problem in motion and video segmentation, natural image clustering, and other applications where high-dimensional data lie on multiple, low-dimensional, nonlinear manifolds. While current state-of-the-art methods on large-scale datasets such as CIFAR provide good empirical performance, they do not have any proof of theoretical correctness. In this work, we propose a method that clusters data belonging to a union of nonlinear manifolds. Furthermore, for a given input data sample $y$ belonging to the $l$th manifold $\mathcal{M}_l$, we provide geometric conditions that guarantee a manifold-preserving representation of $y$ can be recovered from the solution to the proposed model. The geometric conditions require that (i) $\mathcal{M}_l$ is well-sampled in the neighborhood of $y$, with the sampling density given as a function of the curvature, and (ii) $\mathcal{M}_l$ is sufficiently separated from the other manifolds. In addition to providing proof of correctness in this setting, a numerical comparison with state-of-the-art methods on CIFAR datasets shows that our method performs competitively although marginally worse than methods without

ICLR Conference 2024 Conference Paper

Image Clustering via the Principle of Rate Reduction in the Age of Pretrained Models

• Tianzhe Chu
• Shengbang Tong
• Tianjiao Ding
• Xili Dai
• Benjamin D. Haeffele
• René Vidal
• Yi Ma 0001

The advent of large pre-trained models has brought about a paradigm shift in both visual representation learning and natural language processing. However, clustering unlabeled images, as a fundamental and classic machine learning problem, still lacks an effective solution, particularly for large-scale datasets. In this paper, we propose a novel image clustering pipeline that leverages the powerful feature representation of large pre-trained models such as CLIP and cluster images effectively and efficiently at scale. We first developed a novel algorithm to estimate the number of clusters in a given dataset. We then show that the pre-trained features are significantly more structured by further optimizing the rate reduction objective. The resulting features may significantly improve the clustering accuracy, e.g., from 57\% to 66\% on ImageNet-1k. Furthermore, by leveraging CLIP's multimodality bridge between image and text, we develop a simple yet effective self-labeling algorithm that produces meaningful text labels for the clusters. Through extensive experiments, we show that our pipeline works well on standard datasets such as CIFAR-10, CIFAR-100, and ImageNet-1k. It also extends to datasets without predefined labels, such as LAION-Aesthetics and WikiArts.

NeurIPS Conference 2024 Conference Paper

PaCE: Parsimonious Concept Engineering for Large Language Models

• Jinqi Luo
• Tianjiao Ding
• Kwan H. Chan
• Darshan Thaker
• Aditya Chattopadhyay
• Chris Callison-Burch
• René Vidal

Large Language Models (LLMs) are being used for a wide variety of tasks. While they are capable of generating human-like responses, they can also produce undesirable output including potentially harmful information, racist or sexist language, and hallucinations. Alignment methods are designed to reduce such undesirable output, via techniques such as fine-tuning, prompt engineering, and representation engineering. However, existing methods face several challenges: some require costly fine-tuning for every alignment task; some do not adequately remove undesirable concepts, failing alignment; some remove benign concepts, lowering the linguistic capabilities of LLMs. To address these issues, we propose Parsimonious Concept Engineering (PaCE), a novel activation engineering framework for alignment. First, to sufficiently model the concepts, we construct a large-scale concept dictionary in the activation space, in which each atom corresponds to a semantic concept. Given any alignment task, we instruct a concept partitioner to efficiently annotate the concepts as benign or undesirable. Then, at inference time, we decompose the LLM activations along the concept dictionary via sparse coding, to accurately represent the activations as linear combinations of benign and undesirable components. By removing the latter ones from the activations, we reorient the behavior of the LLM towards the alignment goal. We conduct experiments on tasks such as response detoxification, faithfulness enhancement, and sentiment revising, and show that PaCE achieves state-of-the-art alignment performance while maintaining linguistic capabilities.

ICML Conference 2024 Conference Paper

Performance Bounds for Active Binary Testing with Information Maximization

• Aditya Chattopadhyay
• Benjamin D. Haeffele
• René Vidal
• Donald Geman

In many applications like experimental design, group testing, and medical diagnosis, the state of a random variable $Y$ is revealed by successively observing the outcomes of binary tests about $Y$. New tests are selected adaptively based on the history of outcomes observed so far. If the number of states of $Y$ is finite, the process ends when $Y$ can be predicted with a desired level of confidence or all available tests have been used. Finding the strategy that minimizes the expected number of tests needed to predict $Y$ is virtually impossible in most real applications. Therefore, the commonly used strategy is the greedy heuristic of Information Maximization (InfoMax) that selects tests sequentially in order of information gain. Despite its widespread use, existing guarantees on its performance are often vacuous when compared to its empirical efficiency. In this paper, for the first time to the best of our knowledge, we establish tight non-vacuous bounds on InfoMax’s performance. Our analysis is based on the assumption that at any iteration of the greedy strategy, there is always a binary test available whose conditional probability of being ’true’, given the history, is within $\delta$ units of one-half. This assumption is motivated by practical applications where the available set of tests often satisfies this property for modest values of $\delta$, say, ${0. 1 \leq \delta \leq 0. 4}$. Specifically, we analyze two distinct scenarios: (i) all tests are functions of $Y$, and (ii) test outcomes are corrupted by a binary symmetric channel. For both cases, our bounds guarantee the near-optimal performance of InfoMax for modest $\delta$ values. It requires only a small multiplicative factor of the entropy of $Y$, in terms of the average number of tests needed to make accurate predictions.

ICML Conference 2023 Conference Paper

Learning Globally Smooth Functions on Manifolds

• Juan Cerviño
• Luiz F. O. Chamon
• Benjamin D. Haeffele
• René Vidal
• Alejandro Ribeiro

Smoothness and low dimensional structures play central roles in improving generalization and stability in learning and statistics. This work combines techniques from semi-infinite constrained learning and manifold regularization to learn representations that are globally smooth on a manifold. To do so, it shows that under typical conditions the problem of learning a Lipschitz continuous function on a manifold is equivalent to a dynamically weighted manifold regularization problem. This observation leads to a practical algorithm based on a weighted Laplacian penalty whose weights are adapted using stochastic gradient techniques. It is shown that under mild conditions, this method estimates the Lipschitz constant of the solution, learning a globally smooth solution as a byproduct. Experiments on real world data illustrate the advantages of the proposed method relative to existing alternatives. Our code is available at https: //github. com/JuanCervino/smoothbench.

ICML Conference 2023 Conference Paper

On the Convergence of Gradient Flow on Multi-layer Linear Models

• Hancheng Min
• René Vidal
• Enrique Mallada

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\cdots 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\cdots 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.

ICML Conference 2023 Conference Paper

The Ideal Continual Learner: An Agent That Never Forgets

• Liangzu Peng
• Paris Giampouras
• René Vidal

The goal of continual learning is to find a model that solves multiple learning tasks which are presented sequentially to the learner. A key challenge in this setting is that the learner may "forget" how to solve a previous task when learning a new task, a phenomenon known as catastrophic forgetting. To address this challenge, many practical methods have been proposed, including memory-based, regularization-based and expansion-based methods. However, a rigorous theoretical understanding of these methods remains elusive. This paper aims to bridge this gap between theory and practice by proposing a new continual learning framework called "Ideal Continual Learner" (ICL), which is guaranteed to avoid catastrophic forgetting by construction. We show that ICL unifies multiple well-established continual learning methods and gives new theoretical insights into the strengths and weaknesses of these methods. We also derive generalization bounds for ICL which allow us to theoretically quantify "how rehearsal affects generalization". Finally, we connect ICL to several classic subjects and research topics of modern interest, which allows us to make historical remarks and inspire future directions.

ICLR Conference 2023 Conference Paper

Variational Information Pursuit for Interpretable Predictions

• Aditya Chattopadhyay
• Kwan Ho Ryan Chan
• Benjamin D. Haeffele
• Donald Geman
• René Vidal

There is a growing interest in the machine learning community in developing predictive algorithms that are interpretable by design. To this end, recent work proposes to sequentially ask interpretable queries about data until a high confidence prediction can be made based on the answers obtained (the history). To promote short query-answer chains, a greedy procedure called Information Pursuit (IP) is used, which adaptively chooses queries in order of information gain. Generative models are employed to learn the distribution of query-answers and labels, which is in turn used to estimate the most informative query. However, learning and inference with a full generative model of the data is often intractable for complex tasks. In this work, we propose Variational Information Pursuit (V-IP), a variational characterization of IP which bypasses the need to learn generative models. V-IP is based on finding a query selection strategy and a classifier that minimize the expected cross-entropy between true and predicted labels. We prove that the IP strategy is the optimal solution to this problem. Therefore, instead of learning generative models, we can use our optimal strategy to directly pick the most informative query given any history. We then develop a practical algorithm by defining a finite-dimensional parameterization of our strategy and classifier using deep networks and train them end-to-end using our objective. Empirically, V-IP is 10-100x faster than IP on different Vision and NLP tasks with competitive performance. Moreover, V-IP finds much shorter query chains when compared to reinforcement learning which is typically used in sequential-decision-making problems. Finally, we demonstrate the utility of V-IP on challenging tasks like medical diagnosis where the performance is far superior to the generative modeling approach.

ICLR Conference 2022 Conference Paper

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

• Paris Giampouras
• Benjamin D. Haeffele
• René Vidal

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 \emph{unknown 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

ICML Conference 2022 Conference Paper

Reverse Engineering ℓ p attacks: A block-sparse optimization approach with recovery guarantees

• Darshan Thaker
• Paris Giampouras
• René Vidal

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_\infty$) 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.

ICML Conference 2022 Conference Paper

Understanding Doubly Stochastic Clustering

• Tianjiao Ding
• Derek Lim
• René Vidal
• Benjamin D. Haeffele

The problem of projecting a matrix onto the space of doubly stochastic matrices finds several applications in machine learning. For example, in spectral clustering, it has been shown that forming the normalized Laplacian matrix from a data affinity matrix has close connections to projecting it onto the set of doubly stochastic matrices. However, the analysis of why this projection improves clustering has been limited. In this paper we present theoretical conditions on the given affinity matrix under which its doubly stochastic projection is an ideal affinity matrix (i. e. , it has no false connections between clusters, and is well-connected within each cluster). In particular, we show that a necessary and sufficient condition for a projected affinity matrix to be ideal reduces to a set of conditions on the input affinity that decompose along each cluster. Further, in the subspace clustering problem, where each cluster is defined by a linear subspace, we provide geometric conditions on the underlying subspaces which guarantee correct clustering via a continuous version of the problem. This allows us to explain theoretically the remarkable performance of a recently proposed doubly stochastic subspace clustering method.

ICLR Conference 2021 Conference Paper

A Critique of Self-Expressive Deep Subspace Clustering

• Benjamin D. Haeffele
• Chong You
• René Vidal

Subspace clustering is an unsupervised clustering technique designed to cluster data that is supported on a union of linear subspaces, with each subspace defining a cluster with dimension lower than the ambient space. Many existing formulations for this problem are based on exploiting the self-expressive property of linear subspaces, where any point within a subspace can be represented as linear combination of other points within the subspace. To extend this approach to data supported on a union of non-linear manifolds, numerous studies have proposed learning an embedding of the original data using a neural network which is regularized by a self-expressive loss function on the data in the embedded space to encourage a union of linear subspaces prior on the data in the embedded space. Here we show that there are a number of potential flaws with this approach which have not been adequately addressed in prior work. In particular, we show the model formulation is often ill-posed in that it can lead to a degenerate embedding of the data, which need not correspond to a union of subspaces at all and is poorly suited for clustering. We validate our theoretical results experimentally and also repeat prior experiments reported in the literature, where we conclude that a significant portion of the previously claimed performance benefits can be attributed to an ad-hoc post processing step rather than the deep subspace clustering model.

ICML Conference 2021 Conference Paper

A Nullspace Property for Subspace-Preserving Recovery

• Mustafa Devrim Kaba
• Chong You
• Daniel P. Robinson
• Enrique Mallada
• René Vidal

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 the subspace nullspace property, we derive equivalent characterizations that either admit a clear geometric interpretation that relates 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 and preserve the geometric interpretations. These results fill an important gap in the subspace-preserving recovery literature.

ICML Conference 2021 Conference Paper

Dual Principal Component Pursuit for Robust Subspace Learning: Theory and Algorithms for a Holistic Approach

• Tianyu Ding
• Zhihui Zhu
• René Vidal
• Daniel P. Robinson

The Dual Principal Component Pursuit (DPCP) method has been proposed to robustly recover a subspace of high-relative dimension from corrupted data. Existing analyses and algorithms of DPCP, however, mainly focus on finding a normal to a single hyperplane that contains the inliers. Although these algorithms can be extended to a subspace of higher co-dimension through a recursive approach that sequentially finds a new basis element of the space orthogonal to the subspace, this procedure is computationally expensive and lacks convergence guarantees. In this paper, we consider a DPCP approach for simultaneously computing the entire basis of the orthogonal complement subspace (we call this a holistic approach) by solving a non-convex non-smooth optimization problem over the Grassmannian. We provide geometric and statistical analyses for the global optimality and prove that it can tolerate as many outliers as the square of the number of inliers, under both noiseless and noisy settings. We then present a Riemannian regularity condition for the problem, which is then used to prove that a Riemannian subgradient method converges linearly to a neighborhood of the orthogonal subspace with error proportional to the noise level.

ICML Conference 2021 Conference Paper

On the Explicit Role of Initialization on the Convergence and Implicit Bias of Overparametrized Linear Networks

• Hancheng Min
• Salma Tarmoun
• René Vidal
• Enrique Mallada

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.

ICML Conference 2021 Conference Paper

Understanding the Dynamics of Gradient Flow in Overparameterized Linear models

• Salma Tarmoun
• Guilherme França
• Benjamin D. Haeffele
• René Vidal

We provide a detailed analysis of the dynamics ofthe gradient flow in overparameterized two-layerlinear models. A particularly interesting featureof this model is that its nonlinear dynamics can beexactly solved as a consequence of a large num-ber of conservation laws that constrain the systemto follow particular trajectories. More precisely, the gradient flow preserves the difference of theGramian matrices of the input and output weights, and its convergence to equilibrium depends onboth the magnitude of that difference (which isfixed at initialization) and the spectrum of the data. In addition, and generalizing prior work, we proveour results without assuming small, balanced orspectral initialization for the weights. Moreover, we establish interesting mathematical connectionsbetween matrix factorization problems and differ-ential equations of the Riccati type.

NeurIPS Conference 2019 Conference Paper

A Linearly Convergent Method for Non-Smooth Non-Convex Optimization on the Grassmannian with Applications to Robust Subspace and Dictionary Learning

• Zhihui Zhu
• Tianyu Ding
• Daniel Robinson
• Manolis Tsakiris
• René Vidal

Minimizing a non-smooth function over the Grassmannian appears in many applications in machine learning. In this paper we show that if the objective satisfies a certain Riemannian regularity condition with respect to some point in the Grassmannian, then a Riemannian subgradient method with appropriate initialization and geometrically diminishing step size converges at a linear rate to that point. We show that for both the robust subspace learning method Dual Principal Component Pursuit (DPCP) and the Orthogonal Dictionary Learning (ODL) problem, the Riemannian regularity condition is satisfied with respect to appropriate points of interest, namely the subspace orthogonal to the sought subspace for DPCP and the orthonormal dictionary atoms for ODL. Consequently, we obtain in a unified framework significant improvements for the convergence theory of both methods.

ICML Conference 2019 Conference Paper

Noisy Dual Principal Component Pursuit

• Tianyu Ding
• Zhihui Zhu
• Tianjiao Ding
• Yunchen Yang
• Daniel P. Robinson
• Manolis C. Tsakiris
• René Vidal

Dual Principal Component Pursuit (DPCP) is a recently proposed non-convex optimization based method for learning subspaces of high relative dimension from noiseless datasets contaminated by as many outliers as the square of the number of inliers. Experimentally, DPCP has proved to be robust to noise and outperform the popular RANSAC on 3D vision tasks such as road plane detection and relative poses estimation from three views. This paper extends the global optimality and convergence theory of DPCP to the case of data corrupted by noise, and further demonstrates its robustness using synthetic and real data.

ICML Conference 2018 Conference Paper

ADMM and Accelerated ADMM as Continuous Dynamical Systems

• Guilherme França
• Daniel P. Robinson
• René Vidal

Recently, there has been an increasing interest in using tools from dynamical systems to analyze the behavior of simple optimization algorithms such as gradient descent and accelerated variants. This paper strengthens such connections by deriving the differential equations that model the continuous limit of the sequence of iterates generated by the alternating direction method of multipliers, as well as an accelerated variant. We employ the direct method of Lyapunov to analyze the stability of critical points of the dynamical systems and to obtain associated convergence rates.

JMLR Journal 2018 Journal Article

Dual Principal Component Pursuit

• Manolis C. Tsakiris
• René Vidal

We consider the problem of learning a linear subspace from data corrupted by outliers. Classical approaches are typically designed for the case in which the subspace dimension is small relative to the ambient dimension. Our approach works with a dual representation of the subspace and hence aims to find its orthogonal complement; as such, it is particularly suitable for subspaces whose dimension is close to the ambient dimension (subspaces of high relative dimension). We pose the problem of computing normal vectors to the inlier subspace as a non-convex $\ell_1$ minimization problem on the sphere, which we call Dual Principal Component Pursuit (DPCP) problem. We provide theoretical guarantees under which every global solution to DPCP is a vector in the orthogonal complement of the inlier subspace. Moreover, we relax the non-convex DPCP problem to a recursion of linear programs whose solutions are shown to converge in a finite number of steps to a vector orthogonal to the subspace. In particular, when the inlier subspace is a hyperplane, the solutions to the recursion of linear programs converge to the global minimum of the non-convex DPCP problem in a finite number of steps. We also propose algorithms based on alternating minimization and iteratively re-weighted least squares, which are suitable for dealing with large-scale data. Experiments on synthetic data show that the proposed methods are able to handle more outliers and higher relative dimensions than current state-of-the-art methods, while experiments in the context of the three-view geometry problem in computer vision suggest that the proposed methods can be a useful or even superior alternative to traditional RANSAC-based approaches for computer vision and other applications. [abs] [ pdf ][ bib ] &copy JMLR 2018. ( edit, beta )

NeurIPS Conference 2018 Conference Paper

Dual Principal Component Pursuit: Improved Analysis and Efficient Algorithms

• Zhihui Zhu
• Yifan Wang
• Daniel Robinson
• Daniel Naiman
• René Vidal
• Manolis Tsakiris

Recent methods for learning a linear subspace from data corrupted by outliers are based on convex L1 and nuclear norm optimization and require the dimension of the subspace and the number of outliers to be sufficiently small [27]. In sharp contrast, the recently proposed Dual Principal Component Pursuit (DPCP) method [22] can provably handle subspaces of high dimension by solving a non-convex L1 optimization problem on the sphere. However, its geometric analysis is based on quantities that are difficult to interpret and are not amenable to statistical analysis. In this paper we provide a refined geometric analysis and a new statistical analysis that show that DPCP can tolerate as many outliers as the square of the number of inliers, thus improving upon other provably correct robust PCA methods. We also propose a scalable Projected Sub-Gradient Descent method (DPCP-PSGD) for solving the DPCP problem and show it admits linear convergence even though the underlying optimization problem is non-convex and non-smooth. Experiments on road plane detection from 3D point cloud data demonstrate that DPCP-PSGD can be more efficient than the traditional RANSAC algorithm, which is one of the most popular methods for such computer vision applications.

ICML Conference 2018 Conference Paper

On the Implicit Bias of Dropout

• Poorya Mianjy
• Raman Arora
• René Vidal

Algorithmic approaches endow deep learning systems with implicit bias that helps them generalize even in over-parametrized settings. In this paper, we focus on understanding such a bias induced in learning through dropout, a popular technique to avoid overfitting in deep learning. For single hidden-layer linear neural networks, we show that dropout tends to make the norm of incoming/outgoing weight vectors of all the hidden nodes equal. In addition, we provide a complete characterization of the optimization landscape induced by dropout.

ICML Conference 2018 Conference Paper

Theoretical Analysis of Sparse Subspace Clustering with Missing Entries

• Manolis C. Tsakiris
• René Vidal

Sparse Subspace Clustering (SSC) is a popular unsupervised machine learning method for clustering data lying close to an unknown union of low-dimensional linear subspaces; a problem with numerous applications in pattern recognition and computer vision. Even though the behavior of SSC for complete data is by now well-understood, little is known about its theoretical properties when applied to data with missing entries. In this paper we give theoretical guarantees for SSC with incomplete data, and provide theoretical evidence that projecting the zero-filled data onto the observation pattern of the point being expressed can lead to substantial improvement in performance; a phenomenon already known experimentally. The main insight of our analysis is that even though this projection induces additional missing entries, this is counterbalanced by the fact that the projected and zero-filled data are in effect incomplete points associated with the union of the corresponding projected subspaces, with respect to which the point being expressed is complete. The significance of this phenomenon potentially extends to the entire class of self-expressive methods.

ICML Conference 2017 Conference Paper

Hyperplane Clustering via Dual Principal Component Pursuit

• Manolis C. Tsakiris
• René Vidal

State-of-the-art methods for clustering data drawn from a union of subspaces are based on sparse and low-rank representation theory and convex optimization algorithms. Existing results guaranteeing the correctness of such methods require the dimension of the subspaces to be small relative to the dimension of the ambient space. When this assumption is violated, as is, e. g. , in the case of hyperplanes, existing methods are either computationally too intensive (e. g. , algebraic methods) or lack sufficient theoretical support (e. g. , K-Hyperplanes or RANSAC). In this paper we provide theoretical and algorithmic contributions to the problem of clustering data from a union of hyperplanes, by extending a recent subspace learning method called Dual Principal Component Pursuit (DPCP) to the multi-hyperplane case. We give theoretical guarantees under which, the non-convex $\ell_1$ problem associated with DPCP admits a unique global minimizer equal to the normal vector of the most dominant hyperplane. Inspired by this insight, we propose sequential (RANSAC-style) and iterative (K-Hyperplanes-style) hyperplane learning DPCP algorithms, which, via experiments on synthetic and real data, are shown to outperform or be competitive to the state-of-the-art.

ICRA Conference 2016 Conference Paper

Learning convolutional action primitives for fine-grained action recognition

• Colin Lea
• René Vidal
• Gregory D. Hager

Fine-grained action recognition is important for many applications of human-robot interaction, automated skill assessment, and surveillance. The goal is to segment and classify all actions occurring in a time series sequence. While recent recognition methods have shown strong performance in robotics applications, they often require hand-crafted features, use large amounts of domain knowledge, or employ overly simplistic representations of how objects change throughout an action. In this paper we present the Latent Convolutional Skip Chain Conditional Random Field (LC-SC-CRF). This time series model learns a set of interpretable and composable action primitives from sensor data. We apply our model to cooking tasks using accelerometer data from the University of Dundee 50 Salads dataset and to robotic surgery training tasks using robot kinematic data from the JHU-ISI Gesture and Skill Assessment Working Set (JIGSAWS). Our performance on 50 Salads and JIGSAWS are 18. 0% and 5. 3% higher than the state of the art, respectively. This model performs well without requiring hand-crafted features or intricate domain knowledge. The code and features have been made public.

ICML Conference 2015 Conference Paper

Geometric Conditions for Subspace-Sparse Recovery

• Chong You
• René Vidal

Given a dictionary \Pi and a signal ξ= \Pi \mathbf x generated by a few \textitlinearly independent columns of \Pi, classical sparse recovery theory deals with the problem of uniquely recovering the sparse representation \mathbf x of ξ. In this work, we consider the more general case where ξlies in a low-dimensional subspace spanned by a few columns of \Pi, which are possibly \textitlinearly dependent. In this case, \mathbf x may not unique, and the goal is to recover any subset of the columns of \Pi that spans the subspace containing ξ. We call such a representation \mathbf x \textitsubspace-sparse. We study conditions under which existing pursuit methods recover a subspace-sparse representation. Such conditions reveal important geometric insights and have implications for the theory of classical sparse recovery as well as subspace clustering.

ICML Conference 2015 Conference Paper

Sparse Subspace Clustering with Missing Entries

• Congyuan Yang
• Daniel P. Robinson
• René Vidal

We consider the problem of clustering incomplete data drawn from a union of subspaces. Classical subspace clustering methods are not applicable to this problem because the data are incomplete, while classical low-rank matrix completion methods may not be applicable because data in multiple subspaces may not be low rank. This paper proposes and evaluates two new approaches for subspace clustering and completion. The first one generalizes the sparse subspace clustering algorithm so that it can obtain a sparse representation of the data using only the observed entries. The second one estimates a suitable kernel matrix by assuming a random model for the missing entries and obtains the sparse representation from this kernel. Experiments on synthetic and real data show the advantages and disadvantages of the proposed methods, which all outperform the natural approach (low-rank matrix completion followed by sparse subspace clustering) when the data matrix is high-rank or the percentage of missing entries is large.

ICML Conference 2014 Conference Paper

Structured Low-Rank Matrix Factorization: Optimality, Algorithm, and Applications to Image Processing

• Benjamin D. Haeffele
• Eric Young
• René Vidal

Recently, convex solutions to low-rank matrix factorization problems have received increasing attention in machine learning. However, in many applications the data can display other structures beyond simply being low-rank. For example, images and videos present complex spatio-temporal structures, which are largely ignored by current low-rank methods. In this paper we explore a matrix factorization technique suitable for large datasets that captures additional structure in the factors by using a projective tensor norm, which includes classical image regularizers such as total variation and the nuclear norm as particular cases. Although the resulting optimization problem is not convex, we show that under certain conditions on the factors, any local minimizer for the factors yields a global minimizer for their product. Examples in biomedical video segmentation and hyperspectral compressed recovery show the advantages of our approach on high-dimensional datasets.

NeurIPS Conference 2012 Conference Paper

Finding Exemplars from Pairwise Dissimilarities via Simultaneous Sparse Recovery

• Ehsan Elhamifar
• Guillermo Sapiro
• René Vidal

Given pairwise dissimilarities between data points, we consider the problem of finding a subset of data points called representatives or exemplars that can efficiently describe the data collection. We formulate the problem as a row-sparsity regularized trace minimization problem which can be solved efficiently using convex programming. The solution of the proposed optimization program finds the representatives and the probability that each data point is associated to each one of the representatives. We obtain the range of the regularization parameter for which the solution of the proposed optimization program changes from selecting one representative to selecting all data points as the representatives. When data points are distributed around multiple clusters according to the dissimilarities, we show that the data in each cluster select only representatives from that cluster. Unlike metric-based methods, our algorithm does not require that the pairwise dissimilarities be metrics and can be applied to dissimilarities that are asymmetric or violate the triangle inequality. We demonstrate the effectiveness of the proposed algorithm on synthetic data as well as real-world datasets of images and text.

YNIMG Journal 2011 Journal Article

A nonparametric Riemannian framework for processing high angular resolution diffusion images and its applications to ODF-based morphometry

• Alvina Goh
• Christophe Lenglet
• Paul M. Thompson
• René Vidal

High angular resolution diffusion imaging (HARDI) has become an important technique for imaging complex oriented structures in the brain and other anatomical tissues. This has motivated the recent development of several methods for computing the orientation probability density function (PDF) at each voxel. However, much less work has been done on developing techniques for filtering, interpolation, averaging and principal geodesic analysis of orientation PDF fields. In this paper, we present a Riemannian framework for performing such operations. The proposed framework does not require that the orientation PDFs be represented by any fixed parameterization, such as a mixture of von Mises–Fisher distributions or a spherical harmonic expansion. Instead, we use a nonparametric representation of the orientation PDF. We exploit the fact that under the square-root re-parameterization, the space of orientation PDFs forms a Riemannian manifold: the positive orthant of the unit Hilbert sphere. We show that various orientation PDF processing operations, such as filtering, interpolation, averaging and principal geodesic analysis, may be posed as optimization problems on the Hilbert sphere, and can be solved using Riemannian gradient descent. We illustrate these concepts with numerous experiments on synthetic, phantom and real datasets. We show their application to studying left/right brain asymmetries.

NeurIPS Conference 2011 Conference Paper

Sparse Manifold Clustering and Embedding

• Ehsan Elhamifar
• René Vidal

We propose an algorithm called Sparse Manifold Clustering and Embedding (SMCE) for simultaneous clustering and dimensionality reduction of data lying in multiple nonlinear manifolds. Similar to most dimensionality reduction methods, SMCE finds a small neighborhood around each data point and connects each point to its neighbors with appropriate weights. The key difference is that SMCE finds both the neighbors and the weights automatically. This is done by solving a sparse optimization problem, which encourages selecting nearby points that lie in the same manifold and approximately span a low-dimensional affine subspace. The optimal solution encodes information that can be used for clustering and dimensionality reduction using spectral clustering and embedding. Moreover, the size of the optimal neighborhood of a data point, which can be different for different points, provides an estimate of the dimension of the manifold to which the point belongs. Experiments demonstrate that our method can effectively handle multiple manifolds that are very close to each other, manifolds with non-uniform sampling and holes, as well as estimate the intrinsic dimensions of the manifolds.

ICML Conference 2006 Conference Paper

Combined central and subspace clustering for computer vision applications

• Le Lu 0001
• René Vidal

NeurIPS Conference 2006 Conference Paper

Online Clustering of Moving Hyperplanes

• René Vidal

We propose a recursive algorithm for clustering trajectories lying in multiple moving hyperplanes. Starting from a given or random initial condition, we use normalized gradient descent to update the coefficients of a time varying polynomial whose degree is the number of hyperplanes and whose derivatives at a trajectory give an estimate of the vector normal to the hyperplane containing that trajectory. As time proceeds, the estimates of the hyperplane normals are shown to track their true values in a stable fashion. The segmentation of the trajectories is then obtained by clustering their associated normal vectors. The final result is a simple recursive algorithm for segmenting a variable number of moving hyperplanes. We test our algorithm on the segmentation of dynamic scenes containing rigid motions and dynamic textures, e. g. , a bird floating on water. Our method not only segments the bird motion from the surrounding water motion, but also determines patterns of motion in the scene (e. g. , periodic motion) directly from the temporal evolution of the estimated polynomial coefficients. Our experiments also show that our method can deal with appearing and disappearing motions in the scene.

ICRA Conference 2005 Conference Paper

Multi-Subspace Methods for Motion Segmentation from Affine, Perspective and Central Panoramic Cameras

• René Vidal

Many robot navigation tasks require the computation of the motion of multiple objects moving in 3-D space from a collection of images taken by a moving robot. In this paper we present a unifying theoretical framework for both infinitesimal and discrete 3-D motion segmentation from optical flow or point correspondences in multiple affine, perspective or central panoramic views. We exploit the fact that for these motion and camera models, the image measurements associated with a single object live in a low dimensional subspace of a high dimensional space, hence motion segmentation is achieved by segmenting data living in multiple subspaces. We solve this problem in closed form using polynomial fitting and differentiation. Unlike previous work, our method does not restrict the motion of the objects to be full dimensional or fully independent. Instead, our approach deals gracefully with all the spectrum of possible motions: from low dimensional and partially dependent to full dimensional and fully independent. In addition, our method handles the case of missing data, meaning that point tracks do not have to be visible in all images. We test our algorithm on various real sequences with degenerate and nondegenerate motions, missing data, transparent motions, etc. Our algorithm achieves a misclassification error of less than 5% for sequences with up to 30% of missing data points.

ICRA Conference 2003 Conference Paper

Formation control of nonholonomic mobile robots with omnidirectional visual servoing and motion segmentation

• René Vidal
• Omid Shakernia
• S. Shankar Sastry

We consider the problem of having a team of nonholonomic mobile robots follow a desired leader-follower formation using omnidirectional vision. By specifying the desired formation in the image plane, we translate the control problem into a separate visual servoing task for each follower. We use a rank constraint on the omnidirectional optical flows across multiple frames to estimate the position and velocities of the leaders in the image plane of each follower. We show that the direct feedback-linearization of the leader-follower dynamics suffers from degenerate configurations due to the nonholonomic constraints of the robots and the nonlinearity of the omnidirectional projection model. We therefore design a nonlinear tracking controller that avoids such degenerate configurations, while preserving the formation input-to-state stability. Our control law naturally incorporates collision avoidance by exploiting the geometry of omnidirectional cameras. We present simulations and experiments evaluating our omnidirectional vision-based formation control scheme.

ICRA Conference 2003 Conference Paper

Multibody motion estimation and segmentation from multiple central panoramic views

• Omid Shakernia
• René Vidal
• S. Shankar Sastry

We present an algorithm for infinitesimal motion estimation and segmentation from multiple central panoramic views. We first show that the central panoramic optical flows corresponding to independent motions lie in orthogonal ten-dimensional subspaces of a higher-dimensional linear space. We then propose a factorization-based technique that estimates the number of independent motions, the segmentation of the image measurements and the motion of each object relative to the camera from a set of image points and their optical flows in multiple frames. Finally, we present the experimental results on motion estimation and segmentation for a real image sequence with two independently moving mobile robots, and evaluate the performance of our algorithm by comparing the vision estimates with GPS measurements gathered by the mobile robots.

IROS Conference 2003 Conference Paper

Vision-based follow-the-leader

• Noah J. Cowan
• Omid Shakernia
• René Vidal
• S. Shankar Sastry

We consider the problem of having a group of nonholonomic mobile robots equipped with omnidirectional cameras maintain a desired leader-follower formation. Our approach is to translate the formation control problem from the configuration space into a separate visual servoing task for each follower. We derive the questions of motion of the leader in the image plane of the follower and propose two control schemes for the follower. The first one is based on feedback linearization and is either string stable or leader-to-formation stable, depending on the sensing capabilities of the followers. The second one assumes a kinematic model for the evolution of the leader velocities and combines a Luenberger observer with a linear control law that is locally stable. We present simulation results evaluating our vision-based follow-the-leader control strategies.

ICRA Conference 2002 Conference Paper

Multiple View Motion Estimation and Control for Landing an Unmanned Aerial Vehicle

• Omid Shakernia
• René Vidal
• Courtney S. Sharp
• Yi Ma 0001
• S. Shankar Sastry

We present a multiple view algorithm for vision based landing of an unmanned aerial vehicle. Our algorithm is based on our results in multiple view geometry which exploit the rank deficiency of the so called multiple view matrix. We show how the use of multiple views significantly improves motion and structure estimation. We compare our algorithm to our previous linear and non-linear two-view algorithms using an actual flight test. Our results show that the vision-based state estimates are accurate to within 7cm in each axis of translation and 4 degrees in each axis of rotation.

ICRA Conference 2001 Conference Paper

Pursuit-Evasion Games with Unmanned Ground and Aerial Vehicles

• René Vidal
• Shahid Rashid
• Courtney S. Sharp
• Omid Shakernia
• Jin Kim
• S. Shankar Sastry

Presents the implementation of a hierarchical architecture for the coordination and control of a heterogeneous team of autonomous agents. We consider the problem of having a team of agents pursue a second team of evaders while building a map of the environment. The control architecture emphasizes the autonomy of each agent yet allows for coordinated efforts among them. We address the technical challenges and implementation issues of multi-agent operation. Finally we present experimental results of a pursuit-evasion game scenario between unmanned ground and aerial vehicles.