Newest 'convex' Questions

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 ...

asked May 23 at 12:31

axk

6064 silver badges14 bronze badges

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 \,\,\,...

machine-learning optimization svm convex lagrange-multipliers

asked May 1 at 14:12

calveeen

6961 silver badge10 bronze badges

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, ...

robust convex huber

asked Apr 19 at 5:36

cccfran

555 bronze badges

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 ...

machine-learning classification convex vc-dimension pac-learning

asked Apr 7 at 21:09

Dennis

1133 bronze badges

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 ...

machine-learning gradient-descent generative-models convex

asked Mar 23 at 16:30

Arthur Conmy

111 bronze badge

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 ...

optimization nonparametric convex nonparametric-bayes

asked Mar 15 at 4:40

cccfran

555 bronze badges

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 ...

regression optimization least-squares convex constrained-regression

asked Mar 3 at 23:53

zdebruine

1211 gold badge2 silver badges10 bronze badges

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?

machine-learning optimization gradient-descent convex

asked Mar 3 at 23:42

rade

312 bronze badges

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 ...

optimization convergence convex

asked Mar 2 at 19:36

Razzaghnoori

1112 bronze badges

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 ...

optimization gradient-descent gradient convex

asked Jan 31 at 17:02

Moritz Groß

1215 bronze badges

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 ...

optimization distance kolmogorov-smirnov-test approximation convex

asked Jan 6 at 16:27

Chp

33 bronze badges

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 ...

nonparametric density-estimation convex

asked Dec 8 '20 at 15:09

EngrStudent

7,8922 gold badges29 silver badges80 bronze badges

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 ...

self-study optimization convex

asked Dec 7 '20 at 21:28

user8714896

4851 silver badge9 bronze badges

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}\...

regression lasso convex

asked Dec 7 '20 at 13:05

statman

1056 bronze badges

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 ...

neural-networks optimization convex non-convex

asked Dec 3 '20 at 9:14

Fraïssé

7491 gold badge12 silver badges27 bronze badges

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 ...

optimization svm convex

asked Nov 17 '20 at 11:25

phil

13510 bronze badges

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\...

probability multivariate-normal-distribution convex

asked Nov 13 '20 at 2:57

Bernard Pan

1311 bronze badge

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 ...

regression optimization lasso quantile-regression convex

asked Oct 19 '20 at 6:37

CODE GEEK

753 bronze badges

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$...

optimization convex calculus

asked Sep 22 '20 at 23:17

T34driver

1,3824 silver badges10 bronze badges

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^{...

machine-learning generalized-linear-model maximum-likelihood integral convex

asked Sep 15 '20 at 1:26

Zhen Hao

11 bronze badge

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{...

optimization loss-functions gan convex

asked Sep 10 '20 at 4:23

develarist

2,8258 silver badges23 bronze badges

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? ...

optimization convex non-convex concavity

asked Sep 2 '20 at 0:08

develarist

2,8258 silver badges23 bronze badges

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(...

optimization gradient-descent convex

asked Aug 13 '20 at 14:20

Lisa

1312 bronze badges

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&...

machine-learning neural-networks optimization loss-functions convex

asked Aug 6 '20 at 7:57

user6507246

1431 silver badge9 bronze badges

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 ...

maximum-likelihood optimization convex non-convex

asked Jul 13 '20 at 2:50

deep_lazy

1

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, ...

convex bhattacharyya concavity quantum-computing

asked Jun 24 '20 at 18:20

helloworld

113 bronze badges

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 - \...

optimization convex

asked Jun 7 '20 at 7:51

user3389669

1916 bronze badges

5

votes

1answer

113 views

Optimization: Convex function

Problem statement Use the deﬁnition 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*} ...

machine-learning optimization function convex

asked May 25 '20 at 19:15

Stochastic

8011 gold badge6 silver badges26 bronze badges

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} ...

machine-learning optimization svm loss-functions convex

asked May 7 '20 at 22:04

abcd

1213 bronze badges

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 ...

logistic classification optimization convex

asked Apr 30 '20 at 21:57

Amit

234 bronze badges

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=...

optimization online-algorithms multiarmed-bandit convex

asked Apr 27 '20 at 6:46

Japneet Singh

134 bronze badges

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 ...

maximum-likelihood gamma-distribution convex numerical-models

asked Apr 8 '20 at 19:06

JMzance

2742 silver badges7 bronze badges

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 |...

regression optimization lasso convex

asked Apr 1 '20 at 20:33

tcb-lm81

111 bronze badge

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(...

kullback-leibler convex

asked Mar 25 '20 at 10:51

Chesso

1796 bronze badges

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 ...

machine-learning roc auc convex

asked Mar 10 '20 at 16:08

Laksan Nathan

1,6631 gold badge8 silver badges26 bronze badges

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 ...

optimization convex optimal

asked Mar 7 '20 at 19:15

FantasticAI

3871 gold badge3 silver badges12 bronze badges

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 ...

random-variable expected-value convex

asked Mar 5 '20 at 13:10

Antoni Parellada

22.4k15 gold badges94 silver badges186 bronze badges

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 $||.||_{*}$ ...

machine-learning optimization gradient-descent convex non-convex

asked Feb 14 '20 at 14:18

Upendra01

1,4463 gold badges16 silver badges28 bronze badges

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 ...

machine-learning svm nonlinear mathematical-statistics convex

asked Feb 11 '20 at 22:15

Luciano Silva Alarco

213 bronze badges

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 ...

convex inequality

asked Jan 22 '20 at 10:48

ShaharA

2181 silver badge6 bronze badges

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.} \...

machine-learning pca optimization convex

asked Jan 18 '20 at 22:18

Thoth

1234 bronze badges

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:...

causality geometry convex

asked Jan 2 '20 at 0:56

eric_kernfeld

4,5571 gold badge14 silver badges37 bronze badges

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 ...

generalized-linear-model optimization likelihood negative-binomial-distribution convex

asked Dec 28 '19 at 1:44

SWIM S.

7026 silver badges15 bronze badges

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 ...

clustering k-means convex non-convex

asked Dec 26 '19 at 14:04

yer

1155 bronze badges

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 ...

machine-learning classification svm optimization convex

asked Nov 29 '19 at 6:40

Eldacar Hyarmendacil

1655 bronze badges

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 ...

lasso regularization convex

asked Nov 16 '19 at 20:03

Peter

1036 bronze badges

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 ...

experiment-design geometry constraint convex optimal

asked Oct 21 '19 at 21:11

Rodrigo PG

112 bronze badges

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\...

machine-learning optimization reinforcement-learning online-algorithms convex

asked Aug 5 '19 at 4:03

Neil Chandler

111 bronze badge

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^{...

distributions density-function conditional-expectation convex

asked Jul 21 '19 at 18:34

capadocia

1114 bronze badges

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 ...

convex

asked May 22 '19 at 19:24

harsh grover

1312 bronze badges

Questions tagged [convex]

Related Tags