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.
85
questions
0
votes
0answers
10 views
Is penalized logistic regression convex? [duplicate]
Is logistic regression problem penalized by elastic net penalty convex optimization problem? More specifically, I want to find out whether it is suitable for dual formulation such that the duality gap ...
1
vote
0answers
17 views
How to minimize the sum of Frobenius norm and Nuclear norm
I have to minimize an objective function of the the form :
$||X_{s} - Y_{s}D_{s}||_{F}^{2} + ||D_{s}||_{F}^{2} + ||D_{s}||_{*}^{2}$
where $||.||_{F}$ denotes the Frobenius norm and $||.||_{*}$ ...
2
votes
2answers
30 views
Optimization equivalence
Can someone help me with the step by step demonstration of the following equivalence used in SVM:
$$maximize: m = \frac{1} {\|w\|} \equiv minimize: m =\frac{1} {2}\|w\|^2 $$
I would be most grateful ...
1
vote
1answer
41 views
Strongly convex function evaluated over a mean of n points
Let f(x) be a Strongly-convex function under some m > 0.
Given two points x, y it is known that:
$$f(\frac{x + y}{2}) \leq \frac{f(x) + f(y)}{2} - \frac{1}{2^3} \cdot m \cdot ||x - y||^2$$
What is ...
2
votes
1answer
24 views
Some tricky details about PCA non-convexity
I am reading about PCA and I came up with a some contradictions. PCA based on this post, PCA optimization problem is given by:
$$\begin{aligned}
\max_{w} \quad & w^T\Sigma w\\
\textrm{s.t.} \...
0
votes
1answer
7 views
Intervals from an underdetermined nonnegative linear system
I'm working on a problem in genomics that yields the following puzzle. Let $b\in \mathbb R^I$, $t$ and $p\in \mathbb R^J$, and $s \in \mathbb R^{I\times J}$. Suppose $t,b,p$ are known. Further suppose:...
1
vote
2answers
46 views
Concavity of negative binomial GLM
I need to estimate the log-likelihood of the negative binomial regression. I mean full log-likelihood, including the dispersion parameter.
The problem is: when I start LBFGS, BFGS, or gradient ...
3
votes
1answer
52 views
Why are K-means and GMM (Gaussian Mixture Models) not suitable for discovering clusters with non-convexs shapes?
I have seen that mainly here and from a lot of resources that K-means and
Hello all!
Gaussian mixtures are not suitable for detecting clusters with non-convex shapes. I know that because both ...
1
vote
1answer
29 views
Why does the formulation of the SVM problem has the bias (something we try to optimize) as a part of the constraint?
The common formulation of the SVM problem is
$$\min_{\theta, \theta_0}\frac{1}{2}||\theta||^2$$
$$\text{ subject to: } y^{(t)}(\theta \cdot x^{(t)} + \theta_0) \geq 1, \ t=1,...,n,$$
However, it ...
5
votes
2answers
186 views
L1-regularization enforces sparsity for convex functions
I have a convex function $f \colon \mathbb{R}^n \to \mathbb{R}$ that I minimize using L1-regularization:
$\DeclareMathOperator*{\argmin}{arg\,min}$
$$
x^*=\argmin_x f(x) + \lambda ||x||_1
$$
Can I ...
1
vote
1answer
38 views
D-optimal DOE suggest repeated samples
I tried to generate a D optimal design but the design output sounds very weird to me. I have a (real) process and I`d like to explore 3 factors, but the process have a lot of constraints so I provide ...
0
votes
0answers
63 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 ...
1
vote
0answers
24 views
Online Optimization - Regret in Absolute Error
In the online convex optimization literature static regret is defined as $\sum_{t=1}^{T}\left(f_t\left(x_t\right)-f_t\left(x^*\right)\right)$ where $x^*=\arg min_{x\in\mathcal{X}}\sum_{t=1}^{T}f_t\...
1
vote
0answers
69 views
Convexity of conditional expectation
Define $g(k)\equiv\mathbb{E}(X|_{X>k})$ and assume that the probability density $f$ of $X$ is twice continuously differentiable. Is there a sufficient condition in terms of $f$ that imply that $g^{...
0
votes
0answers
34 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. ...
3
votes
1answer
237 views
Prove that a function $\ln (e^{a_1} + e^{a_2} + \cdots + e^{a_n} )$ is convex?
Define the function:
$$f(a_1, a_2, · · · , a_n) = \ln (e^{a_1} + e^{a_2} + \cdots + e^{a_n} ).$$
I want to prove that $f$ is convex. Now, to show that is a function is convex, we can take second ...
1
vote
1answer
76 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 ...
0
votes
0answers
17 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 ...
1
vote
0answers
101 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 ...
2
votes
0answers
31 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 ...
1
vote
2answers
405 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 ...
2
votes
0answers
35 views
Normal equations issue
Let $A\mathbf{x}=\mathbf{b}$ be an overdetermined system, with $A$ being an $n \times m $ full-column rank rectangular matrix.
Are these minimization problems equivalent?
$$ 1) \;\underset{\mathbf{x}...
0
votes
0answers
32 views
Coordinate descent in integer programing: when does it work?
Denote $N_i=\{0,1,\dots,\bar{n}_i\}$ and define $N=N_1\times \dots \times N_I$. I want to minimize a function $f:N\rightarrow \mathbb{R}$. For the functions $f$ that interest me, it is very easy to ...
0
votes
1answer
164 views
Is error function always assumed and convex?
While updating weights of the neural network, most of the algorithms use convex optimisation because of the reason that error is a convex function.
My doubt is that whether the convex-ness of error ...
1
vote
1answer
94 views
How to understand whether Stochastic Gradient Descent has converged?
I am using SGD to solve for MSE function. My training set is around 50K, and I am monitoring the gradient at every epoch (once a pass is completed over all the training data). I played around a lot ...
2
votes
1answer
125 views
Regularizing the inverse coefficient matrix in multivariate regression
I'd like to minimize the objective
$ \operatorname{tr}[ (Y-XR^{-1})^T (Y-XR^{-1}) ] + \lambda \sum_{ij} |R_{ij}|$
wrt to $R$ (which is $P \times P$ but non-symmetric) where $Y$ and $X$ are both $N \...
3
votes
0answers
93 views
Optimization textbooks for statistics and data analytics
Any statistical analysis, machine learning or data science involves some sort of optimization at the end of the day.
I'm looking for good linear and nonlinear optimization textbooks for self ...
25
votes
6answers
4k views
For convex problems, does gradient in Stochastic Gradient Descent (SGD) always point at the global extreme value?
Given a convex cost function, using SGD for optimization, we will have a gradient (vector) at a certain point during the optimization process.
My question is, given the point on the convex, does the ...
2
votes
0answers
127 views
Vapnik-Chervonenkis Dimension
My question has to do with the VC dimension of the class of convex polygons with $m$ vertices. A solution to this problem is given in the following: Advanced Algorithms.
Call the class of all ...
3
votes
1answer
1k views
Any optimization problem can be expressed as one with a linear objective
For any standard optimization problem(think linear programming, convex, non-convex problem), would it be possible to express the optimization problem as one with a linear objective?
3
votes
1answer
69 views
Why is global convexity not possible in higher-dimensional settings for this loss function?
I was reading this paper which discusses nonconvex penalized regression. They use the following notation:
$X\in\mathbb{R}^{n\times p}$ is a data matrix with $n$ observations in $p$ variables
$\beta\...
2
votes
0answers
35 views
Why proximal gradient is a special case of sub-gradient?
While I was learning proximal gradient descent methods, I saw many similar statements as below:
$$p=prox_f(x) \Longleftrightarrow x-p \in \partial f(p) $$
for example, ...
3
votes
1answer
523 views
What is the use of the log of the sum of exponents in machine learning
I want to understand why somebody would use log sum exponent trick.
I am reading this blog.
But I don't really understand the first paragraph.
It says
Let's say we have an n-dimensional ...
1
vote
0answers
22 views
Low-variance estimate for the mean of the sotfmax transformation of a variable
Consider a set of infintiely-differentiable convex functions real-valued functions $f_i: \mathcal X \rightarrow \mathbb R$, where $i$ varies from $1$ to $m$, and suppose
we know all the moments of $...
2
votes
1answer
133 views
L2 SVM (squared hinge) theory
The linear L2 SVM can be intuitively understood as
\begin{equation}
\text{minimize } f(\boldsymbol{w}) = \frac{1}{2} \Vert\boldsymbol{w}\Vert^2_2 + C \sum_{i=1}^m \xi_i^2 \tag{1}
\end{equation}
...
0
votes
0answers
105 views
Is cross-entropy loss for MaxEnt models convex? If so, how do I prove it?
I am trying to prove if cross-entropy loss for MaxEnt models is convex.
My first attempt at approaching this problem is to compute the Hessian matrix of second-order partial derivatives and showing ...
1
vote
1answer
105 views
Is the difference between two iid log-concave distributions still log-concave?
Assume two iid random variables X and Y, with continuous and differentiable pdf $f$ and cdf $F$. Let Z=X-Y. Is the pdf of Z log-concave?
1
vote
1answer
156 views
Restriction of concave function to bounded convex set is concave?
Suppose I have a function that is concave, and has as its domain $R^n$. If I restrict the function to a bounded convex set, say the probability simplex, then the resulting function should still be ...
27
votes
6answers
10k views
Why study convex optimization for theoretical machine learning?
I am working on theoretical machine learning — on transfer learning, to be specific — for my Ph.D.
Out of curiosity, why should I take a course on convex optimization?
What take-aways from convex ...
2
votes
2answers
438 views
Variance of the reciprocal of a strictly positive random variable
In this post it is stated that due to Jensen's inequality the expected value of the reciprocal of a strictly postive random variable $X$ will satisfy:
$$\mathbb{E}\left[\frac{1}{X}\right] \geq \frac{...
2
votes
0answers
110 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?
2
votes
1answer
58 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 ...
1
vote
1answer
250 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 ...
1
vote
1answer
118 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,...
0
votes
0answers
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. ...
12
votes
3answers
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 ...
2
votes
1answer
320 views
Gaussian Processes for convex functions
As I understand, when using Gaussian Processes (GP) for regression, one can/should incorporate prior knowledge about the function into the GP. Let's say I have a nonlinear function $f: \mathbb{R}^n \...
4
votes
2answers
4k views
Logistic Regression is a Convex Problem but my results show otherwise?
I know that logistic regression is a convex problem. Furthermore, from Lemma 1.17 in these optimization lecture notes, if a function $f : \mathbb{R}^n \rightarrow \mathbb{R}$ is convex, then the ...
22
votes
1answer
5k views
Why is the cost function of neural networks non-convex?
There is a similar thread here (Cost function of neural network is non-convex?) but I was not able to understand the points in the answers there and my reason for asking again hoping this will clarify ...
1
vote
2answers
93 views
normalization constraint in support vector machine
A support vector machine initially poses the following optimization problem:
$$max_{\gamma, w, b} \gamma \\
s.t\ \\
y^{(i)}(w^Tx^{(i)} + b) \ge \gamma,\ \ i=1,\dots,m \\
||w|| = 1$$
I understand the ...
