Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

Questions tagged [convex]

A convex set includes all points lying between any two points from the set. A convex function on such a set is a function lying below any straight line connecting two points from its graph. Convex optimization is concerned with searching for the minimum of such a function.

76 questions
Filter by
Sorted by
Tagged with
35 views

Why backpropagation if loss function is not convex in nature?

Backpropagation contains the method of gradient decent, which works well for convex loss functions with a global minima. But, for training, in most of the neural network tasks, backpropagation is ...
19 views

19 views

Hard margin SVM: existence of KKT point?

I'm learning about support vector machines and ran into a question while going through the hard margin case. First I'll have to go through some steps in the problem to arrive where at I'm confused. ...
188 views

Prove that a function $\ln (e^{a_1} + e^{a_2} + \cdots + e^{a_n} )$ is convex?

Let $f(a_1, a_2, · · · , a_n) = \ln (e^{a_1} + e^{a_2} + \cdots + e^{a_n} )$. Show that $f$ is convex. Now, to show that is a function is convex, we can take second derivative of the function and if ...
63 views

How to recover primal problem from its dual counterpart

I am asking this from context of optimization in machine learning. We often talk about a primal problem and how this primal problem can be solved by first converting it into a dual problem (Using ...
15 views

How to get precise answer from stochastic gradient descent

I have a convex optimization problem in few variables and I have an unbiased estimator of the gradient without having the ability to evaluate the function itself. I want to do gradient descent but the ...
73 views

How positive definite Hessian approximations for SGD (e.g. Gauss-Newton) handle saddles?

For example due to symmetry of parameters, functions optimized in machine learning usually have huge number of local minima and saddles - growing exponentially with dimension. I am trying to ...
27 views

How to solve a non-convex with equality constraint optimization problem?

I have a non-convex optimization problem with equality constraint, I can derive the KKT conditions, but it seems just one of the KKT conditions is valid. Could you please give some advice on how to ...
205 views

Convexity of cross entropy

I am not sure if this is a better fit for this site or mathematics.stackexchange but I've seen similar questions on here before. I'd like to know if the following is true and if so, how I could go ...
23 views

Why H(y) is a concave function of p(x) when p(y) is a linear function of p(x)?

I got stuck in the line when reading a theorem in The Elements of Information Theory on page 59: If p(y|x) is fixed, then p(y) is a linear function of p(x). Hence H(Y), which is a concave ...
31 views

104 views

KKT condition in layman's term

The most intuitive explanation for KKT condition I can find is this post, which is still too complex to me. Is there any more intuitive explanation? How to introduce this to a layman?
56 views

Why does Jensen's imply this?

Let $F$ be a convex function. If $Y$ and $Z$ are independent random variables and $EZ=0$, then $$EF(Y) = EF(Y+EZ)\leq E(Y+Z).$$ I fail to understand why the last inequality is true. Can someone ...
203 views

Is the log loss function $f(w) = y_t \log(y_p) + (1 - y_t) \log(1 - y_p)$ convex in $w$? [duplicate]

Kaggle defines the log loss function as: https://www.kaggle.com/wiki/LogarithmicLoss $$f(w) = \log \Pr(y_t|y_p) = y_t \log(y_p) + (1 - y_t) \log(1 - y_p)$$ Let $y_t \in {0, 1}$, and $y_p$ is given ...
99 views

convexity of two convex function combined

If I have such an optimization problem: $$\arg\min_{x,z} \dfrac{||y-x||_2^2}{z}+z(||y-x||_2^2)$$ where $y$ is known and $z>0$. If $z$ is fixed, then this function w.r.t $x$ is convex. Similarly,...
36 views

Convex subspaces and zero covariance?

$\DeclareMathOperator*{\argmin}{arg\,min} \newcommand{\E}{\text{E}}$ This is from the Analytics Iowa LLC notes provided at http://www.public.iastate.edu/~vardeman/stat602/StatLearningNotesII.pdf, p. ...
2k views

Is PCA optimization convex?

The objective function of Principal Component Analysis (PCA) is minimizing the reconstruction error in L2 norm (see section 2.12 here. Another view is trying to maximize the variance on projection. We ...
282 views

543 views

Convexity, linearity and their combination for MLE

I'm going through Murphy's ML a Probabilistic Perspective book and in chapter 9 we have the following excerpt talking about the MLE of exponential family distributions: My question is: How do we ...
76 views

Difference between minima of L1-regularized quadratics

How can I find F(A,b,x,c)=\inf_{\theta\in\mathbb{R}^n}(\theta^{\top}A\theta+b^\top\theta+x^\top\theta+c||\theta||_1)-\inf_{\theta\in\mathbb{R}^n}(\theta^{\top}A\theta+b^\top\theta-x^\top\theta+c||\...
Relating $f(\mathrm{Var}[X])$ to $\mathrm{Var}[f(X)]$ for Positive, Increasing, and Concave $f(X)$
The arrival of photons at a pixel in an image sensor is a Poisson distributed random variable such that the input can be modeled as a Poisson r.v. $X\sim \mathrm{Poisson}(\lambda)$. Since the input ...
Chris Bishop introduces the multi-class linear discriminant functions (a.k.a. linear machine) in PRML as follows (p. 183): In proving the convexity of decision regions, it's assumed that $y_k(\cdot)$ ...