Convex function

In mathematics, a real-valued function is called convex if the line segment between any two distinct points on the graph of the function lies above the graph between the two points. Equivalently, a function is convex if its epigraph (the set of points on or above the graph of the function) is a convex set. A twice-differentiable function of a single variable is convex if and only if its second derivative is nonnegative on its entire domain. Well-known examples of convex functions of a single variable include a linear function f(x) = cx (where c is a real number), a quadratic function cx^2 (c as a nonnegative real number) and a exponential function ce^x (c as a nonnegative real number). In simple terms, a convex function refers to a function whose graph is shaped like a cup \cup (or a straight line like a linear function), while a concave function's graph is shaped like a cap \cap

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (76)

Related publications

Related people (12)

Related people

Related units (10)

Related units

Related concepts (51)

Related concepts

Related courses (87)

Related courses

Related lectures (261)

Related lectures

Regularity in metric spaces

Serguei Timochine

Using arguments developed by De Giorgi in the 1950's, it is possible to prove the regularity of the solutions to a vast class of variational problems in the Euclidean space. The main goal of the present thesis is to extend these results to the more abstract context of metric spaces with a measure. In particular, working in the axiomatic framework of Gol'dshtein – Troyanov, we establish both the interior and the boundary regularity of quasi-minimizers of the p-Dirichlet energy. Our proof works for quite general domains, assuming some natural hypotheses on the (axiomatic) D-structure. Furthermore, we prove analogous results for extremal functions lying in the class of Sobolev functions in the sense of Hajłasz – Koskela, i.e. functions characterized by the single condition that a Poincaré inequality be satisfied. Our strategy to prove these regularity results is first to show that, in a very general setting, the (Hölder) continuity of a function is a consequence of three specific technical hypotheses. This part of the argument is the essence of the De Giorgi method. Then, we verify that for a function u which is a quasi-minimizer in an axiomatic Sobolev space or an extremal Sobolev function in the sense of Hajłasz – Koskela, these technical hypotheses are indeed satisfied and u is thus (Hölder) continuous. In addition to that, we establish the Harnack's inequality for these extremal functions, and we show that the Dirichlet semi-norm of a piecewise-extremal function is equivalent to the sum of the Dirichlet semi-norms of its components.

EPFL2006

Adaptive Gradient Descent without Descent

Konstantin Mishchenko

We present a strikingly simple proof that two rules are sufficient to automate gradient descent: 1) don’t increase the stepsize too fast and 2) don’t overstep the local curvature. No need for functional values, no line search, no information about the function except for the gradients. By following these rules, you get a method adaptive to the local geometry, with convergence guarantees depending only on the smoothness in a neighborhood of a solution. Given that the problem is convex, our method converges even if the global smoothness constant is infinity. As an illustration, it can minimize arbitrary continuously twice differentiable convex function. We examine its performance on a range of convex and nonconvex problems, including logistic regression and matrix factorization.

2020

Stochastic distributed learning with gradient quantization and double-variance reduction

Konstantin Mishchenko, Sebastian Urban Stich

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 order to reduce the overall communication cost. However, existing methods suffer from a significant slowdown due to additional variance omega > 0 coming from the compression operator and as a result, only converge sublinearly. What is needed is a variance reduction technique for taming the variance introduced by compression. We propose the first methods that achieve linear convergence for arbitrary compression operators. For strongly convex functions with condition number kappa, distributed among n machines with a finite-sum structure, each worker having less than in components, we also (i) give analysis for the weakly convex and the non-convex cases and (ii) verify in experiments that our novel variance reduced schemes are more efficient than the baselines. Moreover, we show theoretically that as the number of devices increases, higher compression levels are possible without this affecting the overall number of communications in comparison with methods that do not perform any compression. This leads to a significant reduction in communication cost. Our general analysis allows to pick the most suitable compression for each problem, finding the rig ht balance between additional variance and communication savings. Finally, we also (iii) give analysis for arbitrary quantized updates.

TAYLOR & FRANCIS LTD2022

EE-556: Mathematics of data: from theory to computation

This course provides an overview of key advances in continuous optimization and statistical analysis for machine learning. We review recent learning formulations and models as well as their guarantees, describe scalable solution techniques and algorithms, and illustrate the trade-offs involved.

CS-233(a): Introduction to machine learning (BA3)

Machine learning and data analysis are becoming increasingly central in many sciences and applications. In this course, fundamental principles and methods of machine learning will be introduced, analyzed and practically implemented.

DH-406: Machine learning for DH

This course aims to introduce the basic principles of machine learning in the context of the digital humanities. We will cover both supervised and unsupervised learning techniques, and study and implement methods to analyze diverse data types, such as images, music and social network data.

Mathematical optimization

Mathematical optimization (alternatively spelled optimisation) or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternative

Convex set

In geometry, a subset of a Euclidean space, or more generally an affine space over the reals, is convex if, given any two points in the subset, the subset contains the whole line segment that joins

Derivative

In mathematics, the derivative shows the sensitivity of change of a function's output with respect to the input. Derivatives are a fundamental tool of calculus. For example, the derivative of the p