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.
116
questions
0
votes
1answer
35 views
Can it be proven that non-negative least squares is a perfectly convex problem?
Can it be proven that NNLS is a perfectly convex problem?
Myre writes in section 3 of his TNT-NN manuscript:
The NNLS objective function is a convex quadratic function with
linear inequalities as ...
3
votes
1answer
28 views
Is Convexity necessary to use Gradient descent?
I was reading and I saw that convexity is sufficient for using GD to minimize functions. Would it be also necessary?
1
vote
0answers
12 views
Stochastic gradient descent convergence rate
I need to understand the convergence rate notation in the convex optimization context.
In every paper that I find, the convergence rate of an algorithm is defined as a function of the number of ...
0
votes
0answers
26 views
Is convexity actually necessary for gradient descent?
I understand that the problem that when you are optimizing something using gradient descent, the algorithm might get stuck in a local optimum that isn't global. Otherwise, there are non-convex ...
0
votes
1answer
24 views
Is the set of distribution $\{ X | \max_t |f_X(t) - f_Y(t)| \leq \epsilon \}$ convex, where f is the cdf or inverse cdf?
I'm trying to figure out if the set is convex, where the maximum difference between cdf(or inverse cdf) of X and a reference distribution Y is smaller than $\epsilon$.
1.
Let $f_X(t)$ denote the cdf ...
0
votes
0answers
11 views
Convex hull version of density estimation (or lines of constant density)
Background:
So I had a thought, tried it out, and liked what it did. I'm sure someone else has done this. It feels very convenient. It also gives an interesting take on robust nonparametric density ...
0
votes
0answers
9 views
ADMM updates of $\min_{\beta_1,…\beta_3,\beta}\sum_{i=1}^{3}\frac{1}{2}||y_i-X_i\beta_i||_2^2+\lambda||\beta||_1$
ADMM updates of $\min_{\beta_1,...\beta_3,\beta}\sum_{i=1}^{3}\frac{1}{2}||y_i-X_i\beta_i||_2^2+\lambda||\beta||_1$ s.t. $\beta_1=\beta=\beta_2=\beta_3$
So this is a HW problem and I dunno why they ...
4
votes
2answers
107 views
strict convexity of $\boldsymbol{\beta} \mapsto \| \mathbf{Y}-\mathbf{X}\boldsymbol{\beta}\|_2^2$
So I'm studying lasso regression using https://arxiv.org/pdf/1509.09169.pdf and on page 84 (the beginning of section 6.1) it is stated that $\boldsymbol{\beta} \mapsto \| \mathbf{Y}-\mathbf{X}\...
4
votes
1answer
130 views
Are there any “convex neural networks”?
Are there any neural network training procedure that involves solving a convex problem?
Note that I am referring more to MLPs, instead of (multi-class) logistic regression which is a neural network ...
1
vote
1answer
25 views
SVM: Would we care about the functional margin if maximizing only with geometric margin were convex?
I am reading Andrew Ng's SVM notes (https://see.stanford.edu/materials/aimlcs229/cs229-notes3.pdf) and am lacking the intuition for why we need the functional margin. As far as I understand we need it ...
3
votes
0answers
33 views
Inequality of Probability
This problem is from Matrix Analysis for Statistics by James R. Schott.
Problem. Show that if $x$ and $y$ are two independently distributed random vectors with $x\sim{\rm Normal}(0,\Omega_1)$ and $y\...
4
votes
1answer
46 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
61 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
76 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
127 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
59 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
36 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
21 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 ...
0
votes
1answer
15 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, ...
2
votes
1answer
29 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
107 views
Optimization: Convex function
Problem statement
Use the definition 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
43 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
24 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
66 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
47 views
Is logistic regression always convex? [duplicate]
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
72 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 |...
1
vote
0answers
15 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
113 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 ...
2
votes
1answer
37 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 ...
1
vote
0answers
68 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
39 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
57 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
35 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
182 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
191 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
315 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
52 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
71 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
77 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
323 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
173 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
170 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
32 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
969 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 ...
