UNDERGRAD: A Universal Black-Box Optimization Method with Almost Dimension-Free Convergence Rate Guarantees

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

UNDERGRAD: A Universal Black-Box Optimization Method with Almost Dimension-Free Convergence Rate Guarantees

Chat with Graph Search

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

Enabling Uncertainty Estimation in Iterative Neural Networks

Optimization Algorithms for Decentralized, Distributed and Collaborative Machine Learning

Scalable constrained optimization

Understanding generalization and robustness in modern deep learning

Leveraging Continuous Time to Understand Momentum When Training Diagonal Linear Networks

Augmented Lagrangian Methods for Provable and Scalable Machine Learning

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

Universal and adaptive methods for robust stochastic optimization

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

Probabilistic methods for neural combinatorial optimization

Benign Overfitting in Deep Neural Networks under Lazy Training

Safe Zeroth-Order Convex Optimization Using Quadratic Local Approximations

On The Convergence Of Stochastic Primal-Dual Hybrid Gradient

Proximal Point Imitation Learning

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

Towards Verifiable, Generalizable and Efficient Robust Deep Neural Networks

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

Towards Understanding Sharpness-Aware Minimization

On the Double Descent of Random Features Models Trained with SGD