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.
105
questions
4
votes
1answer
36 views
If we add a constant weight vector with an absolute function, does it still remain convex then?
We know that absolute functions are convex. Now what if we add a constant weight vector to it, does it still remain convex?
Say the equation is Absolute loss regression + L1 regularization, we know ...
1
vote
0answers
59 views
Is there a smart algorithm of finding the maximum of $X^{\top}a$ with $X$ and $a$ both belong to some compact convex set? [closed]
Suppose $X\in\mathcal{X}\subset R^k$ and $a\in\mathcal{A}\subset R^k$, where $\mathcal{X}$ and $\mathcal{A}$ are both compact convex set.
Is there a systematic way of finding the maximum of $X^{\top}a$...
0
votes
0answers
29 views
How to prove that the convexity of Generalized Linear Models?
Refer to question: Does log likelihood in GLM have guaranteed convergence to global maxima?
The top answer said that one can prove
$\frac{d A}{d \theta}=\mathbb{E}[\phi(x)]$
$\frac{d^{2} A}{d \theta^{...
0
votes
2answers
40 views
Is the GAN min-max loss function a convex optimization problem?
The GAN loss function is binary cross entropy consisting of a discriminator function $D(x)$ and generator function $G(z)$.
$$
\min_{G} \max_{D} V(D,G)=\mathbb{E}_{x\sim p_{data}}[\log D(x)] + \mathbb{...
0
votes
1answer
54 views
Is this objective function convex? [closed]
Given that $F(x)$ is the cumulative distribution function (CDF) of continuous random variable $X$, is
$$\frac{\int_0^\infty 1-F(x) dx}{\int_{-\infty}^0 F(x) dx}$$
convex? or is it non-convex/concave? ...
3
votes
0answers
33 views
Are there algorithm for finding a minimum of a separately convex function (i.e., $f(x,y)$ convex in $x$ and $y$ but not in $(x,y)$)
Suppose that $f: \mathbb{R}^n \times \mathbb{R}^n \to \mathbb{R}$ is separatly convex function. That is, for a fixed $y$ the mapping $x \to f(x,y)$ is convex and for a fixed $x$ the mapping $y \to f(...
1
vote
1answer
35 views
is this graph of loss function or input data distribution? [closed]
I have been looking at the Batch normalization and got confused.
https://www.google.com/search?q=how+to+draw+non+convex+optimization+loss+function+in+graph&newwindow=1&tbm=isch&source=iu&...
0
votes
1answer
17 views
Does coordinate wise convex function can be optimized more effectively?
I'm currently working on a non-convex function. It's basically a maximum likelihood problem so I'm trying to optimize this function.
I know that non-convex optimization frequently reaches local optima ...
2
votes
0answers
17 views
Strange constraint in optimization problem
I am trying to solve the following QP :
$$ \min_{x} \quad (1/2)\|y - Ax \|^2 _2 + \lambda \|Dx\|_1$$
where $yĀ \in \mathbb{R}^n$, $A \in \mathbb{R}^{n\times m}$, $D \in \mathbb{R}^{l\times m}$. Assume :...
0
votes
0answers
8 views
Convex variant of Bhattacharyya coefficient
For (discrete, finite) probability distributions $P,Q$, the Bhattacharyya coefficient is $B(P,Q) := \sum_x \sqrt{P_x Q_x}$. It can be shown that this is jointly concave in $P$ and $Q$. My question is, ...
1
vote
1answer
27 views
Proof: Condition for a function being strongly convex
Let $\lambda \in \mathbb{R}_{> 0}$. A function $f : \mathbb{R}^d \to \mathbb{R}$ is $\lambda$-strongly convex, if for all $\alpha \in (0, 1)$ and all $u, v \in \mathbb{R}^d$
$$
f(\alpha u + (1 - \...
5
votes
1answer
100 views
Optimization: Convex function
Problem statement
Use the deļ¬nition of convexity of a function, i.e., that for any $\boldsymbol{x}$, $\boldsymbol{y} \in \mathbb{R}^{d}$ and $\lambda \in \left [0,1 \right ]$ we have
\begin{align*}
...
2
votes
0answers
34 views
Sum of SVM hinge losses always a convex function?
The data loss function for a multi class SVM may take the following expression:
\begin{equation}
L=\frac{1}{N}\sum_{i}\sum_{j\neq y_i}\left[ \max(0,w_j^Tx_i-w_{y_i}^Tx_i+1)\right]
\end{equation}
...
2
votes
1answer
23 views
Question about Decision boundary in Logistical Regression
I am a Machine Learning newbie and studying Logistical Regression.
For the data shown above, a straight line cannot separate all the positive and negative decisions. One thing I could understand is ...
1
vote
1answer
61 views
Doubt about definition of Regret in Online convex optimization setting
In online convex optimization, the regret of an algorithm $\mathcal{A}$ as defined in Introduction to Online Convex Optimization (Page 5) is:
$$
regret_T(\mathcal{A}) = \sup_{\{f_1,...,f_T\}} \sum_{t=...
0
votes
0answers
33 views
Is logistic regression always convex?
I know that the cross-entropy loss is convex, and I've seen it stated that logistic regression is convex and has a global minimum.
e.g. here https://www.cs.cmu.edu/~mgormley/courses/10701-f16/slides/...
2
votes
1answer
61 views
Iterative solution to Gamma distribution MLE problem
I'm trying to follow the derivation for the MLE parameters of the gamma distribution in [1].
The standard approach is to derive an expression for the log likelihood, differentiate with respect to ...
1
vote
0answers
26 views
Extended Lasso problem ( two L1 norms)
I am trying to find a closed form solution for the following problem :
$$
\underset{\beta}{\operatorname{minimize}} \frac{1}{2} || y - X \beta ||^{2} + \lambda || \beta ||_{1} + \mu || \beta - \gamma |...
0
votes
0answers
13 views
Kullback-Leibler divergence from density f to density g
If $f$ and $g$ are density functions that are positive over the same region, then the Kullback-Leibler divergence from density $f$ to density $g$ is defined by:
$$KL(f,g) = E_f\left[\ln\left(\frac{f(...
2
votes
0answers
82 views
ROC Convex Hull for Model Selection
The area under the convex hull of a roc curve is by construction always "better" than its area under curve. Some curves might see more of an increase in reported auc than others. Is it a viable ...
1
vote
1answer
28 views
How to understand the sufficient condition for global optimum for a constrained optimization probelm
How to understand the sufficient condition for global optimum? From my understanding, the global optimum should be 0 instead of $\geq 0$, where does this come from?
Consider the constrained ...
2
votes
1answer
45 views
Basic question about labeling of random variables apropos of the definition of convexity
I understand the definition of convexity in a function $f: \mathbb R^d \to \mathbb R$ as the inequality for all $a,b\in\mathbb R^d$ and $0<\theta<1:$
$$\theta f(a) + (1-\theta)f(b) \geq ...
0
votes
0answers
36 views
Why does quadratic optimization produce non-stable results
Edit: posing the question in a different way
I am running a mean-variance optimization, which is a quadratic optimization problem. I run the optimization 2000 times for different levels of risk (via ...
0
votes
0answers
12 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
35 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
38 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
50 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
30 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:...
2
votes
2answers
121 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
133 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
38 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
251 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
50 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 ...
1
vote
1answer
47 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
73 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^{...
3
votes
1answer
285 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
117 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 ...
1
vote
0answers
147 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 ...
2
votes
2answers
702 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
35 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
245 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
192 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
129 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 \...
4
votes
0answers
162 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
6k 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
134 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?
