El Houcine Bergou

Dr. El Houcine Bergou


Research Focus & Metrics

Academic Career Length

9Years (2018-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
6 April 2020 in arXiv
Verified
Preprint
Open access
PDF file
EBEl Houcine Bergou
El Houcine Bergou
YDY. Diouane
Y. Diouane
VKVyacheslav Kungurtsev
Vyacheslav Kungurtsev
The Levenberg-Marquardt algorithm is one of the most popular algorithms for finding the solution of nonlinear least squares problems. Across different modified variations of the basic procedure, the algorithm enjoys global convergence, a competitive worst case iteration complexity rate, and a guaranteed rate of local convergence for both zero and nonzero small residual problems, under suitable assumptions. We introduce a novel Levenberg-Marquardt method that matches, simultaneously, the state of the art in all of these convergence properties with a single seamless algorithm. Numerical experiments confirm the theoretical behavior of our proposed algorithm.

7 May 2019 in arXiv
Verified
Preprint
Open access
PDF file
EBEl Houcine Bergou
El Houcine Bergou
EGEduard Gorbunov
Eduard Gorbunov
PRPeter Richtárik
Peter Richtárik
In this paper we consider the unconstrained minimization problem of a smooth function in ${\mathbb{R}}^n$ in a setting where only function evaluations are possible. We design a novel randomized derivative-free algorithm --- the stochastic three points (STP) method --- and analyze its iteration complexity. At each iteration, STP generates a random search direction according to a certain fixed probability law. Our assumptions on this law are very mild: roughly speaking, all laws which do not concentrate all measure on any halfspace passing through the origin will work. For instance, we allow for the uniform distribution on the sphere and also distributions that concentrate all measure on a positive spanning set. Given a current iterate $x$, STP compares the objective function at three points: $x$, $x+\alpha s$ and $x-\alpha s$, where $\alpha>0$ is a stepsize parameter and $s$ is the random search direction. The best of these three points is the next iterate. We analyze the method STP under several stepsize selection schemes (fixed, decreasing, estimated through finite differences, etc). We study non-convex, convex and strongly convex cases.

16 February 2020 in arXiv
Verified
Preprint
Open access
PDF file
EGEduard Gorbunov
Eduard Gorbunov
ABAdel Bibi
Adel Bibi
OSOzan Sener
Ozan Sener
EBEl Houcine Bergou
El Houcine Bergou
PRPeter Richtárik
Peter Richtárik
We consider the problem of unconstrained minimization of a smooth objective function in $\mathbb{R}^d$ in setting where only function evaluations are possible. We propose and analyze stochastic zeroth-order method with heavy ball momentum. In particular, we propose, SMTP, a momentum version of the stochastic three-point method (STP) \cite{Bergou_2018}. We show new complexity results for non-convex, convex and strongly convex functions. We test our method on a collection of learning to continuous control tasks on several MuJoCo \cite{Todorov_2012} environments with varying difficulty and compare against STP, other state-of-the-art derivative-free optimization algorithms and against policy gradient methods. SMTP significantly outperforms STP and all other methods that we considered in our numerical experiments. Our second contribution is SMTP with importance sampling which we call SMTP_IS. We provide convergence analysis of this method for non-convex, convex and strongly convex objectives.

6 April 2020 in arXiv
Verified
Preprint
Open access
PDF file
EBEl Houcine Bergou
El Houcine Bergou
YDY. Diouane
Y. Diouane
VKVyacheslav Kungurtsev
Vyacheslav Kungurtsev
In this note we consider the iteration complexity of solving strongly convex multi objective optimization. We discuss the precise meaning of this problem, and indicate it is loosely defined, but the most natural notion is to find a set of Pareto optimal points across a grid of scalarized problems. We derive that in most cases, performing sensitivity based path-following after obtaining one solution is the optimal strategy for this task in terms of iteration complexity.

30 June 2021 in arXiv
Verified
Preprint
Open access
PDF file
EBEl Houcine Bergou
El Houcine Bergou
YDYoussef Diouane
Youssef Diouane
VKVladimir Kunc
Vladimir Kunc
VKVyacheslav Kungurtsev
Vyacheslav Kungurtsev
CRClément W. Royer
Clément W. Royer
In many contemporary optimization problems such as those arising in machine learning, it can be computationally challenging or even infeasible to evaluate an entire function or its derivatives. This motivates the use of stochastic algorithms that sample problem data, which can jeopardize the guarantees obtained through classical globalization techniques in optimization such as a trust region or a line search. Using subsampled function values is particularly challenging for the latter strategy, which relies upon multiple evaluations. On top of that all, there has been an increasing interest for nonconvex formulations of data-related problems, such as training deep learning models. For such instances, one aims at developing methods that converge to second-order stationary points quickly, i.e., escape saddle points efficiently. This is particularly delicate to ensure when one only accesses subsampled approximations of the objective and its derivatives. In this paper, we describe a stochastic algorithm based on negative curvature and Newton-type directions that are computed for a subsampling model of the objective. A line-search technique is used to enforce suitable decrease for this model, and for a sufficiently large sample, a similar amount of reduction holds for the true objective. By using probabilistic reasoning, we can then obtain worst-case complexity guarantees for our framework, leading us to discuss appropriate notions of stationarity in a subsampling context. Our analysis encompasses the deterministic regime, and allows us to identify sampling requirements for second-order line-search paradigms. As we illustrate through real data experiments, these worst-case estimates need not be satisfied for our method to be competitive with first-order strategies in practice.

29 May 2018 in arXiv
Verified
Preprint
Open access
PDF file
EBEl Houcine Bergou
El Houcine Bergou
YDYoussef Diouane
Youssef Diouane
SGSerge Gratton
Serge Gratton
Adaptive regularized framework using cubics has emerged as an alternative to line-search and trust-region algorithms for smooth nonconvex optimization, with an optimal complexity amongst second-order methods. In this paper, we propose and analyze the use of an iteration dependent scaled norm in the adaptive regularized framework using cubics. Within such scaled norm, the obtained method behaves as a line-search algorithm along the quasi-Newton direction with a special backtracking strategy. Under appropriate assumptions, the new algorithm enjoys the same convergence and complexity properties as adaptive regularized algorithm using cubics. The complexity for finding an approximate first-order stationary point can be improved to be optimal whenever a second order version of the proposed algorithm is regarded. In a similar way, using the same scaled norm to define the trust-region neighborhood, we show that the trust-region algorithm behaves as a line-search algorithm. The good potential of the obtained algorithms is shown on a set of large scale optimization problems.