Random directions stochastic approximation with deterministic\n perturbations Article Swipe
L A Prashanth
,
Shalabh Bhatnagar
,
Nirav Bhavsar
,
Michael C. Fu
,
Steven I. Marcus
·
YOU?
·
· 2018
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.1808.02871
YOU?
·
· 2018
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.1808.02871
We introduce deterministic perturbation schemes for the recently proposed\nrandom directions stochastic approximation (RDSA) [17], and propose new\nfirst-order and second-order algorithms. In the latter case, these are the\nfirst second-order algorithms to incorporate deterministic perturbations. We\nshow that the gradient and/or Hessian estimates in the resulting algorithms\nwith deterministic perturbations are asymptotically unbiased, so that the\nalgorithms are provably convergent. Furthermore, we derive convergence rates to\nestablish the superiority of the first-order and second-order algorithms, for\nthe special case of a convex and quadratic optimization problem, respectively.\nNumerical experiments are used to validate the theoretical results.\n
Related Topics
Concepts
Hessian matrix
Convergence (economics)
Mathematical optimization
Quadratic equation
Stochastic optimization
Mathematics
Perturbation (astronomy)
Applied mathematics
Simultaneous perturbation stochastic approximation
Stochastic approximation
Regular polygon
Order (exchange)
Computer science
Stochastic process
Key (lock)
Statistics
Quantum mechanics
Economics
Computer security
Economic growth
Physics
Geometry
Finance
Metadata
- Type
- preprint
- Landing Page
- http://arxiv.org/abs/1808.02871
- https://arxiv.org/pdf/1808.02871
- OA Status
- green
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4289703818
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4289703818Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.48550/arxiv.1808.02871Digital Object Identifier
- Title
-
Random directions stochastic approximation with deterministic\n perturbationsWork title
- Type
-
preprintOpenAlex work type
- Publication year
-
2018Year of publication
- Publication date
-
2018-08-08Full publication date if available
- Authors
-
L A Prashanth, Shalabh Bhatnagar, Nirav Bhavsar, Michael C. Fu, Steven I. MarcusList of authors in order
- Landing page
-
https://arxiv.org/abs/1808.02871Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/1808.02871Direct link to full text PDF
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://arxiv.org/pdf/1808.02871Direct OA link when available
- Concepts
-
Hessian matrix, Convergence (economics), Mathematical optimization, Quadratic equation, Stochastic optimization, Mathematics, Perturbation (astronomy), Applied mathematics, Simultaneous perturbation stochastic approximation, Stochastic approximation, Regular polygon, Order (exchange), Computer science, Stochastic process, Key (lock), Statistics, Quantum mechanics, Economics, Computer security, Economic growth, Physics, Geometry, FinanceTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
0Total citation count in OpenAlex
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W4289703818 |
|---|---|
| doi | https://doi.org/10.48550/arxiv.1808.02871 |
| ids.openalex | https://openalex.org/W4289703818 |
| fwci | 0.0 |
| type | preprint |
| title | Random directions stochastic approximation with deterministic\n perturbations |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T13187 |
| topics[0].field.id | https://openalex.org/fields/13 |
| topics[0].field.display_name | Biochemistry, Genetics and Molecular Biology |
| topics[0].score | 0.9811999797821045 |
| topics[0].domain.id | https://openalex.org/domains/1 |
| topics[0].domain.display_name | Life Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/1312 |
| topics[0].subfield.display_name | Molecular Biology |
| topics[0].display_name | Diffusion and Search Dynamics |
| topics[1].id | https://openalex.org/T10500 |
| topics[1].field.id | https://openalex.org/fields/22 |
| topics[1].field.display_name | Engineering |
| topics[1].score | 0.9724000096321106 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/2206 |
| topics[1].subfield.display_name | Computational Mechanics |
| topics[1].display_name | Sparse and Compressive Sensing Techniques |
| topics[2].id | https://openalex.org/T11830 |
| topics[2].field.id | https://openalex.org/fields/26 |
| topics[2].field.display_name | Mathematics |
| topics[2].score | 0.9718999862670898 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/2604 |
| topics[2].subfield.display_name | Applied Mathematics |
| topics[2].display_name | Point processes and geometric inequalities |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C203616005 |
| concepts[0].level | 2 |
| concepts[0].score | 0.8321958780288696 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q620495 |
| concepts[0].display_name | Hessian matrix |
| concepts[1].id | https://openalex.org/C2777303404 |
| concepts[1].level | 2 |
| concepts[1].score | 0.5743565559387207 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q759757 |
| concepts[1].display_name | Convergence (economics) |
| concepts[2].id | https://openalex.org/C126255220 |
| concepts[2].level | 1 |
| concepts[2].score | 0.5260193943977356 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q141495 |
| concepts[2].display_name | Mathematical optimization |
| concepts[3].id | https://openalex.org/C129844170 |
| concepts[3].level | 2 |
| concepts[3].score | 0.5214561820030212 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q41299 |
| concepts[3].display_name | Quadratic equation |
| concepts[4].id | https://openalex.org/C194387892 |
| concepts[4].level | 2 |
| concepts[4].score | 0.5185071229934692 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q1747770 |
| concepts[4].display_name | Stochastic optimization |
| concepts[5].id | https://openalex.org/C33923547 |
| concepts[5].level | 0 |
| concepts[5].score | 0.514947235584259 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[5].display_name | Mathematics |
| concepts[6].id | https://openalex.org/C177918212 |
| concepts[6].level | 2 |
| concepts[6].score | 0.5057692527770996 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q803623 |
| concepts[6].display_name | Perturbation (astronomy) |
| concepts[7].id | https://openalex.org/C28826006 |
| concepts[7].level | 1 |
| concepts[7].score | 0.4980790615081787 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q33521 |
| concepts[7].display_name | Applied mathematics |
| concepts[8].id | https://openalex.org/C2779880469 |
| concepts[8].level | 3 |
| concepts[8].score | 0.485664963722229 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q17084424 |
| concepts[8].display_name | Simultaneous perturbation stochastic approximation |
| concepts[9].id | https://openalex.org/C55479107 |
| concepts[9].level | 3 |
| concepts[9].score | 0.47646021842956543 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q97663916 |
| concepts[9].display_name | Stochastic approximation |
| concepts[10].id | https://openalex.org/C112680207 |
| concepts[10].level | 2 |
| concepts[10].score | 0.4764443039894104 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q714886 |
| concepts[10].display_name | Regular polygon |
| concepts[11].id | https://openalex.org/C182306322 |
| concepts[11].level | 2 |
| concepts[11].score | 0.458968847990036 |
| concepts[11].wikidata | https://www.wikidata.org/wiki/Q1779371 |
| concepts[11].display_name | Order (exchange) |
| concepts[12].id | https://openalex.org/C41008148 |
| concepts[12].level | 0 |
| concepts[12].score | 0.3652269244194031 |
| concepts[12].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[12].display_name | Computer science |
| concepts[13].id | https://openalex.org/C8272713 |
| concepts[13].level | 2 |
| concepts[13].score | 0.30861377716064453 |
| concepts[13].wikidata | https://www.wikidata.org/wiki/Q176737 |
| concepts[13].display_name | Stochastic process |
| concepts[14].id | https://openalex.org/C26517878 |
| concepts[14].level | 2 |
| concepts[14].score | 0.06184002757072449 |
| concepts[14].wikidata | https://www.wikidata.org/wiki/Q228039 |
| concepts[14].display_name | Key (lock) |
| concepts[15].id | https://openalex.org/C105795698 |
| concepts[15].level | 1 |
| concepts[15].score | 0.0 |
| concepts[15].wikidata | https://www.wikidata.org/wiki/Q12483 |
| concepts[15].display_name | Statistics |
| concepts[16].id | https://openalex.org/C62520636 |
| concepts[16].level | 1 |
| concepts[16].score | 0.0 |
| concepts[16].wikidata | https://www.wikidata.org/wiki/Q944 |
| concepts[16].display_name | Quantum mechanics |
| concepts[17].id | https://openalex.org/C162324750 |
| concepts[17].level | 0 |
| concepts[17].score | 0.0 |
| concepts[17].wikidata | https://www.wikidata.org/wiki/Q8134 |
| concepts[17].display_name | Economics |
| concepts[18].id | https://openalex.org/C38652104 |
| concepts[18].level | 1 |
| concepts[18].score | 0.0 |
| concepts[18].wikidata | https://www.wikidata.org/wiki/Q3510521 |
| concepts[18].display_name | Computer security |
| concepts[19].id | https://openalex.org/C50522688 |
| concepts[19].level | 1 |
| concepts[19].score | 0.0 |
| concepts[19].wikidata | https://www.wikidata.org/wiki/Q189833 |
| concepts[19].display_name | Economic growth |
| concepts[20].id | https://openalex.org/C121332964 |
| concepts[20].level | 0 |
| concepts[20].score | 0.0 |
| concepts[20].wikidata | https://www.wikidata.org/wiki/Q413 |
| concepts[20].display_name | Physics |
| concepts[21].id | https://openalex.org/C2524010 |
| concepts[21].level | 1 |
| concepts[21].score | 0.0 |
| concepts[21].wikidata | https://www.wikidata.org/wiki/Q8087 |
| concepts[21].display_name | Geometry |
| concepts[22].id | https://openalex.org/C10138342 |
| concepts[22].level | 1 |
| concepts[22].score | 0.0 |
| concepts[22].wikidata | https://www.wikidata.org/wiki/Q43015 |
| concepts[22].display_name | Finance |
| keywords[0].id | https://openalex.org/keywords/hessian-matrix |
| keywords[0].score | 0.8321958780288696 |
| keywords[0].display_name | Hessian matrix |
| keywords[1].id | https://openalex.org/keywords/convergence |
| keywords[1].score | 0.5743565559387207 |
| keywords[1].display_name | Convergence (economics) |
| keywords[2].id | https://openalex.org/keywords/mathematical-optimization |
| keywords[2].score | 0.5260193943977356 |
| keywords[2].display_name | Mathematical optimization |
| keywords[3].id | https://openalex.org/keywords/quadratic-equation |
| keywords[3].score | 0.5214561820030212 |
| keywords[3].display_name | Quadratic equation |
| keywords[4].id | https://openalex.org/keywords/stochastic-optimization |
| keywords[4].score | 0.5185071229934692 |
| keywords[4].display_name | Stochastic optimization |
| keywords[5].id | https://openalex.org/keywords/mathematics |
| keywords[5].score | 0.514947235584259 |
| keywords[5].display_name | Mathematics |
| keywords[6].id | https://openalex.org/keywords/perturbation |
| keywords[6].score | 0.5057692527770996 |
| keywords[6].display_name | Perturbation (astronomy) |
| keywords[7].id | https://openalex.org/keywords/applied-mathematics |
| keywords[7].score | 0.4980790615081787 |
| keywords[7].display_name | Applied mathematics |
| keywords[8].id | https://openalex.org/keywords/simultaneous-perturbation-stochastic-approximation |
| keywords[8].score | 0.485664963722229 |
| keywords[8].display_name | Simultaneous perturbation stochastic approximation |
| keywords[9].id | https://openalex.org/keywords/stochastic-approximation |
| keywords[9].score | 0.47646021842956543 |
| keywords[9].display_name | Stochastic approximation |
| keywords[10].id | https://openalex.org/keywords/regular-polygon |
| keywords[10].score | 0.4764443039894104 |
| keywords[10].display_name | Regular polygon |
| keywords[11].id | https://openalex.org/keywords/order |
| keywords[11].score | 0.458968847990036 |
| keywords[11].display_name | Order (exchange) |
| keywords[12].id | https://openalex.org/keywords/computer-science |
| keywords[12].score | 0.3652269244194031 |
| keywords[12].display_name | Computer science |
| keywords[13].id | https://openalex.org/keywords/stochastic-process |
| keywords[13].score | 0.30861377716064453 |
| keywords[13].display_name | Stochastic process |
| keywords[14].id | https://openalex.org/keywords/key |
| keywords[14].score | 0.06184002757072449 |
| keywords[14].display_name | Key (lock) |
| language | |
| locations[0].id | pmh:oai:arXiv.org:1808.02871 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4306400194 |
| locations[0].source.issn | |
| locations[0].source.type | repository |
| locations[0].source.is_oa | True |
| locations[0].source.issn_l | |
| locations[0].source.is_core | False |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | arXiv (Cornell University) |
| locations[0].source.host_organization | https://openalex.org/I205783295 |
| locations[0].source.host_organization_name | Cornell University |
| locations[0].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[0].license | |
| locations[0].pdf_url | https://arxiv.org/pdf/1808.02871 |
| locations[0].version | submittedVersion |
| locations[0].raw_type | text |
| locations[0].license_id | |
| locations[0].is_accepted | False |
| locations[0].is_published | False |
| locations[0].raw_source_name | |
| locations[0].landing_page_url | http://arxiv.org/abs/1808.02871 |
| indexed_in | arxiv |
| authorships[0].author.id | https://openalex.org/A5025716080 |
| authorships[0].author.orcid | |
| authorships[0].author.display_name | L A Prashanth |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | A, Prashanth L |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5038163398 |
| authorships[1].author.orcid | https://orcid.org/0000-0001-7644-3914 |
| authorships[1].author.display_name | Shalabh Bhatnagar |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Bhatnagar, Shalabh |
| authorships[1].is_corresponding | False |
| authorships[2].author.id | https://openalex.org/A5023522093 |
| authorships[2].author.orcid | https://orcid.org/0000-0002-9588-4771 |
| authorships[2].author.display_name | Nirav Bhavsar |
| authorships[2].author_position | middle |
| authorships[2].raw_author_name | Bhavsar, Nirav |
| authorships[2].is_corresponding | False |
| authorships[3].author.id | https://openalex.org/A5000889975 |
| authorships[3].author.orcid | https://orcid.org/0000-0003-2105-4932 |
| authorships[3].author.display_name | Michael C. Fu |
| authorships[3].author_position | middle |
| authorships[3].raw_author_name | Fu, Michael |
| authorships[3].is_corresponding | False |
| authorships[4].author.id | https://openalex.org/A5013807415 |
| authorships[4].author.orcid | https://orcid.org/0000-0002-4926-9567 |
| authorships[4].author.display_name | Steven I. Marcus |
| authorships[4].author_position | last |
| authorships[4].raw_author_name | Marcus, Steven I. |
| authorships[4].is_corresponding | False |
| has_content.pdf | False |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://arxiv.org/pdf/1808.02871 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2022-08-04T00:00:00 |
| display_name | Random directions stochastic approximation with deterministic\n perturbations |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T03:46:38.306776 |
| primary_topic.id | https://openalex.org/T13187 |
| primary_topic.field.id | https://openalex.org/fields/13 |
| primary_topic.field.display_name | Biochemistry, Genetics and Molecular Biology |
| primary_topic.score | 0.9811999797821045 |
| primary_topic.domain.id | https://openalex.org/domains/1 |
| primary_topic.domain.display_name | Life Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/1312 |
| primary_topic.subfield.display_name | Molecular Biology |
| primary_topic.display_name | Diffusion and Search Dynamics |
| related_works | https://openalex.org/W3011817532, https://openalex.org/W2038213655, https://openalex.org/W2079907724, https://openalex.org/W2546134129, https://openalex.org/W359561291, https://openalex.org/W1994333428, https://openalex.org/W2118205332, https://openalex.org/W2157017986, https://openalex.org/W4390895039, https://openalex.org/W2069500793 |
| cited_by_count | 0 |
| locations_count | 1 |
| best_oa_location.id | pmh:oai:arXiv.org:1808.02871 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4306400194 |
| best_oa_location.source.issn | |
| best_oa_location.source.type | repository |
| best_oa_location.source.is_oa | True |
| best_oa_location.source.issn_l | |
| best_oa_location.source.is_core | False |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | arXiv (Cornell University) |
| best_oa_location.source.host_organization | https://openalex.org/I205783295 |
| best_oa_location.source.host_organization_name | Cornell University |
| best_oa_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| best_oa_location.license | |
| best_oa_location.pdf_url | https://arxiv.org/pdf/1808.02871 |
| best_oa_location.version | submittedVersion |
| best_oa_location.raw_type | text |
| best_oa_location.license_id | |
| best_oa_location.is_accepted | False |
| best_oa_location.is_published | False |
| best_oa_location.raw_source_name | |
| best_oa_location.landing_page_url | http://arxiv.org/abs/1808.02871 |
| primary_location.id | pmh:oai:arXiv.org:1808.02871 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4306400194 |
| primary_location.source.issn | |
| primary_location.source.type | repository |
| primary_location.source.is_oa | True |
| primary_location.source.issn_l | |
| primary_location.source.is_core | False |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | arXiv (Cornell University) |
| primary_location.source.host_organization | https://openalex.org/I205783295 |
| primary_location.source.host_organization_name | Cornell University |
| primary_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| primary_location.license | |
| primary_location.pdf_url | https://arxiv.org/pdf/1808.02871 |
| primary_location.version | submittedVersion |
| primary_location.raw_type | text |
| primary_location.license_id | |
| primary_location.is_accepted | False |
| primary_location.is_published | False |
| primary_location.raw_source_name | |
| primary_location.landing_page_url | http://arxiv.org/abs/1808.02871 |
| publication_date | 2018-08-08 |
| publication_year | 2018 |
| referenced_works_count | 0 |
| abstract_inverted_index.a | 73 |
| abstract_inverted_index.In | 20 |
| abstract_inverted_index.We | 0 |
| abstract_inverted_index.in | 40 |
| abstract_inverted_index.of | 63, 72 |
| abstract_inverted_index.so | 49 |
| abstract_inverted_index.to | 29, 83 |
| abstract_inverted_index.we | 56 |
| abstract_inverted_index.and | 14, 17, 66, 75 |
| abstract_inverted_index.are | 25, 46, 52, 81 |
| abstract_inverted_index.for | 5 |
| abstract_inverted_index.the | 6, 21, 35, 41, 61, 64, 85 |
| abstract_inverted_index.case | 71 |
| abstract_inverted_index.that | 34, 50 |
| abstract_inverted_index.used | 82 |
| abstract_inverted_index.[17], | 13 |
| abstract_inverted_index.case, | 23 |
| abstract_inverted_index.rates | 59 |
| abstract_inverted_index.these | 24 |
| abstract_inverted_index.(RDSA) | 12 |
| abstract_inverted_index.and/or | 37 |
| abstract_inverted_index.convex | 74 |
| abstract_inverted_index.derive | 57 |
| abstract_inverted_index.latter | 22 |
| abstract_inverted_index.Hessian | 38 |
| abstract_inverted_index.propose | 15 |
| abstract_inverted_index.schemes | 4 |
| abstract_inverted_index.special | 70 |
| abstract_inverted_index.We\nshow | 33 |
| abstract_inverted_index.for\nthe | 69 |
| abstract_inverted_index.gradient | 36 |
| abstract_inverted_index.problem, | 78 |
| abstract_inverted_index.provably | 53 |
| abstract_inverted_index.recently | 7 |
| abstract_inverted_index.validate | 84 |
| abstract_inverted_index.estimates | 39 |
| abstract_inverted_index.introduce | 1 |
| abstract_inverted_index.quadratic | 76 |
| abstract_inverted_index.resulting | 42 |
| abstract_inverted_index.unbiased, | 48 |
| abstract_inverted_index.algorithms | 28 |
| abstract_inverted_index.directions | 9 |
| abstract_inverted_index.results.\n | 87 |
| abstract_inverted_index.stochastic | 10 |
| abstract_inverted_index.the\nfirst | 26 |
| abstract_inverted_index.algorithms, | 68 |
| abstract_inverted_index.algorithms. | 19 |
| abstract_inverted_index.convergence | 58 |
| abstract_inverted_index.convergent. | 54 |
| abstract_inverted_index.experiments | 80 |
| abstract_inverted_index.first-order | 65 |
| abstract_inverted_index.incorporate | 30 |
| abstract_inverted_index.superiority | 62 |
| abstract_inverted_index.theoretical | 86 |
| abstract_inverted_index.Furthermore, | 55 |
| abstract_inverted_index.optimization | 77 |
| abstract_inverted_index.perturbation | 3 |
| abstract_inverted_index.second-order | 18, 27, 67 |
| abstract_inverted_index.approximation | 11 |
| abstract_inverted_index.deterministic | 2, 31, 44 |
| abstract_inverted_index.perturbations | 45 |
| abstract_inverted_index.to\nestablish | 60 |
| abstract_inverted_index.asymptotically | 47 |
| abstract_inverted_index.perturbations. | 32 |
| abstract_inverted_index.the\nalgorithms | 51 |
| abstract_inverted_index.algorithms\nwith | 43 |
| abstract_inverted_index.new\nfirst-order | 16 |
| abstract_inverted_index.proposed\nrandom | 8 |
| abstract_inverted_index.respectively.\nNumerical | 79 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 5 |
| citation_normalized_percentile.value | 0.25119736 |
| citation_normalized_percentile.is_in_top_1_percent | False |
| citation_normalized_percentile.is_in_top_10_percent | False |