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.

166 questions
Filter by
Sorted by
Tagged with
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-...
• 157
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$ \...
• 157
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 ...
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 ...
• 313
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, ...
• 1,337
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 ...
1 vote
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 ...
• 255
1 vote
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'...
• 235
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 ...
• 21
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 (...
313 views

• 121
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.
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 ...
• 1,015
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, ...
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 ...
• 23
1 vote
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 ...
• 925
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 ...
420 views

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 ...
• 144
1 vote
26 views

• 246
232 views

CVXPY PSD constraint not working

I am using CVXPY to solve for a PSD matrix, example as follows: ...
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 ...
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 ...
• 378
1 vote
68 views

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$, ...
• 1
1 vote
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 ...
• 2,680
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$ ...
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 ...
• 103
141 views

• 3
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 ...
• 281
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 ...
• 313
1 vote
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-...
• 155
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 ...
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 ...
• 818
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 \,\,\,...
• 1,116
1 vote
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, ...
• 75
1 vote
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 ...