{"entities":{"Q1960191":{"pageid":1970933,"ns":120,"title":"Item:Q1960191","lastrevid":51102836,"modified":"2026-01-16T16:40:55Z","type":"item","id":"Q1960191","labels":{"en":{"language":"en","value":"The effect of deterministic noise in subgradient methods"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5799375"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1960191$6634B545-0B9A-4736-B3D2-070F91F32584","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e2a75158fc7995da3ecd0e444338d79c6846088f","datavalue":{"value":{"text":"The effect of deterministic noise in subgradient methods","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1960191$32C4568E-37BB-4269-A898-08735934070E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b43c7a63c19c77112ee964bd7980c59f3e23ce64","datavalue":{"value":"1205.90225","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1960191$3A1AB563-2C0F-4876-A7AD-9FED5C7D2BAD","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5f0fbf40b7982001332b202f83ec435af56cf0ea","datavalue":{"value":{"entity-type":"item","numeric-id":378730,"id":"Q378730"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1960191$43E732EB-5D9D-408B-8AA8-420AB3E6AD50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f3c01a52afec20dad1cdc36d7621a85e8894bddb","datavalue":{"value":{"entity-type":"item","numeric-id":445031,"id":"Q445031"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1960191$6A62439A-CB57-4433-ABD2-10BF0FAE51D1","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"99da72655942e9c2c9c01874c026b7cceeb02de6","datavalue":{"value":{"entity-type":"item","numeric-id":163006,"id":"Q163006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1960191$EB55FD51-385C-4191-86EA-C64CBFA03F39","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5bc825493bb220acb505797bc531e77eaaee5ef2","datavalue":{"value":{"time":"+2010-10-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1960191$1D723FF2-DA0D-4D03-97F4-EB478207A72C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"620d383f555687ba1a0e411d820162af83ff89de","datavalue":{"value":"In the paper the authors consider the problem  \\[ \\min_{x\\in X} \\; f(x)  \\]  where \\(f:\\mathbb R^n\\to \\mathbb R\\) is a convex function, and \\(X\\) is a nonempty, closed and convex set in \\(R^n,\\) in order to focus on the influence of noise on subgradient methods. In particular, they consider an approximate \\(\\epsilon\\)-subgradient method where the \\(\\epsilon\\)-subgradients are computed inexactly; this method is given by  \\[  x_{k+1}={\\mathcal P}_X[x_k-\\alpha_k\\tilde{g}_k],  \\]  where \\({\\mathcal P}_X\\) denotes the projection on the set \\(X.\\) The vector \\(x_0\\) is an initial iterate from the set \\(X\\) (i.e., \\(x_0\\in X\\)) and the scalar \\(\\alpha_k\\) is a positive stepsize. The vector \\(\\tilde{g}_k\\) is an approximate subgradient of the following form  \\[  \\tilde{g}_k=g_k+r_k,  \\]  where \\(r_k\\) is a noise vector and \\(g_k\\) is an \\(\\epsilon_k\\)-subgradient of \\(f\\) at \\(x_k\\) for some \\(\\epsilon_k\\geq 0.\\) Different stepsize rules are considered; in particular, the convergence properties of the method are studied using the following: constant stepsize rule, diminishing stepsize rule and dynamic stepsize rule.  The paper is organized as follows: In Section 2, the authors give the convergence properties of the method for a compact constraint set \\(X,\\) and, in Section 3, they discuss the convergence properties of the method for the case when the objective function \\(f\\) has a set of sharp minima. As a special case, their results show that, with \\(\\epsilon_k\\equiv 0\\) and the diminishing stepsize rule, the method converges to the optimal value even if the noise is nonvanishing but is instead small enough. In both cases, using different stepsize rules, they prove convergence to the optimal value whithin some tolerance that is given explicitly in terms of the errors. In the first case, the tolerance is nonzero, but in the second case, the optimal value can be obtained exactly, provided the size of the error in the subgradient computation is below the threshold. In Section 4, they consider an objective function \\(f\\) that is the sum of a large number of convex functions, in which case an incremental subgradient method can also be used. They give analogs of the results of Sections 2 and 3 for incremental subgradient methods.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1960191$C698D9B7-6ABE-4C8C-B720-2BC4A7AAA89C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"ccd1dd4cefa81e8158b9f080486a4eaed61a9ee8","datavalue":{"value":"90C25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1960191$27D9A9A4-F81B-490D-9C45-AE431940B8F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"82a006ec5bbbadf5f063bfdc770a07a4120063ab","datavalue":{"value":"90C31","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1960191$8B43FEF2-AD85-4721-8BB9-A239FCC9EB22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f06fd3dc85e32174f2979e45efb7334135f9e74e","datavalue":{"value":"90C56","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1960191$587C210D-A6B2-4331-9FFA-E3839986959D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"05fb18c561cbddf9a3c68356c5162fdbfa417282","datavalue":{"value":"5799375","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1960191$047EF297-CB4B-4B83-BD48-C1895ADD1E08","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"be5461d69452711d0fe58f5f76cdc03036299066","datavalue":{"value":"convex constrained optimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1960191$1D4ED908-7E25-4060-98C2-505499F76E05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"de23ad67b3f4fad4abfdf45b2ca801e408db9054","datavalue":{"value":"\\(\\epsilon\\)-subgradient methods","type":"string"},"datatype":"string"},"type":"statement","id":"Q1960191$69CAFEFA-6764-4766-93B6-400DD75B0B27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ac6824637d3ecc9f9cc89914d3b5930f02b066b2","datavalue":{"value":"noise","type":"string"},"datatype":"string"},"type":"statement","id":"Q1960191$7622BE85-FCF8-4F5B-BE1B-7FD1F6D81B9B","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"de3f3ef9349c49d788d3cdfae2b97a39b337988b","datavalue":{"value":{"entity-type":"item","numeric-id":216354,"id":"Q216354"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1960191$944DBF48-F895-442D-939B-A8170DD1B2AE","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1960191$15D85FB6-3161-4BF5-BF53-062816677899","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e78e536c7c7d1f041cddafa548b948ce431d606c","datavalue":{"value":"https://doi.org/10.1007/s10107-008-0262-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q1960191$C2351B7C-B320-422D-8311-EF84D541D56F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ba2be30537f0badfbd6d1c1f033c2aa371965402","datavalue":{"value":"W2172228337","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1960191$276ED7F6-69F2-400C-851C-7560C744BA24","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ddce2562405f9beb0c0e746517f6b0cadddc78ff","datavalue":{"value":{"entity-type":"item","numeric-id":2784404,"id":"Q2784404"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1960191$7E34241F-D376-4591-904F-E75A87FEA0D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"139332cdbf81cdea811deb62b49f6c8c5954e9e3","datavalue":{"value":{"entity-type":"item","numeric-id":3151174,"id":"Q3151174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1960191$51CE3AA0-CA9E-42CD-AC3B-9065B45B12FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c65e8a7ae140e650f6c4e158cda8f990fec2dcc7","datavalue":{"value":{"entity-type":"item","numeric-id":4830373,"id":"Q4830373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1960191$7C0F359C-0010-4EB1-ACDF-0EF827ADE0E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"973419d3c5c1cfe2cead3d8d864c4a8d14afa81b","datavalue":{"value":{"entity-type":"item","numeric-id":3141558,"id":"Q3141558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1960191$86E0BA6E-F08F-4B8C-98DA-C0021F017528","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"59b427775b682fb7e96625d96db3a4c373c9c9f2","datavalue":{"value":{"entity-type":"item","numeric-id":5611351,"id":"Q5611351"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1960191$E178047C-0ADA-43E1-A4DC-7525FD3932B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1aa0088ab95206758111f29c1b575b73edb6c4d4","datavalue":{"value":{"entity-type":"item","numeric-id":3657787,"id":"Q3657787"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1960191$4AEB0E24-2F72-4AA2-AFC5-53527C9818FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c93ba3c78d510ae402e361a2738e79e7da151c5b","datavalue":{"value":{"entity-type":"item","numeric-id":3818809,"id":"Q3818809"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1960191$B06C6A3C-8B4E-483C-BFB2-85C8EB5759F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"983b3c3b360932cbe62e89af553d874ae46531b0","datavalue":{"value":{"entity-type":"item","numeric-id":5387972,"id":"Q5387972"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1960191$D2E70D32-9779-4B94-9561-5582C922BA3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3dd086c2a9d485cc74ac66d4aa3db028d4775024","datavalue":{"value":{"entity-type":"item","numeric-id":1295965,"id":"Q1295965"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1960191$0259CC30-6649-4249-9ABF-2AD02C7F966D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"28ca25e2edf17dab8169a1567cc55cc71d2903bb","datavalue":{"value":{"entity-type":"item","numeric-id":2641788,"id":"Q2641788"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1960191$892935E8-DC02-4EBE-92A2-0BDAAD0CC6C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dadcece0c949b55736ebc615a0aa7a52fe6020fa","datavalue":{"value":{"entity-type":"item","numeric-id":1137249,"id":"Q1137249"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1960191$7EF3DC02-DDFB-4B22-9817-7BF0815A886A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"84cd5bf353dc9e28920a3733d6cb120e94584bdb","datavalue":{"value":{"entity-type":"item","numeric-id":4651971,"id":"Q4651971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1960191$3B4CB8B3-0353-445B-98D0-2D94646382D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7a99cbe88cede46682afbfa2ddf043ba64d9f0e4","datavalue":{"value":{"entity-type":"item","numeric-id":5470229,"id":"Q5470229"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1960191$252D59E8-6A99-41F0-9CEE-7395B681B843","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"06cb2bb53b4b34763df9ebd728cd281494b22f67","datavalue":{"value":{"entity-type":"item","numeric-id":2768028,"id":"Q2768028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1960191$CAE31F9C-926F-41EE-81C1-57579A6E58AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b2fa87b44d6ef2e75d0a0f7d869716c2dbbcfcc","datavalue":{"value":{"entity-type":"item","numeric-id":2784405,"id":"Q2784405"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1960191$AFDC330E-C1A1-4680-929A-220CE403D123","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"584cdb89faad9d4390d5833834ac370223b47f5b","datavalue":{"value":{"entity-type":"item","numeric-id":1365060,"id":"Q1365060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1960191$8F14AB90-1552-4B32-B7C2-20919EAD5B69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"abea1f95b1f17e3ed55d11e1d3a410a75f2e62d4","datavalue":{"value":{"entity-type":"item","numeric-id":4158820,"id":"Q4158820"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1960191$BB8F9C10-1D5A-4731-8B22-5770A023B907","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4e3f01f3bb4a767775c4474d89f1bcd7f12b8388","datavalue":{"value":{"entity-type":"item","numeric-id":3491338,"id":"Q3491338"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1960191$D4DBE3A4-1A17-4520-B5F6-B1ED3CCDDA80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c855972eef626d9d3e3134bc763853fac0456af0","datavalue":{"value":{"entity-type":"item","numeric-id":1273917,"id":"Q1273917"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1960191$CD36160C-4779-452B-B3B0-63D60976DEE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0b411900bb062b299e0c2651d276dc64a32c9805","datavalue":{"value":{"entity-type":"item","numeric-id":4569128,"id":"Q4569128"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1960191$88FA8B64-C38C-4823-9CE9-93F16E8E9316","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d685c733ccda80e0ab3544ca3f9f3bb92db62183","datavalue":{"value":"10.1007/S10107-008-0262-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1960191$8C4873C3-8434-4A73-89A7-13E71248860E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"01f66d6f1259deb380791d754664980a5f905907","datavalue":{"value":{"entity-type":"item","numeric-id":2784405,"id":"Q2784405"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fadf798bea728e99c82afc57972e315d43d7f11c","datavalue":{"value":{"amount":"+0.7977150082588196","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1960191$6EA4D50A-0FB6-4B04-9C6E-0C0956AA8AD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0392903db1e104acdf53c1640b747f24b9f4b838","datavalue":{"value":{"entity-type":"item","numeric-id":2629635,"id":"Q2629635"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fadf798bea728e99c82afc57972e315d43d7f11c","datavalue":{"value":{"amount":"+0.7977150082588196","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1960191$7A0E8997-58DC-49D8-8348-B9AF217D9AB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"47410af948a671f41c4cff0cab58118c89403af1","datavalue":{"value":{"entity-type":"item","numeric-id":2752037,"id":"Q2752037"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4ceb764beebbaa91f002fd113e5fb40c72831b02","datavalue":{"value":{"amount":"+0.7933264374732971","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1960191$1D85F481-3F7A-45A2-AE68-34726D6591E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"70360eb5699628dda0a9030e5f77c11a983aa198","datavalue":{"value":{"entity-type":"item","numeric-id":1083369,"id":"Q1083369"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"57260d76ce3ca84b006205bbaf95041cc5fb8ba5","datavalue":{"value":{"amount":"+0.7933260798454285","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1960191$1B5EC297-1127-4AE7-B5CD-BC0277802CB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dba191717f2036e52ffaca1997bae7cc6ed89d42","datavalue":{"value":{"entity-type":"item","numeric-id":3563901,"id":"Q3563901"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"beb29220a983c0238df7b8bda12e3be71f9ea9d4","datavalue":{"value":{"amount":"+0.7878603935241699","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1960191$2D9D5681-32C6-48F5-8746-817C9ADF6433","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1960191","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1960191"}}}}}