# 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
Filter by
Sorted by
Tagged with
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 ...
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 ...
1 vote
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 ...
1 vote
28 views

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 vote
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 ...
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$ ... 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 ...
31 views

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 ...
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 ...
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 ...
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 ...
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 ...
1 vote
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-...
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 ...
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 ...
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 ...
31 views

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 \,\,\,... 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, ... 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 ... 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 ... 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 ... 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 ... 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? 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 ... 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)? 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 ... 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 ... 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 ... 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}\... 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 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 ... 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\... 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 ... 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... 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{...
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? ...