Noise misleads rotation invariant algorithms on sparse targets Article Swipe
Manfred K. Warmuth
,
Wojciech Kotłowski
,
Matt Jones
,
Ehsan Amid
·
YOU?
·
· 2024
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2403.02697
YOU?
·
· 2024
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2403.02697
It is well known that the class of rotation invariant algorithms are suboptimal even for learning sparse linear problems when the number of examples is below the "dimension" of the problem. This class includes any gradient descent trained neural net with a fully-connected input layer (initialized with a rotationally symmetric distribution). The simplest sparse problem is learning a single feature out of $d$ features. In that case the classification error or regression loss grows with $1-k/n$ where $k$ is the number of examples seen. These lower bounds become vacuous when the number of examples $k$ reaches the dimension $d$. We show that when noise is added to this sparse linear problem, rotation invariant algorithms are still suboptimal after seeing $d$ or more examples. We prove this via a lower bound for the Bayes optimal algorithm on a rotationally symmetrized problem. We then prove much lower upper bounds on the same problem for simple non-rotation invariant algorithms. Finally we analyze the gradient flow trajectories of many standard optimization algorithms in some simple cases and show how they veer toward or away from the sparse targets. We believe that our trajectory categorization will be useful in designing algorithms that can exploit sparse targets and our method for proving lower bounds will be crucial for analyzing other families of algorithms that admit different classes of invariances.
Related Topics
Concepts
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- http://arxiv.org/abs/2403.02697
- https://arxiv.org/pdf/2403.02697
- OA Status
- green
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4392538070
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4392538070Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.48550/arxiv.2403.02697Digital Object Identifier
- Title
-
Noise misleads rotation invariant algorithms on sparse targetsWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2024Year of publication
- Publication date
-
2024-03-05Full publication date if available
- Authors
-
Manfred K. Warmuth, Wojciech Kotłowski, Matt Jones, Ehsan AmidList of authors in order
- Landing page
-
https://arxiv.org/abs/2403.02697Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/2403.02697Direct 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/2403.02697Direct OA link when available
- Concepts
-
Invariant (physics), Algorithm, Noise (video), Computer science, Rotation (mathematics), Mathematics, Artificial intelligence, Image (mathematics), Mathematical physicsTop 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/W4392538070 |
|---|---|
| doi | https://doi.org/10.48550/arxiv.2403.02697 |
| ids.doi | https://doi.org/10.48550/arxiv.2403.02697 |
| ids.openalex | https://openalex.org/W4392538070 |
| fwci | |
| type | preprint |
| title | Noise misleads rotation invariant algorithms on sparse targets |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T11325 |
| topics[0].field.id | https://openalex.org/fields/22 |
| topics[0].field.display_name | Engineering |
| topics[0].score | 0.9858999848365784 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/2202 |
| topics[0].subfield.display_name | Aerospace Engineering |
| topics[0].display_name | Inertial Sensor and Navigation |
| topics[1].id | https://openalex.org/T11405 |
| topics[1].field.id | https://openalex.org/fields/19 |
| topics[1].field.display_name | Earth and Planetary Sciences |
| topics[1].score | 0.9847999811172485 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/1910 |
| topics[1].subfield.display_name | Oceanography |
| topics[1].display_name | Geophysics and Gravity Measurements |
| topics[2].id | https://openalex.org/T13487 |
| topics[2].field.id | https://openalex.org/fields/26 |
| topics[2].field.display_name | Mathematics |
| topics[2].score | 0.9846000075340271 |
| 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 | Statistical and numerical algorithms |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C190470478 |
| concepts[0].level | 2 |
| concepts[0].score | 0.6282116174697876 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q2370229 |
| concepts[0].display_name | Invariant (physics) |
| concepts[1].id | https://openalex.org/C11413529 |
| concepts[1].level | 1 |
| concepts[1].score | 0.5565122961997986 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q8366 |
| concepts[1].display_name | Algorithm |
| concepts[2].id | https://openalex.org/C99498987 |
| concepts[2].level | 3 |
| concepts[2].score | 0.4888159930706024 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q2210247 |
| concepts[2].display_name | Noise (video) |
| concepts[3].id | https://openalex.org/C41008148 |
| concepts[3].level | 0 |
| concepts[3].score | 0.4643203616142273 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[3].display_name | Computer science |
| concepts[4].id | https://openalex.org/C74050887 |
| concepts[4].level | 2 |
| concepts[4].score | 0.4606170356273651 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q848368 |
| concepts[4].display_name | Rotation (mathematics) |
| concepts[5].id | https://openalex.org/C33923547 |
| concepts[5].level | 0 |
| concepts[5].score | 0.3395209014415741 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[5].display_name | Mathematics |
| concepts[6].id | https://openalex.org/C154945302 |
| concepts[6].level | 1 |
| concepts[6].score | 0.2859569191932678 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q11660 |
| concepts[6].display_name | Artificial intelligence |
| concepts[7].id | https://openalex.org/C115961682 |
| concepts[7].level | 2 |
| concepts[7].score | 0.0 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q860623 |
| concepts[7].display_name | Image (mathematics) |
| concepts[8].id | https://openalex.org/C37914503 |
| concepts[8].level | 1 |
| concepts[8].score | 0.0 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q156495 |
| concepts[8].display_name | Mathematical physics |
| keywords[0].id | https://openalex.org/keywords/invariant |
| keywords[0].score | 0.6282116174697876 |
| keywords[0].display_name | Invariant (physics) |
| keywords[1].id | https://openalex.org/keywords/algorithm |
| keywords[1].score | 0.5565122961997986 |
| keywords[1].display_name | Algorithm |
| keywords[2].id | https://openalex.org/keywords/noise |
| keywords[2].score | 0.4888159930706024 |
| keywords[2].display_name | Noise (video) |
| keywords[3].id | https://openalex.org/keywords/computer-science |
| keywords[3].score | 0.4643203616142273 |
| keywords[3].display_name | Computer science |
| keywords[4].id | https://openalex.org/keywords/rotation |
| keywords[4].score | 0.4606170356273651 |
| keywords[4].display_name | Rotation (mathematics) |
| keywords[5].id | https://openalex.org/keywords/mathematics |
| keywords[5].score | 0.3395209014415741 |
| keywords[5].display_name | Mathematics |
| keywords[6].id | https://openalex.org/keywords/artificial-intelligence |
| keywords[6].score | 0.2859569191932678 |
| keywords[6].display_name | Artificial intelligence |
| language | en |
| locations[0].id | pmh:oai:arXiv.org:2403.02697 |
| 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/2403.02697 |
| 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/2403.02697 |
| locations[1].id | doi:10.48550/arxiv.2403.02697 |
| locations[1].is_oa | True |
| locations[1].source.id | https://openalex.org/S4306400194 |
| locations[1].source.issn | |
| locations[1].source.type | repository |
| locations[1].source.is_oa | True |
| locations[1].source.issn_l | |
| locations[1].source.is_core | False |
| locations[1].source.is_in_doaj | False |
| locations[1].source.display_name | arXiv (Cornell University) |
| locations[1].source.host_organization | https://openalex.org/I205783295 |
| locations[1].source.host_organization_name | Cornell University |
| locations[1].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[1].license | cc-by |
| locations[1].pdf_url | |
| locations[1].version | |
| locations[1].raw_type | article |
| locations[1].license_id | https://openalex.org/licenses/cc-by |
| locations[1].is_accepted | False |
| locations[1].is_published | |
| locations[1].raw_source_name | |
| locations[1].landing_page_url | https://doi.org/10.48550/arxiv.2403.02697 |
| indexed_in | arxiv, datacite |
| authorships[0].author.id | https://openalex.org/A5108549518 |
| authorships[0].author.orcid | |
| authorships[0].author.display_name | Manfred K. Warmuth |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Warmuth, Manfred K. |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5001603308 |
| authorships[1].author.orcid | https://orcid.org/0000-0002-5905-8069 |
| authorships[1].author.display_name | Wojciech Kotłowski |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Kotłowski, Wojciech |
| authorships[1].is_corresponding | False |
| authorships[2].author.id | https://openalex.org/A5101746140 |
| authorships[2].author.orcid | https://orcid.org/0000-0001-7657-7373 |
| authorships[2].author.display_name | Matt Jones |
| authorships[2].author_position | middle |
| authorships[2].raw_author_name | Jones, Matt |
| authorships[2].is_corresponding | False |
| authorships[3].author.id | https://openalex.org/A5056776503 |
| authorships[3].author.orcid | https://orcid.org/0000-0001-6097-0226 |
| authorships[3].author.display_name | Ehsan Amid |
| authorships[3].author_position | last |
| authorships[3].raw_author_name | Amid, Ehsan |
| authorships[3].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/2403.02697 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | Noise misleads rotation invariant algorithms on sparse targets |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T06:51:31.235846 |
| primary_topic.id | https://openalex.org/T11325 |
| primary_topic.field.id | https://openalex.org/fields/22 |
| primary_topic.field.display_name | Engineering |
| primary_topic.score | 0.9858999848365784 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/2202 |
| primary_topic.subfield.display_name | Aerospace Engineering |
| primary_topic.display_name | Inertial Sensor and Navigation |
| related_works | https://openalex.org/W1979597421, https://openalex.org/W2007980826, https://openalex.org/W2061531152, https://openalex.org/W3002753104, https://openalex.org/W2077600819, https://openalex.org/W2142036596, https://openalex.org/W2072657027, https://openalex.org/W2600246793, https://openalex.org/W4238204885, https://openalex.org/W2963966623 |
| cited_by_count | 0 |
| locations_count | 2 |
| best_oa_location.id | pmh:oai:arXiv.org:2403.02697 |
| 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/2403.02697 |
| 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/2403.02697 |
| primary_location.id | pmh:oai:arXiv.org:2403.02697 |
| 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/2403.02697 |
| 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/2403.02697 |
| publication_date | 2024-03-05 |
| publication_year | 2024 |
| referenced_works_count | 0 |
| abstract_inverted_index.a | 41, 47, 57, 127, 136 |
| abstract_inverted_index.In | 64 |
| abstract_inverted_index.It | 0 |
| abstract_inverted_index.We | 99, 123, 140, 184 |
| abstract_inverted_index.be | 191, 209 |
| abstract_inverted_index.in | 168, 193 |
| abstract_inverted_index.is | 1, 24, 55, 78, 104 |
| abstract_inverted_index.of | 7, 22, 28, 61, 81, 92, 163, 215, 221 |
| abstract_inverted_index.on | 135, 147 |
| abstract_inverted_index.or | 70, 120, 178 |
| abstract_inverted_index.to | 106 |
| abstract_inverted_index.we | 157 |
| abstract_inverted_index.$d$ | 62, 119 |
| abstract_inverted_index.$k$ | 77, 94 |
| abstract_inverted_index.The | 51 |
| abstract_inverted_index.and | 172, 201 |
| abstract_inverted_index.any | 34 |
| abstract_inverted_index.are | 11, 114 |
| abstract_inverted_index.can | 197 |
| abstract_inverted_index.for | 14, 130, 151, 204, 211 |
| abstract_inverted_index.how | 174 |
| abstract_inverted_index.net | 39 |
| abstract_inverted_index.our | 187, 202 |
| abstract_inverted_index.out | 60 |
| abstract_inverted_index.the | 5, 20, 26, 29, 67, 79, 90, 96, 131, 148, 159, 181 |
| abstract_inverted_index.via | 126 |
| abstract_inverted_index.$d$. | 98 |
| abstract_inverted_index.This | 31 |
| abstract_inverted_index.away | 179 |
| abstract_inverted_index.case | 66 |
| abstract_inverted_index.even | 13 |
| abstract_inverted_index.flow | 161 |
| abstract_inverted_index.from | 180 |
| abstract_inverted_index.loss | 72 |
| abstract_inverted_index.many | 164 |
| abstract_inverted_index.more | 121 |
| abstract_inverted_index.much | 143 |
| abstract_inverted_index.same | 149 |
| abstract_inverted_index.show | 100, 173 |
| abstract_inverted_index.some | 169 |
| abstract_inverted_index.that | 4, 65, 101, 186, 196, 217 |
| abstract_inverted_index.then | 141 |
| abstract_inverted_index.they | 175 |
| abstract_inverted_index.this | 107, 125 |
| abstract_inverted_index.veer | 176 |
| abstract_inverted_index.well | 2 |
| abstract_inverted_index.when | 19, 89, 102 |
| abstract_inverted_index.will | 190, 208 |
| abstract_inverted_index.with | 40, 46, 74 |
| abstract_inverted_index.Bayes | 132 |
| abstract_inverted_index.These | 84 |
| abstract_inverted_index.added | 105 |
| abstract_inverted_index.admit | 218 |
| abstract_inverted_index.after | 117 |
| abstract_inverted_index.below | 25 |
| abstract_inverted_index.bound | 129 |
| abstract_inverted_index.cases | 171 |
| abstract_inverted_index.class | 6, 32 |
| abstract_inverted_index.error | 69 |
| abstract_inverted_index.grows | 73 |
| abstract_inverted_index.input | 43 |
| abstract_inverted_index.known | 3 |
| abstract_inverted_index.layer | 44 |
| abstract_inverted_index.lower | 85, 128, 144, 206 |
| abstract_inverted_index.noise | 103 |
| abstract_inverted_index.other | 213 |
| abstract_inverted_index.prove | 124, 142 |
| abstract_inverted_index.seen. | 83 |
| abstract_inverted_index.still | 115 |
| abstract_inverted_index.upper | 145 |
| abstract_inverted_index.where | 76 |
| abstract_inverted_index.become | 87 |
| abstract_inverted_index.bounds | 86, 146, 207 |
| abstract_inverted_index.linear | 17, 109 |
| abstract_inverted_index.method | 203 |
| abstract_inverted_index.neural | 38 |
| abstract_inverted_index.number | 21, 80, 91 |
| abstract_inverted_index.seeing | 118 |
| abstract_inverted_index.simple | 152, 170 |
| abstract_inverted_index.single | 58 |
| abstract_inverted_index.sparse | 16, 53, 108, 182, 199 |
| abstract_inverted_index.toward | 177 |
| abstract_inverted_index.useful | 192 |
| abstract_inverted_index.$1-k/n$ | 75 |
| abstract_inverted_index.Finally | 156 |
| abstract_inverted_index.analyze | 158 |
| abstract_inverted_index.believe | 185 |
| abstract_inverted_index.classes | 220 |
| abstract_inverted_index.crucial | 210 |
| abstract_inverted_index.descent | 36 |
| abstract_inverted_index.exploit | 198 |
| abstract_inverted_index.feature | 59 |
| abstract_inverted_index.optimal | 133 |
| abstract_inverted_index.problem | 54, 150 |
| abstract_inverted_index.proving | 205 |
| abstract_inverted_index.reaches | 95 |
| abstract_inverted_index.targets | 200 |
| abstract_inverted_index.trained | 37 |
| abstract_inverted_index.vacuous | 88 |
| abstract_inverted_index.examples | 23, 82, 93 |
| abstract_inverted_index.families | 214 |
| abstract_inverted_index.gradient | 35, 160 |
| abstract_inverted_index.includes | 33 |
| abstract_inverted_index.learning | 15, 56 |
| abstract_inverted_index.problem, | 110 |
| abstract_inverted_index.problem. | 30, 139 |
| abstract_inverted_index.problems | 18 |
| abstract_inverted_index.rotation | 8, 111 |
| abstract_inverted_index.simplest | 52 |
| abstract_inverted_index.standard | 165 |
| abstract_inverted_index.targets. | 183 |
| abstract_inverted_index.algorithm | 134 |
| abstract_inverted_index.analyzing | 212 |
| abstract_inverted_index.designing | 194 |
| abstract_inverted_index.different | 219 |
| abstract_inverted_index.dimension | 97 |
| abstract_inverted_index.examples. | 122 |
| abstract_inverted_index.features. | 63 |
| abstract_inverted_index.invariant | 9, 112, 154 |
| abstract_inverted_index.symmetric | 49 |
| abstract_inverted_index.algorithms | 10, 113, 167, 195, 216 |
| abstract_inverted_index.regression | 71 |
| abstract_inverted_index.suboptimal | 12, 116 |
| abstract_inverted_index.trajectory | 188 |
| abstract_inverted_index."dimension" | 27 |
| abstract_inverted_index.algorithms. | 155 |
| abstract_inverted_index.symmetrized | 138 |
| abstract_inverted_index.(initialized | 45 |
| abstract_inverted_index.invariances. | 222 |
| abstract_inverted_index.non-rotation | 153 |
| abstract_inverted_index.optimization | 166 |
| abstract_inverted_index.rotationally | 48, 137 |
| abstract_inverted_index.trajectories | 162 |
| abstract_inverted_index.categorization | 189 |
| abstract_inverted_index.classification | 68 |
| abstract_inverted_index.distribution). | 50 |
| abstract_inverted_index.fully-connected | 42 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 4 |
| citation_normalized_percentile |