Category Archives: Optimization

ORF523: ISTA and FISTA

As we said in the previous lecture it seems stupid to consider that we are in a black-box situation when in fact we know entirely the function to be optimized. Consider for instance the LASSO objective where one wants to minimize over . By … Continue reading

Posted in Optimization | 2 Comments

ORF523: Conditional Gradient Descent and Structured Sparsity

In the following table we summarize our findings of previous lectures in terms of oracle convergence rates (we denote ). Note that in the last two lines the upper bounds and lower bounds are not matching. In both cases one can … Continue reading

Posted in Optimization | 1 Comment

Guest post by Amir Ali Ahmadi: Sum of Squares (SOS) Techniques: An Introduction, Part II/II

The reader is encouraged to read Part I of this series before reading this post. For ease of reference, we recall the polynomial optimization problem from our previous post: (1)   This is the task of minimizing a multivariate polynomial … Continue reading

Posted in Optimization | 1 Comment

ORF523: Strong convexity

Today we will talk about another property of convex functions that can significantly speed-up the convergence of first-order methods: strong convexity. We say that is -strongly convex if it satisfies (1)   Of course this definition does not require differentiability … Continue reading

Posted in Optimization | 2 Comments

Guest post by Amir Ali Ahmadi: Sum of Squares (SOS) Techniques: An Introduction, Part I/II

Sum of squares optimization is an active area of research at the interface of algorithmic algebra and convex optimization. Over the last decade, it has made significant impact on both discrete and continuous optimization, as well as several other disciplines, … Continue reading

Posted in Optimization | 1 Comment

ORF523: Nesterov’s Accelerated Gradient Descent

In this lecture we consider the same setting than in the previous post (that is we want to minimize a smooth convex function over ). Previously we saw that the plain Gradient Descent algorithm has a rate of convergence of … Continue reading

Posted in Optimization | 3 Comments

ORF523: Oracle complexity of smooth convex functions

In this lecture we consider the unconstrained minimization of a function that satisfy the following requirements:  (i) admits a minimizer on . (ii) is continuously differentiable and convex on . (iii) is smooth in the sense that the gradient mapping … Continue reading

Posted in Optimization | Leave a comment

ORF523: Oracle complexity of Lipschitz convex functions

In this lecture we consider the unconstrained minimization of a function that satisfy the following requirements: (i) admits a minimizer on such that . (ii) is convex on . Recall that in particular this implies for any . (iii) is … Continue reading

Posted in Optimization | 4 Comments

ORF523: Oracle complexity, large-scale optimization

Our study of the computational complexity of mathematical optimization led us to realize that we are still far from a complete understanding of what exactly can be optimized with a computer. On the positive side we proved that some problems can be … Continue reading

Posted in Optimization | 2 Comments

ORF523: Classification, SVM, Kernel Learning

In this post I will go over some simple examples of applications for the optimization techniques that we have seen in the previous lectures. The general theme of these examples is the canonical Machine Learning problem of classification. Since the … Continue reading

Posted in Optimization | 2 Comments