68
votes
Why study convex optimization for theoretical machine learning?
Machine learning algorithms use optimization all the time. We minimize loss, or error, or maximize some kind of score functions. Gradient descent is the "hello world" optimization algorithm ...
- 141k
47
votes
Accepted
Why is the cost function of neural networks non-convex?
$\sum_i (y_i- \hat y_i)^2$ is indeed convex in $\hat y_i$. But if $\hat y_i = f(x_i ; \theta)$ it may not be convex in $\theta$, which is the situation with most non-linear models, and we actually ...
- 20.8k
43
votes
For convex problems, does gradient in Stochastic Gradient Descent (SGD) always point at the global extreme value?
They say an image is worth more than a thousand words. In the following example (courtesy of MS Paint, a handy tool for amateur and professional statisticians both) you can see a convex function ...
- 11.5k
33
votes
For convex problems, does gradient in Stochastic Gradient Descent (SGD) always point at the global extreme value?
Gradient descent methods use the slope of the surface.
This will not necessarily (or even most likely not) point directly
towards the extreme point.
An intuitive view is to imagine a path of descent ...
- 86.6k
28
votes
Accepted
Is PCA optimization convex?
No, the usual formulations of PCA are not convex problems. But they can be transformed into a convex optimization problem.
The insight and the fun of this is following and visualizing the sequence of ...
- 334k
28
votes
Accepted
Why are there extra terms $-p_i+q_i$ in SciPy's implementation of Kullback-Leibler divergence?
The other answer tells us why we don't usually see the $-p_i+q_i$ term: $p$ and $q$ are usually residents of the simplex and so sum to one, so this leads to $\sum - [p_i - q_i] = \sum - p_i + \sum q_i ...
- 5,735
22
votes
Why are there extra terms $-p_i+q_i$ in SciPy's implementation of Kullback-Leibler divergence?
The referenced book has a free pdf on Boyd's site: https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf
On page 90, formula 3.17 gives this definition. I suspect the reason for the added terms is ...
- 5,051
19
votes
For convex problems, does gradient in Stochastic Gradient Descent (SGD) always point at the global extreme value?
Steepest descent can be inefficient even if the objective function is strongly convex.
Ordinary gradient descent
I mean "inefficient" in the sense that steepest descent can take steps that oscillate ...
- 94.1k
13
votes
Why study convex optimization for theoretical machine learning?
I think there are two questions here.
Why study optimization
Why convex optimization
I think @Tim has a good answer on why optimization. I strongly agree and would recommend anyone interested in ...
- 37.3k
13
votes
For convex problems, does gradient in Stochastic Gradient Descent (SGD) always point at the global extreme value?
Local steepest direction is not the same with the global optimum direction. If it were, then your gradient direction wouldn't change; because if you go towards your optimum always, your direction ...
- 58.2k
11
votes
Can there be multiple local optimum solutions when we solve a linear regression?
This question is interesting insofar as it exposes some connections among optimization theory, optimization methods, and statistical methods that any capable user of statistics needs to understand. ...
- 334k
11
votes
Accepted
Logistic Regression is a Convex Problem but my results show otherwise?
The problem with your data set is called Complete separation of the data. The likelihood associated to logistic regression models is concave, provided that there is no complete separation of the data.
...
- 126
9
votes
Is PCA optimization convex?
No.
Rank $k$ PCA of matrix $M$ can be formulated as
$\hat{X} = \underset{rank(X) \leq k}{argmin} \| M - X\|_F^2$
($\|\cdot\|_F$ is Frobenius norm). For derivation see Eckart-Young theorem.
Though ...
- 6,006
9
votes
Accepted
In online convex optimization, what is a leader in FTL algorithm?
The Follow-The-Leader (FTL) algorithm is a simple algorithm for solving online prediction problems. Imagine that you have a committee of experts, each of which suggests a strategy. At each time point, ...
- 21.4k
9
votes
Accepted
Any optimization problem can be expressed as one with a linear objective
The perhaps surprising answer is YES, and it doesn't involve Taylor expansion or any other approximations.
First, presume we have an unconstrained optimization problem, $$\min_x f(x)$$ for some ...
- 13.5k
9
votes
Accepted
Prove that a function $\ln (e^{a_1} + e^{a_2} + \cdots + e^{a_n} )$ is convex?
The function you are looking at is the LogSumExp function:
$$f(\mathbf{a}) = \ln \Big( \sum_{i=1}^n \exp(a_i) \Big)
\quad \quad \quad
\text{for all } \mathbf{a} \in \mathbb{R}^n.$$
Its gradient ...
- 133k
9
votes
Minimum expectation
When $p$ increases, that means its cumulative distribution function
$$P(x) = \int_0^x p(x)\,\mathrm{d}x$$
is convex. Since $P(0)=0$ and $P(1)=1,$ the convexity implies the graph of $P$ lies on or ...
- 334k
9
votes
Accepted
Is there an exponential family such that its natural parameter mapping is non-invertible or has non-convex range?
Not a complete answer, but primarily a response to
Question 1. Is there an exponential family with non-injective
parameter mapping?
The short answer is: yes, there is. It's called the curved ...
- 12.1k
8
votes
Accepted
Loss function for Logistic Regression
You got off on the wrong track as detailed here. Just because you have a binary $Y$ it doesn't mean that you should be interested in classification. You are really interested in a probability model, ...
- 98.5k
7
votes
Why l2 norm squared but l1 norm not squared?
But in the ElasticNet and Ridge, we use the l2 norm squared. Why is that, is there a particular reason (computational, optimization dynamics, statistical?)
A possible reason for the l2 norm being ...
- 86.6k
5
votes
Logistic Regression is a Convex Problem but my results show otherwise?
There are two different things going on here.
As you correctly stated, logistic regression is a convex problem. You made your loss function not convex by altering your definition of the sigmoid ...
- 51
5
votes
Accepted
Relating $f(\mathrm{Var}[X])$ to $\mathrm{Var}[f(X)]$ for Positive, Increasing, and Concave $f(X)$
There is no relation between the two quantities $f(\text{Var}[X])$ and $\text{Var}[f(X)]$ for concave $f$. Here are the examples to demonstrate this:
Ex 1: Suppose random variable $X$ has the pmf: $...
- 226
5
votes
What is the use of the log of the sum of exponents in machine learning
The comments address why provide special treatment for the numerical evaluation of logsumexp, as it's known, but not why it arises.
First consider the special case $x_1 = 0, x_2 = x$. Then logsumexp =...
- 13.5k
5
votes
How to recover primal problem from its dual counterpart
In general, it is not (always) possible to obtain the primal from the dual.
The Dual problem is always a convex optimization problem (minimizing a convex function or maximizing a concave function, ...
- 13.5k
5
votes
Accepted
L1-regularization enforces sparsity for convex functions
Regarding your question about general convex functions, you will get a sparse solution given that you apply a sparsity-inducing norm (which l1 is one such norm). For further information, read up to ...
- 847
5
votes
Accepted
strict convexity of $\boldsymbol{\beta} \mapsto \| \mathbf{Y}-\mathbf{X}\boldsymbol{\beta}\|_2^2$
This analysis is intended to illuminate the basic underlying ideas.
Consider the system of linear equations
$$X\gamma = 0$$
where $\gamma$ is a column $p$ vector and $0$ is the zero $n$ vector. When $...
- 334k
5
votes
Why l2 norm squared but l1 norm not squared?
A practical reason for squaring the L2 (that is not specific to ridge regression) is that "squaring" the L2 consists of not bothering to take the square root in the first place. And since $...
- 197
5
votes
Accepted
Expectation under convex order
The implication does not hold.
For example, let $M \equiv 0$, $N$ be the Radamacher random variable (i.e., $P(N = \pm 1) = \frac{1}{2}$). Then for any concave function $u$, it follows by Jensen's ...
- 21.2k
4
votes
Accepted
Is a linear discriminant function actually "linear"?
Affinity is clearly enough for (4.12) to hold. Since
$$\hat{\mathbf{x}}=\lambda\mathbf{x}_A + (1-\lambda)\mathbf{x}_B $$
then, multiplying LHS & RHS by $\mathbf{w}^T_k$ and adding $w_{k0}$, we ...
- 18.4k
Only top scored, non community-wiki answers of a minimum length are eligible