2025-11-16T06:16:12.477685

Approximation theory for 1-Lipschitz ResNets

Murari, Furuya, Schönlieb
1-Lipschitz neural networks are fundamental for generative modelling, inverse problems, and robust classifiers. In this paper, we focus on 1-Lipschitz residual networks (ResNets) based on explicit Euler steps of negative gradient flows and study their approximation capabilities. Leveraging the Restricted Stone-Weierstrass Theorem, we first show that these 1-Lipschitz ResNets are dense in the set of scalar 1-Lipschitz functions on any compact domain when width and depth are allowed to grow. We also show that these networks can exactly represent scalar piecewise affine 1-Lipschitz functions. We then prove a stronger statement: by inserting norm-constrained linear maps between the residual blocks, the same density holds when the hidden width is fixed. Because every layer obeys simple norm constraints, the resulting models can be trained with off-the-shelf optimisers. This paper provides the first universal approximation guarantees for 1-Lipschitz ResNets, laying a rigorous foundation for their practical use.
academic

1-Lipschitz ResNets এর জন্য অনুমান তত্ত্ব

মৌলিক তথ্য

  • পেপার আইডি: 2505.12003
  • শিরোনাম: Approximation theory for 1-Lipschitz ResNets
  • লেখক: Davide Murari (ক্যাম্ব্রিজ বিশ্ববিদ্যালয়), Takashi Furuya (ডোশিশা বিশ্ববিদ্যালয়, RIKEN AIP), Carola-Bibiane Schönlieb (ক্যাম্ব্রিজ বিশ্ববিদ্যালয়)
  • শ্রেণীবিভাগ: cs.LG cs.NA math.NA
  • প্রকাশনা সম্মেলন: নিউরাল ইনফরমেশন প্রসেসিং সিস্টেমস এর ৩৯তম সম্মেলন (NeurIPS 2025)
  • পেপার লিংক: https://arxiv.org/abs/2505.12003v2

সারসংক্ষেপ

এই পেপারটি নেতিবাচক গ্রেডিয়েন্ট প্রবাহের স্পষ্ট অয়লার ধাপের উপর ভিত্তি করে 1-Lipschitz অবশিষ্ট নেটওয়ার্ক (ResNets) এর অনুমান ক্ষমতা অধ্যয়ন করে। সীমাবদ্ধ Stone-Weierstrass উপপাদ্য ব্যবহার করে, প্রথমে প্রমাণ করা হয় যে যখন প্রস্থ এবং গভীরতা বৃদ্ধি পায়, তখন এই 1-Lipschitz ResNets যেকোনো সংক্ষিপ্ত ডোমেনে স্কেলার 1-Lipschitz ফাংশন সেটে ঘন থাকে। এছাড়াও প্রমাণ করা হয় যে এই নেটওয়ার্কগুলি স্কেলার পিসওয়াইজ অ্যাফাইন 1-Lipschitz ফাংশনগুলি সঠিকভাবে প্রতিনিধিত্ব করতে পারে। আরও শক্তিশালী ফলাফল প্রমাণ করা হয়েছে: অবশিষ্ট ব্লকগুলির মধ্যে নর্ম-সীমাবদ্ধ রৈখিক ম্যাপিং সন্নিবেশ করিয়ে, লুকানো প্রস্থ স্থির থাকলেও একই ঘনত্ব বজায় রাখা যায়। যেহেতু প্রতিটি স্তর সহজ নর্ম সীমাবদ্ধতা অনুসরণ করে, ফলস্বরূপ মডেলটি প্রস্তুত অপ্টিমাইজার দিয়ে প্রশিক্ষণ দেওয়া যায়।

গবেষণা পটভূমি এবং প্রেরণা

সমস্যার গুরুত্ব

1-Lipschitz স্নায়ু নেটওয়ার্ক একাধিক গুরুত্বপূর্ণ ক্ষেত্রে মৌলিক ভূমিকা পালন করে:

  • উৎপাদনশীল মডেলিং: Wasserstein GAN তে বিচারক অবশ্যই 1-Lipschitz হতে হবে, যাতে Kantorovich-Rubinstein দ্বৈততার মাধ্যমে 1-Wasserstein দূরত্বের কার্যকর অনুমান প্রদান করা যায়
  • বিপরীত সমস্যা: Plug-and-Play অ্যালগরিদমে, 1-Lipschitz সীমাবদ্ধতা পুনরাবৃত্তিমূলক স্কিমের সংমিশ্রণ নিশ্চিত করে
  • শক্তিশালী শ্রেণীবিভাজক: নেটওয়ার্কের Lipschitz ধ্রুবক নিয়ন্ত্রণ করা প্রতিকূল আক্রমণের বিরুদ্ধে স্থিতিস্থাপকতা উন্নত করে

বিদ্যমান পদ্ধতির সীমাবদ্ধতা

  1. প্রকাশনীয় ক্ষমতা হ্রাস: নেটওয়ার্কের Lipschitz ধ্রুবক সীমাবদ্ধ করা সাধারণত এর প্রকাশনীয় ক্ষমতা হ্রাস করে, যার ফলে কর্মক্ষমতা উল্লেখযোগ্যভাবে হ্রাস পায়
  2. তাত্ত্বিক ঘাটতি: সীমাবদ্ধ নেটওয়ার্কের অনুমান বৈশিষ্ট্য সম্পর্কে বোঝাপড়া অপর্যাপ্ত, বিভিন্ন সীমাবদ্ধতা কৌশল উল্লেখযোগ্যভাবে ভিন্ন প্রকাশনীয় ক্ষমতা তৈরি করতে পারে
  3. বাস্তবায়ন অসুবিধা: বিদ্যমান 1-Lipschitz ResNets কঠোর তাত্ত্বিক গ্যারান্টির অভাব রয়েছে

গবেষণা প্রেরণা

এই পেপারটি 1-Lipschitz ResNets এর তাত্ত্বিক বিশ্লেষণের ফাঁক পূরণ করার লক্ষ্য রাখে, এই ধরনের নেটওয়ার্কের অনুমান ক্ষমতা বোঝার জন্য কঠোর গাণিতিক ভিত্তি প্রদান করে এবং ব্যবহারিক প্রয়োগের জন্য তাত্ত্বিক সহায়তা প্রদান করে।

মূল অবদান

  1. প্রথম সর্বজনীন অনুমান উপপাদ্য: 1-Lipschitz ResNets এর জন্য প্রথম সর্বজনীন অনুমান গ্যারান্টি প্রদান করে, নেতিবাচক গ্রেডিয়েন্ট প্রবাহের উপর ভিত্তি করে ResNets এর স্কেলার 1-Lipschitz ফাংশন সেটে ঘনত্ব প্রমাণ করে
  2. স্থির প্রস্থের অনুমান ফলাফল: নর্ম-সীমাবদ্ধ রৈখিক ম্যাপিং প্রবর্তন করে, প্রমাণ করে যে এমনকি স্থির নেটওয়ার্ক প্রস্থের ক্ষেত্রেও সর্বজনীন অনুমান বৈশিষ্ট্য বজায় রাখা যায়
  3. গঠনমূলক প্রমাণ পদ্ধতি: দুটি প্রমাণ কৌশল প্রদান করে - সীমাবদ্ধ Stone-Weierstrass উপপাদ্যের উপর ভিত্তি করে এবং পিসওয়াইজ অ্যাফাইন ফাংশনের গঠনমূলক পদ্ধতির উপর ভিত্তি করে
  4. ব্যবহারিক স্থাপত্য ডিজাইন: প্রস্তাবিত নেটওয়ার্ক স্থাপত্যে স্পষ্ট সীমাবদ্ধতা রয়েছে, যা মান অপ্টিমাইজার দিয়ে প্রশিক্ষণ দেওয়া যায়

পদ্ধতি বিস্তারিত

কাজের সংজ্ঞা

সংক্ষিপ্ত সেট X⊂RdX \subset \mathbb{R}^d এ 1-Lipschitz ফাংশন স্পেস অধ্যয়ন: C1(X,R)={g:X→R∣∥g(y)−g(x)∥2≤∥y−x∥2,∀x,y∈X}C_1(X,\mathbb{R}) = \{g : X \to \mathbb{R} \mid \|g(y) - g(x)\|_2 \leq \|y - x\|_2, \forall x,y \in X\}

লক্ষ্য হল স্নায়ু নেটওয়ার্ক সেট তৈরি করা যাতে এটি C1(X,R)C_1(X,\mathbb{R}) এ ঘন থাকে।

মূল নির্মাণ ব্লক

1-Lipschitz অবশিষ্ট স্তর

নেতিবাচক গ্রেডিয়েন্ট প্রবাহের স্পষ্ট অয়লার ধাপের উপর ভিত্তি করে: Φθℓ(x)=x−τℓWℓTσ(Wℓx+bℓ)\Phi_{\theta_\ell}(x) = x - \tau_\ell W_\ell^T \sigma(W_\ell x + b_\ell)

যেখানে σ=ReLU\sigma = \text{ReLU}, সীমাবদ্ধতা: 0≤τℓ≤2/∥Wℓ∥220 \leq \tau_\ell \leq 2/\|W_\ell\|_2^2, ∥Wℓ∥2≤1\|W_\ell\|_2 \leq 1

নেটওয়ার্ক স্থাপত্য সংজ্ঞা

অসীম প্রস্থ এবং গভীরতার নেটওয়ার্ক সেট: Gd,σ(X,R)=C1(X,R)∩{vT∘ΦθL∘⋯∘Φθ1∘Q:X→R}\mathcal{G}_{d,\sigma}(X,\mathbb{R}) = C_1(X,\mathbb{R}) \cap \{v^T \circ \Phi_{\theta_L} \circ \cdots \circ \Phi_{\theta_1} \circ Q : X \to \mathbb{R}\}

স্থির প্রস্থের নেটওয়ার্ক সেট: G~d,σ,h(X,R)={vT∘ΦθL∘AL−1∘⋯∘A1∘Φθ1∘Q:X→R}\tilde{\mathcal{G}}_{d,\sigma,h}(X,\mathbb{R}) = \{v^T \circ \Phi_{\theta_L} \circ A_{L-1} \circ \cdots \circ A_1 \circ \Phi_{\theta_1} \circ Q : X \to \mathbb{R}\}

যেখানে AiA_i হল নর্ম-সীমাবদ্ধ অ্যাফাইন ম্যাপিং।

প্রযুক্তিগত উদ্ভাবন পয়েন্ট

1. দ্বৈত প্রমাণ কৌশল

  • Stone-Weierstrass পদ্ধতি: নেটওয়ার্ক সেট বিন্দু বিভাজনকারী জালি যাচাই করে, সীমাবদ্ধ Stone-Weierstrass উপপাদ্যের শর্ত পূরণ করে
  • গঠনমূলক পদ্ধতি: প্রমাণ করে যে নেটওয়ার্ক সমস্ত পিসওয়াইজ অ্যাফাইন 1-Lipschitz ফাংশন সঠিকভাবে প্রতিনিধিত্ব করতে পারে

2. স্থির প্রস্থের উদ্ভাবনী ডিজাইন

বিশেষ অবশিষ্ট স্তর কাঠামো প্রবর্তন করে: E~h,σ={Φθ:Rh+3→Rh+3∣Φθ(x)=[max⁡{x1,x2}min⁡{x1,x2}x3Φ~θ(x4:)]}\tilde{\mathcal{E}}_{h,\sigma} = \left\{\Phi_\theta : \mathbb{R}^{h+3} \to \mathbb{R}^{h+3} \mid \Phi_\theta(x) = \begin{bmatrix} \max\{x_1, x_2\} \\ \min\{x_1, x_2\} \\ x_3 \\ \tilde{\Phi}_\theta(x_{4:}) \end{bmatrix}\right\}

3. ReLU এর মূল বৈশিষ্ট্য ব্যবহার

ReLU এর ধনাত্মক সমজাতীয়তা এবং নিম্নলিখিত পরিচয় ব্যবহার করে:

  • x=σ(x)−σ(−x)x = \sigma(x) - \sigma(-x)
  • max⁡{x,y}=x+σ(y−x)\max\{x,y\} = x + \sigma(y-x)
  • min⁡{x,y}=x−σ(x−y)\min\{x,y\} = x - \sigma(x-y)

পরীক্ষামূলক সেটআপ

ডেটাসেট

  1. Two-moon ডেটাসেট: 4000 পয়েন্ট, 0.1 মানের বিচ্যুতি সহ গাউসিয়ান শব্দ যোগ করা, প্রশিক্ষণের জন্য 20% ব্যবহৃত
  2. MNIST ডেটাসেট: মান প্রশিক্ষণ/পরীক্ষা বিভাজন, ইনপুট স্বাভাবিকীকরণ প্রক্রিয়াকরণ

মূল্যায়ন মেট্রিক্স

  • শ্রেণীবিভাগ নির্ভুলতা
  • সীমাবদ্ধতা বাস্তবায়ন সময় (প্রতিটি epoch এর গড় সময়)

বাস্তবায়ন বিবরণ

  • অপ্টিমাইজার: কোসাইন অ্যানিলিং শিক্ষার হার সময়সূচী সহ Adam অপ্টিমাইজার
  • ব্যাচ আকার: 256
  • ওজন সীমাবদ্ধতা: প্রজেকশন গ্রেডিয়েন্ট ডিসেন্ট পদ্ধতির মাধ্যমে বাস্তবায়িত, শক্তি পদ্ধতি ব্যবহার করে বর্ণালী নর্ম অনুমান
  • আরম্ভীকরণ: গতিশীল সমদূরবর্তী আরম্ভীকরণ কৌশল গ্রহণ করা

পরীক্ষামূলক ফলাফল

প্রধান ফলাফল

Two-moon ডেটাসেট ফলাফল

স্তরউপপাদ্য 3.1 স্থাপত্যউপপাদ্য 4.1 স্থাপত্য
L=299.75%88.25%
L=499.88%99.88%
L=8100.00%99.88%
L=16100.00%100.00%
L=3299.88%100.00%
L=64100.00%100.00%

MNIST ডেটাসেট ফলাফল (উপপাদ্য 4.1 স্থাপত্য)

প্রস্থ\গভীরতাL=5L=10L=20
h=5097.85%97.67%97.82%
h=10097.94%97.70%97.58%
h=20097.68%97.77%97.89%

পরীক্ষামূলক আবিষ্কার

  1. প্রশিক্ষণ স্থিতিশীলতা: উভয় স্থাপত্য স্থিরভাবে প্রশিক্ষণ দেওয়া যায়, নেটওয়ার্ক প্রস্থ এবং গভীরতা দ্বারা প্রভাবিত নয়
  2. সীমাবদ্ধতা খরচ: অ্যাফাইন স্তর সহ স্থাপত্য উচ্চতর সীমাবদ্ধতা খরচ রয়েছে এবং গভীরতার সাথে দ্রুত বৃদ্ধি পায়
  3. কর্মক্ষমতা প্রদর্শন: সহজ কাজে নিখুঁত শ্রেণীবিভাগ অর্জন করতে পারে, জটিল কাজে ভাল কর্মক্ষমতা প্রদর্শন করে

তাত্ত্বিক বিশ্লেষণ

প্রধান উপপাদ্য

উপপাদ্য 3.1 (অসীম প্রস্থ গভীরতা)

ধরুন d∈Nd \in \mathbb{N}, σ=ReLU\sigma = \text{ReLU}, X⊂RdX \subset \mathbb{R}^d সংক্ষিপ্ত, তাহলে Gd,σ(X,R)\mathcal{G}_{d,\sigma}(X,\mathbb{R}) C1(X,R)C_1(X,\mathbb{R}) এর সর্বজনীন অনুমান বৈশিষ্ট্য সন্তুষ্ট করে।

উপপাদ্য 4.1 (স্থির প্রস্থ)

ধরুন d∈Nd \in \mathbb{N}, σ=ReLU\sigma = \text{ReLU}, X⊂RdX \subset \mathbb{R}^d সংক্ষিপ্ত, তাহলে G~d,σ,d+3(X,R)\tilde{\mathcal{G}}_{d,\sigma,d+3}(X,\mathbb{R}) C1(X,R)C_1(X,\mathbb{R}) এর সর্বজনীন অনুমান বৈশিষ্ট্য সন্তুষ্ট করে।

প্রমাণ মূল পদক্ষেপ

Stone-Weierstrass পদ্ধতি

  1. বিন্দু বিভাজন: প্রমাণ করে যে নেটওয়ার্ক সেট যেকোনো দুটি ভিন্ন বিন্দু বিভাজন করতে পারে
  2. জালি বৈশিষ্ট্য: প্রমাণ করে যে নেটওয়ার্ক সেট সর্বোচ্চ এবং সর্বনিম্ন অপারেশনের অধীন বন্ধ
  3. ঘনত্ব: সীমাবদ্ধ Stone-Weierstrass উপপাদ্য দ্বারা প্রাপ্ত

গঠনমূলক পদ্ধতি

  1. মৌলিক অপারেশন: প্রমাণ করে যে স্থানাঙ্ক-অনুযায়ী সর্বোচ্চ এবং সর্বনিম্ন বাস্তবায়ন করা যায়
  2. পিসওয়াইজ অ্যাফাইন প্রতিনিধিত্ব: max-min প্রতিনিধিত্ব উপপাদ্য ব্যবহার করে
  3. সর্বজনীন অনুমান: পিসওয়াইজ অ্যাফাইন ফাংশন 1-Lipschitz ফাংশনে ঘন

সম্পর্কিত কাজ

1-Lipschitz নেটওয়ার্ক সীমাবদ্ধতা পদ্ধতি

  1. বর্ণালী স্বাভাবিকীকরণ: ওজন ম্যাট্রিক্সের বর্ণালী নর্ম নিয়ন্ত্রণ করে
  2. অর্থোগোনাল ওজন ম্যাট্রিক্স: অর্থোগোনাল রূপান্তর ব্যবহার করে Lipschitz বৈশিষ্ট্য বজায় রাখে
  3. গ্রেডিয়েন্ট প্রবাহ পদ্ধতি: গতিশীল সিস্টেম এবং সংখ্যাগত বিশ্লেষণের উপর ভিত্তি করে সীমাবদ্ধতা কৌশল

সীমাবদ্ধ নেটওয়ার্কের অনুমান তত্ত্ব

  • Anil এবং অন্যদের GroupSort সক্রিয়করণ ফাংশন সহ ফিডফরওয়ার্ড নেটওয়ার্ক তত্ত্ব
  • Neumayer এবং অন্যদের স্প্লাইন সক্রিয়করণ ফাংশন সম্পর্কিত গবেষণা
  • এই পেপার 1-Lipschitz ResNets এর জন্য প্রথমবার সম্পূর্ণ তত্ত্ব প্রদান করে

উপসংহার এবং আলোচনা

প্রধান উপসংহার

  1. তাত্ত্বিক অগ্রগতি: প্রথমবার 1-Lipschitz ResNets এর জন্য কঠোর সর্বজনীন অনুমান তত্ত্ব প্রতিষ্ঠা করেছে
  2. ব্যবহারিক মূল্য: প্রস্তাবিত স্থাপত্য মান অপ্টিমাইজার দিয়ে প্রশিক্ষণ দেওয়া যায়, স্পষ্ট সীমাবদ্ধতা রয়েছে
  3. পদ্ধতি উদ্ভাবন: দুটি পরিপূরক প্রমাণ পদ্ধতি প্রদান করে, Lipschitz ক্রমাগত ResNets সম্পর্কে বোঝাপড়া গভীর করে

সীমাবদ্ধতা

  1. সক্রিয়করণ ফাংশন নির্ভরতা: তত্ত্ব ReLU এর বিশেষ বৈশিষ্ট্যের উপর গুরুতরভাবে নির্ভর করে
  2. বাস্তবায়ন জটিলতা: স্থির প্রস্থ স্থাপত্য অতিরিক্ত অ্যাফাইন স্তর প্রয়োজন, বাস্তবায়ন জটিলতা বৃদ্ধি করে
  3. স্কেলার ফাংশন সীমাবদ্ধতা: প্রধান ফলাফল স্কেলার মূল্যবান ফাংশনে কেন্দ্রীভূত, ভেক্টর মূল্যবান ফাংশনের সম্প্রসারণ আরও গবেষণা প্রয়োজন

ভবিষ্যত দিকনির্দেশনা

  1. অন্যান্য সক্রিয়করণ ফাংশন: অন্যান্য সক্রিয়করণ ফাংশনের তাত্ত্বিক বিশ্লেষণে সম্প্রসারণ
  2. আধুনিক স্থাপত্য: Transformers এবং GNNs এর মতো আধুনিক স্থাপত্যে তত্ত্ব প্রয়োগ
  3. অনুমান হার: নির্দিষ্ট অনুমান হার এবং জটিলতা বিশ্লেষণ অধ্যয়ন
  4. ভেক্টর মূল্যবান ফাংশন: বহু-আউটপুট ফাংশনের তাত্ত্বিক কাঠামো সম্পূর্ণ করা

গভীর মূল্যায়ন

সুবিধা

  1. তাত্ত্বিক কঠোরতা: সম্পূর্ণ গাণিতিক প্রমাণ প্রদান করে, গুরুত্বপূর্ণ তাত্ত্বিক ফাঁক পূরণ করে
  2. পদ্ধতি উদ্ভাবনী: দ্বৈত প্রমাণ কৌশল বিভিন্ন তাত্ত্বিক দৃষ্টিভঙ্গি প্রদান করে
  3. ব্যবহারিকতা: সমস্ত তাত্ত্বিক ফলাফল বাস্তবায়নযোগ্য নেটওয়ার্ক স্থাপত্যের সাথে সামঞ্জস্যপূর্ণ
  4. সম্পূর্ণতা: তাত্ত্বিক বিশ্লেষণ থেকে পরীক্ষামূলক যাচাইকরণ পর্যন্ত, সম্পূর্ণ গবেষণা শৃঙ্খল গঠন করে

অপর্যাপ্ততা

  1. সীমিত পরীক্ষা স্কেল: পরীক্ষা প্রধানত সহজ ডেটাসেটে কেন্দ্রীভূত, বৃহৎ-স্কেল প্রয়োগ যাচাইকরণের অভাব
  2. গণনা জটিলতা: সীমাবদ্ধতা বাস্তবায়নের গণনা ওভারহেড বিশ্লেষণ যথেষ্ট গভীর নয়
  3. তুলনা মানদণ্ড: অন্যান্য 1-Lipschitz নেটওয়ার্ক পদ্ধতির সাথে বিস্তারিত তুলনার অভাব

প্রভাব

  1. একাডেমিক মূল্য: সীমাবদ্ধ স্নায়ু নেটওয়ার্ক তত্ত্বের জন্য গুরুত্বপূর্ণ ভিত্তি প্রদান করে
  2. প্রয়োগ সম্ভাবনা: উৎপাদনশীল মডেলিং, বিপরীত সমস্যা এবং শক্তিশালী শিক্ষা ক্ষেত্রে ব্যাপক প্রয়োগ সম্ভাবনা
  3. পদ্ধতিগত অবদান: প্রমাণ কৌশল অন্যান্য সীমাবদ্ধ নেটওয়ার্কের তাত্ত্বিক বিশ্লেষণকে অনুপ্রাণিত করতে পারে

প্রযোজ্য পরিস্থিতি

  1. Wasserstein GANs: বিচারক ডিজাইনের জন্য তাত্ত্বিক সহায়তা প্রদান করে
  2. Plug-and-Play অ্যালগরিদম: সংমিশ্রণ নিশ্চিত করার জন্য ডিনোইজার ডিজাইন
  3. প্রতিকূল স্থিতিস্থাপকতা: প্রতিকূল আক্রমণের বিরুদ্ধে শ্রেণীবিভাজক প্রতিরোধ ক্ষমতা উন্নত করে
  4. বিপরীত সমস্যা সমাধান: চিকিৎসা ইমেজিং, সংকেত প্রক্রিয়াকরণ এবং অন্যান্য ক্ষেত্রে প্রয়োগ

তথ্যসূত্র

এই পেপার 42টি গুরুত্বপূর্ণ সাহিত্য উদ্ধৃত করে, যা সর্বজনীন অনুমান তত্ত্ব, Lipschitz সীমাবদ্ধতা পদ্ধতি, গতিশীল সিস্টেম তত্ত্ব এবং অন্যান্য একাধিক ক্ষেত্রের মূল কাজ অন্তর্ভুক্ত করে, তাত্ত্বিক বিশ্লেষণের জন্য দৃঢ় ভিত্তি প্রদান করে।