Skip to main content

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.

Filter by
Sorted by
Tagged with
2 votes
1 answer
33 views

Expectation under convex order by multiplying

I am trying to understand if the following statement is true, or the conditions under it is satisfied. Let $M,N$ and $X>0$ be random variables. If the following inequality holds for any concave non-...
Don P.'s user avatar
  • 157
2 votes
1 answer
47 views

Expectation under convex order

I am trying to understand if the following statement is true. Let $M,N$ and $X$ be random variables. If the following inequality holds for any concave non-decreasing function $u$ \begin{equation} \...
Don P.'s user avatar
  • 157
0 votes
0 answers
38 views

Understanding GAN Proof

I was reading the original GAN paper, and in the proof of Proposition 2, it is states that $U(p_g, D)$ is convex in $p_g$. I'm not sure how this is implied to be convex. This comment said that it was ...
Leonhard Bosch's user avatar
0 votes
0 answers
19 views

Intercept term of logistic regression in ADMM algorithm

On page 66, the authors of article of ADMM says that the algorithm can be modified to obtain the intercept term easily in the sparse logistic regression model. Can someone explain this easy ...
mert's user avatar
  • 313
2 votes
0 answers
72 views

Do discontinuous functions have subgradients also?

Typically, the subgradient is defined for convex functions. And convex functions are continuous. However, DeepMind's VQ-VAE paper defines a model with a discontinuous vector quantization (VQ) layer, ...
MWB's user avatar
  • 1,337
3 votes
1 answer
171 views

Scenario where minimizing 0-1 loss is different than minimizing hinge loss

Suppose we're using linear predictors. I'm trying to conceptually understand how minimizing hinge loss and 0-1 loss aren't necessarily the same. For instance I was told that one can choose a set of ...
redbull_nowings's user avatar
1 vote
0 answers
29 views

Convexitiy of multi-class hinge loss

The empirical risk of a multi-class hinge-loss is given by $$L(\Theta,(x,y) = \max_{j \neq y} \Big[1+ \sum_{i=1}^{d} x_i(\Theta_{ij} - \Theta_{iy}) \Big]_{+} $$ where $x \in \mathbb{R}^{d}$ is a ...
Oskar's user avatar
  • 255
1 vote
1 answer
74 views

Perturbation for more stable convex optimization

I am thinking of adding some perturbation to my convex optimization problem. The idea is straight forward like below chart. Supposed you are solving $\text{argmax} f(x) $, we want to find an $x$ that'...
Taylor Fang's user avatar
0 votes
0 answers
10 views

how to solve for wasserstein duality easily in a special case when 2-Wasserstein inequality constraint is binding

I was going through this nice paper ” A Simple and General Duality Proof for Wasserstein Distributionally Robust Optimization”, and one quick qu on applying Theorem 1 to my poject: What if in my ...
numpynp's user avatar
  • 21
0 votes
0 answers
34 views

Relationship between Ratio of expectation squared vs ratio of squared expection

I have these pair of numbers $ (a, b) = (\frac{4}{9}, \frac{1}{9}) $ and $(c, d) = (\frac{1}{2}, \frac{1}{6}) $. Note that - (a, b) are pair of numbers which represent $((E(e_1))^2, (E(e_2))^2) $ and (...
Elina Gilbert's user avatar
3 votes
1 answer
313 views

Is there an exponential family such that its natural parameter mapping is non-invertible or has non-convex range?

On the Wikipedia article for exponential families the density of a distribution on a measure space $(X, \xi)$ from an exponential family is written as $$f_{\theta} \colon X \to \mathbb{R}_{\ge 0}, \...
ViktorStein's user avatar
1 vote
0 answers
54 views

Find the minimum of a concave function [closed]

I have proved that my function with two variable is concave. I am looking for the minimum of the function. Since the function is continuous over a convex set the minimum should occur on the border of ...
Taraneh's user avatar
  • 11
0 votes
0 answers
148 views

Do contour plots over first two principal components reveal local convexity/concavity?

When I plot a contour plot of a variable over two principal components I can see what appears to be hills and valleys. But I also know I am only looking at the contours over a projection. Here is a ...
Galen's user avatar
  • 9,249
24 votes
2 answers
2k views

Why are there extra terms $-p_i+q_i$ in SciPy's implementation of Kullback-Leibler divergence?

Why do some definitions of the Kullback-Leibler divergence include extra terms $-p_i + q_i$? For example, kl_div() (in the Python ...
Igor F.'s user avatar
  • 9,353
2 votes
0 answers
36 views

Is there any function that is convex after compounded with a squared loss (besides linear ones)?

It is known that a linear function compounded with a squared loss is convex, so one can efficiently find the optimal solution when performing linear regression. Specifically, given a data point $(x,y)$...
Qcer's user avatar
  • 33
0 votes
0 answers
20 views

Convex optimization problem with nuclear norm constraint

We have the following convex optimization problem:$$ \text{minimize} \quad f({\bf X}) \quad \text{with constraint} \quad \|{\bf X}\|_{\rm tr} \leq t $$ Where $\|{\bf X}\|_{\rm tr}$ is the Schatten 1-...
The Limit Does Not Exist's user avatar
0 votes
2 answers
248 views

What does concurve or convex means in terms of Log likelihood function?

As a non native english speaker and a naive student, I found difficulties in understanding what this means. While studying a paper, I found that some log likelihood functions showed convexity property ...
user avatar
2 votes
1 answer
339 views

Parameter choice rules for L1 regularization?

I am solving an L1 regularized least squares (LASSO) of the form: $$ \arg \min_{\boldsymbol{x}} \frac{1}{2} {\left\| A \boldsymbol{x} - \boldsymbol{y} \right\|}_{2}^{2} + \lambda {\left\| \boldsymbol{...
user376024's user avatar
0 votes
1 answer
24 views

Is it true for rvs $X,Y$ where $E[X]=E[Y]$ & $V[X] \geq V[Y],$ the Jensen gap of $X$ is larger or equal the Jensen gap of $Y?$

Is it true for rvs $X,Y$ where $E[X]=E[Y]$ and $V[X] \geq V[Y],$ the Jensen gap of $X$ is larger or equal the Jensen gap of $Y?$ It seems intuitive. I failed to prove it or find a reference.
curious's user avatar
2 votes
1 answer
178 views

Mean field approximation convergence

The last sentence of Christopher M. Bishop, Pattern Recognition and Machine Learning Section 10.1.1 Factorized distributions on p.466, states, referring to Equation $(10.9)$, that "Convergence is ...
Hans's user avatar
  • 1,015
13 votes
3 answers
1k views

Why l2 norm squared but l1 norm not squared?

In the Lasso, and ElasticNet, we use, as penalty, the l1 norm without squaring. But in the ElasticNet and Ridge, we use the l2 norm squared. Why is that, is there a particular reason (computational, ...
William de Vazelhes's user avatar
2 votes
2 answers
85 views

prove the convexity of zero one loss multiple a convex function

I am now working on a problem To prove the convexity of a zero-one loss multiple with a convex function, and it looks like this: $$L(s) = s^2 \times \boldsymbol 1(s\leq 0);$$ when proving this ...
icc's user avatar
  • 23
1 vote
0 answers
65 views

Double-layered optimization to find optimal regularization parameter lambda for Ridge/LASSO

I have an overdetermined system of equations problem where n >> m and the OLS almost always finds an approximation instead of an exact solution. I already ...
SkyWalker's user avatar
  • 925
2 votes
1 answer
209 views

Linear regression with convex combination of the parameters

I am looking for a method to solve the following linear regression problem: $$ y_i=\sum_{j=1}^Kx_{ij}\beta_j+\varepsilon_i $$ with all $\beta_j\geq0$ and $\sum \beta_j=1$. I am familiar with ...
Nando Vermeer's user avatar
2 votes
1 answer
420 views

Subgradient for sparse-group lasso

Sparse-group lasso is defined as $$\frac{1}{2n}\left\|y-X\beta \right\| + (1-\alpha)\lambda\sum_{l=1}^m \sqrt{p_l}\left\|\beta^{(l)} \right\|_2 + \alpha \lambda \left\| \beta\right\|_1$$ In the SGL ...
user19904's user avatar
  • 144
1 vote
0 answers
26 views

Given a real matrix $M$, find the closest cross-correlation matrix

Say we have an arbitrary real matrix $M$. I am wondering if we can find a cross-correlation matrix that has the least square distance to $M$. In other words, $$\min_{A,B} \|M-A^TB \|^2_F $$ s.t. $$...
CWC's user avatar
  • 281
0 votes
1 answer
215 views

Convexity of linear least squares problem when rank-deficient matrix

A linear least squares problem is always convex as explained mathematically here https://math.stackexchange.com/questions/483339/proof-of-convexity-of-linear-least-squares. However, a linear LS can ...
Maaz's user avatar
  • 317
4 votes
1 answer
107 views

Is the mean of the left-truncated binomial distribution convex in p?

The expectation of the binomial distribution of successes in $G$ trials, left-truncated at $R$, with success probability $p$, is $$ E[X|p] = \frac{\sum_{l=R}^Gl\phi(l)}{\sum_{l=R}^G\phi(l)} $$ where $$...
dash2's user avatar
  • 246
2 votes
0 answers
232 views

CVXPY PSD constraint not working

I am using CVXPY to solve for a PSD matrix, example as follows: ...
regression_practitioner's user avatar
0 votes
1 answer
503 views

Derivate of Neural Network respect to input

I have a neural network like this $x=\text{input}$ $z_1=W_{1x}\cdot x+b_1$ $h_1=\text{relu}(z_1)$ $z_2=W_2\cdot h_1+W_{2x}\cdot x+b_2$ $h_2=\text{relu}(z_2)$ $y=W_3\cdot h_2+W_{3x}\cdot x+b_3$ input ...
Gaweiliex's user avatar
2 votes
0 answers
485 views

Duality gap calculation in Scikit-learn implementation of Lasso

I am writing a custom variation of Lasso regression, using sklearn's Lasso implementation as a "source of inspiration". And I don't quite understand the very last line in the calculation of ...
Boris Burkov's user avatar
1 vote
1 answer
68 views

No gradient for one parameter on the first iteration of gradient descent

Say we have a dataset $D$ of 2-tuples $(x, y)$ where $y$ is the target variable and a function $f_\theta$: $$ D = \{(1, 3), (2, 5), (3, 8), (4, 6), (5, 9)\},\quad f_\theta(x) = \theta_0 + \theta_1 x. $...
Saucy Goat's user avatar
1 vote
0 answers
120 views

Partial derivative of a Group Lasso

I am looking at the gradient descent method for group lasso questions. Here's what I am currently stuck at. Given the quadratic form of the objective function: $$ f(x) = \frac{1}{2} x^T V x - m^T x + \...
Kevin Choon Liang Yew's user avatar
0 votes
0 answers
40 views

from unconstrained to constrained convex optimization

Perhaps a silly question, but I have a Legendre-Fenchel-type optimization $$ \psi^{*}(y) = \max \limits_x \, \langle x,y \rangle - \lambda \, \psi(x) $$ for convex $\psi(x)$ and $\lambda > 0$, ...
RGB's user avatar
  • 1
1 vote
0 answers
32 views

Can we generate HPD regions from MCMC draws using convex hulls?

I thought of a procedure to generate high probability density regions with probability $1-\alpha$ from $n$ MCMC draws: Find the $\lfloor(1-\alpha)\cdot n\rfloor$ draws with the largest probability ...
PedroSebe's user avatar
  • 2,680
0 votes
0 answers
136 views

Speeding up an optimization involving matrix products in CVXR

I have an optimization problem where I need to minimize $$-\log \det(U^T \text{diag}(p) U + V^T\text{diag}(1 - p)V)$$ where $p$ is a vector of probabilities, i.e. $0 \leq p_i \leq 1$, and $U$ and $V$ ...
user avatar
0 votes
1 answer
336 views

Cost function of neural networks can be non-convex, then why do we use it?

I saw a thread here (Cost function of neural network is non-convex?). After I read this, I am really confused. I am wondering that if the cost function is not convex, and we do backpropagation, then ...
JAEMTO's user avatar
  • 103
0 votes
0 answers
141 views

How show that the Dantzig selector is equal to the Lasso when we are in the orthonormal case

I think all is in the title but I just will recall what is the Lasso and the Dantzig selector Lasso:We want minimize $\frac{1}{n}||y-X\theta||^2+2\tau|\theta|_1$ Dantzig: we want to minimize $|\theta|...
Fitz's user avatar
  • 1
0 votes
1 answer
106 views

Property of unbiased estimators

If $f(x)$ and $f(y)$ are both unbiased estimators of $\mu$, aka $E[f(x)]$ = $E[f(y)]$ = $\mu$, is it possible that $f((x+y)/2)$ is also an unbiased estimator of $\mu$? We know $f((x+y)/2)$ would be ...
VDCN's user avatar
  • 31
1 vote
1 answer
186 views

How do linear constraints affect the convexity of my OLS-like optimisation problem?

I would like to augment a linear regression (so a convex OLS problem) with some additional constraints on the coefficients to match the subject I'm working on. Having $x\in \mathbb{R}^n$, the solution ...
quentin's user avatar
  • 11
0 votes
1 answer
127 views

How do I find the optimal values for $\beta$ and $\beta_0$ for sparse linear regression model? Where does the mean of $\lambda$ come into account? [closed]

If someone could point me in the right direction that would be greatly appreciated! Consider the sparse linear regression model: $\min_{\beta_{0},\beta} \left \{ \frac{1}{2}\left \| \beta _{0}e + X\...
711's user avatar
  • 3
2 votes
0 answers
72 views

Gradient descent finds local minima for a problem that can be formulated as a convex problem

I am trying to find $$ \min_W \|Y-XW \|_F^2$$ $$s.t. \exists ij, W_{ij}\geq0 $$ where X is input data and Y is the output data we try to fit to. This is a convex optimization problem that can be ...
CWC's user avatar
  • 281
0 votes
0 answers
99 views

Does the existence of gradient in any function necessarily imply the existence of a subgradient at that point?

First , I apologize if the question is not supposed to be here, or if it is off topic for the subjects dealt with in here. I was reading on subgradients, with respect to convex functions in the ...
noobcoder's user avatar
  • 313
1 vote
1 answer
78 views

Can we benefit from a convex loss function when optimizing a neural network?

Many existing loss functions are convex since they are easy to optimize. However, they are only convex with respect to the output $y$, not to parameter $\theta$ of a neural network, or any other non-...
fatpanda2049's user avatar
0 votes
0 answers
70 views

Log convex function is actually log concave (Pattern Recognition and Machine Learning)

In Pattern Recognition and Machine Learning Ch 6.4.6 at the bottom of page 316 the author states that $p(a_N|t_N)$ is log convex. The author states that: $$-\nabla \nabla \Psi(a_N)=W_N+C_N^{-1}$$ is ...
tail_recursion's user avatar
4 votes
1 answer
1k views

Examples of strongly convex loss functions

This is a reference request. Strong convexity of the loss function is often used in theoretical analyses of convex optimisation for machine learning. My question is, are there important / widely used ...
axk's user avatar
  • 818
2 votes
0 answers
40 views

convex optimisation formulation of SVM

I am currently learning about Support Vector Machine's (SVM) from the CS229 Stanford Class. In page 16 of the notes, they transformed $$max_{\hat{\gamma}, w, b} \frac{\hat{\gamma}}{||w||} \\ s.t \,\,\,...
calveeen's user avatar
  • 1,116
1 vote
1 answer
151 views

Convex set of huber's contamination model

In the celebrated Huber's robust estimation paper, he considered the following model $x_i \sim (1-\epsilon) P_\theta + \epsilon G$ where $P_\theta$ is assume to be standard normal. Under this model, ...
cccfran's user avatar
  • 75
1 vote
1 answer
1k views

VC-Dimension of Axis-Aligned Right Triangles and 5-point Convex Hull

I am having trouble proving the following fact about the VC dimension of triangles. Consider axis-aligned right triangles in the plane, with the the right angle in the lower left corner. The ...
Dennis's user avatar
  • 113
3 votes
2 answers
831 views

Understanding step in proof of GAN algorithm convergence, involving convexity

I am reading the original paper on GANs, https://arxiv.org/abs/1406.2661. The proof of proposition 2, on the convergence of the gradient descent algorithm reads Consider $V(G, D) = U(p_g, D)$ as a ...
Arthur Conmy's user avatar