Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

2
votes
1answer
114 views

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

Let $f(a_1, a_2, · · · , a_n) = \ln (e^{a_1} + e^{a_2} + \cdots + e^{a_n} )$. Show that $f$ is convex. Now, to show that is a function is convex, we can take second derivative of the function and if ...
1
vote
1answer
36 views

How to recover primal problem from its dual counterpart

I am asking this from context of optimization in machine learning. We often talk about a primal problem and how this primal problem can be solved by first converting it into a dual problem (Using ...
0
votes
0answers
12 views

How to get precise answer from stochastic gradient descent

I have a convex optimization problem in few variables and I have an unbiased estimator of the gradient without having the ability to evaluate the function itself. I want to do gradient descent but the ...
1
vote
0answers
48 views

How positive definite Hessian approximations for SGD (e.g. Gauss-Newton) handle saddles?

For example due to symmetry of parameters, functions optimized in machine learning usually have huge number of local minima and saddles - growing exponentially with dimension. I am trying to ...
2
votes
0answers
22 views

How to solve a non-convex with equality constraint optimization problem?

I have a non-convex optimization problem with equality constraint, I can derive the KKT conditions, but it seems just one of the KKT conditions is valid. Could you please give some advice on how to ...
1
vote
2answers
99 views

Convexity of cross entropy

I am not sure if this is a better fit for this site or mathematics.stackexchange but I've seen similar questions on here before. I'd like to know if the following is true and if so, how I could go ...
0
votes
0answers
21 views

Why H(y) is a concave function of p(x) when p(y) is a linear function of p(x)?

I got stuck in the line when reading a theorem in The Elements of Information Theory on page 59: If p(y|x) is fixed, then p(y) is a linear function of p(x). Hence H(Y), which is a concave ...
2
votes
0answers
29 views

Normal equations issue

Let $A\mathbf{x}=\mathbf{b}$ be an overdetermined system, with $A$ being an $n \times m $ full-column rank rectangular matrix. Are these minimization problems equivalent? $$ 1) \;\underset{\mathbf{x}...
0
votes
0answers
26 views

Coordinate descent in integer programing: when does it work?

Denote $N_i=\{0,1,\dots,\bar{n}_i\}$ and define $N=N_1\times \dots \times N_I$. I want to minimize a function $f:N\rightarrow \mathbb{R}$. For the functions $f$ that interest me, it is very easy to ...
0
votes
1answer
81 views

Is error function always assumed and convex?

While updating weights of the neural network, most of the algorithms use convex optimisation because of the reason that error is a convex function. My doubt is that whether the convex-ness of error ...
1
vote
1answer
45 views

How to understand whether Stochastic Gradient Descent has converged?

I am using SGD to solve for MSE function. My training set is around 50K, and I am monitoring the gradient at every epoch (once a pass is completed over all the training data). I played around a lot ...
2
votes
1answer
108 views

Regularizing the inverse coefficient matrix in multivariate regression

I'd like to minimize the objective $ \operatorname{tr}[ (Y-XR^{-1})^T (Y-XR^{-1}) ] + \lambda \sum_{ij} |R_{ij}|$ wrt to $R$ (which is $P \times P$ but non-symmetric) where $Y$ and $X$ are both $N \...
1
vote
0answers
23 views

How to diagnose why numeric solver is not converging? [closed]

Are there specific approaches, methods or software that help in determening why an optimum is not found for a particular optimization problem? For example, the solution landscape could be visualized ...
2
votes
0answers
37 views

Optimization textbooks for statistics and data analytics

Any statistical analysis, machine learning or data science involves some sort of optimization at the end of the day. I'm looking for good linear and nonlinear optimization textbooks for self ...
22
votes
6answers
3k views

For convex problems, does gradient in Stochastic Gradient Descent (SGD) always point at the global extreme value?

Given a convex cost function, using SGD for optimization, we will have a gradient (vector) at a certain point during the optimization process. My question is, given the point on the convex, does the ...
0
votes
0answers
45 views

How to prove that a surrogate cost function is lower bound to original cost function?

This is very specific to a research paper that have been reading recently: It is about constructing cost functions that are more correlated to non-decomposable (cannot be broken down to a summation ...
2
votes
0answers
117 views

Vapnik-Chervonenkis Dimension

My question has to do with the VC dimension of the class of convex polygons with $m$ vertices. A solution to this problem is given in the following: Advanced Algorithms. Call the class of all ...
3
votes
1answer
714 views

Any optimization problem can be expressed as one with a linear objective

For any standard optimization problem(think linear programming, convex, non-convex problem), would it be possible to express the optimization problem as one with a linear objective?
3
votes
1answer
67 views

Why is global convexity not possible in higher-dimensional settings for this loss function?

I was reading this paper which discusses nonconvex penalized regression. They use the following notation: $X\in\mathbb{R}^{n\times p}$ is a data matrix with $n$ observations in $p$ variables $\beta\...
2
votes
0answers
32 views

Why proximal gradient is a special case of sub-gradient?

While I was learning proximal gradient descent methods, I saw many similar statements as below: $$p=prox_f(x) \Longleftrightarrow x-p \in \partial f(p) $$ for example, ...
3
votes
1answer
248 views

What is the use of the log of the sum of exponents in machine learning

I want to understand why somebody would use log sum exponent trick. I am reading this blog. But I don't really understand the first paragraph. It says Let's say we have an n-dimensional ...
1
vote
0answers
22 views

Low-variance estimate for the mean of the sotfmax transformation of a variable

Consider a set of infintiely-differentiable convex functions real-valued functions $f_i: \mathcal X \rightarrow \mathbb R$, where $i$ varies from $1$ to $m$, and suppose we know all the moments of $...
2
votes
1answer
94 views

L2 SVM (squared hinge) theory

The linear L2 SVM can be intuitively understood as \begin{equation} \text{minimize } f(\boldsymbol{w}) = \frac{1}{2} \Vert\boldsymbol{w}\Vert^2_2 + C \sum_{i=1}^m \xi_i^2 \tag{1} \end{equation} ...
1
vote
0answers
90 views

Working between sklearn and scipy for convex optimization [closed]

I have a method for solving convex programs using an alternative method of iterative procedures and would like to compare this to current solvers methods. My approach relies upon randomly projecting ...
1
vote
0answers
46 views

Which machine learning methods include convex maximization? [closed]

As far as I know, maximizing a convex function (or minimizing a concave function) is an NP-hard problem even with linear constraints. Which machine learning methods include such a setting? Can we ...
0
votes
0answers
73 views

Is cross-entropy loss for MaxEnt models convex? If so, how do I prove it?

I am trying to prove if cross-entropy loss for MaxEnt models is convex. My first attempt at approaching this problem is to compute the Hessian matrix of second-order partial derivatives and showing ...
1
vote
1answer
76 views

Is the difference between two iid log-concave distributions still log-concave?

Assume two iid random variables X and Y, with continuous and differentiable pdf $f$ and cdf $F$. Let Z=X-Y. Is the pdf of Z log-concave?
1
vote
1answer
97 views

Restriction of concave function to bounded convex set is concave?

Suppose I have a function that is concave, and has as its domain $R^n$. If I restrict the function to a bounded convex set, say the probability simplex, then the resulting function should still be ...
26
votes
6answers
7k views

Why study convex optimization for theoretical machine learning?

I am working on theoretical machine learning — on transfer learning, to be specific — for my Ph.D. Out of curiosity, why should I take a course on convex optimization? What take-aways from convex ...
2
votes
2answers
316 views

Variance of the reciprocal of a strictly positive random variable

In this post it is stated that due to Jensen's inequality the expected value of the reciprocal of a strictly postive random variable $X$ will satisfy: $$\mathbb{E}\left[\frac{1}{X}\right] \geq \frac{...
2
votes
0answers
90 views

KKT condition in layman's term

The most intuitive explanation for KKT condition I can find is this post, which is still too complex to me. Is there any more intuitive explanation? How to introduce this to a layman?
2
votes
1answer
53 views

Why does Jensen's imply this?

Let $F$ be a convex function. If $Y$ and $Z$ are independent random variables and $EZ=0$, then $$EF(Y) = EF(Y+EZ)\leq E(Y+Z).$$ I fail to understand why the last inequality is true. Can someone ...
1
vote
1answer
170 views

Is the log loss function $f(w) = y_t \log(y_p) + (1 - y_t) \log(1 - y_p)$ convex in $w$? [duplicate]

Kaggle defines the log loss function as: https://www.kaggle.com/wiki/LogarithmicLoss $$f(w) = \log \Pr(y_t|y_p) = y_t \log(y_p) + (1 - y_t) \log(1 - y_p)$$ Let $y_t \in {0, 1}$, and $y_p$ is given ...
1
vote
1answer
83 views

convexity of two convex function combined

If I have such an optimization problem: $$ \arg\min_{x,z} \dfrac{||y-x||_2^2}{z}+z(||y-x||_2^2) $$ where $y$ is known and $z>0$. If $z$ is fixed, then this function w.r.t $x$ is convex. Similarly,...
0
votes
0answers
36 views

Convex subspaces and zero covariance?

$\DeclareMathOperator*{\argmin}{arg\,min} \newcommand{\E}{\text{E}}$ This is from the Analytics Iowa LLC notes provided at http://www.public.iastate.edu/~vardeman/stat602/StatLearningNotesII.pdf, p. ...
12
votes
3answers
2k views

Is PCA optimization convex?

The objective function of Principal Component Analysis (PCA) is minimizing the reconstruction error in L2 norm (see section 2.12 here. Another view is trying to maximize the variance on projection. We ...
2
votes
1answer
229 views

Gaussian Processes for convex functions

As I understand, when using Gaussian Processes (GP) for regression, one can/should incorporate prior knowledge about the function into the GP. Let's say I have a nonlinear function $f: \mathbb{R}^n \...
3
votes
2answers
2k views

Logistic Regression is a Convex Problem but my results show otherwise?

I know that logistic regression is a convex problem. Furthermore, from Lemma 1.17 in these optimization lecture notes, if a function $f : \mathbb{R}^n \rightarrow \mathbb{R}$ is convex, then the ...
20
votes
1answer
4k views

Why is the cost function of neural networks non-convex?

There is a similar thread here (Cost function of neural network is non-convex?) but I was not able to understand the points in the answers there and my reason for asking again hoping this will clarify ...
1
vote
2answers
85 views

normalization constraint in support vector machine

A support vector machine initially poses the following optimization problem: $$max_{\gamma, w, b} \gamma \\ s.t\ \\ y^{(i)}(w^Tx^{(i)} + b) \ge \gamma,\ \ i=1,\dots,m \\ ||w|| = 1$$ I understand the ...
3
votes
1answer
278 views

Online convex optimization: Why use strongly convex regularizer for regularized-follow-the-leader instead of strictly convex (or just convex)

I've read through Hazan's paper on online convex optimization. I don't quite understand why the regularization term must be strongly convex instead of more relaxed condition such as strictly convex. ...
5
votes
2answers
830 views

Logistic regression cost surface not convex [duplicate]

I am building a simple logistic regression model on 2D data. Here is the input I use. I built a logistic regression model using this data and it successfully is able to find the discriminating line ...
1
vote
1answer
347 views

Derivation of the Iterative Reweighted Least Squares Solution for $ {L}_{1} $ Regularized Least Squares Problem

I'm trying to fitting a line with IRLS with L1 norm, but I'm struggling to understand why my idea is wrong. 1 - init the weights $w$ 2 - fit with simple LS and obtain a starting model $\beta_0$ 3 - ...
4
votes
2answers
1k views

In online convex optimization, what is a leader in FTL algorithm?

I am currently reading into online convex optimization. Can someone please explain me what exactly is a leader in the Follow-The-Leader algorithm and its variants? Why is it called Follow-The-Leader?...
2
votes
1answer
178 views

Writing Random variable $X$ as a convex combination of $a$ and $b$

When proving the Hoeffding's lemma on Wikipedia, it says Next, recall that $e^{sX}$ is a convex function on the real line: $\forall X \in [a,b]: $ $e^{sX} \le \frac{b-x}{b-a}e^{sa} + \frac{x-a}...
3
votes
2answers
441 views

Convexity, linearity and their combination for MLE

I'm going through Murphy's ML a Probabilistic Perspective book and in chapter 9 we have the following excerpt talking about the MLE of exponential family distributions: My question is: How do we ...
1
vote
1answer
73 views

Difference between minima of L1-regularized quadratics

How can I find $$F(A,b,x,c)=\inf_{\theta\in\mathbb{R}^n}(\theta^{\top}A\theta+b^\top\theta+x^\top\theta+c||\theta||_1)-\inf_{\theta\in\mathbb{R}^n}(\theta^{\top}A\theta+b^\top\theta-x^\top\theta+c||\...
7
votes
1answer
171 views

Relating $f(\mathrm{Var}[X])$ to $\mathrm{Var}[f(X)]$ for Positive, Increasing, and Concave $f(X)$

The arrival of photons at a pixel in an image sensor is a Poisson distributed random variable such that the input can be modeled as a Poisson r.v. $X\sim \mathrm{Poisson}(\lambda)$. Since the input ...
0
votes
1answer
343 views

Is a linear discriminant function actually “linear”?

Chris Bishop introduces the multi-class linear discriminant functions (a.k.a. linear machine) in PRML as follows (p. 183): In proving the convexity of decision regions, it's assumed that $y_k(\cdot)$ ...
0
votes
1answer
244 views

Would the support vectors in SVM algorithm change with scaling of the functional margin?

Would the Support Vectors in the SVM algorithm change every time that I change the functional margin ? The optimization objective in the SVM algorithm is this - The rest of the SVM optimization ...