-
Fine-Tuning can Distort Pretrained Features and Underperform Out-of-Distribution (ICLR 2022 Oral)
Fine-Tuning can Distort Pretrained Features and Underperform Out-of-Distribution 최근 들어서 굉장히 많은 딥러닝 영역에서 대규모 pretrained model을 특정한 downstream task에 대해 fine-tuning 하는 방식으로 학습을 진행하는 경우가 많습니다. 이전에는 데이터 셋의 규모가 작고 지금과 같이 transformer 구조를 사용하지 않을 때에는 요즘과 같이 large pretrained model이 크게 유행하지 않았습니다. 이전에는 많은 경우에 ImageNet 정도 사이즈의 데이터 셋에서 학습한 pretraiend model의 parameter를 가져와서 이보다도 더 작은 downstream task로 fine-tuning 하였기에 특정 task들에 대해서는 transfer learning을 적용해도 성능이...
-
Erdös-Ginzburg-Ziv 정리의 O(n log n) 시간 해법 찾기
Erdös-Ginzburg-Ziv 정리는 임의의 길이 $2n-1$의 정수열에 대해 길이가 $n$이고 원소의 합이 $n$의 배수인 부분수열이 항상 존재한다는 정리입니다. 이전에 작성된 글에서는 $O(n^2/w)$ 풀이를 소개했지만, 최근에 공개된 이 부분수열을 직접 찾는 $\mathcal{O}(n \log n)$ 풀이에 대해서 소개합니다. Erdös-Ginzburg-Ziv 정리와 증명 Erdös-Ginzburg-Ziv 정리는 길이가 $2n-1$인 임의의 정수열 $A = { {a}_1, {a}_2, \cdots, {a}_{2n-1}}$에 대해 길이가 $n$이고 원소의 합이 $n$의 배수인 부분수열이 항상 존재한다는 정리입니다. $A$에 따른 $A$의 부분수열을 Erdös-Ginzburg-Ziv 정리의 해법이라고 부릅니다. Erdös-Ginzburg-Ziv가 간단한 증명을 제시했고, 이...
-
Hash Functions Monolith for ZK Applications: May the Speed of SHA-3 be With You
이 내용은 https://eprint.iacr.org/2023/1025.pdf 의 요약입니다. ZK Friendly Hash Function의 필요성 해시함수는 굉장히 많은 곳에서 사용되고 있습니다. 그런만큼 ZKP 상에서도 해시함수의 계산에 대한 증명을 하게 될 필요가 상당히 많습니다. 그런데 일반적인 해시함수는 일반적인 컴퓨팅 환경에서 빠르게 작동하는 것을 목표로 하기 때문에, 비트 연산 등을 많이 활용합니다. 이는 비트 연산을 다루는 비용이 큰 ZKP 상에서는 큰 문제로 작용합니다. 이에 따라, ZKP 상에서 비용이 적은, 즉 적은 constraint로 증명을 할 수 있는 해시함수를 만드는 것이 필요해졌습니다. 또한, ZKP...
-
A 1.5-Approximation for s-t Path TSP
이 글에서는 cost function이 metric인 경우에 대해서만 논의한다. 1. Introduction 외판원 문제(Traveling Salesman Problem)와 s-t 경로 외판원 문제(s-t path TSP)는 다음과 같이 정의된다. Traveling Salesman Problem. 완전 그래프 $G = (V, E)$ 와 간선 집합 $E$ 상의 metric cost function $c$가 있을 때, $G$의 모든 정점을 순회하고 돌아오는 최소 cost의 cycle을 구하여라. s-t Path Traveling Salesman Problem. 완전 그래프 $G = (V, E)$ 와 그 상의 두 정점 $s$, $t$ 및 간선 집합 $E$ 상의...
-
Separating Hyperplanes, Lagrange Multipliers, KKT Conditions, and Convex Duality
2021년 발표된 Minimum Cost Flow가 Almost-Linear Time에 풀린다는 결과는 현대적인 Convex Optimization 기법들이 전통적인 알고리즘 문제를 해결하는 아주 강력한 도구를 제공함을 보여주는 상징적인 순간이라고 할 수 있다. 요즘은 기계 학습의 인기가 워낙 엄청나기 때문에 Convex Optimization은 대개 기계 학습의 관점에서 다뤄지지만, Convex Optimization은 현대 전산학 전반에 있어서 중요도가 아주 높으며, 그래프 알고리즘적인 관점에서 Convex Optimization을 다뤘을 때 얻어갈 수 있는 것이 아주 많다. 최근 관심 있는 학생들과 함께 ETH Zurich의 Advanced Graph Algorithms and Optimization...