Publications related to Augmented Lagrangian Methods for Provable and Scalable Machine Learning

On The Convergence Of Stochastic Primal-Dual Hybrid Gradient

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

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

Neural System Level Synthesis: Learning over All Stabilizing Policies for Nonlinear Systems

Giancarlo Ferrari Trecate, Luca Furieri, Clara Lucía Galimberti

We address the problem of designing stabilizing control policies for nonlinear systems in discrete-time, while minimizing an arbitrary cost function. When the system is linear and the cost is convex, the System Level Synthesis (SLS) approach offers an effe ...

IEEE2022

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

Proximal Point Imitation Learning

Volkan Cevher, Luca Viano, Igor Krawczuk, Angeliki Kamoutsi

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

Geometrical Treatise on the Modelling of 3D Particulate Inclusion-Matrix Microstructures with an Application to Historical Stone Masonry Walls

Mahmoud S. M. Shaqfa

As historical stone masonry structures are vulnerable and prone to damage in earthquakes, investigating their structural integrity is important to reduce injuries and casualties while preserving their historical value. Stone masonry is a composite material ...

EPFL2022

Stochastic Second-Order Methods Improve Best-Known Sample Complexity of SGD for Gradient-Dominated Function

Patrick Thiran, Negar Kiyavash, Saber Salehkaleybar

We study the performance of Stochastic Cubic Regularized Newton (SCRN) on a class of functions satisfying gradient dominance property with

1\le\alpha\le2

which holds in a wide range of applications in machine learning and signal processing. This conditio ...

NeurIPS2022

Extra Newton: A First Approach to Noise-Adaptive Accelerated Second-Order Methods

Volkan Cevher, Kimon Antonakopoulos, Ali Kavis

This work proposes a universal and adaptive second-order method for minimizing second-order smooth, convex functions. Our algorithm achieves O(σ/T‾‾√) convergence when the oracle feedback is stochastic with variance σ2, and improves its convergence to O(1/ ...

2022

High-dimensional optimization under nonconvex excluded volume constraints

Antonio Sclocchi

We consider high-dimensional random optimization problems where the dynamical variables are subjected to nonconvex excluded volume constraints. We focus on the case in which the cost function is a simple quadratic cost and the excluded volume constraints a ...

AMER PHYSICAL SOC2022

Binary Perceptron: Efficient Algorithms Can Find Solutions in a RareWell-Connected Cluster

Emmanuel Abbé

It was recently shown that almost all solutions in the symmetric binary perceptron are isolated, even at low constraint densities, suggesting that finding typical solutions is hard. In contrast, some algorithms have been shown empirically to succeed in fin ...

ASSOC COMPUTING MACHINERY2022

Augmented Lagrangian Methods for Provable and Scalable Machine Learning

Graph Chatbot

Chat with Graph Search

On The Convergence Of Stochastic Primal-Dual Hybrid Gradient

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

Neural System Level Synthesis: Learning over All Stabilizing Policies for Nonlinear Systems

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

Proximal Point Imitation Learning

Geometrical Treatise on the Modelling of 3D Particulate Inclusion-Matrix Microstructures with an Application to Historical Stone Masonry Walls

Stochastic Second-Order Methods Improve Best-Known Sample Complexity of SGD for Gradient-Dominated Function

Extra Newton: A First Approach to Noise-Adaptive Accelerated Second-Order Methods

High-dimensional optimization under nonconvex excluded volume constraints

Binary Perceptron: Efficient Algorithms Can Find Solutions in a RareWell-Connected Cluster

Extra Newton: A First Approach to Noise-Adaptive Accelerated Second-Order Methods

Proximal Point Imitation Learning

Binary Perceptron: Efficient Algorithms Can Find Solutions in a RareWell-Connected Cluster

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

High-dimensional optimization under nonconvex excluded volume constraints

On The Convergence Of Stochastic Primal-Dual Hybrid Gradient

Geometrical Treatise on the Modelling of 3D Particulate Inclusion-Matrix Microstructures with an Application to Historical Stone Masonry Walls

Neural System Level Synthesis: Learning over All Stabilizing Policies for Nonlinear Systems

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

Stochastic Second-Order Methods Improve Best-Known Sample Complexity of SGD for Gradient-Dominated Function