Three operator splitting with adaptative step size: prox on x inside loop ?

[tvayer]

Hello,

I am trying to apply the TOS algorithm from your paper https://arxiv.org/pdf/1804.02339.pdf by using the COPT implementation. There is one detail that I do not really catch here.

Based on your article, it seems to me that the steps (lines 2-7) in Algorithm 1 of https://arxiv.org/pdf/1804.02339.pdf do not match the implementation:

copt/copt/splitting.py

Lines 130 to 144 in 28903ab

	x = prox_1(z - step_size * (u + grad_fk), step_size, *args_prox)
	incr = x - z
	norm_incr = np.linalg.norm(incr)
	ls = norm_incr > 1e-7 and line_search
	if ls:
	for it_ls in range(max_iter_backtracking):
	rhs = fk + grad_fk.dot(incr) + (norm_incr ** 2) / (2 * step_size)
	ls_tol = f_grad(x, return_gradient=False) - rhs
	if ls_tol <= LS_EPS:
	# step size found
	# if ls_tol > 0:
	# ls_tol = 0.
	break
	else:
	step_size *= backtracking_factor

I might be wrong but shouldn't the line:

(

copt/copt/splitting.py

Line 130 in 28903ab

x = prox_1(z - step_size * (u + grad_fk), step_size, *args_prox)

)

come after the loop begins:

(

copt/copt/splitting.py

Line 135 in 28903ab

for it_ls in range(max_iter_backtracking):

)

so as to match the steps (lines 2-7) in Algorithm 1 of https://arxiv.org/pdf/1804.02339.pdf

As it is, it seems to me that the variable x is never updated during the backtracking. Am I missing something ?

Thank you for the fantastic work !

[fabianp]

yeah, I think you're right. At least the x = prox(...) like should be re-evaluated if the step-size has changed. Would you be willing to submit a pull request with this change? thanks!

…

On Tue, May 10, 2022 at 4:21 PM Titouan Vayer ***@***.***> wrote: Hello, I am trying to apply the TOS algorithm from your paper https://arxiv.org/pdf/1804.02339.pdf by using the COPT implementation. There is one detail that I do not really catch here. Based on your article, it seems to me that the steps (lines 2-7) in Algorithm 1 of https://arxiv.org/pdf/1804.02339.pdf do not match the implementation: https://github.com/openopt/copt/blob/28903ab7325a078f2056a3ff42ec8a0c992c6a1f/copt/splitting.py#L130-L144 I might be wrong but shouldn't the line: x = prox_1(z - step_size * (u + grad_fk), step_size, *args_prox) ( https://github.com/openopt/copt/blob/28903ab7325a078f2056a3ff42ec8a0c992c6a1f/copt/splitting.py#L130 ) come after the loop begins for it_ls in range(max_iter_backtracking): ( https://github.com/openopt/copt/blob/28903ab7325a078f2056a3ff42ec8a0c992c6a1f/copt/splitting.py#L135 ) so as to match the steps (lines 2-7) in Algorithm 1 of https://arxiv.org/pdf/1804.02339.pdf As it is, it seems to me that the variable x is never updated during the backtracking. Am I missing something ? Thank you for the fantastic work ! — Reply to this email directly, view it on GitHub <#97>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AACDZB5AUZN4LURMSBWWKLLVJLAMFANCNFSM5VSXN77Q> . You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>

[tvayer]

Hello Fabian, Thank you for your answer, yes will do that ! Titouan Le jeu. 12 mai 2022 à 21:40, Fabian Pedregosa ***@***.***> a écrit :

…

yeah, I think you're right. At least the x = prox(...) like should be re-evaluated if the step-size has changed. Would you be willing to submit a pull request with this change? thanks! On Tue, May 10, 2022 at 4:21 PM Titouan Vayer ***@***.***> wrote: > Hello, > > I am trying to apply the TOS algorithm from your paper > https://arxiv.org/pdf/1804.02339.pdf by using the COPT implementation. > There is one detail that I do not really catch here. > > Based on your article, it seems to me that the steps (lines 2-7) in > Algorithm 1 of https://arxiv.org/pdf/1804.02339.pdf do not match the > implementation: > > > https://github.com/openopt/copt/blob/28903ab7325a078f2056a3ff42ec8a0c992c6a1f/copt/splitting.py#L130-L144 > > I might be wrong but shouldn't the line: > > x = prox_1(z - step_size * (u + grad_fk), step_size, *args_prox) ( > https://github.com/openopt/copt/blob/28903ab7325a078f2056a3ff42ec8a0c992c6a1f/copt/splitting.py#L130 > ) > > come after the loop begins > > for it_ls in range(max_iter_backtracking): ( > https://github.com/openopt/copt/blob/28903ab7325a078f2056a3ff42ec8a0c992c6a1f/copt/splitting.py#L135 > ) > > so as to match the steps (lines 2-7) in Algorithm 1 of > https://arxiv.org/pdf/1804.02339.pdf > > As it is, it seems to me that the variable x is never updated during the > backtracking. Am I missing something ? > > Thank you for the fantastic work ! > > — > Reply to this email directly, view it on GitHub > <#97>, or unsubscribe > < https://github.com/notifications/unsubscribe-auth/AACDZB5AUZN4LURMSBWWKLLVJLAMFANCNFSM5VSXN77Q > > . > You are receiving this because you are subscribed to this thread.Message > ID: ***@***.***> > — Reply to this email directly, view it on GitHub <#97 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AEDBMDKMMHAEB26HKE43LZDVJVNBJANCNFSM5VSXN77Q> . You are receiving this because you authored the thread.Message ID: ***@***.***>