Publications related to Barrier Smoothing for Nonsmooth Convex Minimization

Optimization Algorithms for Decentralized, Distributed and Collaborative Machine Learning

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

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

Perturbed Utility Stochastic Traffic Assignment

Rui Yao

This paper develops a fast algorithm for computing the equilibrium assignment with the perturbed utility route choice (PURC) model. Without compromise, this allows the significant advantages of the PURC model to be used in large-scale applications. We form ...

Informs2024

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

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

Training Efficient Controllers via Analytic Policy Gradient

Dario Floreano, Davide Scaramuzza, Valentin Wüest

Control design for robotic systems is complex and often requires solving an optimization to follow a trajectory accurately. Online optimization approaches like Model Predictive Control (MPC) have been shown to achieve great tracking performance, but requir ...

New York2023

Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum Minimization

Volkan Cevher, Ali Kavis, Leello Tadesse Dadi, Efstratios Panteleimon Skoulakis, Kimon Antonakopoulos

We propose an adaptive variance-reduction method, called AdaSpider, for minimization of L-smooth, non-convex functions with a finite-sum structure. In essence, AdaSpider combines an AdaGrad-inspired [Duchi et al., 2011, McMahan & Streeter, 2010], but a fai ...

2022

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

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

Momentum-Based Policy Gradient with Second-Order Information

Patrick Thiran, Saber Salehkaleybar, Negar Kiyavash, Mohammadsadegh Khorasani

Variance-reduced gradient estimators for policy gradient methods have been one of the main focus of research in the reinforcement learning in recent years as they allow acceleration of the estimation process. We propose a variance-reduced policy-gradient m ...

2022

Masked Training of Neural Networks with Partial Gradients

Martin Jaggi, Sebastian Urban Stich, Amirkeivan Mohtashami

State-of-the-art training algorithms for deep learning models are based on stochastic gradient descent (SGD). Recently, many variations have been explored: perturbing parameters for better accuracy (such as in Extra-gradient), limiting SGD updates to a sub ...

JMLR-JOURNAL MACHINE LEARNING RESEARCH2022

An Accelerated First-Order Method for Non-convex Optimization on Manifolds

Nicolas Boumal, Christopher Arnold Criscitiello

We describe the first gradient methods on Riemannian manifolds to achieve accelerated rates in the non-convex case. Under Lipschitz assumptions on the Riemannian gradient and Hessian of the cost function, these methods find approximate first-order critical ...

SPRINGER2022

On the Double Descent of Random Features Models Trained with SGD

Volkan Cevher, Fanghui Liu

We study generalization properties of random features (RF) regression in high dimensions optimized by stochastic gradient descent (SGD) in under-/overparameterized regime. In this work, we derive precise non-asymptotic error bounds of RF regression under b ...

2022

Information Retrieval Under Network Uncertainty: Robust Internet Ranking

Ralf Seifert, Anna Timonina-Farkas

Internet ranking algorithms play a crucial role in information technologies and numerical analysis due to their efficiency in high dimensions and wide range of possible applications, including scientometrics and systemic risk in finance (SinkRank, DebtRank ...

2023

Memory of Motion for Initializing Optimization in Robotics

Teguh Santoso Lembono

Many robotics problems are formulated as optimization problems. However, most optimization solvers in robotics are locally optimal and the performance depends a lot on the initial guess. For challenging problems, the solver will often get stuck at poor loc ...

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

Adaptation in Stochastic Algorithms: From Nonsmooth Optimization to Min-Max Problems and Beyond

Ahmet Alacaoglu

Stochastic gradient descent (SGD) and randomized coordinate descent (RCD) are two of the workhorses for training modern automated decision systems. Intriguingly, convergence properties of these methods are not well-established as we move away from the spec ...

EPFL2021

A first-order primal-dual method with adaptivity to local smoothness

Volkan Cevher, Maria-Luiza Vladarean

We consider the problem of finding a saddle point for the convex-concave objective

\min_x \max_y f(x) + \langle Ax, y\rangle - g^*(y)

, where

f

is a convex function with locally Lipschitz gradient and

g

is convex and possibly non-smooth. We propose an ...

2021

Large Steps in Inverse Rendering of Geometry

Wenzel Alban Jakob, Baptiste Alexandre Marie Philippe Claude Nicolet

Inverse reconstruction from images is a central problem in many scientific and engineering disciplines. Recent progress on differentiable rendering has led to methods that can efficiently differentiate the full process of image formation with respect to mi ...

ASSOC COMPUTING MACHINERY2021

Complexity analysis of stochastic gradient methods for PDE-constrained optimal control problems with uncertain parameters

Fabio Nobile, Matthieu Claude Martin, Sebastian Krumscheid

We consider the numerical approximation of an optimal control problem for an elliptic Partial Differential Equation (PDE) with random coefficients. Specifically, the control function is a deterministic, distributed forcing term that minimizes the expected ...

2021