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
1answer
24 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 ...
2
votes
0answers
24 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 \,\,\,...
0
votes
1answer
27 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
0answers
159 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 ...
1
vote
1answer
29 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
1answer
54 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
1answer
72 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
1answer
34 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
0answers
19 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 ...
0
votes
0answers
31 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
1answer
27 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 ...
0
votes
0answers
14 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 ...
0
votes
0answers
13 views

ADMM updates of $\min_{\beta_1,…\beta_3,\beta}\sum_{i=1}^{3}\frac{1}{2}||y_i-X_i\beta_i||_2^2+\lambda||\beta||_1$

ADMM updates of $\min_{\beta_1,...\beta_3,\beta}\sum_{i=1}^{3}\frac{1}{2}||y_i-X_i\beta_i||_2^2+\lambda||\beta||_1$ s.t. $\beta_1=\beta=\beta_2=\beta_3$ So this is a HW problem and I dunno why they ...
4
votes
2answers
108 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}\...
4
votes
1answer
201 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
1answer
38 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
0answers
35 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
1answer
47 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
0answers
61 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
0answers
151 views

How to prove that the convexity of Generalized Linear Models?

Refer to question: Does log likelihood in GLM have guaranteed convergence to global maxima? The top answer said that one can prove $\frac{d A}{d \theta}=\mathbb{E}[\phi(x)]$ $\frac{d^{2} A}{d \theta^{...
0
votes
2answers
305 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{...
0
votes
1answer
61 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
votes
0answers
36 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(...
1
vote
1answer
37 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&...
0
votes
1answer
37 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
1answer
16 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, ...
2
votes
1answer
32 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 - \...
5
votes
1answer
113 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*} ...
2
votes
0answers
59 views

Sum of SVM hinge losses always a convex function?

The data loss function for a multi class SVM may take the following expression: \begin{equation} L=\frac{1}{N}\sum_{i}\sum_{j\neq y_i}\left[ \max(0,w_j^Tx_i-w_{y_i}^Tx_i+1)\right] \end{equation} ...
2
votes
1answer
33 views

Question about Decision boundary in Logistical Regression

I am a Machine Learning newbie and studying Logistical Regression. For the data shown above, a straight line cannot separate all the positive and negative decisions. One thing I could understand is ...
1
vote
1answer
77 views

Doubt about definition of Regret in Online convex optimization setting

In online convex optimization, the regret of an algorithm $\mathcal{A}$ as defined in Introduction to Online Convex Optimization (Page 5) is: $$ regret_T(\mathcal{A}) = \sup_{\{f_1,...,f_T\}} \sum_{t=...
2
votes
1answer
91 views

Iterative solution to Gamma distribution MLE problem

I'm trying to follow the derivation for the MLE parameters of the gamma distribution in [1]. The standard approach is to derive an expression for the log likelihood, differentiate with respect to ...
1
vote
0answers
27 views

Extended Lasso problem ( two L1 norms)

I am trying to find a closed form solution for the following problem : $$ \underset{\beta}{\operatorname{minimize}} \frac{1}{2} || y - X \beta ||^{2} + \lambda || \beta ||_{1} + \mu || \beta - \gamma |...
1
vote
0answers
19 views

Kullback-Leibler divergence from density f to density g

If $f$ and $g$ are density functions that are positive over the same region, then the Kullback-Leibler divergence from density $f$ to density $g$ is defined by: $$KL(f,g) = E_f\left[\ln\left(\frac{f(...
2
votes
0answers
131 views

ROC Convex Hull for Model Selection

The area under the convex hull of a roc curve is by construction always "better" than its area under curve. Some curves might see more of an increase in reported auc than others. Is it a viable ...
2
votes
1answer
42 views

How to understand the sufficient condition for global optimum for a constrained optimization probelm

How to understand the sufficient condition for global optimum? From my understanding, the global optimum should be 0 instead of $\geq 0$, where does this come from? Consider the constrained ...
2
votes
1answer
46 views

Basic question about labeling of random variables apropos of the definition of convexity

I understand the definition of convexity in a function $f: \mathbb R^d \to \mathbb R$ as the inequality for all $a,b\in\mathbb R^d$ and $0<\theta<1:$ $$\theta f(a) + (1-\theta)f(b) \geq ...
1
vote
0answers
82 views

How to minimize the sum of Frobenius norm and Nuclear norm

I have to minimize an objective function of the the form : $||X_{s} - Y_{s}D_{s}||_{F}^{2} + ||D_{s}||_{F}^{2} + ||D_{s}||_{*}^{2}$ where $||.||_{F}$ denotes the Frobenius norm and $||.||_{*}$ ...
2
votes
2answers
40 views

Optimization equivalence

Can someone help me with the step by step demonstration of the following equivalence used in SVM: $$maximize: m = \frac{1} {\|w\|} \equiv minimize: m =\frac{1} {2}\|w\|^2 $$ I would be most grateful ...
1
vote
1answer
66 views

Strongly convex function evaluated over a mean of n points

Let f(x) be a Strongly-convex function under some m > 0. Given two points x, y it is known that: $$f(\frac{x + y}{2}) \leq \frac{f(x) + f(y)}{2} - \frac{1}{2^3} \cdot m \cdot ||x - y||^2$$ What is ...
2
votes
1answer
39 views

Some tricky details about PCA non-convexity

I am reading about PCA and I came up with a some contradictions. PCA based on this post, PCA optimization problem is given by: $$\begin{aligned} \max_{w} \quad & w^T\Sigma w\\ \textrm{s.t.} \...
0
votes
1answer
7 views

Intervals from an underdetermined nonnegative linear system

I'm working on a problem in genomics that yields the following puzzle. Let $b\in \mathbb R^I$, $t$ and $p\in \mathbb R^J$, and $s \in \mathbb R^{I\times J}$. Suppose $t,b,p$ are known. Further suppose:...
2
votes
2answers
230 views

Concavity of negative binomial GLM

I need to estimate the log-likelihood of the negative binomial regression. I mean full log-likelihood, including the dispersion parameter. The problem is: when I start LBFGS, BFGS, or gradient ...
3
votes
1answer
250 views

Why are K-means and GMM (Gaussian Mixture Models) not suitable for discovering clusters with non-convexs shapes?

I have seen that mainly here and from a lot of resources that K-means and Hello all! Gaussian mixtures are not suitable for detecting clusters with non-convex shapes. I know that because both ...
1
vote
1answer
38 views

Why does the formulation of the SVM problem has the bias (something we try to optimize) as a part of the constraint?

The common formulation of the SVM problem is $$\min_{\theta, \theta_0}\frac{1}{2}||\theta||^2$$ $$\text{ subject to: } y^{(t)}(\theta \cdot x^{(t)} + \theta_0) \geq 1, \ t=1,...,n,$$ However, it ...
5
votes
2answers
372 views

L1-regularization enforces sparsity for convex functions

I have a convex function $f \colon \mathbb{R}^n \to \mathbb{R}$ that I minimize using L1-regularization: $\DeclareMathOperator*{\argmin}{arg\,min}$ $$ x^*=\argmin_x f(x) + \lambda ||x||_1 $$ Can I ...
1
vote
1answer
55 views

D-optimal DOE suggest repeated samples

I tried to generate a D optimal design but the design output sounds very weird to me. I have a (real) process and I`d like to explore 3 factors, but the process have a lot of constraints so I provide ...
1
vote
1answer
88 views

Online Optimization - Regret in Absolute Error

In the online convex optimization literature static regret is defined as $\sum_{t=1}^{T}\left(f_t\left(x_t\right)-f_t\left(x^*\right)\right)$ where $x^*=\arg min_{x\in\mathcal{X}}\sum_{t=1}^{T}f_t\...
1
vote
0answers
85 views

Convexity of conditional expectation

Define $g(k)\equiv\mathbb{E}(X|_{X>k})$ and assume that the probability density $f$ of $X$ is twice continuously differentiable. Is there a sufficient condition in terms of $f$ that imply that $g^{...
3
votes
1answer
349 views

Prove that a function $\ln (e^{a_1} + e^{a_2} + \cdots + e^{a_n} )$ is convex?

Define the function: $$f(a_1, a_2, · · · , a_n) = \ln (e^{a_1} + e^{a_2} + \cdots + e^{a_n} ).$$ I want to prove that $f$ is convex. Now, to show that is a function is convex, we can take second ...