Publications de Nicolas Henri Bernard Flammarion

Learning Algorithms in the Limit

Nicolas Henri Bernard Flammarion, Hristo Georgiev Papazov

This paper studies the problem of learning computable functions in the limit by extending Gold's inductive inference framework to incorporate computational observations and restricted input sources. Complimentary to the traditional Input-Output Observation ...

2025

Leveraging Continuous Time to Understand Momentum When Training Diagonal Linear Networks

Scott William Pesme, Nicolas Henri Bernard Flammarion, Hristo Georgiev Papazov

In this work, we investigate the effect of momentum on the optimisation trajectory of gradient descent. We leverage a continuous-time approach in the analysis of momentum gradient descent with step size

\gamma

and momentum parameter

\beta

that allows u ...

2024

(S)GD over Diagonal Linear Networks: Implicit Regularisation, Large Stepsizes and Edge of Stability

Scott William Pesme, Nicolas Henri Bernard Flammarion, Mathieu Even

In this paper, we investigate the impact of stochasticity and large stepsizes on the implicit regularisation of gradient descent (GD) and stochastic gradient descent (SGD) over diagonal linear networks. We prove the convergence of GD and SGD with macroscop ...

2023

Saddle-to-Saddle Dynamics in Diagonal Linear Networks

Scott William Pesme, Nicolas Henri Bernard Flammarion

In this paper we fully describe the trajectory of gradient flow over diagonal linear networks in the limit of vanishing initialisation. We show that the limiting flow successively jumps from a saddle of the training loss to another until reaching the minim ...

2023

Sparse-RS: A Versatile Framework for Query-Efficient Sparse Black-Box Adversarial Attacks

Maksym Andriushchenko, Nicolas Henri Bernard Flammarion, Francesco Croce

We propose a versatile framework based on random search, Sparse-RS, for score-based sparse targeted and untargeted attacks in the black-box setting. Sparse-RS does not rely on substitute models and achieves state-of-the-art success rate and query efficienc ...

ASSOC ADVANCEMENT ARTIFICIAL INTELLIGENCE2022

Trace norm regularization for multi-task learning with scarce data

Nicolas Henri Bernard Flammarion, Mikhail Konobeev, Etienne Patrice Boursier

Multi-task learning leverages structural similarities between multiple tasks to learn despite very few samples. Motivated by the recent success of neural networks applied to data-scarce tasks, we consider a linear low-dimensional shared representation mode ...

COLT2022

An Efficient Sampling Algorithm for Non-smooth Composite Potentials

Nicolas Henri Bernard Flammarion

We consider the problem of sampling from a density of the form p(x) ? exp(-f (x) - g(x)), where f : Rd-+ R is a smooth function and g : R-d-+ R is a convex and Lipschitz function. We propose a new algorithm based on the Metropolis-Hastings framework. Under ...

Microtome Publishing2022

Towards Understanding Sharpness-Aware Minimization

Maksym Andriushchenko, Nicolas Henri Bernard Flammarion

Sharpness-Aware Minimization (SAM) is a recent training method that relies on worst-case weight perturbations which significantly improves generalization in various settings. We argue that the existing justifications for the success of SAM which are based ...

JMLR-JOURNAL MACHINE LEARNING RESEARCH2022

Gradient flow dynamics of shallow ReLU networks for square loss and orthogonal inputs

Nicolas Henri Bernard Flammarion, Loucas Pillaud-Vivien, Etienne Patrice Boursier

The training of neural networks by gradient descent methods is a cornerstone of the deep learning revolution. Yet, despite some recent progress, a complete theory explaining its success is still missing. This article presents, for orthogonal input vectors, ...

NeurIPS2022

Implicit Bias of SGD for Diagonal Linear Networks: a Provable Benefit of Stochasticity

Scott William Pesme, Nicolas Henri Bernard Flammarion, Loucas Pillaud-Vivien

Understanding the implicit bias of training algorithms is of crucial importance in order to explain the success of overparametrised neural networks. In this paper, we study the dynamics of stochastic gradient descent over diagonal linear networks through i ...

2021

Is there an analog of Nesterov acceleration for gradient-based MCMC?

Xiang Cheng, Nicolas Henri Bernard Flammarion

We formulate gradient-based Markov chain Monte Carlo (MCMC) sampling as optimization on the space of probability measures, with Kullback-Leibler (KL) divergence as the objective functional. We show that an under-damped form of the Langevin algorithm perfor ...

2021

Last iterate convergence of SGD for Least-Squares in the Interpolation regime

Aditya Vardhan Varre, Nicolas Henri Bernard Flammarion, Loucas Pillaud-Vivien

Motivated by the recent successes of neural networks that have the ability to fit the data perfectly \emph{and} generalize well, we study the noiseless model in the fundamental least-squares setup. We assume that an optimum predictor fits perfectly inputs ...

Advances in Neural Information Processing Systems 20212021

A Continuized View on Nesterov Acceleration

Nicolas Henri Bernard Flammarion, Raphaël Jean Berthier

We introduce the "continuized" Nesterov acceleration, a close variant of Nesterov acceleration whose variables are indexed by a continuous time parameter. The two variables continuously mix following a linear ordinary differential equation and take gradien ...

2021

Understanding and Improving Fast Adversarial Training

Maksym Andriushchenko, Nicolas Henri Bernard Flammarion

A recent line of work focused on making adversarial training computationally efficient for deep learning models. In particular, Wong et al. (2020) showed that ℓ∞-adversarial training with fast gradient sign method (FGSM) can fail due to a phenomenon called ...

2020

Square Attack: a query-efficient black-box adversarial attack via random search

Maksym Andriushchenko, Nicolas Henri Bernard Flammarion, Francesco Croce

We propose the Square Attack, a new score-based black-box

l_2

and

l_\infty

adversarial attack that does not rely on local gradient information and thus is not affected by gradient masking. The Square Attack is based on a randomized search scheme where ...

2020

Online Robust Regression via SGD on the l1 loss

Scott William Pesme, Nicolas Henri Bernard Flammarion

We consider the robust linear regression problem in the online setting where we have access to the data in a streaming manner, one data point after the other. More specifically, for a true parameter , we consider the corrupted Gaussian linear model $ y=\la ...

2020

On Convergence-Diagnostic based Step Sizes for Stochastic Gradient Descent

Aymeric Daphnis Kévin Dieuleveut, Scott William Pesme, Nicolas Henri Bernard Flammarion

Constant step-size Stochastic Gradient Descent exhibits two phases: a transient phase during which iterates make fast progress towards the optimum, followed by a stationary phase during which iterates oscillate around the optimal point. In this paper, we s ...

2020

Sparse-RS: a versatile framework for query-efficient sparse black-box adversarial attacks

Maksym Andriushchenko, Nicolas Henri Bernard Flammarion, Francesco Croce

A large body of research has focused on adversarial attacks which require to modify all input features with small l2- or l∞-norms. In this paper we instead focus on query-efficient sparse attacks in the black-box setting. Our versatile framework, Sparse-RS ...

2020