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
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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. $...
user avatar
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 ...
user avatar
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 + \...
user avatar
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$, ...
user avatar
  • 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 ...
user avatar
  • 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$ ...
user avatar
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 ...
user avatar
  • 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|...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 , ...
user avatar
  • 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\...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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-...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 \,\,\,...
user avatar
  • 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, ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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?
user avatar
  • 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 ...
user avatar
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)$?
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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}\...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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\...
user avatar
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 ...
user avatar
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$...
user avatar
  • 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{...
user avatar
  • 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? ...
user avatar
  • 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(...
user avatar
  • 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&...
user avatar
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 ...
user avatar
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, ...
user avatar
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 - \...
user avatar
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*} ...
user avatar