Publication

Separation with restricted families of sets

Publications associées (28)

Stochastic homogenization of degenerate integral functionals with linear growth

We study the limit behaviour of sequences of non-convex, vectorial, random integral functionals, defined on W1,1, whose integrands are ergodic and satisfy degenerate linear growth conditions. The latter involve suitable random, scale-dependent weight-funct ...

2023

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

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

Localizing Unsynchronized Sensors With Unknown Sources

Ivan Dokmanic, Dalia Salem Hassan Fahmy El Badawy

We propose a method for sensor array self-localization using a set of sources at unknown locations. The sources produce signals whose times of arrival are registered at the sensors. We look at the general case where neither the emission times of the source ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2023

T-5 configurations and hyperbolic systems

Carl Johan Peter Johansson, Riccardo Tione

In this paper, we study the rank-one convex hull of a differential inclusion associated to entropy solutions of a hyperbolic system of conservation laws. This was introduced in [B. Kirchheim, S. Muller and V. S(sic)ver & aacute;k, Studying Nonlinear PDE by ...

WORLD SCIENTIFIC PUBL CO PTE LTD2023

Safe Zeroth-Order Convex Optimization Using Quadratic Local Approximations

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

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

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

Stochastic distributed learning with gradient quantization and double-variance reduction

Sebastian Urban Stich, Konstantin Mishchenko

We consider distributed optimization over several devices, each sending incremental model updates to a central server. This setting is considered, for instance, in federated learning. Various schemes have been designed to compress the model updates in orde ...

TAYLOR & FRANCIS LTD2022

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

A convex set of robust D—stabilizing controllers using Cauchy's argument principle

Alireza Karimi, Philippe Louis Schuchert

A new approach is presented to obtain a convex set of robust D—stabilizing fixed structure controllers, relying on Cauchy's argument principle. A convex set of D—stabilizing controllers around an initial D—stabilizing controller for a multi-model set is re ...

Elsevier2022

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

Finding stationary points on bounded-rank matrices: a geometric hurdle and a smooth remedy

Nicolas Boumal

We consider the problem of provably finding a stationary point of a smooth function to be minimized on the variety of bounded-rank matrices. This turns out to be unexpectedly delicate. We trace the difficulty back to a geometric obstacle: On a nonsmooth se ...

SPRINGER HEIDELBERG2022

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

Proximal Point Imitation Learning

Volkan Cevher, Angeliki Kamoutsi, Igor Krawczuk, Luca Viano

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

Asymptotic Errors for Teacher-Student Convex Generalized Linear Models (Or: How to Prove Kabashima’s Replica Formula)

Florent Gérard Krzakala, Alia Abbara

There has been a recent surge of interest in the study of asymptotic reconstruction performance in various cases of generalized linear estimation problems in the teacher-student setting, especially for the case of i.i.d standard normal matrices. Here, we g ...

2022

Predicting in Uncertain Environments: Methods for Robust Machine Learning

Paul Thierry Yves Rolland

One of the main goal of Artificial Intelligence is to develop models capable of providing valuable predictions in real-world environments. In particular, Machine Learning (ML) seeks to design such models by learning from examples coming from this same envi ...

EPFL2022

Learning of Continuous and Piecewise-Linear Functions With Hessian Total-Variation Regularization

Michaël Unser, Joaquim Gonçalves Garcia Barreto Campos, Shayan Aziznejad

We develop a novel 2D functional learning framework that employs a sparsity-promoting regularization based on second-order derivatives. Motivated by the nature of the regularizer, we restrict the search space to the span of piecewise-linear box splines shi ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2022

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

Critical Parameters for Scalable Distributed Learning with Large Batches and Asynchronous Updates

Martin Jaggi, Sebastian Urban Stich, Amirkeivan Mohtashami

It has been experimentally observed that the efficiency of distributed training with stochastic gradient (SGD) depends decisively on the batch size and—in asynchronous implementations—on the gradient staleness. Especially, it has been observed that the spe ...

MICROTOME PUBLISHING2021

Convex optimization in sums of Banach spaces

Michaël Unser, Shayan Aziznejad

We characterize the solution of a broad class of convex optimization problems that address the reconstruction of a function from a finite number of linear measurements. The underlying hypothesis is that the solution is decomposable as a finite sum of compo ...

2021

Publications associées (28)

\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

Critical Parameters for Scalable Distributed Learning with Large Batches and Asynchronous Updates

Martin Jaggi, Sebastian Urban Stich, Amirkeivan Mohtashami

MICROTOME PUBLISHING2021

Convex optimization in sums of Banach spaces

Michaël Unser, Shayan Aziznejad

2021