DISCUSSION
A. Adequacy of the Summary Dismissal Procedures
Padilla claims that the INS failed to timely serve him with its motion to summarily dismiss his appeal. He also claims that because the BIA failed to provide him with notice of a possible summary dismissal, that dismissal violated his fifth amendment right to procedural due process.
We reject the first of his contentions. Padilla simply cannot establish that he was prejudiced by the INS’s failure to properly serve him with its motion to dismiss: the INS sought to dismiss the appeal as frivolous under 8 C.F.R. § 3.1(d)(1-a)(iv) (1992), but the BIA independently dismissed his appeal under another provision, 8 C.F.R. § 3.1(d)(1-a)(i) (1992), because he failed to specify the bases for his appeal. See Tejeda-Mata v. INS, 626 F.2d 721, 725 (9th Cir.1980) (stating that a “[violation of a regulation renders a deportation unlawful only if [it] prejudiced the interests of the alien”) (internal quotation omitted), cert. denied, 456 U.S. 994, 102 S.Ct. 2280, 73 L.Ed.2d 1291 (1982). Thus, the action or inaction of the INS is beside the point.
His second contention has merit. He did not receive adequate notice of the potential for summary dismissal of his appeal. “[T]o survive judicial scrutiny, the BIA’s procedures in summarily dismissing appeals must” not sink to the level of being “so arbitrary as to undermine the principles of due process.” Toquero v. INS, 956 F.2d 193, 196 (9th Cir.1992). The Supreme Court has specifically held that due process requires administrative agencies not only to inform petitioners that proceedings have been instituted against them, but also to provide them with sufficient information to allow them to prepare and present objections to the agency’s preliminary action or decision. See Memphis Light, Gas & Water Div. v. Craft, 436 U.S. 1, 14—15, 98 S.Ct. 1554, 1562-63, 56 L.Ed.2d 30 (1978); see also Administrative Procedure Act, 5 U.S.C. §§ 554(b) and (c), 557(c); Hatch v. Federal Energy Reg. Comm’n, 654 F.2d 825, 835 (D.C.Cir.1981); Hess & Clark, Div. of Rhodia, Inc. v. Food & Drug Admin., 495 F.2d 975, 983 (D.C.Cir.1974); Abercrombie v. Clarke, 920 F.2d 1351, 1360 (7th Cir.1990), cert. denied, - U.S. -, 112 S.Ct. 52, 116 L.Ed.2d 29 (1991).
Moreover, in Mathews v. Eldridge, 424 U.S. 319, 335, 96 S.Ct. 893, 903, 47 L.Ed.2d 18 (1976), the Court detailed the factors to be considered when there is a claim that an administrative procedure which affects private interests denies due process. Those are:
First, the private interest that will be affected by the official action; second, the risk of an erroneous deprivation of such interest through the procedures used, and the probable value, if any, of additional or substitute procedural safeguards; and finally, the Government’s interest, including the function involved and the fiscal and administrative burdens that the additional or substitute procedural requirement would entail.
Id.; see also, National Ass’n of Radiation Survivors v. Derwinski, 994 F.2d 583, 588 (9th Cir.1992) (setting forth and applying Mathews factors), cert. denied, — U.S. —, 114 S.Ct. 634, 126 L.Ed.2d 592 (1993). We think it cannot be gainsaid that the private liberty interests involved in deportation proceedings are among the most substantial. See, e.g., INS v. Cardoza-Fonseca, 480 U.S. 421, 449, 107 S.Ct. 1207, 1222, 94 L.Ed.2d 434 (1987) (“Deportation is always a harsh measure”); Bridges v. Wixon, 326 U.S. 135, 154, 65 S.Ct. 1443, 1452-53, 89 L.Ed. 2103 (1945) (“Here the liberty of an individual is at stake_ Though deportation is not technically a criminal proceeding, it visits a great hardship on the individual and deprives him of the right to stay and live and work in this land of freedom.... Meticulous care must be exercised lest the procedure by which he is deprived of that liberty not meet the essential standards of fairness.”); Yamataya v. Fisher, 189 U.S. 86, 101, 23 S.Ct. 611, 614-15, 47 L.Ed. 721 (1903) (“[N]o person shall be deprived of his liberty without opportunity ... to be heard_ Therefore, it is not competent ... arbitrarily to cause an alien who has entered the country ... to be taken into custody and deported without giving him all opportunity to be heard-”); Yepes-