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.
142
questions
0
votes
0
answers
13
views
What is the Best Neural Network architecture to estimate a convex function?
I am currently working on a Q learning algorithm for multi-agent systems and sub-classes of Dec-POMDPs .. It has been shown before that the Q value at any time step can be reduced to a piecewise ...
0
votes
0
answers
18
views
How is the objective function of the different flavors of GARCH different?
How does the objective function/likelihood function of these different GARCH variations differ? Is it convex in all cases? Knowing convexity tells me whether some are not possible to find a globally ...
- 285
1
vote
0
answers
32
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 ...
- 308
1
vote
1
answer
28
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.
$...
- 169
0
votes
0
answers
21
views
t-Copula MLE on nu (DoF) only - log-likelihood function possibly convex?
I am working with t-Copula's to generate random synthetic data eventually. The paper I use as the foundation is Benali et al., 2021. To determine the best fitting t-Copula, they propose determining ...
1
vote
0
answers
35
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 + \...
0
votes
0
answers
33
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
0
answers
17
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,536
0
votes
0
answers
31
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$ ...
user272429
0
votes
1
answer
79
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
0
votes
0
answers
31
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|...
- 1
0
votes
1
answer
53
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 ...
- 1
1
vote
1
answer
69
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 ...
- 11
0
votes
0
answers
15
views
Finding subdifferentials of lasso regularizers (Lasso, Group, and Fused)
I understand how to find the subdifferential for $\lambda\left \| x \right \|_{1}$ but the other two I'm not sure.
Let $\phi: \mathbb{R}^{n}\rightarrow \mathbb{R}$ be a regularizer combining lasso , ...
- 3
0
votes
1
answer
40
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\...
- 3
0
votes
0
answers
13
views
Clarification needed for a proof step in the paper "Perceptron Mistake Bounds"
I was trying to understand the section 3.1 L1 norm mistake bound (for non-separable case). In the proof of theorem 2, there is a step that takes into account the property of convexity and derives an ...
- 1
2
votes
0
answers
52
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 ...
- 261
0
votes
0
answers
39
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
0
votes
0
answers
13
views
Convergence analysis for federated learning using DNN model
In convergence analysis of federated learning (FL), usually, we have an assumption that the loss function is strongly convex. However, when the loss function model is non-convex, e.g., using DNN, I ...
- 101
0
votes
0
answers
93
views
Convergence of CAVI(Coordinate Ascent Variational Inference)
I was reading several resources on variational inference, and most of them stated that the CAVI algorithm converges to local maximum, and Bishop's textbook stated that the convergence is guaranteed as ...
- 21
1
vote
1
answer
54
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-...
- 45
0
votes
0
answers
36
views
Find an extreme point (of a convex polytope) with the minimum of a quadratic cost function
For example, I am trying to do the following:
Doubly stochastic matrices (i.e. matrices whose rows and columns sum to 1) form a polytope with permutation matrices as extreme points (Birkhoff–von ...
- 261
0
votes
0
answers
44
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 ...
- 249
3
votes
1
answer
219
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 ...
- 736
2
votes
0
answers
31
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 \,\,\,...
- 926
0
votes
1
answer
45
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, ...
- 55
1
vote
0
answers
362
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 ...
- 113
2
votes
2
answers
240
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 ...
- 21
2
votes
1
answer
85
views
Why nonparametric maximum likelihood of mixture is convex
Consider $x_i \sim N(\mu_i, 1)$ where $i = 1, \ldots, n$ and assume $\mu_i$ is generated i.i.d. from an unknown distribution $F$. We are interested in estimating the unknown $\mu_i$. One way to solve ...
- 55
0
votes
1
answer
203
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 ...
- 151
3
votes
1
answer
38
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?
- 31
1
vote
0
answers
27
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 ...
- 111
5
votes
2
answers
255
views
Minimum expectation
The random variable $X$ has a continuous distribution. For an increasing density function $f(X)$ defined in the interval [0,1], what can be the minimum value of its expectation ${E} (X)$?
user312739
0
votes
0
answers
54
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 ...
- 121
0
votes
1
answer
33
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 ...
- 33
1
vote
0
answers
28
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 ...
- 8,300
4
votes
2
answers
114
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}\...
- 125
5
votes
1
answer
806
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,081
1
vote
1
answer
100
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 ...
- 341
3
votes
0
answers
40
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\...
- 131
4
votes
1
answer
55
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 ...
- 75
1
vote
0
answers
62
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$...
- 1,734
0
votes
2
answers
938
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{...
- 3,089
-1
votes
1
answer
79
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,089
3
votes
0
answers
69
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(...
- 131
1
vote
1
answer
80
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&...
- 143
0
votes
1
answer
109
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
1
answer
29
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, ...
- 71
2
votes
1
answer
41
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 - \...
- 233
5
votes
1
answer
387
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*}
...
- 809