The tag has no usage guidance.

learn more… | top users | synonyms

-1
votes
0answers
10 views

Difference between mirror descent and dual averaging [closed]

What is the main differences between mirror descent and dual averaging methods? When the number of steps or accuracy are fixed, they are equivalent. But what can be said when these parameters are not ...
0
votes
0answers
15 views

subdifferential of $\max_{i=1,\cdots,k} x_i+\frac{1}{2}\|x\|_2^2,\ \ \ x\in \mathbb{R}^n$

How to find the subdifferential of $$f(x) = \max_{i=1,\cdots,k} x_i+\frac{1}{2}\|x\|_2^2,\ \ \ x\in \mathbb{R}^n$$ My derivation is: $\nabla \frac{1}{2}\|x\|_2^2=\nabla \frac{1}{2}x^Tx=x$ ...
0
votes
0answers
7 views

More understanding about $E_u[\partial_x h(x,u)]$, $u$ is a random variable

Consider the subdifferential "$\partial_x h(x,u)$", $u$ is a random variable. (Note: subdifferential is a set with the definition in subgradient method.) How to understand $$E_u[\partial_x h(x,u)]$$ ...
0
votes
1answer
25 views

Subgradients of non-convex functions

In these notes (section 2.3), it is stated that: A point $x^*$ is a minimizer of a function $f$ (not necessarily convex) if and only if $f$ is subdifferentiable at $x^*$ and $0 \in\partial ...
0
votes
0answers
9 views

Lower bound of averaging gradient method (Prof. Yurii Nesterov's paper)

I am reading the paper of Prof. Yurii Nesterov: Primal-dual subgradient methods for convex problems The last inequality confuses me: (p.231) Note: 1. The ...
0
votes
0answers
24 views

Subdifferential optimality conditions

I need help with subdifferential optimality. Let $f(x_1, x_2)=x_1^2 + x_2^2 + |x_1 -x_2 - y|$. Find: \begin{align} \min_{x_1, x_2} f(x_1, x_2) \end{align} This is convex, so must have unique ...
1
vote
1answer
26 views

Proximal-type support function properties - nonnegative & strongly convex (proof)

I am reading the paper of Prof. Yurii Nesterov: Primal-dual subgradient methods for convex problems The following part confuses me: $\\$ $\\$ ...
1
vote
1answer
33 views

Proof of unique solution of strongly convex function (Prof. Nesterov Paper)

I am reading the paper of Prof. Yurii Nesterov: Primal-dual subgradient methods for convex problems I am confused about the green part of the following: $\\$ ...
0
votes
0answers
15 views

Lipschitz condition for the stochastic subgradient

We know that for the subgradient method convergence, $f$ should satisfy the Lipschitz condition, i.e., $|f(x_1)-f(x_2)|\leq G\|x_1-x_2\|_2\ \ \ $ for all $x_1, x_2$ For the stochastic ...
0
votes
0answers
21 views

Subgradient of function of two variables

i do not have any experience in convex analysis and I would be most grateful if you would help me with the concept of subgradient. I get the concept of subderivative (one dimension) but it is hard ...
2
votes
0answers
23 views

Can a subgradient always be found in polynomial time?

Given a convex function, under what conditions can we find a subgradient in polynomial time? There are easy examples such as $f$ being an supremum of a finite number of differentiable functions, but ...
0
votes
0answers
46 views

L1-norm minimisation

I am working on this tutorial question. The question asks me to write a Matlab code to implement the method. I was stuck in how to formulate a code for the proximal operator as well as the ...
0
votes
1answer
35 views

Subgradient at the boundary of a closed set

Suppose I have the convex function $f(x) = |x|$ over the domain $x \in [-1,1]$, and I wish to find the subgradient. It is easy to find the subgradient in the interior of the domain. At the ...
0
votes
0answers
16 views

Find the subgradient set of $\|x\|$ in $x=0$

Find the subgradient set of $\|x\|$ in $x=0$, $x\in\mathbb{R}^n$ I already solved the problem by definition, but I am asking for another easier way, thanks.
0
votes
0answers
38 views

How to find the subgradients of $f(x)=\|x\|^2-1$ if $\|x\|\geq 1$, $f(x)=0$ if $\|x\|\leq 1$, $x\in\mathbb{R}^2$.

How to find the subgradients of $f(x)=\|x\|^2-1$ if $\|x\|\geq 1$, $f(x)=0$ if $\|x\|\leq 1$, $x\in\mathbb{R}^2$. By definition a subgradient $a$ must satisfy $f(x+y)\geq f(x)+a\cdot y$ I just have ...
0
votes
1answer
39 views

about scaling property of proximal operator

If the proximal operator of $f(x)$ is $\text{prox}_{\lambda f}(x)$, what about $cf(x)$ and $f(cx)$, c is a scalar. For example, If $f(x) = ||x||_{1}$, $x \in \mathbb{R}^{n}$, how about the proximal ...
0
votes
0answers
19 views

Scaling issue with Gradient descent methods

As is the common knowledge that gradient methods are affected by scaling issue of the variables. For example, If minimizing a function of say 2 variables $x_1$, $x_2$. Both variables have different ...
0
votes
1answer
20 views

Conditions of convergence of stochastic subgradient algorithm

It is well known that for appropriate step size, $E[g^t] \in \partial f(x^t)$ is sufficient conditions for this subgradient algorithm to converge. What I'm wondering is whether the requirement has to ...
0
votes
3answers
22 views

Gradient on curves

Please with a bit of explanation, what is the gradient on the curve $y = 16/x$ where $x = 8$. I'm finding it hard to solve problem like this.
3
votes
1answer
60 views

Geometric concept of $A$-orthogonality, $A>0$

Assume the following is in in $\mathbb{R}^n$ 1. If $d_i,d_j$ are orthogonal with $i \neq j$, it means $d_i^Td_j=0$. 2. If $d_i,d_j$ are $A$-orthogonal with $i \neq j$, it means $d_i^TAd_j=0$. In ...
0
votes
1answer
77 views

How to computer the proximal operator of a indicator function?

For $G_{1}(x) = I_{c}(x), c =\{x|Ax=b\}$, the Proximal operator is: $Prox_{\gamma G_{1}}(x) = Proj_{c}(x) = x + A^{T}(AA^{T})^{-1}(y-Ax)$ I hope to know, how to derivative this result. And, for ...
0
votes
1answer
115 views

Gradient of a Lagrange dual function

Consider: $$\min_{x \in \mathbb{R}^n} f(x)$$ $$\ \ \ \ \ \ \ \text{s.t. }\ h(x) \leq 0$$ Lagrangian:$\ \ \ L(x,\lambda) = f(x) + \lambda h(x)$ Suppose $x^* = \arg\min_{x} L(x,\lambda)$ ...
3
votes
1answer
40 views

$\nabla f$ Lipschitz & $f$ Lipschitz

My question is: Which of the following is more restrictive? $\nabla f$ Lipschitz & $f$ Lipschitz I think each one cannot imply the other. For example ($1$D): $$f(x) = \frac {x^2}{3}$$ ...
0
votes
0answers
34 views

Convergence analysis of gradient descent method

From the following: Convex Optimization (S. Boyd) p.467 Content: We will see that the gradient method does in fact require a large number of iterations when the Hessian of $f$, ...
1
vote
0answers
52 views

How to understand a proposition of subgradient

The question is from the following: Convex Optimization Algorithm (p.512)----- Prof. Bertsekas Let $f: R^n \rightarrow (-\infty, \infty]$ be a proper convex function. For every $x \in ...
0
votes
1answer
76 views

Gradient of the elastic net with extra terms

Can anyone tell me the gradient of the below function (w.r.to X) $$ argmin_{X} ~~\frac{\lambda}{2}\lVert X\lVert_2^2 + \lVert X\lVert_1 + tr\bigg(\Delta^T\Big(diag(X)-X\Big)\bigg) + ...
2
votes
1answer
60 views

Proof of relationship of subgradients of function to convexity of function

I am trying to follow the proof of the first claim of Proposition 7 on this page: https://blogs.princeton.edu/imabandit/2013/02/05/orf523-advanced-optimization-introduction/ Basically, we are given: ...
0
votes
2answers
40 views

Dual subgradient method - can we solve approximation of dual?

Consider the problem to minimize $f(x)$ under the constraints $x \leq b$ and $x \in X$. I Lagrange relax the constraint $x \leq b$ getting $L(x,u) = f(x) + u^t(x-b)$. When using the subgradient ...
0
votes
0answers
67 views

Getting explicit expression of function from the dual function

Considering the following problem : $$ minimize_{x_1,x_2} \ -2x_1+x_2 \\ subject \ to \ x_1+x_2=\frac52 \\ (x_1,x_2) \in X ,\\$$ where $X=\{(0,0),(0,2),(2,0),(2,2),(\frac54,\frac54)\}$ The dual ...
1
vote
1answer
331 views

Sub-gradient of the “$\ell_0$ norm”

I am trying to characterize the sub-gradient of l0-norm ($f(x) = ||x||_0=\sum_{i=1}^n 1\{{x_i \neq 0}\}$). At first, I thought l0-norm is a convex non-smooth function since it satisfies the triangle ...
1
vote
0answers
95 views

Subdifferential of a convex function

How would I find a convex function $f: \mathbb{R} \to \mathbb{R}$ such that $\partial f(0) = [0,1]$ A subdifferential is just the collection of vectors $w \in \mathbb{R}^n$ such that $f(y) \geq ...
0
votes
1answer
74 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
39 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
73 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
40 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
116 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
147 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
145 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
1answer
79 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
28 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
44 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 ...
1
vote
1answer
1k 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
2answers
90 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
1k 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
85 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
169 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
57 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
2answers
61 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
2answers
1k 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
87 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 ...