A proximal Newton framework for composite minimization: Graph learning without Cholesky decompositions and matrix inversions

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

This paper investigates the fundamental regression task of learning k neurons (a.k.a. teachers) from Gaussian input, using two-layer ReLU neural networks with width m (a.k.a. students) and m, k = O(1), trained via gradient descent under proper initializati ...

For any 𝜀 > 0, we prove that 𝑘-Dimensional Matching is hard to approximate within a factor of 𝑘/(12+𝜀) for large 𝑘 unless NP ⊆ BPP. Listed in Karp’s 21 NP-complete problems, 𝑘-Dimensional Matching is a benchmark computational complexity problem which we fi ...

In decentralized optimization, nodes of a communication network each possess a local objective function, and communicate using gossip-based methods in order to minimize the average of these per-node functions. While synchronous algorithms are heavily impac ...

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 ...

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 ...

In this PhD manuscript, we explore optimisation phenomena which occur in complex neural networks through the lens of

2

-layer diagonal linear networks. This rudimentary architecture, which consists of a two layer feedforward linear network with a diagonal ...

Orthogonal group synchronization is the problem of estimating n elements Z(1),& mldr;,Z(n) from the rxr orthogonal group given some relative measurements R-ij approximate to Z(i)Z(j)(-1). The least-squares formulation is nonconvex. To avoid its local minim ...

Spectral algorithms are some of the main tools in optimization and inference problems on graphs. Typically, the graph is encoded as a matrix and eigenvectors and eigenvalues of the matrix are then used to solve the given graph problem. Spectral algorithms ...

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 ...

In this paper, we present a new parameterization and optimization procedure for minimizing the weight of ribbed plates. The primary goal is to reduce embodied CO2 in concrete floors as part of the effort to diminish the carbon footprint of the construction ...

We develop new tools to study landscapes in nonconvex optimization. Given one optimization problem, we pair it with another by smoothly parametrizing the domain. This is either for practical purposes (e.g., to use smooth optimization algorithms with good g ...

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 ...

We present a combination technique based on mixed differences of both spatial approximations and quadrature formulae for the stochastic variables to solve efficiently a class of optimal control problems (OCPs) constrained by random partial differential equ ...

Established techniques that enable robots to learn from demonstrations are based on learning a stable dynamical system (DS). To increase the robots' resilience to perturbations during tasks that involve static obstacle avoidance, we propose incorporating b ...

While momentum-based accelerated variants of stochastic gradient descent (SGD) are widely used when training machine learning models, there is little theoretical understanding on the generalization error of such methods. In this work, we first show that th ...

. We study very weak solutions to scalar Euler-Lagrange equations associated with quadratic convex functionals. We investigate whether W1,1 solutions are necessarily W 1,2 Nash and Schauder applicable. We answer this question positively for a suitable clas ...

Quantum support vector machines employ quantum circuits to define the kernel function. It has been shown that this approach offers a provable exponential speedup compared to any known classical algorithm for certain data sets. The training of such models c ...

In this paper, we propose a reduced-order modeling strategy for two-way Dirichlet-Neumann parametric coupled problems solved with domain-decomposition (DD) sub-structuring methods. We split the original coupled differential problem into two sub-problems wi ...

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 ...

Given a sequence of functions

f_1,\ldots,f_n

with

f_i:\mathcal{D}\mapsto \mathbb{R}

, finite-sum minimization seeks a point

{x}^\star \in \mathcal{D}

minimizing

\sum_{j=1}^nf_j(x)/n

. In this work, we propose a key twist into the finite-sum minimizat ...

A proximal Newton framework for composite minimization: Graph learning without Cholesky decompositions and matrix inversions

Chattez avec Graph Search

How Gradient Descent Balances Features: A Dynamical Analysis For Two-Layer Neural Networks

Asymptotically Optimal Hardness for 𝑘-Set Packing and 𝑘-Matroid Intersection

Asynchronous Speedup in Decentralized Optimization

Optimization Algorithms for Decentralized, Distributed and Collaborative Machine Learning

Perturbed Utility Stochastic Traffic Assignment

Deep Learning Theory Through the Lens of Diagonal Linear Networks

BENIGN LANDSCAPES OF LOW-DIMENSIONAL RELAXATIONS FOR ORTHOGONAL SYNCHRONIZATION ON GENERAL GRAPHS

The Power of Two Matrices in Spectral Algorithms for Community Recovery

Scalable constrained optimization

Mesh-based topology, shape and sizing optimization of ribbed plates

The effect of smooth parametrizations on nonconvex optimization landscapes

Understanding generalization and robustness in modern deep learning

A Combination Technique for Optimal Control Problems Constrained by Random PDEs

Learning Barrier-Certified Polynomial Dynamical Systems for Obstacle Avoidance with Robots

On the Generalization of Stochastic Gradient Descent with Momentum

WILD SOLUTIONS TO SCALAR EULER-LAGRANGE EQUATIONS

The complexity of quantum support vector machines

A Reduced Order Model for Domain Decompositions with Non-conforming Interfaces

Leveraging Continuous Time to Understand Momentum When Training Diagonal Linear Networks

Efficient Continual Finite-Sum Minimization