Author: isadorenabi

Duchi et. al. (2008) (Reference 1) has a simple and efficient algorithm for projecting a point onto the simplex. Formally, the optimization problem is where represents the Euclidean norm and is some constant. Their algorithm runs in time, with the most expensive step being sorting the elements of in descending order. Here is the algorithm: […]

O(n log n) algorithm for Euclidean projection onto a simplex

Relations and resolvents A relation on is a subset of . We use the notation to mean the set . You can think of as an operator that maps vectors to sets . (Along this line of thinking, functions are a special kind of relation where every vector is mapped to a set consisting of […]

Relations, resolvents and the proximal operator

Let be a convex function. Moreau’s Decomposition Theorem is the following result: Theorem (Moreau Decomposition). For all , , where is the proximal operator for and is the convex conjugate of . Here is the proof: Let . Then, The second equivalence is a result involving convex conjugates and subdifferentials (see this post for statement […]

What is Moreau’s Decomposition Theorem?

Convex conjugate functions and Fenchel’s inequality Let be some function. The convex conjugate of (also know as the Fenchel transformation), is the function defined as Fenchel’s equality is the following statement: Theorem (Fenchel’s inequality). For any , The proof of Fenchel’s equality follows directly from the definition of the convex conjugate: A direct application of […]

Convex conjugate functions, Fenchel’s inequality, subdifferentials and optimality

Introduction Consider the general machine learning set-up. We have a class of models parameterized by (e.g. for linear regression, would be the coefficients of the model). Each of these models takes in some input and outputs a result . We want to select the parameter which minimizes some population loss: where is the loss incurred […]

What is Sharpness-Aware Minimization (SAM)?

A matrix is said to be in block-angular form if it is of the form where the ‘s are arbitrary rectangular matrices (they need not be square). These matrices appear in optimization in the context of the Dantzig-Wolfe decomposition in linear programming (LP). The problem with the Dantzig-Wolfe decomposition solves is of the form The […]

What is a block-angular matrix?

A square matrix is said to be doubly stochastic if its entries are all non-negative and each row and column sums to one, i.e. The Birkhoff polytope, denoted by , is the set of all doubly stochastic matrices. One interesting fact about the Birkhoff polytope is that it is a convex polytope, with the vertices […]

What is the Birkhoff polytope?

Minkowski’s representation theorem is a fundamental result on how polyhedra can be represented. Preliminary definitions In , a polyhedron is a set which can be described as , where and . is an extreme point of a polyhedron if there do not exist such that . is a ray of a polyhedron if is non-zero […]

What is Minkowski’s Representation Theorem?

Review of the recently published book authored by Guglielmo Carchedi & Michael Roberts. the-prism-or-diamond-final-1Download

CAPITALISM IN THE 21st CENTURY THROUGH THE PRISM OF VALUE.CAPITALISM IN THE 21st CENTURY. More of a diamond than a prism.

‘Polycrisis’ is the buzz word among leftists right now.  The word expresses the coming together and interlocking of various crises: economic (inflation and slump); environmental (climate and pandemic); and geopolitical (war and international divisions). Indeed, I raised a similar idea early last year.  So it is no surprise that the latest Human Development Report from the […]

Polycrisis and depression in the 21st century