Questions tagged [subgradient]

This tag is for questions relating to subgradient, an iterative method for solving convex minimization problems, used predominantly in Nondifferentiable optimization for functions that are convex but nondifferentiable. The subgradient method is a very simple algorithm for minimizing convex nondifferentiable functions where newton's method and simple linear programming will not work.

Filter by
Sorted by
Tagged with
0 votes
0 answers
21 views

Subdifferentials of a strictly convex function are disjoint

I'm trying to prove below result which is mentioned in page 24 of Santambrogio's Optimal Transport for Applied Mathematicians: Calculus of Variations, PDEs, and Modeling. Could you have a check on my ...
user avatar
  • 1,991
0 votes
1 answer
40 views

Are subgradients bounded on compact subsets of an open set?

Context & Motivation: This is a preliminary question that I wanted to answer in order to generalize the nonconvex projected gradient descent method in Chapter 3 of the book Non-convex Optimization ...
user avatar
1 vote
0 answers
16 views

Convergence Rate of Stochastic Gradient Method analysis with more realistic stochastic graident bound

I am reading this Lectur Slides of SGD convergence analysis. In page 3, it says the realistic bound "Just get some extra terms in the result." I tried to use this bound and derive the result,...
user avatar
1 vote
0 answers
17 views

Analyzing the subgradient method with convex and Lipschitz condition

For a convex function $f: D \rightarrow \mathbb{R}$, where $D \subseteq \mathbb{R}^{n}$ is convex and open, define a subgradient of $f$ at $x_{0} \in D$ to be any vector $s \in \mathbb{R}^{n}$ such ...
user avatar
1 vote
0 answers
38 views

Defining the Subgradient with Polar of the Tagent Cone on the Epigraph, or the Convex Hull

To start, I would like to state both definitions for sub-gradient and where they came from. Definition 1 Let $f$ be $\mathbb E \mapsto \mathbb {\bar R}$ with $x\in \text{dom}(f)$ then $v\in \mathbb E$...
user avatar
1 vote
1 answer
25 views

Subgradient method for nonconvex nonsmooth function

Gradient descent or stochastic gradient descent are frequently used to find stationary points (and in some cases even to local minimum) of a nonconvex function. I was wondering if the same can be said ...
user avatar
0 votes
0 answers
32 views

subgradient - subdifferential of spectral norm for a complex matrix

I found the following definition in this answer $$ \partial f(x) := \{x^* \in X^* \mid f(x') \ge f(x) + \langle x^*, x'-x\rangle\;\forall x' \in X\} $$ Can I define this $$ \langle A, B\rangle\ = Re(...
user avatar
  • 1
0 votes
0 answers
22 views

Boundedness of the gradient of Cross Entropy Loss

When analyzing the convergence of algorithms, the assumption of the bounded gradient is often used. I wondered if this holds in the case of cross-entropy loss; otherwise, is there a way to ensure that ...
user avatar
  • 99
0 votes
0 answers
19 views

Strong convexity definition based on subgradient

Suppose that we have $f: \mathbb R^d \to \mathbb R$ is convex and satisfies $$f(\textbf y) \geq f(\textbf x) + \nabla f(\textbf x)^\top(\textbf y - \textbf x) + \frac{\mu}{2} \| \textbf x - \textbf y \...
user avatar
0 votes
1 answer
31 views

Existence of accelerated subgradient methods

Heavy Ball method and Nesterov's gradient method are two kinds of accelerated versions of gradient methods that achieve optimal convergence for smooth optimization. I wonder whether there is an ...
user avatar
  • 1
0 votes
1 answer
79 views

If a function is convex, then its subgradient set is non-empty

Theorem: A function $f: \textbf{dom}(f) \to \mathbb R$ is convex if and only if $\textbf{dom}(f)$ is convex and $\partial f(\textbf x)$ is not empty for all $\textbf x \in \textbf{dom}(f)$ I know the ...
user avatar
1 vote
1 answer
57 views

Convex and Lipschitz implies "bounded" subgradient in Banach spaces

In this question: Lipschitz implies bounded gradient it is shown that if $f: \mathbb{R}^n \to \mathbb{R}^n$ is convex and L-Lipschitz the gradient is bounded by L. I wonder if this holds in Banach ...
user avatar
0 votes
0 answers
39 views

Large number of absolute value expressions in constrained, non-convex optimization problem

Say I have a problem given by \begin{align} \min_{x\in\mathbb{R}^n} & \ ||g(x)||_1, \\ \text{s.t. } &z_i(x)+||c^{(i)}(x)||_1 \leq d_i, \ i\in\{1,...,N\}, \end{align} where $g:\mathbb{R}...
user avatar
  • 272
0 votes
0 answers
62 views

Subgradient with the Frobenius norm

I'm working in the space of symmetric positive semi-definite matrices $S_n^+$ considered as a Hilbert space with respect to the inner product $\langle A,B \rangle = Tr(A^t B)$. I'm computing a ...
user avatar
  • 5,403
1 vote
0 answers
30 views

Constant step lengths in subgradient method

I was reading these notes (if the previous link doesn't work, use this) on the subgradient method, it says that the choice for step sizes (or step lengths) are determined before the algorithm is run, ...
user avatar
0 votes
1 answer
42 views

"Adding" to an inner product

I wanted to get some clarification on a linear algebra operation I've not seen before. In demonstrating how subgradients are found, a lecuturer did the following: $$\begin{align} 0 &\geq \langle g,...
user avatar
0 votes
0 answers
43 views

Motivate the Definition of Upper Gradient in a Metric Space.

The following (from the book of Santambrogio) is a given as a definition of modulus of a gradient in a metric space I can motivate this definition myself. Why should this be a good definition of ...
user avatar
  • 41
0 votes
0 answers
38 views

subdifferential of a convex multivariate function

I want to calculate the subgradient of the following function: $$f(w, b) = \max \{0, v(w^T u + b)\}+ \rho\|w\|_{l^1}$$ where $u\in \mathbb{R^n}$ and $v\in \mathbb{R}$ are given, $w \in \mathbb{R^n}$ ...
user avatar
  • 1,311
0 votes
0 answers
33 views

compute the subgradient set of $\max(x,0)$ using Danskin

I'd like to compute the subgradient set of $f(x):=\max(x,0)$ using Danskin's theorem, similar to what is done here. We have \begin{align} f(x) = \max(x,0) = \max\{\phi(x,z): z\in Z\} \end{align} where ...
user avatar
  • 2,400
1 vote
0 answers
27 views

subdifferential set of nested nonsmooth function

I am trying to compute the subdifferential set of the convex function \begin{align} f_n(x_1,x_2,\ldots, x_n) := \max(x_1+\max(x_2 + \cdots + \max(x_n,0),0),\cdots0). \end{align} I'm considering for ...
user avatar
  • 2,400
0 votes
1 answer
41 views

least squares with L1 regularization in selected entries

Say for $x \in \mathbb{R}^n$, I'm minimizing $\|Ax - b \|_2^2$ with L1 regularization on selected entries of $x$. i.e. instead of directly add a $\|x\|_1$ regularization term, it would be on $|x_i| + |...
user avatar
  • 155
0 votes
2 answers
145 views

Gradient Descent on Function that is non-differentiable at finitely many points

Suppose that I have a (possibly non-convex) function that maps $R^N$ to $R$, and is differentiable at all points except finitely many points. I want to use gradient descent algorithm to show ...
user avatar
0 votes
1 answer
47 views

Find Fenchel conjugate for a function

During my self learning I come across the function for which I want to find (Fenchel) conjugate and the subdifferential $\partial \psi$ function, could you please help! I have no clue about this topic....
user avatar
  • 1,265
1 vote
0 answers
59 views

Chain rule for composite function with inner function non-smooth

Let $f:\mathbb{R}^2\mapsto\mathbb{R}$ be given by $f(w_1,w_2)=\frac{1}{2}(1-w_2\sigma(w_1))^2$, where $\sigma(x)=\max\{x,0\}$ is the ReLU function. I want to compute the Clarke subdifferential of $f$ ...
user avatar
  • 692
1 vote
0 answers
56 views

When solving this differential equation why should we look for absolutely continuous solutions?

Why does the author here suggest that we look for absolutely continuous curves as solutions to the following differential inclusion (or LESS generally a differential equation)? Here the $\partial F$ ...
user avatar
0 votes
1 answer
16 views

If $0\notin\partial f(x_k)$ then any $-\xi\in-\partial f(x_k)$ is a descent direction.

Let $f:R^n\to R$ a convex function, let's supposse $0\notin\partial f(x_k)$. I think any $-\xi\in -\partial f(x_k)$ is a descent direction, i.e., exists $T>0$ such that for all $t\in(0,T]$ $$f(x_k-...
user avatar
  • 145
0 votes
0 answers
56 views

Subgradient of the objective

I want to apply Danskin's Theorem to find the subgradient of the following function $g(x)$ $$ g(x) = \begin{aligned} \max_{z \in Z{\color{red}{(x)}}} &\; \phi(x, z) \end{aligned} = \begin{...
user avatar
  • 282
1 vote
0 answers
42 views

Characterisation of the subdifferential of a $\lambda$-convex function.

If $F$ is convex, then the inequality that characterizes the subgradient is $$F(y)\ge F(x)+\langle p,y-x\rangle$$ and if F is $\lambda$-convex (i.e. $F(x)-\frac{\lambda}{2}\|x\|^2$ is convex), the ...
user avatar
  • 1,026
1 vote
0 answers
60 views

Existence of subgradient for strictly convex function on the domain

Let $f:\mathbb{R}^n\to \mathbb{R}\cup\{\infty\}$ be proper, lower semicontinuous and convex, and $\operatorname{dom}f=\{x\in \mathbb{R}^n\mid f(x)<\infty\}$ be the domain of $f$. Assume further ...
user avatar
  • 12.4k
0 votes
1 answer
44 views

Subgradient everywhere terminology

Suppose I have a function $h$ and a function $f$. The function $f$ is non-differentiable and thus, does not have a gradient. However, the function $h$ belongs to the subgradient of $f$ at every $x$, i....
user avatar
0 votes
0 answers
21 views

Identity for $|u-t| - |u|$ using fundamental theorem of calculus for subgradients

I am trying to show that for all $u,t \in \mathbb R$: $$|u-t| - |u| = -t\left (\mathbb 1( u>0) - \mathbb 1( u\leq0)\right) + 2 \int_0^t \left (\mathbb 1( u\leq s) - \mathbb 1( u \leq 0)\right) ds$$ ...
user avatar
  • 1,624
1 vote
1 answer
57 views

About the subdifferential of a convex function

Suppose $f$ is a convex function over $\mathbb R$, and there exists two points $b_1 < b_2$, $a_1 \leq 0\leq a_2$ such that $$a_1 \in \partial f(b_1), $$ $$ a_2 \in \partial f(b_2).$$ Then $\arg\min ...
user avatar
0 votes
0 answers
22 views

Subdifferential, two different definitions.

The subdifferential of the function $W$ at $x$ was defined as $$\partial W(x):=\{\kappa\in\mathbb{R}^d:W(y)−W(x)≥\kappa\cdot(y − x),\text{ for all }y ∈ \mathbb{R}^d\}.$$ I understand what this means ...
user avatar
  • 3,858
1 vote
3 answers
119 views

Subgradient along one direction of a convex function and its directional derivative

I am considering the following two things and trying to prove that they equals to each other: $$ u = \inf_{\lambda>0}\left\{\frac{f(\boldsymbol{x} + \lambda\boldsymbol{p}) - f(\boldsymbol{x})}{\...
user avatar
  • 371
0 votes
0 answers
20 views

Continuity property of sub-differentials

Assume that $g\colon\mathbb{R}^n\to\left(-\infty,\infty\right]$ is continuous over its domain, convex, closed and proper. For some $x,y\in\mathbb{R}^n$, assume that $x\in\partial g\left(y\right)$. ...
user avatar
  • 996
0 votes
0 answers
18 views

Subgradient empty for composed nonspooth function?

Let $f(t) = |t|$, and let $g(\boldsymbol{w}) = \langle \boldsymbol{a}, \boldsymbol{w} \rangle^2 - y$, with $y \geq 0$. I have to compute the subdifferential of $h(\boldsymbol{w}) = f(g(\boldsymbol{w}))...
user avatar
1 vote
0 answers
315 views

Subdifferential of infinity norm

I'm trying to calculate the subdifferential of the infinity norm, but I'm a bit stuck. The definition of the subdifferential $\partial f(x)$ of a function $f(x)$ that I am working with is $$\partial f(...
user avatar
0 votes
1 answer
64 views

How can I understand the "scaled subdifferential"?

The definitions of subdifferential and scaled subdifferential are (screenshot) Subdifferential: The subdifferential of $f$ at $x$ is the set of vectors $\partial f(\boldsymbol{x})=\left\{\boldsymbol{...
user avatar
  • 103
1 vote
1 answer
501 views

Find the subdifferential for $\max\left(x^2,|x|\right)$

We define the function $f:\mathbb R \rightarrow \mathbb R$ as the following: $$f\left(x\right)=\max\left(x^2,|x|\right)$$ Find the subdifferential $\partial f\left(x\right)$ for all $x\in \mathbb R$. ...
user avatar
1 vote
0 answers
167 views

Calculate subdifferential of a function

Calculate the subdifferential of a function $f: \mathbb{R}^3 \to \mathbb{R}$ defined by $$f(x) = \vert x_1 - x_2\vert + \vert x_2 - x_3\vert$$ My attempt Applying the sum rule we have $$\partial f(x) ...
user avatar
0 votes
1 answer
78 views

Is the norm square of a ReLU function differentiable?

Suppose $f(X)$ is a function from $\mathbb{R}^{m\times n}\mapsto \mathbb{R}$ defined by $f(X)=\lVert\sigma(X)\rVert_F^2$, where $\sigma(X)=\max\{X,0\}$ is an entry-wise ReLU function, i.e., mapping ...
user avatar
  • 692
1 vote
0 answers
37 views

How to find a subdifferential of $(x_1, x_2) \mapsto |x_1 + x_2| + |x_1 - x_2|$?

I know that function $x \mapsto |x|$ has the following subdifferential $$\partial f(x) = \begin{cases} 1 &, x>0 \\ [-1,1] &, x=0 \\ -1 &, x<0. \end{cases}$$ for $x \...
user avatar
0 votes
1 answer
30 views

Gradient wrt a parameter of a parametrized integral

I am unable to understand how the operator is taken out of the integral. Is this some standard practice? $$ \begin{aligned} &=\int_{-\infty}^{\infty} \nabla_{\theta} p(y ; \theta) d y \\ &=\...
user avatar
0 votes
0 answers
24 views

What happens when numerically approximating the gradient of a function at a nondifferentiable point?

I am asking myself this question: Can anything be said of the resulting gradient, when the gradient of a function is approximated numerically (for example using the finite differences method) at a ...
user avatar
  • 115
0 votes
2 answers
100 views

Calculate the subgradient at $\pm \sqrt{2}$ for $1/2 x^2$

Let $f(x) = (1/2) x^2, x \in [-\sqrt{2}, \sqrt{2}]$ and $f(x) = +\infty$ elsewhere I would like to compute the subgradient of this function at the boundary $\pm\sqrt2$. However, I am not sure how to ...
user avatar
0 votes
1 answer
51 views

Find a subgradient of a real function

Let $f(x)=\chi_{\{-1\}}(x)+I_{[-1,1]}(x)$, where $\chi_{A}(x)=1$ when $x\in A$ and $\chi_{A}(x)=0$ when $x\notin A$, and $I$ is the indicator funcion (which is zero in its domain and infinity ...
user avatar
0 votes
0 answers
130 views

Property of epsilon-subdifferential

For convex function $f$, its subdifferential at $x \in R^n$ is defined as \begin{equation} \partial f(x) = \{m \mid f(y) \geq f(x) + \langle m,y-x\rangle, \forall y \in R^n\}. \end{equation} Then if $...
user avatar
  • 151
0 votes
1 answer
40 views

Subdifferential of $f(x) = |c^{T} x|$

I want to find a subdifferential of function $f(x) = |c^Tx|$, where $x \in \mathbb{R}^n$. I know that if $h(x) = f(Ax + b)$ then $\partial{h(x)} = A^T\partial{f(Ax+b)}$, which is exactly my case. ...
user avatar
0 votes
1 answer
317 views

L1 Norm Optimization Solution

I am trying to find the solution for the following optimization problem: $\max_{w} {z^Tw - \lambda ||w - w_0||_1}$ where $z, w, w_0 \in R^{Nx1}$ and $z, w_0$ are known. We let $s$ be the subgradient ...
user avatar
  • 155
1 vote
1 answer
62 views

How to find the subgradient of $x \mapsto \max \left( (x+1)^2, (x-3)^2 \right) $ at $x=1$?

I need help finding the subgradient of the following function at the point $x = 1$. $$ \max \left( (x+1)^2, (x-3)^2 \right) $$ I think it's $$ [-4,4] $$ since that is the range between the left-hand ...
user avatar

1
2 3 4 5