Publications by Nicolas Henri Bernard Flammarion

Related publications (18)

An Efficient Sampling Algorithm for Non-smooth Composite Potentials

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

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

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

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

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

Nicolas Henri Bernard Flammarion, Scott William Pesme, 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

Online Robust Regression via SGD on the l1 loss

Nicolas Henri Bernard Flammarion, Scott William Pesme

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

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

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

On Convergence-Diagnostic based Step Sizes for Stochastic Gradient Descent

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

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

Saddle-to-Saddle Dynamics in Diagonal Linear Networks

Nicolas Henri Bernard Flammarion, Scott William Pesme

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

Leveraging Continuous Time to Understand Momentum When Training Diagonal Linear Networks

Nicolas Henri Bernard Flammarion, Scott William Pesme, 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

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

Nicolas Henri Bernard Flammarion, Maksym Andriushchenko, 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

Understanding and Improving Fast Adversarial Training

Nicolas Henri Bernard Flammarion, Maksym Andriushchenko

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

Towards Understanding Sharpness-Aware Minimization

Nicolas Henri Bernard Flammarion, Maksym Andriushchenko

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

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

Nicolas Henri Bernard Flammarion, Scott William Pesme

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

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

Nicolas Henri Bernard Flammarion, Maksym Andriushchenko, 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

Mikhail Konobeev, Nicolas Henri Bernard Flammarion, 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

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

Nicolas Henri Bernard Flammarion, Maksym Andriushchenko, 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

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