Publications associées à UNDERGRAD: A Universal Black-Box Optimization Method with Almost Dimension-Free Convergence Rate Guarantees

Publications associées (34)

The topology of a chaotic attractor in the Kuramoto-Sivashinsky equation

The Birman-Williams theorem gives a connection between the collection of unstable periodic orbits (UPOs) contained within a chaotic attractor and the topology of that attractor, for three-dimensional systems. In certain cases, the fractal dimension of a ch ...

2025

Enabling Uncertainty Estimation in Iterative Neural Networks

Pascal Fua, Minh Hieu Lê, Doruk Oner, Nikita Durasov

Turning pass-through network architectures into iterative ones, which use their own output as input, is a well-known approach for boosting performance. In this paper, we argue that such architectures offer an additional benefit: The convergence rate of the ...

Curran Associates2024

Optimization Algorithms for Decentralized, Distributed and Collaborative Machine Learning

Anastasiia Koloskova

Distributed learning is the key for enabling training of modern large-scale machine learning models, through parallelising the learning process. Collaborative learning is essential for learning from privacy-sensitive data that is distributed across various ...

EPFL2024

Scalable constrained optimization

Maria-Luiza Vladarean

Modern optimization is tasked with handling applications of increasingly large scale, chiefly due to the massive amounts of widely available data and the ever-growing reach of Machine Learning. Consequently, this area of research is under steady pressure t ...

EPFL2024

Understanding generalization and robustness in modern deep learning

Maksym Andriushchenko

In this thesis, we study two closely related directions: robustness and generalization in modern deep learning. Deep learning models based on empirical risk minimization are known to be often non-robust to small, worst-case perturbations known as adversari ...

EPFL2024

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

Fast convergence to non-isolated minima: four equivalent conditions for C2 functions

Nicolas Boumal, Quentin Rebjock

Optimization algorithms can see their local convergence rates deteriorate when the Hessian at the optimum is singular. These singularities are inescapable when the optima are non-isolated. Yet, under the right circumstances, several algorithms preserve the ...

2024

Augmented Lagrangian Methods for Provable and Scalable Machine Learning

Mehmet Fatih Sahin

Non-convex constrained optimization problems have become a powerful framework for modeling a wide range of machine learning problems, with applications in k-means clustering, large- scale semidefinite programs (SDPs), and various other tasks. As the perfor ...

EPFL2023

Well-posedness Issues For the Half-Wave Maps Equation With Hyperbolic And Spherical Targets

Yang Liu

This thesis is a study of the global well-posedness of the Cauchy problems for half-wave maps from the Minkowski space of dimension n+1 to the 2-dimensional sphere and the hyperbolic plane. The work is mainly based on the results from Krieger-Sire 17' in ...

EPFL2023

Universal and adaptive methods for robust stochastic optimization

Ali Kavis

Within the context of contemporary machine learning problems, efficiency of optimization process depends on the properties of the model and the nature of the data available, which poses a significant problem as the complexity of either increases ad infinit ...

EPFL2023

A Spatial Branch and Bound Algorithm for Continuous Pricing with Advanced Discrete Choice Demand Modeling

Michel Bierlaire

In this paper, we present a spatial branch and bound algorithm to tackle the continuous pricing problem, where demand is captured by an advanced discrete choice model (DCM). Advanced DCMs, like mixed logit or latent class models, are capable of modeling de ...

2023

Probabilistic methods for neural combinatorial optimization

Nikolaos Karalias

The monumental progress in the development of machine learning models has led to a plethora of applications with transformative effects in engineering and science. This has also turned the attention of the research community towards the pursuit of construc ...

EPFL2023

Benign Overfitting in Deep Neural Networks under Lazy Training

Volkan Cevher, Grigorios Chrysos, Fanghui Liu, Zhenyu Zhu

This paper focuses on over-parameterized deep neural networks (DNNs) with ReLU activation functions and proves that when the data distribution is well-separated, DNNs can achieve Bayesoptimal test error for classification while obtaining (nearly) zero-trai ...

2023

Safe Zeroth-Order Convex Optimization Using Quadratic Local Approximations

Giancarlo Ferrari Trecate, Yuning Jiang, Maryam Kamgarpour, Baiwei Guo

We address black-box convex optimization problems, where the objective and constraint functions are not explicitly known but can be sampled within the feasible set. The challenge is thus to generate a sequence of feasible points converging towards an optim ...

IEEE2023

On The Convergence Of Stochastic Primal-Dual Hybrid Gradient

Volkan Cevher, Ahmet Alacaoglu

In this paper, we analyze the recently proposed stochastic primal-dual hybrid gradient (SPDHG) algorithm and provide new theoretical results. In particular, we prove almost sure convergence of the iterates to a solution with convexity and linear convergenc ...

SIAM PUBLICATIONS2022

Proximal Point Imitation Learning

Volkan Cevher, Luca Viano, Igor Krawczuk

This work develops new algorithms with rigorous efficiency guarantees for infinite horizon imitation learning (IL) with linear function approximation without restrictive coherence assumptions. We begin with the minimax formulation of the problem and then o ...

2022

Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization

Volkan Cevher, Alp Yurtsever, Maria-Luiza Vladarean

We propose a stochastic conditional gradient method (CGM) for minimizing convex finitesum objectives formed as a sum of smooth and non-smooth terms. Existing CGM variants for this template either suffer from slow convergence rates, or require carefully inc ...

2022

Towards Verifiable, Generalizable and Efficient Robust Deep Neural Networks

Chen Liu

In the last decade, deep neural networks have achieved tremendous success in many fields of machine learning. However, they are shown vulnerable against adversarial attacks: well-designed, yet imperceptible, perturbations can make the state-of-the-art deep ...

EPFL2022

Iterative pre-conditioning for expediting the distributed gradient-descent method: The case of linear least-squares problem

Nirupam Gupta

This paper considers the multi-agent linear least-squares problem in a server-agent network architecture. The system comprises multiple agents, each with a set of local data points. The agents are connected to a server, and there is no inter-agent communic ...

PERGAMON-ELSEVIER SCIENCE LTD2022

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