The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
0answers
58 views

What is the gradient of an Absolute Value..?

what is the gradient of the following term (with respect to vector $v_1$, where $C$ is simply a constant)?? $$L(v) =C\sum_k|v_k|$$ In other words, I want to find: $$\frac{dL(v)}{dv_1}$$
0
votes
1answer
33 views

Distributed Newton methods for large scale problems

I am keen to know about the literature landscape for distributed convex optimization methods which use second order information like the Newton step. This is as such a less evolved area compared to ...
1
vote
0answers
18 views

Is there a good textbook/book out there that explains sub gradients thoroughly?

I was interested in learning and understanding sub gradients as much as I could from some good resource. I know what the definition is, but I seem unable to apply the definition to prove basic facts ...
0
votes
1answer
30 views

What is the sub-differential of the separable sum $R(w) = \sum^{d}_{j=1} |w_j|$?

Recall the definition of a sub-differential: $$\partial F(w_0) = \{ v : \forall w, F(w)-F(w_0) \geq v \cdot (w - w_0)\} $$ Intuitively, for any w in the domain of the function one can draw a plane ...
1
vote
1answer
29 views

How does $\in$ behave with simple algebra dealing with sub gradients?

I was trying to understand the following optimization problem: $$argmin_{v \in H} {R(v) + \frac{1}{2}||v - w||^2}$$ Assume $R(v)$ is Convex, proper and semi-continuous with a unique minimizer. ...
0
votes
1answer
24 views

Subgradient example

Let $f(x_1, x_2)$ be defined as: if $x_1 =0$ then $f(x_1,x_2)=x^2_2$ else $\infty$ The subgradient of $f(x_1,x_2)$ at $(0,0)$ is given as: $\mathbf{R} \times \{0\}$. (The real line crossed with ...
1
vote
0answers
36 views

What is the left derivative of the hinge loss function in the context of subgradients?

Let: $$|a|_+ = max\{0,a\}$$ Then the Hinge loss function (in the context of classification in Machine Learning) is: $$V(-yf(x)) = |1 - yf(x)|_+$$ Note that $y \in \{-1,1\}$ Let $f(x) = \langle w, ...
0
votes
0answers
20 views

gradient descent - cost reduces and then increases

I am optimizing a function using Gradient Descent. The learning rate is fixed. First for few iterations the cost decreases after that it starts increases. What is the reason for this?
0
votes
0answers
12 views

Convergence results for incremental generalized gradient methods

Are there convergence results of incremental and stochastic subgradient / generalized gradient methods for locally Lipschitz functions that are not necessarily convex? I am mainly interested in ...
0
votes
1answer
48 views

Common subdifferentials of convex function

Let $f: \mathbb R^n \rightarrow \mathbb R$ be a convex function. By a subdifference of $f$ in $x\in \mathbb R^n$ we mean an $h\in \mathbb R^n$ such that $f(x) \geq f(p)+<x-p,h>$ for all ...
1
vote
1answer
22 views

Easy question about subdifferential of a functional on $L^2(0,T;L^2)$

Define $J:L^1(0,T;L^1) \to \mathbb{R}$ by $$J(v) = \int_0^T \int_\Omega \Psi(v)$$ where $\Psi(v) = \int_0^v \beta(s)\;ds$ where $\beta$ is a nice function that passes through the origin. We have ...
0
votes
0answers
28 views

Question about meaning of evolution problem.

Consider the following "evolution problem" $f(t) - u_t(t) \in \partial \psi(u(t))$ $u(0) = u_0$ Where $f:[0,T] \rightarrow H$ $ u:[0,T] \rightarrow H$ $ \psi:H \rightarrow (-\infty,\infty]$ is ...
0
votes
1answer
138 views

Smooth approximation of maximum using softmax?

Look at the Wiki page for Softmax function (section "Smooth approximation of maximum"): https://en.wikipedia.org/wiki/Softmax_function It is saying that the following is a smooth approximation to the ...
0
votes
1answer
19 views

gradient norm of a simple function

In this answer Derivation of soft thresholding operator how can I derive that $\nabla(||x-b||_2^2)=b-x$?
4
votes
2answers
382 views

Conjugates of norms

How would one find the conjugate of the following : $$f(x) = \|x\|^2 /2$$ The conjugate function is defined as $ f^*(y) = \max_x y^Tx - f(x)$ I am stuck at how I can derive the explicit form for ...
2
votes
1answer
46 views

Finding subgradients

How would I find the subgradients of this : $$ f(x) = \max_{i=1,\ldots,n} a_i^Tx + b_i$$ I'm new to subgradients and any hint on how to start this would be useful for me.
1
vote
1answer
59 views

What is the difference between projected gradient descent and ordinary gradient descent?

I just read about projected gradient descent but I did not see the intuition to use Projected one instead of normal gradient descent. Would you tell me the reason and preferable situations of ...
1
vote
2answers
51 views

Subdifferential of $(\eta^{\textrm{T}}\mathbf{K}\eta)^{\frac{1}{2}}$ at the origin

What is the subdifferential of the following norm at the origin \begin{align} \lVert\eta\rVert_{\mathbf{K}}=(\eta^{\textrm{T}}\mathbf{K}\eta)^{\frac{1}{2}} \end{align} where $\mathbf{K}$ is a ...
0
votes
0answers
54 views

KKT minimization problem

Solve $x^2 - 2y \rightarrow \min$ subject to $\max\{3x^2, e^y + 2\} + \sqrt{x^2 + y^2 - 2x + 1} \leq 6x + \sqrt{5}$ and $ \sqrt{x^2 + y^2 - 4x - 4y +8} -2x+2y \leq 0$ I tried computing the ...
0
votes
2answers
54 views

Confusion related to calculation of derivative

I have this function \begin{align} &s = f(\theta,x),\\ &s_1 = f(\theta,x_1),\\ &s_2 = f(\theta,x_2),\\ &P = A^T \left[\begin{array}{cc} s_1 & 0 \\ 0 & s_2 \end{array} \right] ...
1
vote
1answer
383 views

proximal operator of infinity norm

What is the proximal operator of $||x||_\infty $? I know we have to take the subgradient and compute it but I am a bit stuck. Can anyone show me steps?
0
votes
1answer
80 views

Confusion related to the calculation of gradient

I am having some confusion related to the calculation of gradient. My function $f(X) = g(X) + \lambda||X||_1$ where g(X) is convex and differentiable. I didn't get how the second expression when ...
1
vote
0answers
46 views

Confusion related to calculation of Hessian and notation

I was reading this paper where they have calculate the gradient and hessian of a function as I didn't get what the cross sign means here. Further I am confused about the second row first column ...
0
votes
1answer
273 views

Subdifferential of the sum

Let $C \subset \mathbb R^n$ a nonempty subset. Let us define the indicator function of $C$ $$ I_C(x) = \begin{cases} 0 & x \in C \\ +\infty & x \notin C \end{cases}. $$ Let us consider, in ...
0
votes
1answer
64 views

Subdifferential calculus

Let $\phi : H \to \mathbb{R}$ ($H$ is a vectorial space) be a convex function $\mathcal{C}^1$. I have the following inequality, for $\sigma \in H$ fixed, $$\forall \tau\in H, \ (\sigma - \tau \mid ...
1
vote
2answers
73 views

How many methods for smoothing an unsmoothed function?

Which is the simplest one? For example, we smooth $f(x)=|x|$ to $$f(x)=\begin{cases} \frac{x^2}{\epsilon}+\frac{\epsilon}{2} & |x| \le \epsilon\\ |x| & |x|\ge epsilon ...
1
vote
1answer
213 views

Solving a constrained Lagrangian dual problem

Consider the following $\max-\min$ integer programming formulation expressed in the binary decision variable $\mathbf{z}$: $$\begin{align*} \max&m \\ s.t.&\\ m \leq& s_i + \sum_j^J ...
0
votes
0answers
99 views

Calculation of the sub gradient of the first norm of a matrix

Lets say I have a matrix X and its first norm $||X||_1$. How do I calculate the subgradient of this norm with respect to matrix X itself.
2
votes
0answers
70 views

Nonlinear optimization of constraint parameter - subdifferential?

Disclaimer: I discovered that the FAQ suggests to post research-level to mathoverflow instead of math.stackexchange. I "moved" the question accordingly, cp. post at mathoverflow. Sorry for the ...
6
votes
0answers
192 views

Subgradient of convex minimization duality

$$\min(f_0(x))$$ $$\text{s.t. }f_i(x) \le y_i \forall i, i = 1 ,\ldots, m$$ $$f_i : \text{convex};\quad x : \text{variable}$$ It is also considered that $g(y)$ is the optimal value of the problem ...
1
vote
0answers
234 views

Gradient Descent for Primal Kernel SVM with Soft-Margin(Hinge) Loss

Given the primal objective $$F({\bf a})=L\sum_{i,j}a_{i}a_{j}k(x_i,x_j) + \sum_{i}max(0, 1-y_i \sum_{j}a_jk(x_i,x_j)$$ for the soft margin SVM, where ${\bf a}=(a_1,...,a_N)$, N being the number of ...
1
vote
1answer
128 views

Why is the set of subgradients a convex set?

I'm struggling to understand an example we were given. The problem description is: Let $f$ be a convex function in $E^n$. Prove that the set of subgradients of $f$ in a given point form a ... convex ...
2
votes
1answer
190 views

Mathematical applications of the subgradient

Do you know mathematical results which can be nicely proved using subgradient? For example, Jensen's inequilaty can be proved like that: Let $\varphi : \mathbb{R}^n \to \mathbb{R}$ be a convex ...