After appellant Barbara Ann Kuhl filed in bankruptcy and achieved the discharge of her debts, the IRS garnished her wages. Kuhl demonstrated that most of the tax liabilities had been discharged, and she thereby defeated the garnishment. She now seeks to recover from the IRS attorneys’ fees she incurred litigating the issue of dischargeability.
The Bankruptcy Court for the Eastern District of New York (Bernstein, J.) denied her motion for attorneys’ fees, and the District Court for the Eastern District of New York (Seybert, J.) affirmed. On appeal, the IRS asserts that Kuhl failed to exhaust her administrative remedies. We agree, and therefore vacate the judgment and remand with the instruction to dismiss for lack of jurisdiction.
BACKGROUND
Barbara Ann Kuhl filed joint tax returns with her husband, Paul, from 1981-1990. On March 24, 1993, she filed a joint return for tax year 1991 bearing both names and both signatures. On that date, the couple was in the midst of divorce proceedings. Mr. Kuhl later told an IRS auditor that he had not himself signed the 1991 return. A deficiency was thereupon assessed against Ms. Kuhl.
Ms. Kuhl filed for Chapter 7 relief in the Eastern District of New York on February 10, 2000. An order of discharge was issued in May 2000, relieving her of specified liabilities pursuant to 11 U.S.C. § 524, which grants relief as against the IRS in respect to years in which a return was filed. By notice of levy dated February 27, 2003, the IRS nevertheless garnished Ms. Kuhl’s wages to satisfy alleged outstanding tax liabilities, including the 1991 tax deficiency. The position of the IRS was that the nominally joint return filed for 1991 did not constitute a proper return within the meaning of 11 U.S.C. § 524.1
On March 29, 2003, Ms. Kuhl protested the garnishment in a letter sent by certified mail to the IRS office in Fresno, California, from which the levy notification was mailed to her employer.2 Her exasperated letter stated:
In regard to the attached notice requesting payment of $92055.10 in unpaid taxes, please be advised, again, that I filed bankruptcy. I have enclosed copies of the Bankruptcy Discharge Papers, again.
I am writing you because calling the IRS is very time consuming and I have never gotten any results. I have faxed the Bankruptcy Discharged Papers directly to an IRS agent with no results.
Let’s try this one more time. Please release the levy sent to my employer, Belesi & Donovan, PC, requesting a salary garnishment.
Please call me at [telephone number] to clear up this matter. Thank you.
*147Soon after, in May 2003, Ms. Kuhl moved to reopen her bankruptcy case in order to discharge the assessment. She also sought “compensatory damages, attorneys’ fees and costs, and other charges for the IRS’ willful violation” of the discharge order.
In the fall of 2004, the bankruptcy court discharged the 1991 tax liability, but it denied Ms. Kuhl’s motion for sanctions, and both parties appealed. The IRS ultimately dropped its appeal from the discharge, but Ms. Kuhl pursued her appeal of the denial of sanctions. On August 16, 2005, the district court affirmed. On appeal, Ms. Kuhl seeks only attorneys’ fees.
We have appellate jurisdiction pursuant to 28 U.S.C. § 158(d)(1), and “review the bankruptcy court decision independently, accepting its factual findings unless clearly erroneous but reviewing its conclusions of law de novo.” In re Enron Corp., 419 F.3d 115, 124 (2d Cir.2005) (internal citation omitted).
DISCUSSION
A discharge in bankruptcy operates as an injunction against collection of any discharged debts. 11 U.S.C. § 524(a)(2). Congress has conditionally waived sovereign immunity for the IRS’s willful violation of such a discharge: after exhausting administrative remedies, the taxpayer may petition the bankruptcy court for damages. 26 U.S.C. § 7433(e). However, “[ljitigation costs and administrative costs are not recoverable as actual, direct economic damages,” but are instead “recoverable under [26 U.S.C.] section 7430.” 26 C.F.R. § 301.7433-2(b)(2).
Section 7430 in turn allows recovery of attorneys’ fees provided that “the prevailing party has exhausted the administrative remedies available to such party within the Internal Revenue Service.” 26 U.S.C. § 7430(b)(1). Failure to exhaust such remedies deprives the federal court of jurisdiction over the suit. Cf. Venen v. United States, 38 F.3d 100, 103 (3d Cir.1994) (failure to pursue administrative remedies afforded in 26 U.S.C. § 7433 strips the federal court of jurisdiction).
The administrative remedies that were available to Ms. Kuhl are spelled out in 26 C.F.R. § 301.7430-1, which is entitled “Exhaustion of administrative remedies,” and which prescribes different remedies depending on the nature of the taxpayer’s claim. Subsection (e) of that regulation prescribes the remedies for “Actions involving willful violations of ... the discharge provisions under section 524 of the Bankruptcy Code.” Here, the IRS asserts on appeal (for the first time) that Ms. Kuhl failed to exhaust the remedy afforded in subsection (e)(1) of the regulation, which specified where the taxpayer must send her administrative claim.
Unhelpfully, subsection (e)(1) carries the subtitle “Section 7433 claims,” a cross-reference to the statutory provision for damages. We do not infer from the subtitle, however, that subsection (e)(1) prescribes the administrative remedy only for damages, and not for attorneys’ fees. The regulation makes abundantly clear at the outset that it applies generally to attorneys’ fees as well as damages:
[26 U.S.C.] 7430(b)(1) provides that a court shall not award reasonable litigation costs in any civil tax proceeding under section 7430(a) unless the court determines that the prevailing party has exhausted the administrative remedies available to the party within the Internal Revenue Service. This section sets forth the circumstances in which such administrative remedies shall be deemed to have been exhausted.
26 C.F.R. § 301.7430-l(a) (emphasis added). Accordingly, attorneys’ fees are in-*148eluded in the category of losses that are governed by subsection (e)(1), which requires that to exhaust, a taxpayer must:
fil[e] an administrative claim for damages or for relief from a violation of section ... 524 of the Bankruptcy Code with the Chief, Local Insolvency Unit, for the judicial district in which the bankruptcy petition that is the basis for the asserted ... discharge violation was filed.
26 C.F.R. § 301.7430-l(e)(l). The claim must describe the violation and the injuries incurred. Id. (cross-referencing § 301.7433-2). (The text of the subsection that specifies the requirements of notice is set forth in the margin.3)
Were subsection (e)(1) read in light of its title (“Section 7433 claims”), rather than in light of the structure and meaning of the regulation as a whole, a taxpayer such as Ms. Kuhl seeking attorneys’ fees incurred in defeating a levy imposed in violation of a discharge order could proceed under subsection (e)(1) only if she sought damages as well, or otherwise must proceed under § 301.7430-l(d) — which is entitled “Actions involving summonses, levies, liens, jeopardy and termination assessments.” (Emphasis added). (Subsection (d) prescribes a different means of exhaustion: the taxpayer must send a letter to the “district director of the district having jurisdiction over the dispute” and await a response.) However, since subsection (d) does not expressly refer to either “damages” or “costs,” such a reading would require that Ms. Kuhl have sent one letter for damages (which are indisputably covered by subsection (e)(1)) and another for fees.
We therefore apply subsection (e)(l)’s exhaustion requirements to Ms. Kuhl’s claim for attorneys’ fees, and conclude that she failed to exhaust the administrative remedies available to her. In order to overcome sovereign immunity, Ms. Kuhl should have sent a letter detailing her claim to the IRS Insolvency Unit in the Eastern District of New York, specifying her claim for attorneys’ fees. Instead, Ms. Kuhl wrote a letter that did not refer to attorneys’ fees and sent it to the IRS office in Fresno, California. The burden imposed by 26 C.F.R. § 301.7430-1 is exacting and non-intuitive, but taxpayers must comply with the letter of the government’s naiTow waiver of sovereign immunity in order to get to federal court. See Amwest Sur. Ins. Co. v. United States, 28 F.3d 690 (7th Cir.1994) (dismissing for lack of jurisdiction where appellant failed to comply with 26 C.F.R. § 301.6343-1 because it sent its complaint to the wrong IRS division).
Ms. Kuhl’s argument that inexhaustion was not raised below is a nonstarter. See *149Arbaugh v. Y & H Corp., — U.S. —, 126 S.Ct. 1235, 1244, 163 L.Ed.2d 1097 (2006) (jurisdictional objections are never waived). Likewise, her argument that the IRS had notice in fact of her claim does not amount to the required showing that the IRS official designated by the regulation was on notice and thus in a position to resolve her claim administratively. See Amwest, 28 F.3d at 697-98.
Ms. Kuhl advances two other arguments that bear mention. First, she argues that the regulations at issue did not take effect until after the February 27, 2003 wage seizure. That may be so, but the regulation is expressly retroactive and applies to all proceedings commencing after May 7, 1992. 26 C.F.R. § 301.7430-l(h). Second, she argues that “a regulatory amendment cannot vary a court’s statutory jurisdiction.” However, the authorizing statute requires categorically that taxpayers “exhaust[ ] the administrative remedies available ... within the Internal Revenue Service.” 26 U.S.C. § 7430(b)(1). Insofar as Kuhl disputes whether the regulations at issue have the force and effect of law, we note that they were promulgated under this explicit delegation of rule-making authority, affect individual rights and obligations, and though exacting, are clearly non-arbitrary and reasonably related to the purpose of the enabling legislation. See Amwest, 28 F.3d at 695. In any event, Congress evidently did not foreclose the agency from effecting changes in the scheme of administrative remedies.
* * *
Kuhl’s failure to exhaust her administrative remedies in pursuit of attorneys’ fees deprives this Court of jurisdiction over her claim. We do not reach the IRS’s other defenses.
CONCLUSION
For the foregoing reasons, we vacate the order denying Kuhl’s motion for attorneys’ fees and remand to the district court with the instruction to remand to the bankruptcy court with the instruction to dismiss for lack of jurisdiction.
. The soundness of that position is not before us on appeal.
. The IRS objects that the letter was not in the record. While Ms. Kuhl bears the burden of demonstrating jurisdiction, the IRS's challenge to jurisdiction is raised for the first time on appeal. We therefore exercise discretion to allow Ms. Kuhl to submit the letter to us, without considering whether she was entitled to do so.
. (i) The name, taxpayer identification number, current address, and current home and work telephone numbers (with an identification of any convenient times to be contacted) of the taxpayer making the claim;
(ii) The location of the bankruptcy court in which the underlying bankruptcy case was filed and the case number of the case in which the violation occurred;
(iii) A description, in reasonable detail, of the violation (include copies of any available substantiating documentation or correspondence with the Internal Revenue Service);
(iv) A description of the injuries incurred by the taxpayer filing the claim (include copies of any available substantiating documentation or evidence);
(v) The dollar amount of the claim, including any damages that have not yet been incurred but which are reasonably foreseeable (include copies of any available documentation or evidence); and
(vi) The signature of the taxpayer or duly authorized representative.
26 C.F.R. 301.7433-2(e)(2).