This is an appeal from a 64-month sentence of imprisonment imposed by the United States District Court for the Eastern District of New York (Townes, J.), after Defendanb-Appellant Walford Folkes pleaded guilty to illegally reentering the United States following removal subsequent to a conviction for a felony, in violation of 8 U.S.C. § 1326(a) and (b)(2), and aggravated identity theft, in violation of 18 U.S.C. § 1028A(a)(1), (b), (c)(2), and (c)(7) Folkes’s sentence consists principally of a 40-month term of imprisonment on the illegal reentry count and a mandatory consecutive 24-month term of imprisonment on the identity theft count.
Folkes’s sole contention on appeal is that the district court erred in its calculation of his Sentencing Guidelines range with respect to the illegal reentry count when it applied a 16-level enhancement under U.S.S.G. § 2L1.2(b)(1)(A)(ii) after it concluded that Folkes had reentered the United States after being deported for commission of a crime of violence. The Government concedes that this was error and that the sentence should be corrected. Upon review of the record, we too agree, and we remand for resentencing.
BACKGROUND
In October 2008, Folkes took a Jamaica Airlines flight from Kingston, Jamaica, to John F. Kennedy International Airport in Queens, New York. At the airport, Folkes claimed to be a United States citizen named “James Pittman” and presented a United States passport in that name. When a customs officer scanned the passport, a computer database alerted him that “James Pittman” was a known alias of Walford Folkes, a previously deported felon. Officers fingerprinted Folkes, and after a preliminary comparison indicated that he was the same person who had been deported in October 1996, the officers arrested him. After waiving his Miranda rights, Folkes admitted that he was knowingly using another person’s identity and that he was a citizen of Jamaica and not a citizen of the United States. It is undisputed that in October 1996, an Immigration Judge had ordered Folkes deported because of a conviction in New York State for third-degree burglary, N.Y. Penal Law § 140.20.
Folkes was indicted in November 2008 on illegal reentry and identity theft charges, as well as one count of misusing a passport and one count of making a false claim of U.S. citizenship. In February 2009, Folkes and the Government entered into a plea agreement in which Folkes agreed to plead guilty to the illegal reentry and identity theft charges and the Government agreed to drop the other charges. The parties agreed that, pursuant to 18 U.S.C. § 1028A(a)(1) and (b)(2), the identity theft count carried a mandatory sentence of 24 months to run consecutively to any term of imprisonment imposed on the illegal reentry count. With respect to the illegal reentry count, the plea agreement assumed that the base offense level was eight, pursuant to U.S.S.G. § 2L1.2(a), and that an eight-level enhancement was warranted under U.S.S.G. § 2L1.2(b)(1)(C) because Folkes had been deported after conviction for an aggravated felony. The plea agreement also contemplated a three-level reduction for acceptance of responsibility, resulting in an adjusted offense level of 13. Assuming Folkes to be in Criminal History Category I, the plea agreement thus calculated a sentencing range of 12 to 18 months for the illegal reentry count and, with the mandatory 24-month sentence on the identity theft count added in, arrived at a combined Guidelines range of 36 to 42 *155months.1 The Government stood by this Guidelines range at Folkes’s subsequent guilty plea hearing. At that hearing, Folkes admitted attempting to enter the United States under a false name and with false identification, and also admitted to having previously been convicted of a burglary.
The Pre-Sentence Report (“PSR”) prepared by the Probation Department reached a different Guidelines calculation from the one described in the plea agreement. Specifically, the Probation Department took the position that Folkes’s conviction for burglary was not only an aggravated felony but also a crime of violence, such that a 16-level enhancement under U.S.S.G. § 2L1.2(b)(1)(A)(ii) should apply rather than the 8-level enhancement under § 2L1.2(b)(1)(C) proposed by the plea agreement. The PSR’s calculation resulted in an advisory Guidelines range of 37 to 46 months on the illegal reentry count. The PSR stated that Folkes had stolen property after he forced his way into an apartment at gunpoint and tied up a victim with a telephone line, in the presence of the victim’s child who was less than one year old.
In his sentencing letter to the district court, Folkes did not dispute that the 16-level enhancement for a crime of violence could apply to him. He argued for a lower sentence only on the basis that the Guidelines range agreed to by the parties in the plea agreement was adequate to serve the purposes of sentencing set forth in 18 U.S.C. § 3553(a). The Government, in its sentencing letter, endorsed the new calculation by the Probation Department, arguing that the 16-level enhancement was justified not by the burglary conviction but by Folkes’s separate conviction in January 1995 for third-degree criminal possession of a loaded firearm, in violation of N.Y. Penal Law § 265.02(4) (repealed 2006). The Government claimed that it had previously declined to pursue a 16-level enhancement based on the firearms conviction only because it had concluded that it did not qualify as a “firearms offense” within the meaning of U.S.S.G. § 2L1.2, Application Note 1(B)(v), and that it had failed to notice that the firearms conviction nevertheless qualified as a crime of violence.2
At the sentencing hearing, defense counsel made no objection to the PSR, calling it “a very thorough and accurate report.” Sent. Tr. at 3. Defense counsel did not dispute the PSR’s calculations but argued that the district court should nevertheless sentence within the range contemplated by the plea agreement, which adequately addressed the seriousness of the offense, and that Folkes’s burglary “sounds very serious but it is much more serious on paper than it actually was because the [district [attorney and the [c]ourt allowed him to plead guilty to the gun [charge] and get one year.” Id. at 5. The Government stated that it “t[ook] issue with some of the factual assertions made by defense counsel,” but otherwise stated only that it *156believed a sentence between 58 and 67 months to be appropriate. Id. at 13.
The district court adopted the Sentencing Guidelines calculation set forth by the Probation Department in the PSR. It then stated:
I have also considered the factors pursuant to 18 U.S.C. § 3553(a), the nature and circumstances of this offense and the history and characteristics of the defendant. The defendant appears before this [e]ourt having been convicted of ... 13 prior crimes and those prior crimes include sale and possession of a controlled substance, specifically marijuana, a forged instruments charge, phony driver’s license, using an alias, burglary in the third degree, [and] criminal possession of a loaded firearm. It is the finding of the [c]ourt that the defendant’s criminal history does not over-represent his past criminal conduct but it under-represents the defendant’s past criminal conduct.
Id. at 16-17. The district court imposed a 40-month term of imprisonment on the illegal reentry charge and a consecutive 24-month term of imprisonment on the identity theft charge. Folkes timely appealed.
DISCUSSION
I. Standard of Review
We review a district court’s sentencing decisions for both substantive and procedural reasonableness. See United States v. Rattoballi 452 F.3d 127, 131-32 (2d Cir.2006). Here, Folkes challenges only the procedural reasonableness of his sentence. An error in calculating the applicable Guidelines range is among the kinds of procedural error that renders a sentence unreasonable. See United States v. Canova, 485 F.3d 674, 679 (2d Cir.2007). Normally, we review a district court’s interpretation of the Guidelines de novo. See United States v. Villafuerte, 502 F.3d 204, 207 (2d Cir.2007). However, when a party fails to raise a sentencing issue in the district court, we review for plain error, see id. (citing United States v. Keppler, 2 F.3d 21, 23 (2d Cir.1993)), see also Fed.R.Crim.P. 52(b), although on occasion we have applied a less rigorous standard, see, e.g., United States v. Sofsky, 287 F.3d 122, 125-26 (2d Cir.2002). Plain error is (1) error (2) that is plain and (3) affects substantial rights. See United States v. Banks, 464 F.3d 184, 189 (2d Cir.2006). Once we have noticed plain error, it is within our discretion to decide whether to correct it, and we will do so only if it “seriously affect[s] the fairness, integrity or public reputation of judicial proceedings.” United States v. Doe, 297 F.3d 76, 82 (2d Cir.2002) (quoting United States v. Olano, 507 U.S. 725, 732, 113 S.Ct. 1770, 123 L.Ed.2d 508 (1993)).
II. Sentencing Guidelines Analysis
Sentencing for the offense of illegally reentering the United States is governed by U.S.S.G. § 2L1.2. The base offense level for this crime is 8. See § 2L1.2(a). If the offense is committed after the defendant was previously removed from the United States after a conviction for an aggravated felony — and it is undisputed that this is true of Folkes — then an additional eight levels are added to the total offense level. See § 2L1.2(b)(1)(C). If, however, the defendant has also been convicted of a “crime of violence,” the Guidelines instead require a 16-level enhancement. See § 2L1.2(b)(1)(A)(ii).
For purposes of this particular Guideline, “ ‘crime of violence’ means any of the following: murder, manslaughter, kidnapping, aggravated assault, forcible sex offenses, statutory rape, sexual abuse of a minor, robbery, arson, extortion, extortionate extension of credit, burglary of a *157dwelling, or any offense under federal, state, or local law that has as an element the use, attempted use, or threatened use of physical force against the person of another.” U.S.S.G. § 2L1.2, Application Note 1(B)(iii) (emphasis added). At the outset, it is crucial to take note that the words “crime of violence” are not defined in the same way for every part of the Sentencing Guidelines; for example, for purposes of the Guidelines section dealing with the sentencing of career offenders, “crime of violence” means most of the crimes listed above but also means “any offense ..., punishable by imprisonment for a term exceeding one year, that ... otherwise involves conduct that presents a serious potential risk of physical injury to another.” U.S.S.G. § 4B1.2(a)(2).
“In determining whether a given crime fits within the definition of the relevant predicate offenses, we take a ‘categorical’ approach; that is, we generally look only to the statutory definition of the prior offense of conviction rather than to the underlying facts of that offense.” United States v. Brown, 514 F.3d 256, 265 (2d Cir.2008) (citing Taylor v. United States, 495 U.S. 575, 600, 110 S.Ct. 2143, 109 L.Ed.2d 607 (1990)). Thus, for purposes of calculating Folkes’s Guidelines range, we must consider not descriptions of his actions in the PSR or elsewhere, but the statutes under which he was convicted — in this case, New York’s third-degree burglary statute, N.Y. Penal Law § 140.20, and the then-applicable third-degree criminal possession of a weapon statute under which Folkes was convicted in 1995, N.Y. Penal Law § 265.02(4) (repealed 2006).
Under § 140.20, “[a] person is guilty of burglary in the third degree when he knowingly enters or remains unlawfully in a building with intent to commit a crime therein.” As it happens, in Brown, we considered the same burglary statute. See Brown, 514 F.3d at 265. In that case, however, the relevant Guideline for the defendant’s offense stated that “crime of violence” had the same meaning given to it in U.S.S.G. § 4B1.2(a). See Brown, 514 F.3d at 260. We concluded that a violation of § 140.20 could not be considered categorically a crime of violence under the “burglary of a dwelling” clause because “[p]lainly, ‘buildingfs]’ includes structures other than ‘dwelling[s].’ ” Id. at 265-67. We held that § 140.20 was nevertheless a crime of violence under the relevant Guidelines in that case because it fell under § 4B1.2(a)’s residual clause, as it “otherwise involve[d] conduct that presents a serious potential risk of physical injury to another.” Id. at 268-69.
We are bound by Brown’s holding that § 140.20 is not a crime of violence under a clause that defines such a crime as one involving “burglary of a dwelling.” But in this case, where “crime of violence” is defined by U.S.S.G. § 2L1.2 rather than by § 4B 1.2(a), there is no residual clause under which we may look to the inherent dangers of the conduct described by the statute as a basis for holding that it is a crime of violence. Section 2L1.2 does contain a different residual clause, which defines a crime of violence as any crime other than those already listed that “has as an element the use, attempted use, or threatened use of physical force against the person of another.” (emphasis added) But however serious Folkes’s actual conduct may have been, the elements of § 140.20 are that the defendant (1) knowingly (2) enter or remain unlawfully (3) in a building (4) with intent to commit a crime therein. None of these elements necessarily involves the “use, attempted use, or threatened use of physical force against the person of another.” Accordingly, for purposes of sentencing under U.S.S.G. § 2L1.2, a conviction under N.Y. *158Penal Law § 140.20 does not constitute a crime of violence.
The Government further concedes on appeal that it was mistaken when it argued, in the district court, that Folkes’s separate firearms conviction could support the crime of violence enhancement. We agree. The relevant statute stated that “[a] person is guilty of criminal possession of a weapon in the third degree when [such] person possesses any loaded firearm.” N.Y. Penal Law § 265.02(4) (repealed 2006). We have previously held that secomi-degree criminal possession under New York law, as defined in N.Y. Penal Law § 265.03, is not a crime of violence under U.S.S.G. § 2L1.2. See United States v. Gamez, 577 F.3d 394, 398 (2d Cir.2009). Under § 265.03, “[a] person is guilty of criminal possession of a weapon in the second degree when, with intent to use the same unlawfully against another ... [h]e possesses a loaded firearm.” In Gamez, we concluded that “intent to use a gun unlawfully against another, an element of the offense for which he was convicted, cannot be equated with the actual, attempted or threatened use of physical force, which all involve some affirmative conduct beyond the mere possession of a gun.” Id. (internal quotation marks omitted). Given that § 265.03 contains all of the elements of § 265.02(4) as well as the additional element of intent to use the firearm unlawfully against another, the reasoning of Gamez applies a fortiori to § 265.02(4) and requires us to hold that it, too, is not a crime of violence.
The Government admits that the district court’s error was plain, and urges us to exercise our discretion to correct it. We have no difficulty agreeing to do so. “To be plain, the error must be clear or obvious ... at the time of appellate review.” Villafuerte, 502 F.3d at 209 (citing Olano, 507 U.S. at 734, 113 S.Ct. 1770; United States v. Stewart, 433 F.3d 273, 290 (2d Cir.2006)). After Brown and Gamez, it is obvious that neither N.Y. Penal Law § 140.20 nor N.Y. Penal Law § 265.02(4) could qualify as a crime of violence for purposes of sentencing under the illegal reentry guideline.3 We have also recognized that a defendant’s substantial rights are affected by any error that results in a significantly overstated Guidelines range, because “the advisory Guidelines range [is] the starting point for the district court’s determination of the sentence.... ” Gamez, 577 F.3d at 401 (finding substantial rights affected where defendant’s offense level was incorrectly calculated to be 21 and should have been, at most, 13). Finally, because the district court’s determination of an appropriate sentence was influenced by a Guidelines range that was more than twice the correct range, see, e.g., id., we exercise our discretion to correct the error as one that “seriously affect[ed] the fairness ... of judicial proceedings.” Doe, 297 F.3d at 82.
That said, we are mindful that the district court believed that Folkes’s criminal history category under the Guidelines understated the seriousness of his past conduct. Although the procedural error in this case is sufficiently serious to require correction, the district judge retains her authority, at resentencing, “to select any appropriate sentence, consistent with 18 U.S.C. § 3553(a), whether or not pursuant to the Guidelines.” United States v. Whitley, 529 F.3d 150, 158 (2d Cir.2008); see also United States v. Cavera, 550 F.3d 180, 194 (2d Cir.2008) (en banc) (“[D]istrict *159courts have the power to impose sentences both above and below the Guidelines range.”).
CONCLUSION
We remand for resentencing. The mandate shall issue forthwith.